ioftools / networkxMiCe / networkxmaster / examples / algorithms / plot_beam_search.py @ 5cef0f13
History  View  Annotate  Download (3.74 KB)
1 
# beam_search.py  progressive widening beam search


2 
#

3 
# Copyright 20162019 NetworkX developers.

4 
"""

5 
===========

6 
Beam Search

7 
===========

8 

9 
Beam search with dynamic beam width.

10 

11 
The progressive widening beam search repeatedly executes a beam search

12 
with increasing beam width until the target node is found.

13 
"""

14 
import math 
15  
16 
import networkx as nx 
17  
18  
19 
def progressive_widening_search(G, source, value, condition, initial_width=1): 
20 
"""Progressive widening beam search to find a node.

21 

22 
The progressive widening beam search involves a repeated beam

23 
search, starting with a small beam width then extending to

24 
progressively larger beam widths if the target node is not

25 
found. This implementation simply returns the first node found that

26 
matches the termination condition.

27 

28 
`G` is a NetworkX graph.

29 

30 
`source` is a node in the graph. The search for the node of interest

31 
begins here and extends only to those nodes in the (weakly)

32 
connected component of this node.

33 

34 
`value` is a function that returns a real number indicating how good

35 
a potential neighbor node is when deciding which neighbor nodes to

36 
enqueue in the breadthfirst search. Only the best nodes within the

37 
current beam width will be enqueued at each step.

38 

39 
`condition` is the termination condition for the search. This is a

40 
function that takes a node as input and return a Boolean indicating

41 
whether the node is the target. If no node matches the termination

42 
condition, this function raises :exc:`NodeNotFound`.

43 

44 
`initial_width` is the starting beam width for the beam search (the

45 
default is one). If no node matching the `condition` is found with

46 
this beam width, the beam search is restarted from the `source` node

47 
with a beam width that is twice as large (so the beam width

48 
increases exponentially). The search terminates after the beam width

49 
exceeds the number of nodes in the graph.

50 

51 
"""

52 
# Check for the special case in which the source node satisfies the

53 
# termination condition.

54 
if condition(source):

55 
return source

56 
# The largest possible value of `i` in this range yields a width at

57 
# least the number of nodes in the graph, so the final invocation of

58 
# `bfs_beam_edges` is equivalent to a plain old breadthfirst

59 
# search. Therefore, all nodes will eventually be visited.

60 
#

61 
# TODO In Python 3.3+, this should be `math.log2(len(G))`.

62 
log_m = math.ceil(math.log(len(G), 2)) 
63 
for i in range(log_m): 
64 
width = initial_width * pow(2, i) 
65 
# Since we are always starting from the same source node, this

66 
# search may visit the same nodes many times (depending on the

67 
# implementation of the `value` function).

68 
for u, v in nx.bfs_beam_edges(G, source, value, width): 
69 
if condition(v):

70 
return v

71 
# At this point, since all nodes have been visited, we know that

72 
# none of the nodes satisfied the termination condition.

73 
raise nx.NodeNotFound('no node satisfied the termination condition') 
74  
75  
76 
def main(): 
77 
"""Search for a node with high centrality.

78 

79 
In this example, we generate a random graph, compute the centrality

80 
of each node, then perform the progressive widening search in order

81 
to find a node of high centrality.

82 

83 
"""

84 
G = nx.gnp_random_graph(100, 0.5) 
85 
centrality = nx.eigenvector_centrality(G) 
86 
avg_centrality = sum(centrality.values()) / len(G) 
87  
88 
def has_high_centrality(v): 
89 
return centrality[v] >= avg_centrality

90  
91 
source = 0

92 
value = centrality.get 
93 
condition = has_high_centrality 
94  
95 
found_node = progressive_widening_search(G, source, value, condition) 
96 
c = centrality[found_node] 
97 
print('found node {0} with centrality {1}'.format(found_node, c))

98  
99  
100 
if __name__ == '__main__': 
101 
main() 