python - 在Python中禁止执行compute_resilience函数

Question

其思想是以无向图的形式计算网络的恢复力。
{node: (set of its neighbors) for each node in the graph}
该函数按随机顺序逐个从图中删除节点，并计算剩余最大连接组件的大小。
helper函数返回仍然连接到给定节点的节点集。
如何改进python 2中算法的实现？最好不改变helper函数中的宽度优先算法

def bfs_visited(graph, node):
    """undirected graph {Vertex: {neighbors}}
    Returns the set of all nodes visited by the algrorithm"""
    queue = deque()
    queue.append(node)
    visited = set([node])
    while queue:
        current_node = queue.popleft()
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

def cc_visited(graph):
    """ undirected graph {Vertex: {neighbors}}
    Returns a list of sets of connected components"""
    remaining_nodes = set(graph.keys())
    connected_components = []
    for node in remaining_nodes:
        visited = bfs_visited(graph, node)
        if visited not in connected_components:
            connected_components.append(visited)
        remaining_nodes = remaining_nodes - visited
        #print(node, remaining_nodes)
    return connected_components

def largest_cc_size(ugraph):
    """returns the size (an integer) of the largest connected component in 
    the ugraph."""
    if not ugraph:
        return 0
    res = [(len(ccc), ccc) for ccc in cc_visited(ugraph)]
    res.sort()
    return res[-1][0]

def compute_resilience(ugraph, attack_order):
    """
    input: a graph {V: N}

    returns a list whose k+1th entry is the size of the largest cc after 
    the removal of the first k nodes
    """
    res = [len(ugraph)]
    for node in attack_order:
        neighbors = ugraph[node]  
        for neighbor in neighbors:
            ugraph[neighbor].remove(node)
        ugraph.pop(node)
        res.append(largest_cc_size(ugraph))      
    return res

Answer 1

我从加雷斯那里得到了这个非常好的答案，完全涵盖了这个问题。
回顾
bfs_visited的docstring应该解释node参数。
compute_resilience的docstring应该解释ugraph参数被修改。或者，该函数可以获取图形的副本，以便不修改原始图形。
在bfs}u参观了线路：

queue = deque()
queue.append(node)
can be simplified to:

queue = deque([node])    

函数 largest_cc_size生成一个成对的列表：

res = [(len(ccc), ccc) for ccc in cc_visited(ugraph)]
res.sort()
return res[-1][0]

但是您可以看到它只使用每对的第一个元素（组件的大小）。因此，您可以通过不构建对来简化它：

res = [len(ccc) for ccc in cc_visited(ugraph)]
res.sort()
return res[-1]

因为只需要最大组件的大小，所以不需要构建整个列表。相反，您可以使用max来查找最大的：

if ugraph:
    return max(map(len, cc_visited(ugraph)))
else:
    return 0

如果您使用的是Python3.4或更高版本，则可以使用默认参数max进一步简化：

return max(map(len, cc_visited(ugraph)), default=0)

现在这很简单，它可能不需要自己的函数。
这一行：

remaining_nodes = set(graph.keys())

可以写得更简单：

remaining_nodes = set(graph)

在集合剩余的_节点上有一个循环，在每个循环迭代中，更新剩余的_节点：

for node in remaining_nodes:
    visited = bfs_visited(graph, node)
    if visited not in connected_components:
        connected_components.append(visited)
    remaining_nodes = remaining_nodes - visited

看起来代码的意图是通过从剩余的节点中删除访问的节点来避免在访问的节点上迭代，但是这不起作用！问题是for语句：

for node in remaining_nodes:

在循环开始时，只计算一次剩余的_节点表达式。因此，当代码创建一个新集合并将其分配给其余的节点时：

remaining_nodes = remaining_nodes - visited

这对正在迭代的节点没有影响。
您可以想象使用difference_update方法调整正在迭代的集合来修复此问题：

remaining_nodes.difference_update(visited)

但是这是一个坏主意，因为这样你就可以在一个集合上迭代并在循环中修改它，这是不安全的。相反，您需要按如下方式编写循环：

while remaining_nodes:
    node = remaining_nodes.pop()
    visited = bfs_visited(graph, node)
    if visited not in connected_components:
        connected_components.append(visited)
    remaining_nodes.difference_update(visited)

使用while和pop是python中在修改数据结构时使用数据结构的标准习惯用法-在访问的bfs中可以执行类似的操作。
现在不需要进行测试：
如果未在连接的组件中访问：
因为每个组件只生产一次。
在计算弹性中，第一行是：

res = [len(ugraph)]

但是，只有当图是一个单独的连接组件时，这才起作用要处理一般情况，第一行应该是：

res = [largest_cc_size(ugraph)]

对于攻击顺序中的每个节点，计算恢复能力调用：

res.append(largest_cc_size(ugraph))

但这并没有利用以前所做的工作。当我们从图中移除节点时，除了包含节点的连接组件外，所有连接组件都保持不变。因此，如果我们只对该组件进行广度优先搜索，而不是对整个图形进行广度优先搜索，就可能节省一些工作。（这是否真的节省了任何工作取决于图表的弹性。对于高弹性的图表，这不会有太大的区别。）
为此，我们需要重新设计数据结构，以便能够有效地找到包含节点的组件，并有效地从组件集合中移除该组件。
这个答案已经很长了，所以我不会详细解释如何重新设计数据结构，我只会给出修改后的代码，让您自己解决。

def connected_components(graph, nodes):
    """Given an undirected graph represented as a mapping from nodes to
    the set of their neighbours, and a set of nodes, find the
    connected components in the graph containing those nodes.

    Returns:
    - mapping from nodes to the canonical node of the connected
      component they belong to
    - mapping from canonical nodes to connected components

    """
    canonical = {}
    components = {}
    while nodes:
        node = nodes.pop()
        component = bfs_visited(graph, node)
        components[node] = component
        nodes.difference_update(component)
        for n in component:
            canonical[n] = node
    return canonical, components

def resilience(graph, attack_order):
    """Given an undirected graph represented as a mapping from nodes to
    an iterable of their neighbours, and an iterable of nodes, generate
    integers such that the the k-th result is the size of the largest
    connected component after the removal of the first k-1 nodes.

    """
    # Take a copy of the graph so that we can destructively modify it.
    graph = {node: set(neighbours) for node, neighbours in graph.items()}

    canonical, components = connected_components(graph, set(graph))
    largest = lambda: max(map(len, components.values()), default=0)
    yield largest()
    for node in attack_order:
        # Find connected component containing node.
        component = components.pop(canonical.pop(node))

        # Remove node from graph.
        for neighbor in graph[node]:
            graph[neighbor].remove(node)
        graph.pop(node)
        component.remove(node)

        # Component may have been split by removal of node, so search
        # it for new connected components and update data structures
        # accordingly.
        canon, comp = connected_components(graph, component)
        canonical.update(canon)
        components.update(comp)
        yield largest()

在修改后的代码中，max操作必须遍历所有剩余的连接组件才能找到最大的组件。通过将连接的组件存储在优先级队列中，可以提高此步骤的效率，以便在时间上找到最大的组件，其数量是组件数量的对数。
我怀疑这部分算法在实践中是一个瓶颈，所以可能不值得额外的代码，但是如果需要这样做，那么python文档中有一些优先级队列实现说明。
性能比较
下面是制作测试用例的有用函数：
从itertools导入组合
从随机导入随机
定义随机图（n，p）：
“”返回一个随机无向图，其中n个节点和每个选择的边
独立于概率p。

"""
assert 0 <= p <= 1
graph = {i: set() for i in range(n)}
for i, j in combinations(range(n), 2):
    if random() <= p:
        graph[i].add(j)
        graph[j].add(i)
return graph

现在，快速比较修改后的代码和原始代码的性能。请注意，我们必须先运行修订后的代码，因为原始代码会破坏性地修改图形，如上文第1.2节所述。

>>> from timeit import timeit

>>> G = random_graph(300, 0.2)

>>> timeit(lambda:list(resilience(G, list(G))), number=1) # revised
0.28782312001567334

>>> timeit(lambda:compute_resilience(G, list(G)), number=1) # original
59.46968446299434

所以在这个测试用例中，修改后的代码大约快了200倍。