This is the homepage of Peter Alexander. I am currently at Facebook working on Core Data. Previously a game developer at Codemasters. Any opinions are my own.
- unique_ptr Type Erasure
- The Condenser Part 1
- Cube Vertex Numbering
- Range-Based Graph Search in D
- Ranges Part 1 - Basics
Range-Based Graph Search in D
I’ve just made my first commit of a range-based graph library for D. At the moment it only contains a few basic search algorithms (DFS, BFS, Dijsktra, and A*), but I wanted to write a bit about the design of the library, and how you can use it.
As a bit of a teaser, the snippet below shows how you can use the library to solve those word change puzzles (you know, the ones when you have to get from one word to another by only changing one letter at a time?)
This promptly produces the desired result:
The last two lines are the interesting part. The first of those lines defines
our graph as an implicit graph of words connected by one-letter changes. The
second line performs the A* search and writes the resultant path to
On the second-last line,
graph is defined as an
An implicit graph is a graph that is represented by functions rather than
in-memory data structures. Instead of having an array of adjacency lists, we
just define a function that returns a range of adjacent words (that’s the
second parameter to
implicitGraph). This representation saves us the tedium
of generating the graph beforehand, and saves your RAM from having to store it
unnecessarily. It also makes for succinct graph definitions!
The last line is where the algorithm is called. Unlike most other graph
stdex.graph implements graph searches as ranges – iterations
of the graph vertices.
aStarSearch returns a range of vertices in the
order they would be visited by the A* search algorithm (parameterized by the
A* heuristic). By implementing the search as a range, the user can take
advantage of Phobos’ multitude of range algorithms.
For instance, suppose you want to count the number of nodes searched by the
algorithm until it reaches the target node. For this task, you can just use
For tuning and debugging, it might be useful to print out the nodes visited by the algorithm as it runs.
When no path is available, graph search algorithms typically end up searching
the entire vertex space. It is common to cut-off the search after a certain
threshold of nodes have been searched. This can be accomplished by
only so many nodes from the search.
Similarly, you could have the search continue until 10 seconds have elapsed.
The beauty of all this is that none of these features are part of the graph library – they come for free as a side-effect of being a range.
One unsolved part of the design for the graph searches is how to handle visitation. The Boost Graph Library solves this by having users implement a visitor object, which has to define a suite of callback methods, one for each event (vertex discovered, examine edge, etc.) This is certainly mimicable in D, but it may be more effective to model visitation with output ranges, which would again allow composition with existing Phobos constructs. This is what I will be investigating next.