时间戳

首页 > 解决方案 > 计算是否存在巨型组件

python - 计算是否存在巨型组件

问题描述

我有一组整数，它通过连接集合的整数来创建一个图形，其中二进制表示仅相差一个位置，例如：

set={0, 3, 16} --> their binary representation are  {00000, 00011, 10000}

这将是一个图，其中两个节点已连接（0 和 16），而 3 未连接。现在我想计算，如果集合创建了一个图，那么它是完全连接的。换句话说，如果图的巨型组件包含所有节点。目前，我只使用networkx解决了这个问题，首先在networkx中创建一个图，然后使用nx.is_connected(G)

G = nx.Graph()
for key in set:
    G.add_node(key)

for n1 in G.nodes(data=True):
    for n2 in G.nodes(data=True):
        if bin(n1[0]^n2[0]).count("1") == 1:  #compare if binary rep. differs at one position
            G.add_edge(n1[0], n2[0], weight=1)

if nx.is_connected(G):

这是有问题的，因为它很慢，我不想使用networkx。你能帮助我吗？谢谢！

标签： pythonoptimizationnetworkxgraph-theory

解决方案

如果您关心速度，那么 C++ 是您的最佳选择。

要确定一个图是否完全连通，确定最大团的数量正好是一个就足够了。

这是寻找最大团的伪代码

LOOP
    CONSTRUCT empty current set
    SELECT V arbitrary vertex
    add V to current set
    remove V from graph
    LOOP      // while set is growing
        added_to_set = false
        LOOP V over vertices in graph
            LOOP Vset over current set
                IF Vset connected to V
                     add V to current set
                     remove V from graph
                     added_to_set = true
                     break;
        IF added_to_set == false
           break;    // the set is maximal
    ADD current set to list of sets
    IF graph has no remaining vertices
       OUTPUT sets found
       STOP

有关此代码的 C++ 实现，请参见https://github.com/JamesBremner/PathFinder2/blob/dbd6ff06edabd6a6d35d5eb10ed7972dc2d779a6/src/cPathFinder.cpp#L483处的代码

此代码可以在不到一秒的时间内处理数千个节点的图形。您使用 networkx 可以获得什么性能？

推荐阅读