Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/linalg/graphmatrix.py @ 5:9b1c78e6ba9c draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6c0a8142489327ece472c84e558c47da711a9142"
author shellac
date Mon, 01 Jun 2020 08:59:25 -0400
parents 79f47841a781
children
comparison
equal deleted inserted replaced
4:79f47841a781 5:9b1c78e6ba9c
1 """
2 Adjacency matrix and incidence matrix of graphs.
3 """
4 # Copyright (C) 2004-2019 by
5 # Aric Hagberg <hagberg@lanl.gov>
6 # Dan Schult <dschult@colgate.edu>
7 # Pieter Swart <swart@lanl.gov>
8 # All rights reserved.
9 # BSD license.
10 import networkx as nx
11 __author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
12 'Pieter Swart (swart@lanl.gov)',
13 'Dan Schult(dschult@colgate.edu)'])
14
15 __all__ = ['incidence_matrix',
16 'adj_matrix', 'adjacency_matrix',
17 ]
18
19
20 def incidence_matrix(G, nodelist=None, edgelist=None,
21 oriented=False, weight=None):
22 """Returns incidence matrix of G.
23
24 The incidence matrix assigns each row to a node and each column to an edge.
25 For a standard incidence matrix a 1 appears wherever a row's node is
26 incident on the column's edge. For an oriented incidence matrix each
27 edge is assigned an orientation (arbitrarily for undirected and aligning to
28 direction for directed). A -1 appears for the tail of an edge and 1
29 for the head of the edge. The elements are zero otherwise.
30
31 Parameters
32 ----------
33 G : graph
34 A NetworkX graph
35
36 nodelist : list, optional (default= all nodes in G)
37 The rows are ordered according to the nodes in nodelist.
38 If nodelist is None, then the ordering is produced by G.nodes().
39
40 edgelist : list, optional (default= all edges in G)
41 The columns are ordered according to the edges in edgelist.
42 If edgelist is None, then the ordering is produced by G.edges().
43
44 oriented: bool, optional (default=False)
45 If True, matrix elements are +1 or -1 for the head or tail node
46 respectively of each edge. If False, +1 occurs at both nodes.
47
48 weight : string or None, optional (default=None)
49 The edge data key used to provide each value in the matrix.
50 If None, then each edge has weight 1. Edge weights, if used,
51 should be positive so that the orientation can provide the sign.
52
53 Returns
54 -------
55 A : SciPy sparse matrix
56 The incidence matrix of G.
57
58 Notes
59 -----
60 For MultiGraph/MultiDiGraph, the edges in edgelist should be
61 (u,v,key) 3-tuples.
62
63 "Networks are the best discrete model for so many problems in
64 applied mathematics" [1]_.
65
66 References
67 ----------
68 .. [1] Gil Strang, Network applications: A = incidence matrix,
69 http://academicearth.org/lectures/network-applications-incidence-matrix
70 """
71 import scipy.sparse
72 if nodelist is None:
73 nodelist = list(G)
74 if edgelist is None:
75 if G.is_multigraph():
76 edgelist = list(G.edges(keys=True))
77 else:
78 edgelist = list(G.edges())
79 A = scipy.sparse.lil_matrix((len(nodelist), len(edgelist)))
80 node_index = dict((node, i) for i, node in enumerate(nodelist))
81 for ei, e in enumerate(edgelist):
82 (u, v) = e[:2]
83 if u == v:
84 continue # self loops give zero column
85 try:
86 ui = node_index[u]
87 vi = node_index[v]
88 except KeyError:
89 raise nx.NetworkXError('node %s or %s in edgelist '
90 'but not in nodelist' % (u, v))
91 if weight is None:
92 wt = 1
93 else:
94 if G.is_multigraph():
95 ekey = e[2]
96 wt = G[u][v][ekey].get(weight, 1)
97 else:
98 wt = G[u][v].get(weight, 1)
99 if oriented:
100 A[ui, ei] = -wt
101 A[vi, ei] = wt
102 else:
103 A[ui, ei] = wt
104 A[vi, ei] = wt
105 return A.asformat('csc')
106
107
108 def adjacency_matrix(G, nodelist=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 weight : string or None, optional (default='weight')
121 The edge data key used to provide each value in the matrix.
122 If None, then each edge has weight 1.
123
124 Returns
125 -------
126 A : SciPy sparse matrix
127 Adjacency matrix representation of G.
128
129 Notes
130 -----
131 For directed graphs, entry i,j corresponds to an edge from i to j.
132
133 If you want a pure Python adjacency matrix representation try
134 networkx.convert.to_dict_of_dicts which will return a
135 dictionary-of-dictionaries format that can be addressed as a
136 sparse matrix.
137
138 For MultiGraph/MultiDiGraph with parallel edges the weights are summed.
139 See to_numpy_matrix for other options.
140
141 The convention used for self-loop edges in graphs is to assign the
142 diagonal matrix entry value to the edge weight attribute
143 (or the number 1 if the edge has no weight attribute). If the
144 alternate convention of doubling the edge weight is desired the
145 resulting Scipy sparse matrix can be modified as follows:
146
147 >>> import scipy as sp
148 >>> G = nx.Graph([(1,1)])
149 >>> A = nx.adjacency_matrix(G)
150 >>> print(A.todense())
151 [[1]]
152 >>> A.setdiag(A.diagonal()*2)
153 >>> print(A.todense())
154 [[2]]
155
156 See Also
157 --------
158 to_numpy_matrix
159 to_scipy_sparse_matrix
160 to_dict_of_dicts
161 adjacency_spectrum
162 """
163 return nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight)
164
165
166 adj_matrix = adjacency_matrix
167
168
169 # fixture for pytest
170 def setup_module(module):
171 import pytest
172 scipy = pytest.importorskip('scipy')