Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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 2016-2019 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 breadth-first 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 breadth-first
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()