bfs_beam_edges(G, source, value, width=None)¶
Iterates over edges in a beam search.
The beam search is a generalized breadth-first search in which only the “best” w neighbors of the current node are enqueued, where w is the beam width and “best” is an application-specific heuristic. In general, a beam search with a small beam width might not visit each node in the graph.
- G (NetworkX graph)
- source (node) – Starting node for the breadth-first search; this function iterates over only those edges in the component reachable from this node.
- value (function) – A function that takes a node of the graph as input and returns a
real number indicating how “good” it is. A higher value means it
is more likely to be visited sooner during the search. When
visiting a new node, only the
widthneighbors with the highest
valueare enqueued (in decreasing order of
- width (int (default = None)) – The beam width for the search. This is the number of neighbors
value) to enqueue when visiting each new node.
edge – Edges in the beam search starting from
source, given as a pair of nodes.
To give nodes with, for example, a higher centrality precedence during the search, set the
valuefunction to return the centrality value of the node:
>>> G = nx.karate_club_graph() >>> centrality = nx.eigenvector_centrality(G) >>> source = 0 >>> width = 5 >>> for u, v in nx.bfs_beam_edges(G, source, centrality.get, width): ... print((u, v))