15,037,662 members
Articles / Programming Languages / C#
Article
Posted 7 Dec 2003

1.1M views
358 bookmarked

# QuickGraph: A 100% C# Graph Library with Graphviz Support

Rate me:
A generic directed graph library with a Graphviz Web Control Bonus!
In this article, you will learn about a 100% C# Generic Graph Library, an attempt to port the Boost Graph Library (BGL) from C++ to C#.

There have been a lot of changes to the source code and the article below, since the first submission on December 8th, 2020.

## 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 than 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:

C#
```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.

C#
`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 five methods, `discover_vertex`, `tree_edge`, `back_egde`, `forward_or_cross_edge `and `finish_vertex`. These events are illustrated below in a practical example.

In `QuickGraph`, the decision could be done to reuse the BGL visitor pattern, but it turned out that C# provided a very 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 a 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 be used to create and populate a graph:

C#
```// Create a 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:

C#
```//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:

C#
```//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 of typed dictionary to help you with this task.

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

C#
```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:

C#
```// 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:

C#
```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.

C#
```PredecessorRecorder p = new PredecessorRecorder();

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

Therefore, plugging custom actions to algorithms is quite easy and takes 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 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 lets 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 render the graph to SVG and use the vertex name map to render the vertices' name:

C#
```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
ASP.NET
```<%@ Register TagPrefix="quickgraph"
Namespace="QuickGraph.Web.Controls" Assembly="QuickGraph.Web" %>
...
<quickgraph:GraphvizControl RunAt="server" id="Dot" />```
• Code behind:
C#
```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: 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

## 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).

 First PrevNext
 project dead? kiquenet.com5-Feb-19 2:05 kiquenet.com 5-Feb-19 2:05
 Re: project dead? Member 1280563629-Dec-19 5:34 Member 12805636 29-Dec-19 5:34
 Outdated article and source code EivindGL10-Aug-18 22:38 EivindGL 10-Aug-18 22:38
 CodeProject has a concept of alternatives to articles, but this article doesn't have any alternatives listed. Since the content is no longer reproduceable using the current version of the sources - and which fork at GitHub is the current version of the CodePlex sources anyway(?) - this article should be updated and point to documentation of some working samples of todays code. If the author knows the best direction to go from here, please point that out somehow.
 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 rinmic2-Apr-13 17:50 rinmic 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 herrstress12-Jan-12 7:45 herrstress 12-Jan-12 7:45
 Graph Objects herrstress8-Jan-12 1:20 herrstress 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 Artem Sovetnikov25-Jan-11 20:07 Artem 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