Search code examples
c#.netf#quickgraph

Getting connected components from a QuickGraph graph

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:

output from x in the FSI

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.

Solution

  • 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;}]) ]