Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / traversal / beamsearch.py @ 5cef0f13

History | View | Annotate | Download (3.46 KB)

1
# beamsearch.py - breadth-first search with limited queueing
2
#
3
# Copyright 2016-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Basic algorithms for breadth-first searching the nodes of a graph."""
10

    
11
import networkx as nx
12
from .breadth_first_search import generic_bfs_edges
13

    
14
__all__ = ['bfs_beam_edges']
15

    
16

    
17
def bfs_beam_edges(G, source, value, width=None):
18
    """Iterates over edges in a beam search.
19

20
    The beam search is a generalized breadth-first search in which only
21
    the "best" *w* neighbors of the current node are enqueued, where *w*
22
    is the beam width and "best" is an application-specific
23
    heuristic. In general, a beam search with a small beam width might
24
    not visit each node in the graph.
25

26
    Parameters
27
    ----------
28
    G : NetworkX graph
29

30
    source : node
31
        Starting node for the breadth-first search; this function
32
        iterates over only those edges in the component reachable from
33
        this node.
34

35
    value : function
36
        A function that takes a node of the graph as input and returns a
37
        real number indicating how "good" it is. A higher value means it
38
        is more likely to be visited sooner during the search. When
39
        visiting a new node, only the `width` neighbors with the highest
40
        `value` are enqueued (in decreasing order of `value`).
41

42
    width : int (default = None)
43
        The beam width for the search. This is the number of neighbors
44
        (ordered by `value`) to enqueue when visiting each new node.
45

46
    Yields
47
    ------
48
    edge
49
        Edges in the beam search starting from `source`, given as a pair
50
        of nodes.
51

52
    Examples
53
    --------
54
    To give nodes with, for example, a higher centrality precedence
55
    during the search, set the `value` function to return the centrality
56
    value of the node::
57

58
        >>> G = nx.karate_club_graph()
59
        >>> centrality = nx.eigenvector_centrality(G)
60
        >>> source = 0
61
        >>> width = 5
62
        >>> for u, v in nx.bfs_beam_edges(G, source, centrality.get, width):
63
        ...     print((u, v))  # doctest: +SKIP
64

65
    """
66

    
67
    if width is None:
68
        width = len(G)
69

    
70
    def successors(v):
71
        """Returns a list of the best neighbors of a node.
72

73
        `v` is a node in the graph `G`.
74

75
        The "best" neighbors are chosen according to the `value`
76
        function (higher is better). Only the `width` best neighbors of
77
        `v` are returned.
78

79
        The list returned by this function is in decreasing value as
80
        measured by the `value` function.
81

82
        """
83
        # TODO The Python documentation states that for small values, it
84
        # is better to use `heapq.nlargest`. We should determine the
85
        # threshold at which its better to use `heapq.nlargest()`
86
        # instead of `sorted()[:]` and apply that optimization here.
87
        #
88
        # If `width` is greater than the number of neighbors of `v`, all
89
        # neighbors are returned by the semantics of slicing in
90
        # Python. This occurs in the special case that the user did not
91
        # specify a `width`: in this case all neighbors are always
92
        # returned, so this is just a (slower) implementation of
93
        # `bfs_edges(G, source)` but with a sorted enqueue step.
94
        return iter(sorted(G.neighbors(v), key=value, reverse=True)[:width])
95

    
96
    # TODO In Python 3.3+, this should be `yield from ...`
97
    for e in generic_bfs_edges(G, source, successors):
98
        yield e