束搜索

动态束宽的束搜索。

逐步加宽的束搜索会反复执行束搜索， 并逐渐增加束宽，直到找到目标节点。

import math

import matplotlib.pyplot as plt
import networkx as nx


def progressive_widening_search(G, source, value, condition, initial_width=1):
    """逐步加宽的束搜索以找到一个节点。

逐步加宽的束搜索涉及重复的束搜索，从较小的束宽度开始，如果未找到目标节点，则扩展到更大的束宽度。此实现仅返回第一个满足终止条件的节点。

`G` 是一个 NetworkX 图。

`source` 是图中的一个节点。搜索感兴趣的节点从这里开始，并且仅扩展到与此节点（弱）连接的组件中的那些节点。

`value` 是一个函数，返回一个实数，指示在决定将哪些邻居节点加入广度优先搜索队列时，潜在邻居节点的好坏程度。在每个步骤中，只有当前束宽度内的最佳节点会被加入队列。

`condition` 是搜索的终止条件。这是一个函数，输入一个节点并返回一个布尔值，指示该节点是否是目标节点。如果没有节点匹配终止条件，此函数会引发 :exc:`NodeNotFound` 异常。

`initial_width` 是束搜索的起始束宽度（默认值为1）。如果在该束宽度下未找到匹配 `condition` 的节点，则从 `source` 节点重新开始束搜索，束宽度是原来的两倍（因此束宽度呈指数增长）。搜索在束宽度超过图中节点数量时终止。
"""
    # 检查特殊情况，即源节点满足
    # termination condition.
    if condition(source):
        return source
    # 在此范围内`i`的最大可能值产生的宽度为
    # 至少是图中节点的数量，因此最终调用
    # `bfs_beam_edges` 等同于传统的广度优先搜索
    # 搜索。因此，所有节点最终都会被访问。
    log_m = math.ceil(math.log2(len(G)))
    for i in range(log_m):
        width = initial_width * pow(2, i)
        # 由于我们总是从相同的源节点开始，这个
        # 搜索可能会多次访问相同的节点（取决于
        # 实现`value`函数。
        for u, v in nx.bfs_beam_edges(G, source, value, width):
            if condition(v):
                return v
    # 至此，由于所有节点都已被访问，我们知道
    # 没有节点满足终止条件。
    raise nx.NodeNotFound("no node satisfied the termination condition")

寻找具有高中心性的节点。

我们生成一个随机图，计算每个节点的中心性，然后执行 为了找到一个具有高中心性的节点，进行逐步扩大搜索。

# 设置随机数生成的种子，以便示例可重复
seed = 89

G = nx.gnp_random_graph(100, 0.5, seed=seed)
centrality = nx.eigenvector_centrality(G)
avg_centrality = sum(centrality.values()) / len(G)


def has_high_centrality(v):
    return centrality[v] >= avg_centrality


source = 0
value = centrality.get
condition = has_high_centrality

found_node = progressive_widening_search(G, source, value, condition)
c = centrality[found_node]
print(f"found node {found_node} with centrality {c}")


# Draw graph
pos = nx.spring_layout(G, seed=seed)
options = {
    "node_color": "blue",
    "node_size": 20,
    "edge_color": "grey",
    "linewidths": 0,
    "width": 0.1,
}
nx.draw(G, pos, **options)
# 将中心性高的节点绘制为大而红色
nx.draw_networkx_nodes(G, pos, nodelist=[found_node], node_size=100, node_color="r")
plt.show()

found node 73 with centrality 0.12598283530728402