Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/traversal/beamsearch.py: 50%

1"""Basic algorithms for breadth-first searching the nodes of a graph.""" 

2import networkx as nx 

3 

4from .breadth_first_search import generic_bfs_edges 

5 

6__all__ = ["bfs_beam_edges"] 

7 

8 

9@nx._dispatch 

10def bfs_beam_edges(G, source, value, width=None): 

11 """Iterates over edges in a beam search. 

12 

13 The beam search is a generalized breadth-first search in which only 

14 the "best" *w* neighbors of the current node are enqueued, where *w* 

15 is the beam width and "best" is an application-specific 

16 heuristic. In general, a beam search with a small beam width might 

17 not visit each node in the graph. 

18 

19 Parameters 

20 ---------- 

21 G : NetworkX graph 

22 

23 source : node 

24 Starting node for the breadth-first search; this function 

25 iterates over only those edges in the component reachable from 

26 this node. 

27 

28 value : function 

29 A function that takes a node of the graph as input and returns a 

30 real number indicating how "good" it is. A higher value means it 

31 is more likely to be visited sooner during the search. When 

32 visiting a new node, only the `width` neighbors with the highest 

33 `value` are enqueued (in decreasing order of `value`). 

34 

35 width : int (default = None) 

36 The beam width for the search. This is the number of neighbors 

37 (ordered by `value`) to enqueue when visiting each new node. 

38 

39 Yields 

40 ------ 

41 edge 

42 Edges in the beam search starting from `source`, given as a pair 

43 of nodes. 

44 

45 Examples 

46 -------- 

47 To give nodes with, for example, a higher centrality precedence 

48 during the search, set the `value` function to return the centrality 

49 value of the node: 

50 

51 >>> G = nx.karate_club_graph() 

52 >>> centrality = nx.eigenvector_centrality(G) 

53 >>> source = 0 

54 >>> width = 5 

55 >>> for u, v in nx.bfs_beam_edges(G, source, centrality.get, width): 

56 ... print((u, v)) 

57 ... 

58 (0, 2) 

59 (0, 1) 

60 (0, 8) 

61 (0, 13) 

62 (0, 3) 

63 (2, 32) 

64 (1, 30) 

65 (8, 33) 

66 (3, 7) 

67 (32, 31) 

68 (31, 28) 

69 (31, 25) 

70 (25, 23) 

71 (25, 24) 

72 (23, 29) 

73 (23, 27) 

74 (29, 26) 

75 """ 

76 

77 if width is None: 

78 width = len(G) 

79 

80 def successors(v): 

81 """Returns a list of the best neighbors of a node. 

82 

83 `v` is a node in the graph `G`. 

84 

85 The "best" neighbors are chosen according to the `value` 

86 function (higher is better). Only the `width` best neighbors of 

87 `v` are returned. 

88 

89 The list returned by this function is in decreasing value as 

90 measured by the `value` function. 

91 

92 """ 

93 # TODO The Python documentation states that for small values, it 

94 # is better to use `heapq.nlargest`. We should determine the 

95 # threshold at which its better to use `heapq.nlargest()` 

96 # instead of `sorted()[:]` and apply that optimization here. 

97 # 

98 # If `width` is greater than the number of neighbors of `v`, all 

99 # neighbors are returned by the semantics of slicing in 

100 # Python. This occurs in the special case that the user did not 

101 # specify a `width`: in this case all neighbors are always 

102 # returned, so this is just a (slower) implementation of 

103 # `bfs_edges(G, source)` but with a sorted enqueue step. 

104 return iter(sorted(G.neighbors(v), key=value, reverse=True)[:width]) 

105 

106 yield from generic_bfs_edges(G, source, successors)