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

• Updated source and downloads available at: CodePlex
• Download source code - 232 Kb
• Download assembly + doc - 357 Kb

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.

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 // this interface defines the Graph conecpt

{
    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 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

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

AdjacencyGraph g = new AdjacencyGraph(
    new VertexAndEdgeProvider(), // vertex and edge provider 

    true // directed graph

    );

// adding vertices u,v

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

IVertex v = g.AddVertex();    

// adding the edge (u,v)

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();

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:

// 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();

// adding handler

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;
  ...
  
  // PageLoad method
  
  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;

License

zlib/png license.

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

• The BoostGraphLibrary.
• Graphviz home page.
• Discrete Finite Automata for .NET, from Leppie. This is where the .NET Dot DLL is coming from.