This documents the development version of NetworkX. Documentation for the current release can be found here.
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.
- GNetworkX graph
Starting node for the breadth-first search; this function iterates over only those edges in the component reachable from this node.
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
- widthint (default = None)
The beam width for the search. This is the number of neighbors (ordered by
value) to enqueue when visiting each new node.
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)) ... (0, 2) (0, 1) (0, 8) (0, 13) (0, 3) (2, 32) (1, 30) (8, 33) (3, 7) (32, 31) (31, 28) (31, 25) (25, 23) (25, 24) (23, 29) (23, 27) (29, 26)