Steven Steven - 1 year ago 204
C# Question

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 =
|> (fun x -> ({decimal = fst x}, {decimal = snd x}))
|> (fun x -> Edge<Vertex> x)

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


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

Output from

val it : Collections.Generic.IEnumerable<Edge<Vertex>> =
[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

val it : Collections.Generic.IEnumerable<Vertex> =
[{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
to contain the components in the graph but output from
in FSI looks like this:

output from x in the FSI

The values in the example
tuple list
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 Source

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)
comp1 <- components(g1)
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 |> (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.