Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/walks.py: 42%

1"""Function for computing walks in a graph.""" 

2 

3import networkx as nx 

4 

5__all__ = ["number_of_walks"] 

6 

7 

8@nx._dispatchable 

9def number_of_walks(G, walk_length): 

10 """Returns the number of walks connecting each pair of nodes in `G` 

11 

12 A *walk* is a sequence of nodes in which each adjacent pair of nodes 

13 in the sequence is adjacent in the graph. A walk can repeat the same 

14 edge and go in the opposite direction just as people can walk on a 

15 set of paths, but standing still is not counted as part of the walk. 

16 

17 This function only counts the walks with `walk_length` edges. Note that 

18 the number of nodes in the walk sequence is one more than `walk_length`. 

19 The number of walks can grow very quickly on a larger graph 

20 and with a larger walk length. 

21 

22 Parameters 

23 ---------- 

24 G : NetworkX graph 

25 

26 walk_length : int 

27 A nonnegative integer representing the length of a walk. 

28 

29 Returns 

30 ------- 

31 dict 

32 A dictionary of dictionaries in which outer keys are source 

33 nodes, inner keys are target nodes, and inner values are the 

34 number of walks of length `walk_length` connecting those nodes. 

35 

36 Raises 

37 ------ 

38 ValueError 

39 If `walk_length` is negative 

40 

41 Examples 

42 -------- 

43 

44 >>> G = nx.Graph([(0, 1), (1, 2)]) 

45 >>> walks = nx.number_of_walks(G, 2) 

46 >>> walks 

47 {0: {0: 1, 1: 0, 2: 1}, 1: {0: 0, 1: 2, 2: 0}, 2: {0: 1, 1: 0, 2: 1}} 

48 >>> total_walks = sum(sum(tgts.values()) for _, tgts in walks.items()) 

49 

50 You can also get the number of walks from a specific source node using the 

51 returned dictionary. For example, number of walks of length 1 from node 0 

52 can be found as follows: 

53 

54 >>> walks = nx.number_of_walks(G, 1) 

55 >>> walks[0] 

56 {0: 0, 1: 1, 2: 0} 

57 >>> sum(walks[0].values()) # walks from 0 of length 1 

58 1 

59 

60 Similarly, a target node can also be specified: 

61 

62 >>> walks[0][1] 

63 1 

64 

65 """ 

66 import scipy as sp 

67 

68 if walk_length < 0: 

69 raise ValueError(f"`walk_length` cannot be negative: {walk_length}") 

70 

71 A = nx.adjacency_matrix(G, weight=None) 

72 power = sp.sparse.linalg.matrix_power(A, walk_length).tocsr() 

73 result = { 

74 u: {v: power[u_idx, v_idx].item() for v_idx, v in enumerate(G)} 

75 for u_idx, u in enumerate(G) 

76 } 

77 return result