Simple Route Traversal

So a while ago, during a university module, we all had to make a design data structures that could support bi-directional travel. It was a fairly interesting task, and I’m happy to say I did very well.

The problem with this was that the implementation wasn’t very fun to look at; the purpose of the task was to build efficient data structures in C++. I’ve decided to build a similar sort of thing, but instead of just re-uploading my old code (which feels a bit like cheating) I’ve built a new system complete with a GUI.

RouteTraversalBasicLayout

Figure 1. My program displaying a simple network

The system currently works as follows. Add a node, create a link between two nodes, and find a path between the two.

RouteTraversalHighlightedRoute

Figure 2. A highlighted route in my program based upon input criteria

The data object

One of the reasons I decided to do build this is that I’ve recently being writing C programs with data structures. Since these only had to be tiny things to demonstrate functionality I kept finding myself writing a simple list implementation that can be searched by recursively checking each node and accessing its ‘Next’ node. This project finally puts this structure to some use.

Each ‘node’ in this project contains an identifier, X and Y coordinates, and a list of other nodes that connect to it. Algorithms in this project work by recursively calling each connected node from the current. The root node is accessed first.

Infinite loops

Creating this the first time was infuriating! Create a system in which you can only visited a place once and you’re fine, but add the ability to travel backwards and you have to start keeping track of where your going.

RouteTraversalInfiniteLoop

Figure 3. A simple recursive loop that would cause a stack overflow if previously visited nodes were not taken into account

Take the above example. You’d think that a simple square route wouldn’t be too much of a hassle, but trust simple logic to outfox the lazy programmer. You start at Route, which goes to 1, then to 2, 3 follows, and then since you don’t remember that you went to Route already you visit again. This continues until your program throws a scary exception, chastising you for not thinking ahead.

Which isn’t to say that this is a particularly difficult problem to solve once you put some thought into it, but it does mean you have to pass another list of nodes to whatever function you want to make sure you don’t visit them again. In the past coursework when I did this I created route objects and node objects; the route objects would hold the node objects it connected. This might be a better way to do this; have each route object have a flag denoting whether its been traversed yet. It would be more complicated (something I’d rather avoid when an overly-complex spec isn’t provided), but it would be more elegant, and would stop me iterating through the entire list of past nodes every time a new node is checked.

Drawing the network

WPF doesn’t have a HTML like canvas, but if you inherit from a ‘UserControl’ it will let you override the OnRender method you can access the basic visual methods: DrawLine, DrawRectangle, etc. Apparently this doesn’t do particularly well when the visual element has to refresh quickly, so my hope of making this scroll-able might have to wait a while (I’m sure I’ll try it, though I’ll feel a tad less proud if I wind up with a sluggish mess).

Saving and loading

It never occurred to me that this would be so time-consuming. As with all other software I want to be able to save what I’ve made so I don’t feel like the 2 hours I’ve spent looking at a screen could have been spent lazing around on the couch for all the effect it’d have on my productivity.

The problem with saving the state of this program was that you have to create load in links between nodes that might not have been loaded yet; you can save out a node with its list of connections, but when you load it in you can’t recreate that connection until you recreate the necessary nodes. My solution: create a simple structure to store the node and its list in string format and then evaluate each once they’ve all been created. I know, hardly splitting the atom is it? Nonetheless, I’m pretty happy that I’ve got an extensible solution that could be applied regardless of the size or structure of the route put in.

Improving the program

Right now the route that the program suggests when prompted is based upon the order in which the nodes were attached to each other. This was all I wanted for the time being, but it’s not the best way of finding a route. There are many different algorithms, and I want my program to tout at least some variety. What would make this really great would be the ability to calculate the shortest path between nodes, or fewest individual routes.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s