12,700,558 members (31,340 online)
alternative version

878.7K views
352 bookmarked
Posted

# QuickGraph: A 100% C# graph library with Graphviz Support.

, 23 Apr 2007
 Rate this:
A generic directed graph library with a Graphviz Web Control Bonus!

There has been a lot of changes to the source code and the article below, since the first submission on Dec. 8.

## Introduction

This article presents a Generic Graph Library, 100% C#. This library is an attempt to port the Boost Graph Library (BGL) from C++ to C#.

Graph problems arise in a number of situations (more often that you would think): file compilation order, network band-with, shortest path, etc. The library provides the basic data structure to represent vertices, edges and graphs, and also provides generic implementation of various graph algorithms such as the depth-first-search, the Dijkstra shortest path, etc.

As the library comes with a full NDoc reference manual, this article will not enter into deep coding details.

This is a quick remainder about graph theory:

A directed graph G=(VxE) consists of a finite set V=V(G) of vertices and a finite multi-set E contained in VxV = {(u,v)| u,v in V} of edges that are ordered pair of vertices.

If e=(u,v), then e is an outgoing edge of u and an incoming edge of v. indegree(v) denotes the number of incoming edges of v and outdegree(u), the number of outgoing edges of u.

Classic graph examples are:

• Transportation network:
• vertex = crossing,
• Internet:
• vertex = computer,
• edge = telephone line,
• Source code files:
• vertex = file,
• edge = dependency

## What is the BoostGraphLibrary?

This section discusses aspects about the porting from C++ to C# of the BoostGraphLibrary. The BoostGraphLibrary is a C++ generic graph library that introduces itself as such:

"Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. Consequently, these abstractions must also be represented in computer programs. A standardized generic interface for traversing graphs is of utmost importance to encourage reuse of graph algorithms and data structures. Part of the Boost Graph Library is an interface for how the structure of a graph can be accessed using a generic interface that hides the details of the graph data structure implementation. This is an "open" interface in the sense that any graph library that implements this interface will be interoperable with the BGL generic algorithms and with other algorithms that also use this interface. BGL provides some general purpose graph classes that conform to this interface, but they are not meant to be the "only" graph classes; there certainly will be other graph classes better for certain situations. We believe that the main contribution of the BGL is the formulation of this interface."

Introduction taken from the BGL introduction page.

QuickGraphLibrary has been highly influenced by the BGL implementation and, indeed, a large part of the concept and structure of the library is directly taken from the BGL. Here below, some major points about porting the BGL to C# are discussed.

### No templates in C#:

This is, for sure, the biggest issue: C# does not support templates... yet (Generics in .NET 2.0). So class templates, function templates and partial template specialization could not be used. At first, without templates, the genericity of the library is seriously compromised.

### Concepts and C# interface: natural friends

The C# interfaces come to the rescue. Indeed, they are the natural C# equivalent of the abstract concepts. In fact, turning a BGL concept into a C# interface is just a matter of ... writing the valid expressions into an interface.

For example, the VertexList concept defines the add_vertex and remove_vertex methods and refines the graph concepts. The corresponding interface is:

public interface IVertexListGraph :
IGraph // this interface defines the Graph conecpt
{
void RemoveVertex(IVertex u);
}

A model of the VertexList concept will have to implement the IVertexListGraph interface. For example, the AdjacencyGraph class will derive from IVertexListGraph which will oblige it to implement the desired methods.

public class AdjacencyGraph : ..., IVertexListGraph

All the QuickGraph concepts are centralized in the QuickGraph.Concepts namespace (in the QuickGraph.Concepts.dll assembly) which in fact contains interfaces only.

### ConceptChecking and C# interface: natural friends

C# interfaces have a lot of advantages. In fact, they enforce the implementation of their defined methods which is implicitly a form of ConceptChecking.

### Visitors ... no Events!

The BGL adds great flexibility and reusability to its algorithms through the use of visitors (see the VisitorPattern of the GoF).

In the BGL, to define visitors, you must first create a visitor class that defines a number of methods. For instance, in the depth_firsts_search algorithm, the visitor must implement 5 methods discover_vertex, tree_edge, back_egde, forward_or_cross_edge and finish_vertex. These events are illustrated below on a practical example.

In QuickGraph, the decision could be done to reuse the BGL visitor pattern, but it turned out that C# provided a much flexible solution: events. In C#, events are delegates, i.e. function calls dispatcher, to which static functions or instance bound methods (handlers) can be attached. Whenever this event is fired, the handlers are called. Therefore, the BGL visitor methods naturally translate into events where visitors can attach their handlers.

Another interesting advantage about delegates is that they are multi-cast. Therefore, multiple visitors can be attached to the same algorithm out-of-the-box.

### Vertex, edge descriptors... Providers

In the BGL, the choice of vertex and edge descriptor comes out-of-the-box with the use of templates. To tackle this problem, QuickGraph asks the user to provide VertexAndEdgeProvider classes that generate the vertex and edges on demand. Therefore, you can use any object as vertex or edge as long as it derives from IVertex or IEdge. Providers are detailed in the ProviderConcepts section.

## Quick description of the library

As in the BGL, concepts play crucial role in QuickGraph. They are implemented by interfaces in the QuickGraph.Concepts namespace. The concept are grouped in the following families:

• Core concepts: defining a vertex (IVertex), an edge (IEdge), a graph (IGraph)
• Graph Traversal concepts: defining how the graph, edges and vertices can be iterated. (IVertexListGraph, IIncidenceGraph, etc...)
• Graph Modification concepts: defining how the graph can be modified by adding or removing edges and vertices (IEdgeMutableGraph, IMutableIncidenceGraph, etc...)
• ...

The AdjacencyGraph class implements a number of Traversal concepts and Modification concepts and it is the equivalent of the adjacency_list template of the BGL. It can used to create and populate a graph:

// Create new graph
new VertexAndEdgeProvider(), // vertex and edge provider
true // directed graph
);

IVertex u = g.AddVertex();    // IVertexMutableGraph

IEdge e = g.AddEdge(u,v);     // IEdgeMutableGraph

Since the vertices and the edges are sets, indexing and ordering does not have a sense on these collections. However, they can easily be iterated:

//iterating vertices
foreach(IVertex v in g.Vertices) // IVertexListGraph
{
...
}

// iterating edges
foeach(IEdge e in g.Edges)       // IEdgeListGraph
{
...
}

Vertices and edges can also be removed from the graph:

//this will automatically remove the in and out edges of u
g.Remove(u); // IVertexMutableGraph
g.Remove(e);

### Attaching data to vertices and edges

Similarly to the BGL property map, it is the user's job to create and maintain data maps to associate data to vertices and edges. The namespace Collections contains a number a typed dictionary to help you with this task.

The following example shows how to create a vertex name map:

using QuickGraph.Collections;
...
VertexStringDictionary names = new VertexStringDictionary();

names[u] = "u";

## Algorithms

Algorithms are the problem solvers of the library. Without algorithms, this library would not have much sense.

Similar to the BGL, the algorithms are implemented in a generic way using a Visitor pattern. The algorithms call user defined actions at specific events: when a vertex is discovered for the first time, when an edge is discovered for the first time, etc... In QuickGraph, the visitor pattern is implemented through events.

### Quick Example

Let us illustrate that with an example, the depth-first-search algorithm. When possible, a depth-first traversal chooses a vertex adjacent to the current vertex to visit next. If all adjacent vertices have already been discovered, or there are no adjacent vertices, then the algorithm backtracks to the last vertex that had undiscovered neighbors. Once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal. The algorithm finishes when all vertices have been visited. Depth-first search is useful for categorizing edges in a graph, and for imposing an ordering on the vertices. To achieve that, the algorithms use colors: vertex color markers:

• White vertex: vertex not yet discovered
• Gray Vertex: vertex discovered, and sub-tree being explored
• Black Vertex: vertex discovered and sub-tree traversal finished

In QuickGraph, the depth first search is implemented by the DepthFirstSearchAlgorithm class. This class exposes a number of events (not all are detailed here):

• DiscoverVertex, invoked when a vertex is encountered for the first time,
• ExamineEdge, invoked on every out-edge of each vertex after it is discovered,
• TreeEdge, invoked on each edge as it becomes a member of the edges that form the search tree,
• FinishVertex, invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

The application of the depth first search to a simple graph is detailed in the figures below. The code to achieve this looks (more or less) as follows:

// A graph that implements the IVertexListGraph interface
IVertexListGraph g = ...;
// create algorithm
DepthFirstSearchAlgorithm dfs = new DepthFirstSearchAlgorithm(g);
//do the search
dfs.Compute();
1. InitializeVertex event,

2. Visiting u vertex,

3. Visiting v vertex,

4. Visiting y vertex,

5. Visiting x vertex,

6. Finishing u vertex,

7. Visiting w vertex,

8. Finishing graph

The figures above show when the events are called. The events can be used by the user to achieve custom actions. For example, suppose that you want to record the vertex predecessors (this will create an ordering), first you need to create a class that provides a delegate for the TreeEdge event:

class PredecessorRecorder
{
private VertexEdgeDictionary m_Predecessors;

public PredecessorRecorder()
{
m_Predecessors = new VertexEdgeDictionary();
}

// the delegate
public void RecordPredecessor(object sender, EdgeEventArgs args)
{
m_Predecessors[ args.Edge.Target ] = args.Edge;
}
}

The PredecessorRecorder class can then be plugged to the depth first search algorithm.

PredecessorRecorder p = new PredecessorRecorder();

dfs.TreeEdge += new EdgeHandler( p.RecordPredecessor );

Therefore, plugging custom actions to algorithms is quite easy and take full advantage of the event-multidelegates feature of C#.

Other algorithms are available and detailed in the NDoc documentation.

## GraphViz Renderer and Web Control

Visualization of the graph can be done using the Graphviz renderer and web control. Graphviz is an open source C application for drawing directed and undirected graphs.

A BIG thanks can be done to Leppie who took the time and work to port the Graphviz application to .NET

### Graphviz Renderer

QuickGraph provides a number of helper classes to output your graphs using Graphviz:

• DotRenderer wraps up the Dot call and let you choose the output path, image type, etc...
• GraphvizAlgorithm is an algorithm that traverses the graph and creates the dot output. This algorithm provides three events that can be used to customize the vertices' and edges' appearance:
• WriteGraph is called for setting global properties
• WriteVertex is called on each vertex
• WriteEdge is called on each edge
• GraphvizGraph is a class helper for setting global settings
• GraphvizVertex is a class helper to set vertices' appearance properties
• GraphvizEdge is a class helper to set edges' appearance properties

The following examples renders the graph to SVG and uses the vertex name map to render the vertices' name:

public class MyRenderer
{
private VertexStringDictionary m_Names; // name map
private GraphvizVertex m_Vertex; // helper
...

// vertex delegate
public WriteVertex(Object sender, VertexEventArgs args)
{
// sender is of type GraphvizWriterAlgorithm
GraphvizWriterAlgorithm algo = (GraphvizWriterAlgorithm)sender;
// setting name
m_Vertex.Label = m_Names[args.Vertex];

// outputing
algo.Output.Write( m_Vertex.ToDot() );
}

// rendering method
public void Render(Graph g, VerteStringDictionary names)
{
m_Names =names;
GraphvizWriterAlgorithm algo = new GraphvizWriterAlgorithm(g);

algo.WriteVertex += new VertexHandler( this.WriteVertex );

algo.Renderer.ImageType = GraphvizImageType.Svg;
algo.Compute();
}
}

### Graphviz Web Control

A server web control, QuickGraph.Web.Controls.GraphvizControl, is available: It has design time support so you can insert it in your toolbox.

The following examples show how to use the control:

• .aspx
<%@ Register TagPrefix="quickgraph"
Namespace="QuickGraph.Web.Controls" Assembly="QuickGraph.Web" %>
• code behind
GraphvizControl Dot;
...

IVertexAndEdgeListGraph g = ...;

// output file path
Dot.RelativePath = "./temp";
Dot.Algo.VisitedGraph = g;

Dot.Algo.Renderer.Prefix="customprefix";
Dot.TimeOut = new TimeSpan(0,0,1,0,0); // files are cached
Dot.Algo.Renderer.ImageType =
QuickGraph.Algorithms.Graphviz.GraphvizImageType.Svgz;

## History

• 2.1, the library has almost been totally rewritten. The main changes are:
• complete mapping of BGL concepts to interfaces,
• complete separation of graph implementations and algorithms,
• unit testing of algorithms,
• improved the Graphviz control.
• v1.0, Initial release.

## References

A list of licenses authors might use can be found here

## Share

 Engineer United States
Jonathan de Halleux is Civil Engineer in Applied Mathematics. He finished his PhD in 2004 in the rainy country of Belgium. After 2 years in the Common Language Runtime (i.e. .net), he is now working at Microsoft Research on Pex (http://research.microsoft.com/pex).

## You may also be interested in...

 Pro Pro

 graduation project wich name is (AI BASED E-COMMERCE) muhammed123-Mar-08 1:08 muhammed1 23-Mar-08 1:08
 can not find dot.dll Pranav Kaushik14-Jan-08 3:30 Pranav Kaushik 14-Jan-08 3:30
 Re: can not find dot.dll Denny6-Jun-08 3:30 Denny 6-Jun-08 3:30
 Re: can not find dot.dll xeno7614-Jan-10 2:22 xeno76 14-Jan-10 2:22
 Re: can not find dot.dll Atlatic17-Mar-13 18:20 Atlatic 17-Mar-13 18:20
 quickgraph in .net web application arbrunda13-Dec-07 3:13 arbrunda 13-Dec-07 3:13
 urgent help with quick graph library I_risho16-Oct-07 14:09 I_risho 16-Oct-07 14:09
 Sample to Create Class Diagram? SteveC-A915-Jun-07 11:23 SteveC-A9 15-Jun-07 11:23
 Can you show a simple C# console application that uses this library to create a class diagram?
 Question about dot.dll kbutter6-Jun-07 5:44 kbutter 6-Jun-07 5:44
 How can I change the output direction? kbutter1-Jun-07 2:12 kbutter 1-Jun-07 2:12
 documentation/help csetzkorn30-May-07 1:19 csetzkorn 30-May-07 1:19
 Re: documentation/help kbutter6-Jun-07 5:52 kbutter 6-Jun-07 5:52
 png output [modified] kbutter29-May-07 22:38 kbutter 29-May-07 22:38
 Re: png output Allam25-Jun-08 5:32 Allam 25-Jun-08 5:32
 png output Allam28-Aug-08 4:03 Allam 28-Aug-08 4:03
 Re: png output kbutter28-Aug-08 4:27 kbutter 28-Aug-08 4:27
 GraphvizAlgorithm Lissi4kin8-May-07 0:36 Lissi4kin 8-May-07 0:36
 Nice library, but hard to extend s_dimi23-Apr-07 11:11 s_dimi 23-Apr-07 11:11
 Re: Nice library, but hard to extend Jonathan de Halleux23-Apr-07 20:05 Jonathan de Halleux 23-Apr-07 20:05
 QuickGraph for .NET 2.0 is out david_k1323-Apr-07 4:20 david_k13 23-Apr-07 4:20
 Calling QuickGraph.Algorithms.Graphviz.DotRenderer.Render just creates a DOT file david_k1328-Mar-07 6:27 david_k13 28-Mar-07 6:27
 Re: Calling QuickGraph.Algorithms.Graphviz.DotRenderer.Render just creates a DOT file david_k1330-Mar-07 5:09 david_k13 30-Mar-07 5:09
 where is the latest source siegfriedDb26-Mar-07 7:12 siegfriedDb 26-Mar-07 7:12
 How to display the graph ? alexsantos28-Feb-07 11:08 alexsantos 28-Feb-07 11:08
 Last Visit: 31-Dec-99 19:00     Last Update: 23-Jan-17 3:55 Refresh 12345678 Next »