A few years ago I had to create some animations of graph algorithms. That meant two things: I had to implement algorithms like Dijkstra or Kruskal and then create a visual representation of the algorithm, so one could see what happens step by step.
The code was written in C++ using LEDA for the graphs data structure and AGD (now called OGDF) for visualization.
In this series I will describe how I implemented a tool for creating graph animations in .NET using WPF. This first part will discuss the underlying data structures. The second part will concentrate on the 3D stuff and the animations.
What LEDA and AGD do
With LEDA and and AGD you could create graphs that look like the following example:
The problem is, that the API of LEDA is not object orientated (see this tutorial) and if you want to move a node in a fluid animation, you have to do this by repositioning it until the target is reached.
Thus I decided to write my own graph visualization tool with the following features:
- Object orientated graph data structure, independent from the UI
- 3D graphics and animations based on WPF
- Higher level API to create animations without having to know details about WPF
The data structure
A graph consists of nodes and edges. A graph can be directed or undirected and often you attach some data to a node or an edge (e.g. the distance).
Since a graph can implemented in many different ways (e.g. incidence list, adjacency list or incidence matrix) I decided to use the following implementation:
All graphs have to implement the interface IGraph, which basically allows to add/remove nodes and edges to/from the graph and lets you retrieve the neighbor nodes and edges of a node.
When you add a node or edge to a graph, my implementation of Node or Edge keep a reference to the IGraph they were added to. If you want to get the neighbors of a node the request is forwarded to the currently used implementation of the IGraph interface.
That makes it simple to create your your own IGraph implementations. I only provide one implementation called Graph which utilizes two hashsets for storing nodes and edges.
You can attach data to nodes and edges. In the following example two nodes connected by one edge are created:
IGraph<string, int> graph = new Graph<string, int>();var node1 = new Node<string, int>("Munich"); var node2 = new Node<string, int>("Berlin"); var edge = new Edge<string, int>(node1, node2, 586);
graph.Add(node1); graph.Add(node2); graph.Add(edge);
Console.WriteLine("Distance from {0} to {1}: {2}", node1.Data, node2.Data, edge.Data);
Conclusion
Now we can create strongly typed graphs and access neighbors and data in a simple but flexible way. Based on the given implementation we are already capable to implement arbitrary graph algorithms. In the next part we will see some sample algorithms and a WPF based UI will be implemented to create and see animations.
Feedly
