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