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

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

2 

3import networkx as nx 

4 

5__all__ = ["bfs_beam_edges"] 

6 

7 

8@nx._dispatchable 

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

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

11 

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

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

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

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

16 not visit each node in the graph. 

17 

18 .. note:: 

19 

20 With the default value of ``width=None`` or `width` greater than the 

21 maximum degree of the graph, this function equates to a slower 

22 version of `~networkx.algorithms.traversal.breadth_first_search.bfs_edges`. 

23 All nodes will be visited, though the order of the reported edges may 

24 vary. In such cases, `value` has no effect - consider using `bfs_edges` 

25 directly instead. 

26 

27 Parameters 

28 ---------- 

29 G : NetworkX graph 

30 

31 source : node 

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

33 iterates over only those edges in the component reachable from 

34 this node. 

35 

36 value : function 

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

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

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

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

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

42 

43 width : int (default = None) 

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

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

46 

47 Yields 

48 ------ 

49 edge 

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

51 of nodes. 

52 

53 Examples 

54 -------- 

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

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

57 value of the node: 

58 

59 >>> G = nx.karate_club_graph() 

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

61 >>> list(nx.bfs_beam_edges(G, source=0, value=centrality.get, width=3)) 

62 [(0, 2), (0, 1), (0, 8), (2, 32), (1, 13), (8, 33)] 

63 """ 

64 

65 if width is None: 

66 width = len(G) 

67 

68 def successors(v): 

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

70 

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

72 

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

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

75 `v` are returned. 

76 """ 

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

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

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

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

81 # 

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

83 # neighbors are returned by the semantics of slicing in 

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

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

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

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

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

89 

90 yield from nx.generic_bfs_edges(G, source, successors)