Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2====================
3Biadjacency matrices
4====================
5"""
7import itertools
9import networkx as nx
10from networkx.convert_matrix import _generate_weighted_edges
12__all__ = ["biadjacency_matrix", "from_biadjacency_matrix"]
15@nx._dispatchable(edge_attrs="weight")
16def biadjacency_matrix(
17 G, row_order, column_order=None, dtype=None, weight="weight", format="csr"
18):
19 r"""Returns the biadjacency matrix of the bipartite graph G.
21 Let `G = (U, V, E)` be a bipartite graph with node sets
22 `U = u_{1},...,u_{r}` and `V = v_{1},...,v_{s}`. The biadjacency
23 matrix [1]_ is the `r` x `s` matrix `B` in which `b_{i,j} = 1`
24 if, and only if, `(u_i, v_j) \in E`. If the parameter `weight` is
25 not `None` and matches the name of an edge attribute, its value is
26 used instead of 1.
28 Parameters
29 ----------
30 G : graph
31 A NetworkX graph
33 row_order : list of nodes
34 The rows of the matrix are ordered according to the list of nodes.
36 column_order : list, optional
37 The columns of the matrix are ordered according to the list of nodes.
38 If column_order is None, then the ordering of columns is arbitrary.
40 dtype : NumPy data-type, optional
41 A valid NumPy dtype used to initialize the array. If None, then the
42 NumPy default is used.
44 weight : string or None, optional (default='weight')
45 The edge data key used to provide each value in the matrix.
46 If None, then each edge has weight 1.
48 format : str in {'dense', 'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'}
49 The type of the matrix to be returned (default 'csr'). For
50 some algorithms different implementations of sparse matrices
51 can perform better. See [2]_ for details.
53 Returns
54 -------
55 M : SciPy sparse array
56 Biadjacency matrix representation of the bipartite graph G.
58 Notes
59 -----
60 No attempt is made to check that the input graph is bipartite.
62 For directed bipartite graphs only successors are considered as neighbors.
63 To obtain an adjacency matrix with ones (or weight values) for both
64 predecessors and successors you have to generate two biadjacency matrices
65 where the rows of one of them are the columns of the other, and then add
66 one to the transpose of the other.
68 See Also
69 --------
70 adjacency_matrix
71 from_biadjacency_matrix
73 References
74 ----------
75 .. [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph
76 .. [2] Scipy Dev. References, "Sparse Matrices",
77 https://docs.scipy.org/doc/scipy/reference/sparse.html
78 """
79 import scipy as sp
81 nlen = len(row_order)
82 if nlen == 0:
83 raise nx.NetworkXError("row_order is empty list")
84 if len(row_order) != len(set(row_order)):
85 msg = "Ambiguous ordering: `row_order` contained duplicates."
86 raise nx.NetworkXError(msg)
87 if column_order is None:
88 column_order = list(set(G) - set(row_order))
89 mlen = len(column_order)
90 if len(column_order) != len(set(column_order)):
91 msg = "Ambiguous ordering: `column_order` contained duplicates."
92 raise nx.NetworkXError(msg)
94 row_index = dict(zip(row_order, itertools.count()))
95 col_index = dict(zip(column_order, itertools.count()))
97 if G.number_of_edges() == 0:
98 row, col, data = [], [], []
99 else:
100 row, col, data = zip(
101 *(
102 (row_index[u], col_index[v], d.get(weight, 1))
103 for u, v, d in G.edges(row_order, data=True)
104 if u in row_index and v in col_index
105 )
106 )
107 A = sp.sparse.coo_array((data, (row, col)), shape=(nlen, mlen), dtype=dtype)
108 try:
109 return A.asformat(format)
110 except ValueError as err:
111 raise nx.NetworkXError(f"Unknown sparse array format: {format}") from err
114@nx._dispatchable(graphs=None, returns_graph=True)
115def from_biadjacency_matrix(
116 A,
117 create_using=None,
118 edge_attribute="weight",
119 *,
120 row_order=None,
121 column_order=None,
122):
123 r"""Creates a new bipartite graph from a biadjacency matrix given as a
124 SciPy sparse array.
126 Parameters
127 ----------
128 A : scipy sparse array
129 A biadjacency matrix representation of a graph
131 create_using : NetworkX graph
132 Use specified graph for result. The default is Graph()
134 edge_attribute : string
135 Name of edge attribute to store matrix numeric value. The data will
136 have the same type as the matrix entry (int, float, (real,imag)).
138 row_order : list, optional (default: range(number of rows in `A`))
139 A list of the nodes represented by the rows of the matrix `A`. Will
140 be represented in the graph as nodes with the `bipartite` attribute set
141 to 0. Must be the same length as the number of rows in `A`.
143 column_order : list, optional (default: range(number of columns in `A`))
144 A list of the nodes represented by the columns of the matrix `A`. Will
145 be represented in the graph as nodes with the `bipartite` attribute set
146 to 1. Must be the same length as the number of columns in `A`.
148 Returns
149 -------
150 G : NetworkX graph
151 A bipartite graph with edges from the biadjacency matrix `A`, and
152 nodes from `row_order` and `column_order`.
154 Raises
155 ------
156 ValueError
157 If `row_order` or `column_order` are provided and are not the same
158 length as the number of rows or columns in `A`, respectively.
160 Notes
161 -----
162 The nodes are labeled with the attribute `bipartite` set to an integer
163 0 or 1 representing membership in the `top` set (`bipartite=0`) or `bottom`
164 set (`bipartite=1`) of the bipartite graph.
166 If `create_using` is an instance of :class:`networkx.MultiGraph` or
167 :class:`networkx.MultiDiGraph` and the entries of `A` are of
168 type :class:`int`, then this function returns a multigraph (of the same
169 type as `create_using`) with parallel edges. In this case, `edge_attribute`
170 will be ignored.
172 See Also
173 --------
174 biadjacency_matrix
175 from_numpy_array
177 References
178 ----------
179 [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph
180 """
181 G = nx.empty_graph(0, create_using)
182 n, m = A.shape
183 # Check/set row_order and column_order to have correct length and default values
184 row_order, column_order = _validate_initialize_bipartite_nodelists(
185 A, row_order, column_order
186 )
188 # Make sure we get even the isolated nodes of the graph.
189 G.add_nodes_from(range(n), bipartite=0)
190 G.add_nodes_from(range(n, n + m), bipartite=1)
191 # Create an iterable over (u, v, w) triples and for each triple, add an
192 # edge from u to v with weight w.
193 triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A))
194 # If the entries in the adjacency matrix are integers and the graph is a
195 # multigraph, then create parallel edges, each with weight 1, for each
196 # entry in the adjacency matrix. Otherwise, create one edge for each
197 # positive entry in the adjacency matrix and set the weight of that edge to
198 # be the entry in the matrix.
199 if A.dtype.kind in ("i", "u") and G.is_multigraph():
200 chain = itertools.chain.from_iterable
201 triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples)
202 G.add_weighted_edges_from(triples, weight=edge_attribute)
204 # If the user provided nodelists, relabel the nodes of the graph inplace
205 mapping = dict(
206 itertools.chain(zip(range(n), row_order), zip(range(n, n + m), column_order))
207 )
208 if len(mapping):
209 nx.relabel_nodes(G, mapping, copy=False)
210 return G
213def _validate_initialize_bipartite_nodelists(A, row_order, column_order):
214 n, m = A.shape
215 # Validate nodelists if provided
216 if row_order is not None:
217 if len(row_order) != n:
218 raise ValueError(
219 "Length of row_order does not match number of rows in A ({n})"
220 )
221 else:
222 row_order = []
224 if column_order is not None:
225 if len(column_order) != m:
226 raise ValueError(
227 "Length of column_order does not match number of columns in A ({m})"
228 )
229 else:
230 column_order = []
232 return row_order, column_order