Data structures example: the graph class

In the last data structures post I talked about the tree structure, now let’s head towards graphs. As usual I’m also providing the source files for all included examples, which you can download here.
The code is a bit rough and there is plenty room for optimizations, but nevertheless I hope you understand what’s going on. Also make sure you have the latest release, because I have modified almost all graph-related classes.

What’s a graph?

Graphs (also known as Networks) are very powerful structures and find their applications in path-finding, visibility determination, soft-bodies using mass-spring systems and probably a lot more. A graph is similar to a tree, but it imposes no restrictions on how nodes are connected to each other. In fact each node can point to another node or even multiple nodes at once.

A node is represented by the GraphNode class, and the connections between GraphNode objects are modeled by the GraphArc class. The arc has only one direction (uni-directional) and points from one node to another so you are only allowed to go from A to B and not in the opposite direction. Bi-directional connections can be simulated by creating an arc from node A to B and vice-versa from B to A. Also, each arc has a weight value associated with it, which describes how costly it is to move along the arc. This is optional though, so the default value is 1.

Putting it together, the graph is implemented as an uni-directional weighted graph. The Graph manages everything: it stores the nodes and the arcs in separate lists, makes sure you don’t add a node twice, or mess up the arcs (for example if you remove a node from the graph, it also scans the arc list and removes all arcs pointing to that node) and provides you with tools to traverse the graph.

Building the graph structure

In figure 1, you see a simple graph containing 8 nodes. You can add additional nodes, which will be placed at the position of the cursor by pressing ‘a’ or start with a fresh graph by pressing ‘r’. To create an arc point from node A to Node B, simply click both nodes successively. Traversal is also possible: First press ‘t’ to switch to ‘traverse’ mode, then click a node to find all nodes which are connected to the this node.

Figure 1: Building a graph structure

Graph traversal

If you have tried out the traversal in the example above, you may wonder how it’s done. The answer lies in two common algorithms to accomplish this: Breadth-first search (BFS) and depth-first search (DFS). (The demonstration above used the breadth-first search.)

The BFS algorithm visits all nodes that are closest to the starting node first, so it gradually expands outward in all directions equally. This looks like a virus infecting the direct neighborhood at each search iteration. BFS utilizes a queue and proceeds as follows:

  1. Mark the starting node and enqueue it.
  2. Process the node by calling a user-defined function on it.
  3. Mark all connected nodes and also put them into the queue.
  4. Remove the node at the front of the queue.
  5. Repeat steps 2-5 with the node that is now at the front of the queue.
  6. Stop if the queue is empty.

The depth-first search (DFS) on the other hand takes the starting node, follows the next arc it finds to get to the next node, and continues this until the complete path has been discovered, then goes back to the starting node and follows the next path until it reaches a dead end and so on. It’s currently implemented as a recursive function, that means that it probably can fail for very large graphs when the call-stack exceeds the maximum size (I don’t know how big it is in AS3 though).

Both algorithms have in common that they mark a node when it’s added to the queue, otherwise the node would be enqueued and unnecessarily processed multiple times, because different nodes can all point to a common node. So before you start a BFS or DFS it’s very important to reset all markers by calling the clearMarks() function on the graph.

The two algorithms are visualized in figure 2 below. I’ve created a rectangular grid of nodes (similar to a tilemap) by connecting each node with the top, bottom, left and right neighbors (I left out the arcs because it would be a total mess). I have also deleted some nodes to show you that both algorithms don’t rely on a regular structure and can look like anything. Just click a node to start the traversal. You can toggle between both algorithms by pressing ‘b’ BFS and ‘d’ (guess what ;-)).

Figure 2: Building a graph structure

BFS is much more useful than DFS in most situations. But DFS is likely to be faster, for example when you only want to modify all connected nodes in some way.

A graph-based A* pathfinder

Now for the cool part. I have created a pathfinder to demonstrate the power of the BFS algorithm. When building the graph it’s important that all arcs are bi-directional, so the pathfinder can figure out the shortest path between two locations.

I can’t explain how a pathfinder works in detail, because it’s a vast subject, but actually it’s not that different from the tile-based version, which you probably realized when looking at figure2: in a tilemap, you have 8 directions (N, S, W, E, NW, NE, SW, SE) and you go from one tile to another by adjusting the x and y tile index, in a graph you just follow all arcs of the current node. The implementation is a little chaotic, because I have to render and compute the path simultaneously, so it needs definitely some refactoring to make it clean and reusable, but for demonstration purposes it should hopefully do the work.

Figure 3: Graph based pathfinding, click a start and end node.

After finding a path through the A* algorithm, I store the nodes in a queue. You could then use a command queue so a character can follow the path. In contrast to tile-based path finding, the graph based version is lightning fast and there is still plenty room for optimizations: for example you could run a breath-first search on the graph to precompute all distances between the nodes. That’s all I have to say about graphs, next time I take an closer look at my favorite structure – linked lists!

See also:
Linked lists
The queue class
The tree class

28 thoughts on “Data structures example: the graph class”

  1. Wow Michael your posts blow me away, so much good info all the time and presented top notch. The A* and command queue is quite a piece of work.

  2. thank you :-) coding the examples takes some time, but it’s also a good opportunity to debug and enhance the data structure classes this way.

  3. Pingback: baby steps
  4. It’s interesting that the route from 26-13 is different than the route from 13-26, though 26-12 is the same as 12-26.

  5. Cool, a bug :-) I fixed it and uploaded a new version. I was computing squared distances between arc nodes, and somehow due to roundoff very short arcs messed things up. So in the Waypoint.distanceTo() function it’s now computed as:
    Math.sqrt((dx * dx) + (dy * dy)); instead of (dx * dx) + (dy * dy); But the path finder definitely needs some refinement, it’s quickly written for demonstration.

  6. Hello

    You put really good articles :)

    I have one question about Graph .breadthFirst, why you don’t use your ArrayedQueue for queue and performance ?

  7. Usually the queue in the breath-first search only contains a few nodes so push/shift is a little faster in this case. It also saves some function calls which would be required if using the ArrayedQueue class. This of course can change if you build *really* complex graphs.

  8. All connections between nodes are bidirectional. Would be nice to see how it would work if some of them were one way only? :)

  9. Fringe Search is faster than A*. I Have implemented both in AS2 in the same coding “style”, and found Fringe 20-50% faster. Do some googling to find out more about Fringe Search,

  10. thankZZZzzz!!!! 4 d short-knowledgeable explaination abawt data structuring…. 8 hLp me to know more…

  11. Thanks for sharing your code. I’m not an Computer science Studient, but realy find it amazing what Guy like you build up. Thank you very much for your sharing. It offers me so many fields of uses without I havnt even think of.

  12. the ‘A graph-based A* pathfinder’is not working. [Errors: ‘’ (1046) Type was not found or was not a compile-time constant ’’ lines:19,34,48,135.]
    when I test it I can see only the bmp (path.bmp)
    (I did not change anything)
    What is wrong?

  13. Great tutorial, even if i really don’t get stuff like “public class PathFinder extends MovieClip” or the Node class that extends from Sprite… all your sample code looks very ugly because of that

  14. Great work! I’m playing a little bit with GraphBuilder to create such Graphs interactive. Could you tell me how i can remove a Node? For example I want to remove node3 from the graph. It works with ‘graph.removeNode(target0.graphIndex)’ in combination with ‘nodeCanvas.removeChildAt(target0.graphIndex)’. The problem is that the other nodes stay at the same index. Is there an easy way to make this delete possible? thx

  15. Thanks a lot for all the explanations… they’re what a half-programmer like me needs!
    I will be using your structures for UFHO 2, sometime at the start of next year.
    Thanks, thanks, thanks.

  16. I am missing the Waypoint class in your library.. is there any place to get it ? :)

    col: 41 Error: Type was not found or was not a compile-time constant: Waypoint.

Comments are closed.