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

is a a graph Ccondensation graphG=(CV,CE)based on the graphG=(V,E)where each vertex in CVcorresponds to a strongly connected component inGand edge(u,v)is in CEif and only if there exists an edge inEconnecting any of the vertices in the component ofuto any of the vertices in the component ofv.The

transitive closureof a graphG = (V,E)is a graph TG = (V,TE)such that TEcontains an edge(u,v)if and only ifGcontains a path (of at least one edge) fromutov.

**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); condensator.Create(cg);

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(), true); // attaching event handler condensation.InitCondensationGraphVertex+= new CondensationGraphVertexEventHandler(condensator_InitCondensationGraphVertex); // computing condensator.Create(cg); ... // 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.