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.