Getting connected components from a QuickGraph graph

Question

I'm new to graph theory.

I've created an adjacency graph with the QuickGraph library and ultimately, I'd like to have the connected components from the graph.

open QuickGraph

let tup = [(1M,1M); (2M, 18M); (3M, 3M); (4M, 5M); (5M, 24M); (24M, 6M); (7M, 6M); (8M, 9M); (10M, 9M)]

type Vertex = {decimal: decimal}

let edges = 
    tup
    |> List.map (fun x -> ({decimal = fst x}, {decimal = snd x}))
    |> List.map (fun x -> Edge<Vertex> x)

//Undirected Graph
let undirGraph = edges.ToUndirectedGraph()

undirGraph.Edges
undirGraph.Vertices

let x = QuickGraph.Algorithms.ConnectedComponents.ConnectedComponentsAlgorithm(undirGraph)

Output from undirGraph.Edges:

val it : Collections.Generic.IEnumerable<Edge<Vertex>> =
seq
[FSI_0227+Vertex->FSI_0227+Vertex {Source = {decimal = 1M;};
                                       Target = {decimal = 1M;};};
 FSI_0227+Vertex->FSI_0227+Vertex {Source = {decimal = 2M;};
                                   Target = {decimal = 18M;};};
 FSI_0227+Vertex->FSI_0227+Vertex {Source = {decimal = 3M;};
                                   Target = {decimal = 3M;};};
 FSI_0227+Vertex->FSI_0227+Vertex {Source = {decimal = 4M;};
                                   Target = {decimal = 5M;};}; ...]

and from undirGraph.Vertices:

val it : Collections.Generic.IEnumerable<Vertex> =
seq
[{decimal = 1M;}; {decimal = 2M;}; {decimal = 18M;}; {decimal = 3M;}; ...]

are as expected.

The undirected graph is created successfully, but now I'm stuck. From here, I don't know how to get the connected components of the graph or, frankly, if I'm using the correct graph structure.

I would have expected x to contain the components in the graph but output from x;; in FSI looks like this:

The values in the example tuple list represent BillTo and ShipTo customer ID values in a database.

The documentation in the QuickGraph library is sparse, particularly for someone trying to "learn on the fly."

This question supplants a previous question I posted. I had considered modifying my prior question but, as this is a completely separate question, have decided to leave it as is.

Answer 1

Is this something you are looking for?

I would use use the RProvider to send the code to R and generate this and then wrap it in a dll if necessary. You can then use components, clusters, groups etc. to extract the connections.

# In R:
g1 <- graph(  edges=c( "1","1", "2", "18", "3", "3", "4", "5", "5", "24", "24", "6", "7", "6", "8", "9", "10", "9"),n=9,directed=T)
plot(g1)
comp1 <- components(g1)
comp1
groups(comp1)
cl <- clusters(g1)
lapply(seq_along(cl$csize)[cl$csize > 1], function(x) 
  V(g1)$name[cl$membership %in% x]) 

In case you decide to still stick to QuickGraph, what you are seeing in FSI is because you are defining a record type called Vertex that has one member called decimal of type decimal. This is a tad bit confusing, so initially I would suggest you stick to int and just generate the graph the following way:

let tup = [(1,1); (2, 18); (3, 3); (4, 5); (5, 24); (24, 6); (7, 6); (8, 9); (10, 9)]
let edges =
    tup |> List.map (fun x -> SEdge<int>(fst x, snd x))
let graph = edges.ToAdjacencyGraph()
let uniGraph = edges.ToUndirectedGraph()

You could also just write some sort of dictionary like data structure that keeps record/count of the references.

Answer 2

It turns out that you need to call the Compute method on the algorithm to actually get it to run!

I took your sample code and just added call to Compute:

let x = QuickGraph.Algorithms.ConnectedComponents.
          ConnectedComponentsAlgorithm(undirGraph)
x.Compute()

Once you do this, x.Components contains a dictionary that assigns an index of a component to each vertex, so if you want groups of vertices (representing components), you can just group the results by the Value (which is the component index):

x.Components 
|> Seq.groupBy (fun kv -> kv.Value)
|> Seq.map (fun (comp, vertices) -> 
    comp, vertices |> Seq.map (fun kv -> kv.Key))

This gives the following:

[ (0, [{decimal = 1M;}]); 
  (1, [{decimal = 2M;}; {decimal = 18M;}]);
  (2, [{decimal = 3M;}]);
  (3, [{decimal = 4M;}; {decimal = 5M;}; {decimal = 24M;}; 
       {decimal = 6M;}; {decimal = 7M;}]);
  (4, [{decimal = 8M;}; {decimal = 9M;}; {decimal = 10M;}]) ]