A.I on the 1s and 0s

Silverlight Shortest Path Simulation

I recently accepted a PM position on the Silverlight team that I’m very excited about. I’ve always kept a close eye on Silverlight but never had the time to invest into the 1s and 0s of Silverlight development . As I slowly transition over I’ve made it a priority to get my hands dirty by building a few apps that use the core Silverlight features.

The first app I built was a simulation of Dijkstra’s shortest path algorithm. The app allows the user to create their own weighted graph (nodes connected by edges each with an associated cost) to run the simulation on. While running the simulation you’ll see the active nodes and edges changing colors as they get discovered, and chosen or rejected. You can play with the app below (source at the bottom) but one warning – this is a POC so error handling, testing, and UX are minimal.

The UI  is lacking and doesn’t have clear affordances for its use so here are the steps:
1) Make sure ‘Add Nodes’ at the top is selected then click anywhere to create some nodes
2) Make sure ‘Add Edges’ at the top is selected then click on two nodes to connect them with an edge
3) Set the weight of the edge by typing in a number in the textbox associated with the edge
4) Repeat to create a simple/complex graph
5) Set the source and target (the value of the node) and run the simulation.

The goal of this POC was to create an app that showed the algorithm at work without tightly coupling the model (graph), algorithm (Dijkstra), and view (UI updates).

Here’s a high level overview:

1) Design

To avoid tightly coupling the model, algorithm, and view I used a design pattern similar to MVC. I opted for a similar pattern because with MVC it’s hard to have a controller that’s suited for an interactive UI. Instead I used the MVVM (Model-View-ViewModel) pattern which works well with Silverlight because it overcomes the interactive UI problem, and still lets you loosely couple the app. 

The ViewModel sits between the View and the Model and knows nothing about the View. The View on the other hand is tightly coupled to the ViewModel because it consumes the ViewModel via data-binding.

For my app having a data-bound ViewModel didn’t make sense so instead I let the ViewModel throw events that the View would catch.

2) Graph

The graph breaks down into two logical objects: Nodes and Edges. I created a node user control, to abstract the Node logic for reusability, which gets created and added to the Canvas in response to the MouseLeftButtonUp event. I set the node-control’s position based on the mouse position using the Canvas.Left and Canvas.Top dependency properties.

To connect the nodes with an edge I exposed an event that is called in response to the node-control’s MouseLeftButtonUp. This allows me to track which nodes the user is selecting. Once the user selects two distinct nodes I create a Line with it’s {X1,Y1} and {X2,Y2} properties set to the first and second nodes’ position respectively. To make it look “nicer” I use the Canvas.ZIndexProperty to push the edge behind the nodes.

The final step is to add a Textbox so the user can assign a weight to the edge. This done in similar fashion to adding edges.

3) Simulation (Updating UI)

In Silverlight you can explicitly execute a method on the UI thread by calling Dispatcher.BeginInvoke(…) that accepts a delegate.  However, you must ensure that you don’t block the UI thread with any lengthy computations like computing the shortest path.

Consequently, I created a new thread to run Dijkstra’s algorithm on.

The algorithm updates the state of the nodes and edges in the graph which in turn raise a series of events that bubble up to the View that invokes the UI update.

I’m eager to know if this was the best way to design and implement this POC in SL. If you look at the source and see anything that can be improved upon using existing SL features drop me a comment and let me know.

Source here. (Built using VS2010)