9

我是图论的新手。

我已经使用QuickGraph 库创建了一个邻接图，最终，我希望从图中获得连接的组件。

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)

输出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;};}; ...]

并从undirGraph.Vertices：

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

符合预期。

无向图创建成功，但现在我卡住了。从这里开始，我不知道如何获取图形的连通分量，或者坦率地说，我是否使用正确的图形结构。

我本来希望x在图中包含组件，但x;;FSI 中的输出如下所示：

FSI 中 x 的输出

示例中的值tuple list表示数据库中BillTo的ShipTo客户 ID 值。

QuickGraph 库中的文档很少，特别是对于那些试图“即时学习”的人。

这个问题取代了我之前发布的问题。我曾考虑修改我之前的问题，但由于这是一个完全独立的问题，因此决定保留原样。

4

2 回答 2

6

这是你要找的东西吗？

图形

我会使用 RProvider 将代码发送到 R 并生成它，然后在必要时将其包装在 dll 中。然后，您可以使用components,等来提取连接。clustersgroups

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

如果您决定仍然坚持使用 QuickGraph，那么您在 FSI 中看到的内容是因为您正在定义一个名为的记录类型，该记录类型Vertex有一个名为 decimal 的十进制类型的成员。这有点令人困惑，所以最初我建议您坚持int并按以下方式生成图表：

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

您也可以只编写某种字典之类的数据结构来记录/计数引用。

于 2016-09-13T03:15:55.777 回答
6

事实证明，您需要调用Compute算法上的方法才能真正让它运行！

我拿了你的示例代码，只是添加了对Compute：

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

完成此操作后，x.Components将包含一个字典，该字典将组件的索引分配给每个顶点，因此如果您想要顶点组（表示组件），您可以按Value（即组件索引）对结果进行分组：

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

这给出了以下内容：

[ (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;}]) ]
于 2016-09-19T23:01:52.897 回答