从有向图中制作只有相互边的子图的最佳方法

Question

我正在使用 igraph python 库中的有向图。我正在尝试获取仅包含互边的子图。

我当前的实现是：

i = 0
edgeList = list()
for e in completeGraph.es:
    i = i+1
    if not e.is_mutual():
        edgeList.append(e)
        if i % 1000 == 0:
            print(i)
completeGraph.delete_edges(edgeList)
completeGraph.vs.select(_degree=0).delete()

这似乎可行，但感觉像是一种非常迂回的方式，而且在非常大的图上（作为我正在使用 ~20 Mio.Edges 处理的类型）它相当慢。

是否有更好或更有效的方法来完成同样的事情？

Answer 1

我有一个可能的解决方案。我用 Python 3.8.5 和 igraph 0.9.1 做到了。我创建了一个简单的示例，一个有 10 个顶点和 7 个边（4 个互边）的有向图。或许能帮到你。

from igraph import *

g = Graph(directed=True)
g.add_vertices(10)
g.add_edges([(0, 1), (1, 0), (5, 3), (7, 8), (9, 1), (7, 2), (2, 7)])

g.es.select(_is_mutual=False).delete()
g.vs.select(_degree=0).delete()

结果是图g只有互边（以及那些边中涉及的顶点）。

祝你好运！

从有向图中制作只有相互边的子图的最佳方法

Best way to make a subgraph with only mutual edges out of a directed graph

python

igraph