Steven - 6 months ago 97

C# 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`

`x;;`

The values in the example

`tuple list`

`BillTo`

`ShipTo`

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

Answer

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.