Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/linalg/graphmatrix.py: 16%

1""" 

2Adjacency matrix and incidence matrix of graphs. 

3""" 

4import networkx as nx 

5 

6__all__ = ["incidence_matrix", "adjacency_matrix"] 

7 

8 

9@nx._dispatch(edge_attrs="weight") 

10def incidence_matrix( 

11 G, nodelist=None, edgelist=None, oriented=False, weight=None, *, dtype=None 

12): 

13 """Returns incidence matrix of G. 

14 

15 The incidence matrix assigns each row to a node and each column to an edge. 

16 For a standard incidence matrix a 1 appears wherever a row's node is 

17 incident on the column's edge. For an oriented incidence matrix each 

18 edge is assigned an orientation (arbitrarily for undirected and aligning to 

19 direction for directed). A -1 appears for the source (tail) of an edge and 

20 1 for the destination (head) of the edge. The elements are zero otherwise. 

21 

22 Parameters 

23 ---------- 

24 G : graph 

25 A NetworkX graph 

26 

27 nodelist : list, optional (default= all nodes in G) 

28 The rows are ordered according to the nodes in nodelist. 

29 If nodelist is None, then the ordering is produced by G.nodes(). 

30 

31 edgelist : list, optional (default= all edges in G) 

32 The columns are ordered according to the edges in edgelist. 

33 If edgelist is None, then the ordering is produced by G.edges(). 

34 

35 oriented: bool, optional (default=False) 

36 If True, matrix elements are +1 or -1 for the head or tail node 

37 respectively of each edge. If False, +1 occurs at both nodes. 

38 

39 weight : string or None, optional (default=None) 

40 The edge data key used to provide each value in the matrix. 

41 If None, then each edge has weight 1. Edge weights, if used, 

42 should be positive so that the orientation can provide the sign. 

43 

44 dtype : a NumPy dtype or None (default=None) 

45 The dtype of the output sparse array. This type should be a compatible 

46 type of the weight argument, eg. if weight would return a float this 

47 argument should also be a float. 

48 If None, then the default for SciPy is used. 

49 

50 Returns 

51 ------- 

52 A : SciPy sparse array 

53 The incidence matrix of G. 

54 

55 Notes 

56 ----- 

57 For MultiGraph/MultiDiGraph, the edges in edgelist should be 

58 (u,v,key) 3-tuples. 

59 

60 "Networks are the best discrete model for so many problems in 

61 applied mathematics" [1]_. 

62 

63 References 

64 ---------- 

65 .. [1] Gil Strang, Network applications: A = incidence matrix, 

66 http://videolectures.net/mit18085f07_strang_lec03/ 

67 """ 

68 import scipy as sp 

69 

70 if nodelist is None: 

71 nodelist = list(G) 

72 if edgelist is None: 

73 if G.is_multigraph(): 

74 edgelist = list(G.edges(keys=True)) 

75 else: 

76 edgelist = list(G.edges()) 

77 A = sp.sparse.lil_array((len(nodelist), len(edgelist)), dtype=dtype) 

78 node_index = {node: i for i, node in enumerate(nodelist)} 

79 for ei, e in enumerate(edgelist): 

80 (u, v) = e[:2] 

81 if u == v: 

82 continue # self loops give zero column 

83 try: 

84 ui = node_index[u] 

85 vi = node_index[v] 

86 except KeyError as err: 

87 raise nx.NetworkXError( 

88 f"node {u} or {v} in edgelist but not in nodelist" 

89 ) from err 

90 if weight is None: 

91 wt = 1 

92 else: 

93 if G.is_multigraph(): 

94 ekey = e[2] 

95 wt = G[u][v][ekey].get(weight, 1) 

96 else: 

97 wt = G[u][v].get(weight, 1) 

98 if oriented: 

99 A[ui, ei] = -wt 

100 A[vi, ei] = wt 

101 else: 

102 A[ui, ei] = wt 

103 A[vi, ei] = wt 

104 return A.asformat("csc") 

105 

106 

107@nx._dispatch(edge_attrs="weight") 

108def adjacency_matrix(G, nodelist=None, dtype=None, weight="weight"): 

109 """Returns adjacency matrix of G. 

110 

111 Parameters 

112 ---------- 

113 G : graph 

114 A NetworkX graph 

115 

116 nodelist : list, optional 

117 The rows and columns are ordered according to the nodes in nodelist. 

118 If nodelist is None, then the ordering is produced by G.nodes(). 

119 

120 dtype : NumPy data-type, optional 

121 The desired data-type for the array. 

122 If None, then the NumPy default is used. 

123 

124 weight : string or None, optional (default='weight') 

125 The edge data key used to provide each value in the matrix. 

126 If None, then each edge has weight 1. 

127 

128 Returns 

129 ------- 

130 A : SciPy sparse array 

131 Adjacency matrix representation of G. 

132 

133 Notes 

134 ----- 

135 For directed graphs, entry i,j corresponds to an edge from i to j. 

136 

137 If you want a pure Python adjacency matrix representation try 

138 networkx.convert.to_dict_of_dicts which will return a 

139 dictionary-of-dictionaries format that can be addressed as a 

140 sparse matrix. 

141 

142 For MultiGraph/MultiDiGraph with parallel edges the weights are summed. 

143 See `to_numpy_array` for other options. 

144 

145 The convention used for self-loop edges in graphs is to assign the 

146 diagonal matrix entry value to the edge weight attribute 

147 (or the number 1 if the edge has no weight attribute). If the 

148 alternate convention of doubling the edge weight is desired the 

149 resulting SciPy sparse array can be modified as follows: 

150 

151 >>> G = nx.Graph([(1, 1)]) 

152 >>> A = nx.adjacency_matrix(G) 

153 >>> print(A.todense()) 

154 [[1]] 

155 >>> A.setdiag(A.diagonal() * 2) 

156 >>> print(A.todense()) 

157 [[2]] 

158 

159 See Also 

160 -------- 

161 to_numpy_array 

162 to_scipy_sparse_array 

163 to_dict_of_dicts 

164 adjacency_spectrum 

165 """ 

166 return nx.to_scipy_sparse_array(G, nodelist=nodelist, dtype=dtype, weight=weight)