Introduction
In this article, I will describe how I implemented a tool for creating graph animations in .NET using WPF. First, the underlying data structures are discussed. The second part will concentrate on the 3D stuff and the animations. This article will only give a rough overview. I do not explain everything in depth, but at the end of the article, you can find some resources which could be useful to learn more about the fundamentals.
Here is what this article contains:
- Object oriented graph data structure, independent from the UI
- 3D graphics and animations based on WPF
- Higher level API to create animations without having to know the details about WPF
Before starting with the implementation, I want to show a simple animation created with the final tool:
- By clicking on an empty area, a new node is created
- By clicking on two nodes within one second (not necessarily different nodes), a new edge is created
- By clicking at a node or edge, its properties can be edited in the panel on the right
- All graph algorithms can be executed by selecting the corresponding entry in the menu
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 be 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 keeps 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 own IGraph implementations. I only provide one implementation called Graph which utilizes two hashsets for storing 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);
Now, we can create strongly typed graphs, and access neighbors and data in a simple but flexible way. You can attach data to nodes and edges. Based on the given implementation, we are already capable to implement arbitrary graph algorithms.
The UI should be capable of creating graphs consisting of nodes and edges with some mouse clicks. Moreover, it should be easy to execute previously created graph algorithms and to show their animations.
Most parts of the application are straightforward using the MVVM-pattern, with one exception: 3D elements within a ViewPort3D can not be created by using data binding, they have to be added to the container manually. Arbitrary data could be attached to nodes and edges. The application uses an IGraph<NodeData,EdgeData> as a graph. NodeData and EdgeData contain UI specific information like position and color.
Since the node and edge elements should react on click events, our 3D elements have to derive from UIElement3D. The WPF3D team has blogged about how to subclass UIElement3D. Nodes should be represented by a sphere, and edges by a cylinder/torus; therefore, I created the following hierarchy:
Every time a new node or edge is added to the graph, the VisualFactory instantiates the corresponding GraphUIElement. A GraphUIElement has a GeometryModel3D which is a MeshGeometry3D together with a Material.
Whenever the underlying data changes (e.g., new position or color), the GraphUIElement updates itself. When a node should move, a new animation is added to the corresponding DependencyProperty. This all happens under the covers; if you want to create your own graph algorithms (see below), you don't have to care about the internals.
The most complex GraphUIElement is the RegularEdgeUIElement which connects two nodes; the difficulty was to rotate and scale the cylinder to the correct position.
The application already contains several graph algorithms like Dijkstra or Kruskal. To create your own algorithms, add a new class to the solution and implement the interface IGraphAlgorithm. After recompiling the solution, your algorithm will be listed in the menu.
Creating animations is quite simple, some extension methods make things even easier. In the following example, we add two nodes to the graph, then we flash the two nodes for 3 seconds. After the flashing is finished, both nodes are moved to another position.
public void Execute(IGraph<NodeData, EdgeData> graph)
{
graph.Clear();
this.node1 = graph.AddNode(new NodeData(new Point3D(0, 25, 0)));
this.node2 = graph.AddNode(new NodeData(new Point3D(0, -25, 0)));
this.graph.AddEdge(this.node1, this.node2);
this.node1.Blink(3000);
this.node2.Blink(3000, this.Callback);
}
private void Callback()
{
this.node1.Move(new Point3D(25, 0, 0), 4000);
this.node2.Move(new Point3D(-25, 0, 0), 4000);
}
Animations in WPF run asynchronously and parallel, that's great as long as animations should run parallel (like the flashing of both nodes). But the nodes should not move until the flashing animation has finished, therefore a callback is registered, and it gets executed at the end of the animation.
I hope this article gave you an overview of how the application works. You may download the code and modify or extend it as you like. If you have any questions, feel free to ask.
History
- 21/01/2010 - Initial release.
