图工具有没有投影二部图的方法？

Question

我正在尝试将一个二部图投影成两个单模式图。

我想用对偶投影法来分析二部图。我一直在使用NetworkX，但我想尝试一下图形工具，因为它声称效率更高。有可能我的图形很快就会变得非常大，所以我想使用最有效的方法/包。包图工具声称效率更高，我想试一试，但我找不到一种方法来使用它来投影二部图。有没有人知道用图形工具能做到这一点？我发现的唯一信息是创建者要求提出类似问题的人创建一个工单，以便他/他们可以开始工作，但它是从2014年开始的。

Answer 1

我也遇到了同样的问题，并得到了一个有效的解决方案。我已经让它在多达500万个节点的图形上工作。

它遵循三个主要步骤：

1. 使用is_bipartite函数生成一个布尔数组，每个顶点都属于该数组。在要删除的集合上进行循环，并在neighbours.
2. use
3. GraphView的所有组合之间添加边，以通过仅保留感兴趣的集合的节点来生成新图。

g = gt.lattice([5,5])
is_biparitite, part = gt.is_bipartite(g, partition=True)
gt.graph_draw(g, vertex_fill_color=part)  # to view the full graph coloured by set

from itertools import combinations

g_temp = g.copy()  # this is a deepcopy

for v, bipartite_label in enumerate(part):
    if bipartite_label == 0:
        neighbours = list(g.vertex(v).all_neighbours())

        for s, t in combinations(neighbours, 2):
            g_temp.add_edge(s, t)

g_projected = gt.Graph(gt.GraphView(g_temp, vfilt=part.a==1), prune=True)

gt.graph_draw(g_projected)