Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/matrix.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 ==================== | |
3 Biadjacency matrices | |
4 ==================== | |
5 """ | |
6 import itertools | |
7 from networkx.convert_matrix import _generate_weighted_edges | |
8 import networkx as nx | |
9 | |
10 __all__ = ["biadjacency_matrix", "from_biadjacency_matrix"] | |
11 | |
12 | |
13 def biadjacency_matrix( | |
14 G, row_order, column_order=None, dtype=None, weight="weight", format="csr" | |
15 ): | |
16 r"""Returns the biadjacency matrix of the bipartite graph G. | |
17 | |
18 Let `G = (U, V, E)` be a bipartite graph with node sets | |
19 `U = u_{1},...,u_{r}` and `V = v_{1},...,v_{s}`. The biadjacency | |
20 matrix [1]_ is the `r` x `s` matrix `B` in which `b_{i,j} = 1` | |
21 if, and only if, `(u_i, v_j) \in E`. If the parameter `weight` is | |
22 not `None` and matches the name of an edge attribute, its value is | |
23 used instead of 1. | |
24 | |
25 Parameters | |
26 ---------- | |
27 G : graph | |
28 A NetworkX graph | |
29 | |
30 row_order : list of nodes | |
31 The rows of the matrix are ordered according to the list of nodes. | |
32 | |
33 column_order : list, optional | |
34 The columns of the matrix are ordered according to the list of nodes. | |
35 If column_order is None, then the ordering of columns is arbitrary. | |
36 | |
37 dtype : NumPy data-type, optional | |
38 A valid NumPy dtype used to initialize the array. If None, then the | |
39 NumPy default is used. | |
40 | |
41 weight : string or None, optional (default='weight') | |
42 The edge data key used to provide each value in the matrix. | |
43 If None, then each edge has weight 1. | |
44 | |
45 format : str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'} | |
46 The type of the matrix to be returned (default 'csr'). For | |
47 some algorithms different implementations of sparse matrices | |
48 can perform better. See [2]_ for details. | |
49 | |
50 Returns | |
51 ------- | |
52 M : SciPy sparse matrix | |
53 Biadjacency matrix representation of the bipartite graph G. | |
54 | |
55 Notes | |
56 ----- | |
57 No attempt is made to check that the input graph is bipartite. | |
58 | |
59 For directed bipartite graphs only successors are considered as neighbors. | |
60 To obtain an adjacency matrix with ones (or weight values) for both | |
61 predecessors and successors you have to generate two biadjacency matrices | |
62 where the rows of one of them are the columns of the other, and then add | |
63 one to the transpose of the other. | |
64 | |
65 See Also | |
66 -------- | |
67 adjacency_matrix | |
68 from_biadjacency_matrix | |
69 | |
70 References | |
71 ---------- | |
72 .. [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph | |
73 .. [2] Scipy Dev. References, "Sparse Matrices", | |
74 https://docs.scipy.org/doc/scipy/reference/sparse.html | |
75 """ | |
76 from scipy import sparse | |
77 | |
78 nlen = len(row_order) | |
79 if nlen == 0: | |
80 raise nx.NetworkXError("row_order is empty list") | |
81 if len(row_order) != len(set(row_order)): | |
82 msg = "Ambiguous ordering: `row_order` contained duplicates." | |
83 raise nx.NetworkXError(msg) | |
84 if column_order is None: | |
85 column_order = list(set(G) - set(row_order)) | |
86 mlen = len(column_order) | |
87 if len(column_order) != len(set(column_order)): | |
88 msg = "Ambiguous ordering: `column_order` contained duplicates." | |
89 raise nx.NetworkXError(msg) | |
90 | |
91 row_index = dict(zip(row_order, itertools.count())) | |
92 col_index = dict(zip(column_order, itertools.count())) | |
93 | |
94 if G.number_of_edges() == 0: | |
95 row, col, data = [], [], [] | |
96 else: | |
97 row, col, data = zip( | |
98 *( | |
99 (row_index[u], col_index[v], d.get(weight, 1)) | |
100 for u, v, d in G.edges(row_order, data=True) | |
101 if u in row_index and v in col_index | |
102 ) | |
103 ) | |
104 M = sparse.coo_matrix((data, (row, col)), shape=(nlen, mlen), dtype=dtype) | |
105 try: | |
106 return M.asformat(format) | |
107 # From Scipy 1.1.0, asformat will throw a ValueError instead of an | |
108 # AttributeError if the format if not recognized. | |
109 except (AttributeError, ValueError) as e: | |
110 raise nx.NetworkXError(f"Unknown sparse matrix format: {format}") from e | |
111 | |
112 | |
113 def from_biadjacency_matrix(A, create_using=None, edge_attribute="weight"): | |
114 r"""Creates a new bipartite graph from a biadjacency matrix given as a | |
115 SciPy sparse matrix. | |
116 | |
117 Parameters | |
118 ---------- | |
119 A: scipy sparse matrix | |
120 A biadjacency matrix representation of a graph | |
121 | |
122 create_using: NetworkX graph | |
123 Use specified graph for result. The default is Graph() | |
124 | |
125 edge_attribute: string | |
126 Name of edge attribute to store matrix numeric value. The data will | |
127 have the same type as the matrix entry (int, float, (real,imag)). | |
128 | |
129 Notes | |
130 ----- | |
131 The nodes are labeled with the attribute `bipartite` set to an integer | |
132 0 or 1 representing membership in part 0 or part 1 of the bipartite graph. | |
133 | |
134 If `create_using` is an instance of :class:`networkx.MultiGraph` or | |
135 :class:`networkx.MultiDiGraph` and the entries of `A` are of | |
136 type :class:`int`, then this function returns a multigraph (of the same | |
137 type as `create_using`) with parallel edges. In this case, `edge_attribute` | |
138 will be ignored. | |
139 | |
140 See Also | |
141 -------- | |
142 biadjacency_matrix | |
143 from_numpy_array | |
144 | |
145 References | |
146 ---------- | |
147 [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph | |
148 """ | |
149 G = nx.empty_graph(0, create_using) | |
150 n, m = A.shape | |
151 # Make sure we get even the isolated nodes of the graph. | |
152 G.add_nodes_from(range(n), bipartite=0) | |
153 G.add_nodes_from(range(n, n + m), bipartite=1) | |
154 # Create an iterable over (u, v, w) triples and for each triple, add an | |
155 # edge from u to v with weight w. | |
156 triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A)) | |
157 # If the entries in the adjacency matrix are integers and the graph is a | |
158 # multigraph, then create parallel edges, each with weight 1, for each | |
159 # entry in the adjacency matrix. Otherwise, create one edge for each | |
160 # positive entry in the adjacency matrix and set the weight of that edge to | |
161 # be the entry in the matrix. | |
162 if A.dtype.kind in ("i", "u") and G.is_multigraph(): | |
163 chain = itertools.chain.from_iterable | |
164 triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples) | |
165 G.add_weighted_edges_from(triples, weight=edge_attribute) | |
166 return G |