Several times a year I need to find a path through a graph.
The graphs might be representations of the layout of streets, the distances between cities, the connections between nodes, or they might be models of abstract relationships such as the concept of prerequisites – you need to finish A before you can start B.
Many of these path finding problems can, with some thought, be transformed into a modification of one of the standard graph theory problems ( travelling salesman, spanning tree, maze searching or most often Dijkstra’s shortest path ) Now all that remains is to find the relevant routine in a graph library such as boost::graph and adjust the data into a form that the library routine can process.
Well, not so easy. Graph theory libraries are complex beasts, powerful but hard to tame.
However, over the years I have developed several software tools for making the connection between the mundane world of city streets and university curricula and the magical mathematical world of graph theory. Now I am working on combining them into one easy to usepackage: PathFinder.
The package is really only easy to use if you code in C++. For certain standard problems PathFinder comes with a graphical user interface that allows it to be used by anyone unfamiliar with C++.
On a personal note: I am dedicating this work to my father, Taylor Bremner. In the early 1940s, during the second world war, my father designed, built and maintained the bombsights used by Path Finder Squadron. The planes in this squadron were crewed by the most experienced pilots, navigators and bombardiers the Royal Air Forces possessed. They flew ahead of the bomber fleets to pick out the target and mark it with flares, so that the raw recruits in the remaining planes could find their way in the darkness over Germany.
My father once showed my brother and me the inner working of one of his bombsights. Packed into a suitcase sized green metal box was a fascinating maze of eccentric cogs and twisty worm gears of brass and steel that whirled around solving in real time cascading sequences of differential equations that adjusted the moment of bomb release for velocity, height, wind speed and direction. Perhaps this was the moment my brother became a mechanical engineer and I a software engineer.
In an early form of extreme usability testing, my father also flew in the raids that carried his bombsights. Since the German air force knew all about Path Finder Squadron, and knew that destroying the squadron planes was the best chance of diverting the bombs from their cities, the enemy fighters concentrated their attacks on the aircraft carrying my father and his colleagues. The life expectancy of a member of Path Finder was measured in weeks.
::raven::set 