Boost logo

Boost :

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 : +32-10-47 2595
B-1348 Louvain-la-Neuve Belgium
E-mail : dehalleux_at_[hidden]
-----------------------------------------------------------------------------------


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk