2

给定一个由有向和无向边组成的混合无环图，我想将此图分解为链组件的有向图（链组件中的每个节点将仅通过无向边相互连接）及其排序。

我很困惑是否应该首先对所有有向边进行拓扑排序，然后将无向边作为链组件进行搜索，或者我应该首先遍历所有无向边并给它们组 ID，然后找到一些有向边来连接这些组件。

由于该图是非循环的，我认为可以将它们从低编号组件排序到高编号组件，但无法得出一个可靠的答案。

4

3 回答 3

1

定义链组件的等价关系是Drton 2009的以下内容：如果存在一条路径使得G 中所有 0 ≤ i ≤ k - 1 ，则在链图中定义两个顶点v_0和G 是等价的。v_k(v_0,..., v_k)v_i − v_{i+1}

这种等价关系下的等价类是 G 的链分量。粗略地说，这意味着由链图的无向边构成的图的所有连通分量，加上仅与有向边相关的所有节点，加上所有与根本没有邻居，这相当于彼得的回答

这是正确分解 Cowell 2005,Probabilistic Networks and ..., p. 中给出的链图 CH-Asia 的函数。110 图 6.1。它是我作为业余项目开发的图形模型库的一部分。

虽然它使用自定义数据结构，但它应该不难适应其他涉及图形模型的代码库。

def get_chain_components(self) -> Set[Set[Node]]:
    """!
    """
    # filter out undirected edges
    edges = set()
    for e in self.edges():
        if e.type() == EdgeType.UNDIRECTED:
            edges.add(e)

    # make a graph from undirected edges
    undi = UndiGraph.from_graph(Graph.from_edge_node_set(edges, self.nodes()))
    return undi.get_components_as_node_set()
于 2021-01-29T02:05:38.030 回答
0

您描述的混合图又是有向图。只需将每个无向边替换为两个指向相反方向的有向边。

此外，您不能拥有具有无向边的无环图。至少一个长度为 2 的循环将始终存在，所以我不确定你的意思是什么。

看来您正在此图中寻找强连接的组件，因此我建议您使用Tarjan 的算法来查找它们。

于 2013-01-25T09:15:53.693 回答
0

我认为您的两种方法都可以正常工作。

在我看来，第二种方法似乎更自然。

如果我在 networkx 中执行此操作，我将通过以下方式实现您的第二种方法：

  1. 创建一个包含所有顶点但仅包含无向边的新图 H。

  2. 在 H 上调用connected_components以提取链组件并为每个组件分配不同的组 id。

  3. 为每个组 id 创建一个具有 1 个节点的新图 F。基于原始图中的有向边将 F 中的组与有向边连接。

  4. 在 F 上调用topological_sort来计算组 ID 的排序。

于 2013-01-25T09:08:20.777 回答