Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/walks.py: 36%

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

2""" 

3 

4import networkx as nx 

5 

6__all__ = ["number_of_walks"] 

7 

8 

9@nx._dispatch 

10def number_of_walks(G, walk_length): 

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

12 

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

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

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

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

17 

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

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

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

21 and with a larger walk length. 

22 

23 Parameters 

24 ---------- 

25 G : NetworkX graph 

26 

27 walk_length : int 

28 A nonnegative integer representing the length of a walk. 

29 

30 Returns 

31 ------- 

32 dict 

33 A dictionary of dictionaries in which outer keys are source 

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

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

36 

37 Raises 

38 ------ 

39 ValueError 

40 If `walk_length` is negative 

41 

42 Examples 

43 -------- 

44 

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

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

47 >>> walks 

48 {0: {0: 1, 1: 0, 2: 1}, 1: {0: 0, 1: 2, 2: 0}, 2: {0: 1, 1: 0, 2: 1}} 

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

50 

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

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

53 can be found as follows: 

54 

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

56 >>> walks[0] 

57 {0: 0, 1: 1, 2: 0} 

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

59 1 

60 

61 Similarly, a target node can also be specified: 

62 

63 >>> walks[0][1] 

64 1 

65 

66 """ 

67 import numpy as np 

68 

69 if walk_length < 0: 

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

71 

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

73 # TODO: Use matrix_power from scipy.sparse when available 

74 # power = sp.sparse.linalg.matrix_power(A, walk_length) 

75 power = np.linalg.matrix_power(A.toarray(), walk_length) 

76 result = { 

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

78 for u_idx, u in enumerate(G) 

79 } 

80 return result