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(A, create_using=None, edge_attribute="weight"):
116 r"""Creates a new bipartite graph from a biadjacency matrix given as a
117 SciPy sparse array.
119 Parameters
120 ----------
121 A: scipy sparse array
122 A biadjacency matrix representation of a graph
124 create_using: NetworkX graph
125 Use specified graph for result. The default is Graph()
127 edge_attribute: string
128 Name of edge attribute to store matrix numeric value. The data will
129 have the same type as the matrix entry (int, float, (real,imag)).
131 Notes
132 -----
133 The nodes are labeled with the attribute `bipartite` set to an integer
134 0 or 1 representing membership in part 0 or part 1 of the bipartite graph.
136 If `create_using` is an instance of :class:`networkx.MultiGraph` or
137 :class:`networkx.MultiDiGraph` and the entries of `A` are of
138 type :class:`int`, then this function returns a multigraph (of the same
139 type as `create_using`) with parallel edges. In this case, `edge_attribute`
140 will be ignored.
142 See Also
143 --------
144 biadjacency_matrix
145 from_numpy_array
147 References
148 ----------
149 [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph
150 """
151 G = nx.empty_graph(0, create_using)
152 n, m = A.shape
153 # Make sure we get even the isolated nodes of the graph.
154 G.add_nodes_from(range(n), bipartite=0)
155 G.add_nodes_from(range(n, n + m), bipartite=1)
156 # Create an iterable over (u, v, w) triples and for each triple, add an
157 # edge from u to v with weight w.
158 triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A))
159 # If the entries in the adjacency matrix are integers and the graph is a
160 # multigraph, then create parallel edges, each with weight 1, for each
161 # entry in the adjacency matrix. Otherwise, create one edge for each
162 # positive entry in the adjacency matrix and set the weight of that edge to
163 # be the entry in the matrix.
164 if A.dtype.kind in ("i", "u") and G.is_multigraph():
165 chain = itertools.chain.from_iterable
166 triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples)
167 G.add_weighted_edges_from(triples, weight=edge_attribute)
168 return G