Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/beamsearch.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Basic algorithms for breadth-first searching the nodes of a graph.""" | |
2 | |
3 from .breadth_first_search import generic_bfs_edges | |
4 | |
5 __all__ = ["bfs_beam_edges"] | |
6 | |
7 | |
8 def bfs_beam_edges(G, source, value, width=None): | |
9 """Iterates over edges in a beam search. | |
10 | |
11 The beam search is a generalized breadth-first search in which only | |
12 the "best" *w* neighbors of the current node are enqueued, where *w* | |
13 is the beam width and "best" is an application-specific | |
14 heuristic. In general, a beam search with a small beam width might | |
15 not visit each node in the graph. | |
16 | |
17 Parameters | |
18 ---------- | |
19 G : NetworkX graph | |
20 | |
21 source : node | |
22 Starting node for the breadth-first search; this function | |
23 iterates over only those edges in the component reachable from | |
24 this node. | |
25 | |
26 value : function | |
27 A function that takes a node of the graph as input and returns a | |
28 real number indicating how "good" it is. A higher value means it | |
29 is more likely to be visited sooner during the search. When | |
30 visiting a new node, only the `width` neighbors with the highest | |
31 `value` are enqueued (in decreasing order of `value`). | |
32 | |
33 width : int (default = None) | |
34 The beam width for the search. This is the number of neighbors | |
35 (ordered by `value`) to enqueue when visiting each new node. | |
36 | |
37 Yields | |
38 ------ | |
39 edge | |
40 Edges in the beam search starting from `source`, given as a pair | |
41 of nodes. | |
42 | |
43 Examples | |
44 -------- | |
45 To give nodes with, for example, a higher centrality precedence | |
46 during the search, set the `value` function to return the centrality | |
47 value of the node:: | |
48 | |
49 >>> G = nx.karate_club_graph() | |
50 >>> centrality = nx.eigenvector_centrality(G) | |
51 >>> source = 0 | |
52 >>> width = 5 | |
53 >>> for u, v in nx.bfs_beam_edges(G, source, centrality.get, width): | |
54 ... print((u, v)) # doctest: +SKIP | |
55 | |
56 """ | |
57 | |
58 if width is None: | |
59 width = len(G) | |
60 | |
61 def successors(v): | |
62 """Returns a list of the best neighbors of a node. | |
63 | |
64 `v` is a node in the graph `G`. | |
65 | |
66 The "best" neighbors are chosen according to the `value` | |
67 function (higher is better). Only the `width` best neighbors of | |
68 `v` are returned. | |
69 | |
70 The list returned by this function is in decreasing value as | |
71 measured by the `value` function. | |
72 | |
73 """ | |
74 # TODO The Python documentation states that for small values, it | |
75 # is better to use `heapq.nlargest`. We should determine the | |
76 # threshold at which its better to use `heapq.nlargest()` | |
77 # instead of `sorted()[:]` and apply that optimization here. | |
78 # | |
79 # If `width` is greater than the number of neighbors of `v`, all | |
80 # neighbors are returned by the semantics of slicing in | |
81 # Python. This occurs in the special case that the user did not | |
82 # specify a `width`: in this case all neighbors are always | |
83 # returned, so this is just a (slower) implementation of | |
84 # `bfs_edges(G, source)` but with a sorted enqueue step. | |
85 return iter(sorted(G.neighbors(v), key=value, reverse=True)[:width]) | |
86 | |
87 yield from generic_bfs_edges(G, source, successors) |