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 8*^{th}, 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.

## About Graph Theory

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
- edge = road

- 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
{
IVertex AddVertex();
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 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

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:

AdjacencyGraph g = new AdjacencyGraph(
new VertexAndEdgeProvider(),
true
);
IVertex u = g.AddVertex();
IVertex v = g.AddVertex();
IEdge e = g.AddEdge(u,v);

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:

foreach(IVertex v in g.Vertices)
{
...
}
foeach(IEdge e in g.Edges)
{
...
}

Vertices and edges can also be removed from the graph:

g.Remove(u);
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:

using QuickGraph.Collections;
...
VertexStringDictionary names = new VertexStringDictionary();
IVertex u = g.AddVertex();
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:

IVertexListGraph g = ...;
DepthFirstSearchAlgorithm dfs = new DepthFirstSearchAlgorithm(g);
dfs.Compute();

`InitializeVertex`

event:
- Visiting
*u* vertex:
- Visiting
*v* vertex:
- Visiting
*y* vertex:
- Visiting
*x* vertex:
- Finishing
*u* vertex:
- Visiting
*w* vertex:
- 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();
}
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 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:

public class MyRenderer
{
private VertexStringDictionary m_Names;
private GraphvizVertex m_Vertex;
...
public WriteVertex(Object sender, VertexEventArgs args)
{
GraphvizWriterAlgorithm algo = (GraphvizWriterAlgorithm)sender;
m_Vertex.Label = m_Names[args.Vertex];
algo.Output.Write( m_Vertex.ToDot() );
}
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 = ...;
Dot.RelativePath = "./temp";
Dot.Algo.VisitedGraph = g;
Dot.Algo.Renderer.Prefix="customprefix";
Dot.TimeOut = new TimeSpan(0,0,1,0,0);
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

## References

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