c# - 从 QuickGraph 图中获取连接的组件

Question

我是图论新手。

我用 QuickGraph library 创建了一个邻接图最后，我想从图中获得连接的组件。

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 包含图中的组件，但 FSI 中 x;; 的输出看起来像这样:

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

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

这个问题取代了 previous question I posted .我曾考虑修改我之前的问题，但由于这是一个完全独立的问题，因此决定保持原样。

Answer 1

事实证明，您需要调用算法的 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;}]) ]