# Friday, August 13, 2004

QuickGraph now contains a condensation graph and transitive closure algorithm which were ported from the BGL by Rohit Gadogkar. Here's a recap. of the definitions of those type of graphs (takened from the Boost Graph Library reference)

A condensation graph is a a graph CG=(CV,CE) based on the graph G=(V,E) where each vertex in CV corresponds to a strongly connected component in G and edge (u,v) is in CE if and only if there exists an edge in E connecting any of the vertices in the component of u to any of the vertices in the component of v.

The transitive closure of a graph G = (V,E) is a graph TG = (V,TE) such that TE contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v.

Condenstation Graph

Assume that you have built a graph g using QuickGraph:

IVertexListGraph g = ...;

The algorithm responsible for the condensation graph creation is QuickGraph.Algorithms.CondensationGraphAlgorithm and takes the graph to condensate as parameter:

CondensationGraphAlgorithm condensator = new CondensationGraphAlgorithm(g);

In order to compute the condensation, we need to provide a mutable graph, for example a AdjacencyGraph, and call the Create method:

AdjacencyGraph cg = new AdjacencyGraph(true);

At this moment, cg contains the condensation graph of g. The only problem here, is that we have not stored the information about which vertex from V was associated to a vertex in CV. In order to do that, we need to add some event handlers to the algorithm. 

This algorithm defines one event, InitCondensationGraphVertex, which is trigerred for each new vertex of the condenstation graph CG. Remember that this vertex (in CV) "contains" all the vertices of a component in the original graph. In this example, we will create a condensation graph that creates NamedVertex, which has the Name property, and we concatenate the names of the condensed vertices to make it the name of the condensated vertex:

// using NamedVertexProvider in order 
// to create NamedVertex instances
AdjacencyGraph cg = new AdjacencyGraph(
    new NamedVertexProvider(),
    new EdgeProvider(),

// attaching event handler
    new CondensationGraphVertexEventHandler(condensator_InitCondensationGraphVertex);
// computing

// Event handler
void condensation_InitCondensationGraphVertex(
    object sender, 
    CondensationGraphVertexEventArgs arg)
    NamedVertex cv = (NamedVertex)arg.CondensationGraphVertex;
    StringWriter sw = new StringWriter();
    foreach (IVertex v in arg.StronglyConnectedVertices)
        sw.Write("{0}\\n", v);
    v.Name = sw.ToString();

That's it... Here are two images of graphs. The left image shows a state graph that is not strongly connected and the right image shows the condensation graph of it.

posted on Friday, August 13, 2004 10:44:00 AM (Pacific Daylight Time, UTC-07:00)  #    Comments [0]