Steven - 1 month ago 7x
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 =
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.

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))