[boost] BGL ported to C#

From: Jonathan de Halleux (dehalleux_at_[hidden])
Date: 2003-12-12 11:26:33

Hi all,

(This thread is a bit out of topic since boost is a C++ library but it is 
worth to mention. If you have nothing to do with C#, please do not mind 
this post)

The QuickGraph library is an attempt to port the BGL library to C#.  It has 
now reached a stable form and therefore I am sending this mail to the BGL 
C++ users.

A large part of the concept and structure of the library is directly 
takened from the BGL. Here below, I discuss some major points about porting 
the BGL to C#.

1) No templates in C#:
-----------------------------

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

2) Concepts and C# interface: natural friends
----------------------------------------------------------

The C# interfaces come to the rescue. Indeed, they are the natural C# 
equivalent of the 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 VertexListConcept defines the add_vertex and remove_vertex 
methods. The corresponding interface is:

public interface IVertexListGraph
{
     IVertex AddVertex();
     void RemoveVertex(IVertex u);
}

A model of the VertexListConcept 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.

3) ConceptChecking and C# interface: natural friends
---------------------------------------------------------------

C# interface have a lot of advantages. In fact, they enforce the 
implementation of their defined methods wich is implicitely a form of 
ConceptChecking.

4) Visitors ... no Events!
--------------------------------

The BGL adds greate flexibility and reusability 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 method. For instance, in the DepthFirstSearchAlgorithm, 
the visitor must implement 5 methods discover_vertex, tree_edge, back_egde, 
forward_or_cross_edge and finish_vertex.

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

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

5) 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 "Provider" 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 detailled in the ProviderConcepts section.

If interrested, you can downlaod it at
QuickGraph homepage: http://www.dotnetwiki.org

About licensing: QuickGraph is licensed under the zlib/png license.

-----------------------------------------------------------------------------------
Jonathan de Halleux, Research Assistant
Center for Systems Engineering and Applied Mechanics (CESAME)
Universite catholique de Louvain
Batiment Euler , Av. Georges Lemaitre, 4 Tel : [phone]
B-1348 Louvain-la-Neuve Belgium
E-mail : dehalleux_at_[hidden]
-----------------------------------------------------------------------------------