13,702,595 members
alternative version

#### Stats

1M views
354 bookmarked
Posted 7 Dec 2003
Licenced

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

, 23 Apr 2007
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" %>
...
<quickgraph:GraphvizControl RunAt="server" id="Dot" />```
• 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

 First PrevNext
 Outdated article and source code EivindGL10-Aug-18 22:38 EivindGL 10-Aug-18 22:38
 My vote of 5 Gun Gun Febrianza9-Jan-17 9:37 Gun Gun Febrianza 9-Jan-17 9:37
 My vote of 5 Daniel Miller22-Dec-15 11:18 Daniel Miller 22-Dec-15 11:18
 Display Member 115492358-May-15 0:09 Member 11549235 8-May-15 0:09
 Re: Display Frayion17-Aug-15 21:38 Frayion 17-Aug-15 21:38
 UndirectedGraph Member 1043647924-Feb-15 4:12 Member 10436479 24-Feb-15 4:12
 GraphViz Map Member 99611112-Apr-13 17:50 Member 9961111 2-Apr-13 17:50
 Decomposition of medial axis tree Member 917583215-Jul-12 15:38 Member 9175832 15-Jul-12 15:38
 My vote of 5 manoj kumar choubey15-Feb-12 23:17 manoj kumar choubey 15-Feb-12 23:17
 REALLY using QuickGraph oistrez12-Jan-12 7:45 oistrez 12-Jan-12 7:45
 Graph Objects oistrez8-Jan-12 1:20 oistrez 8-Jan-12 1:20
 My vote of 5 I'm Chris18-Mar-11 2:01 I'm Chris 18-Mar-11 2:01
 Latest code is on codeplex - http://quickgraph.codeplex.com/ (version 3.3.x) I'm Chris18-Mar-11 1:58 I'm Chris 18-Mar-11 1:58
 Re: Latest code is on codeplex - http://quickgraph.codeplex.com/ (version 3.3.x) EivindGL10-Aug-18 22:29 EivindGL 10-Aug-18 22:29
 Dijkstra shortest path algorithm with edge cost 4salwa24-Nov-10 0:29 4salwa 24-Nov-10 0:29
 Visualize the dot-file Barill19-Sep-10 21:24 Barill 19-Sep-10 21:24
 Re: Visualize the dot-file Sovetnikov25-Jan-11 20:07 Sovetnikov 25-Jan-11 20:07
 Re: Visualize the dot-file Win32nipuh12-Mar-11 1:05 Win32nipuh 12-Mar-11 1:05
 Re: Visualize the dot-file Artem Sovetnikov12-Mar-11 5:55 Artem Sovetnikov 12-Mar-11 5:55
 show caption/label/text on edge/arrow line of each vertex Adnan Aman12-Jul-10 4:02 Adnan Aman 12-Jul-10 4:02
 graphviz web render error alog is not implement ?? apo944-Apr-08 0:06 apo94 4-Apr-08 0:06
 graduation project wich name is (AI BASED E-COMMERCE) muhammed123-Mar-08 0:08 muhammed1 23-Mar-08 0:08
 can not find dot.dll Pranav Kaushik14-Jan-08 2:30 Pranav Kaushik 14-Jan-08 2:30
 Re: can not find dot.dll Denny6-Jun-08 2:30 Denny 6-Jun-08 2:30
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Sep-18 2:13 Refresh 12345678 Next »