|
|
""" |
|
|
==================== |
|
|
Biadjacency matrices |
|
|
==================== |
|
|
""" |
|
|
import itertools |
|
|
|
|
|
import networkx as nx |
|
|
from networkx.convert_matrix import _generate_weighted_edges |
|
|
|
|
|
__all__ = ["biadjacency_matrix", "from_biadjacency_matrix"] |
|
|
|
|
|
|
|
|
@nx._dispatchable(edge_attrs="weight") |
|
|
def biadjacency_matrix( |
|
|
G, row_order, column_order=None, dtype=None, weight="weight", format="csr" |
|
|
): |
|
|
r"""Returns the biadjacency matrix of the bipartite graph G. |
|
|
|
|
|
Let `G = (U, V, E)` be a bipartite graph with node sets |
|
|
`U = u_{1},...,u_{r}` and `V = v_{1},...,v_{s}`. The biadjacency |
|
|
matrix [1]_ is the `r` x `s` matrix `B` in which `b_{i,j} = 1` |
|
|
if, and only if, `(u_i, v_j) \in E`. If the parameter `weight` is |
|
|
not `None` and matches the name of an edge attribute, its value is |
|
|
used instead of 1. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : graph |
|
|
A NetworkX graph |
|
|
|
|
|
row_order : list of nodes |
|
|
The rows of the matrix are ordered according to the list of nodes. |
|
|
|
|
|
column_order : list, optional |
|
|
The columns of the matrix are ordered according to the list of nodes. |
|
|
If column_order is None, then the ordering of columns is arbitrary. |
|
|
|
|
|
dtype : NumPy data-type, optional |
|
|
A valid NumPy dtype used to initialize the array. If None, then the |
|
|
NumPy default is used. |
|
|
|
|
|
weight : string or None, optional (default='weight') |
|
|
The edge data key used to provide each value in the matrix. |
|
|
If None, then each edge has weight 1. |
|
|
|
|
|
format : str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'} |
|
|
The type of the matrix to be returned (default 'csr'). For |
|
|
some algorithms different implementations of sparse matrices |
|
|
can perform better. See [2]_ for details. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
M : SciPy sparse array |
|
|
Biadjacency matrix representation of the bipartite graph G. |
|
|
|
|
|
Notes |
|
|
----- |
|
|
No attempt is made to check that the input graph is bipartite. |
|
|
|
|
|
For directed bipartite graphs only successors are considered as neighbors. |
|
|
To obtain an adjacency matrix with ones (or weight values) for both |
|
|
predecessors and successors you have to generate two biadjacency matrices |
|
|
where the rows of one of them are the columns of the other, and then add |
|
|
one to the transpose of the other. |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
adjacency_matrix |
|
|
from_biadjacency_matrix |
|
|
|
|
|
References |
|
|
---------- |
|
|
.. [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph |
|
|
.. [2] Scipy Dev. References, "Sparse Matrices", |
|
|
https://docs.scipy.org/doc/scipy/reference/sparse.html |
|
|
""" |
|
|
import scipy as sp |
|
|
|
|
|
nlen = len(row_order) |
|
|
if nlen == 0: |
|
|
raise nx.NetworkXError("row_order is empty list") |
|
|
if len(row_order) != len(set(row_order)): |
|
|
msg = "Ambiguous ordering: `row_order` contained duplicates." |
|
|
raise nx.NetworkXError(msg) |
|
|
if column_order is None: |
|
|
column_order = list(set(G) - set(row_order)) |
|
|
mlen = len(column_order) |
|
|
if len(column_order) != len(set(column_order)): |
|
|
msg = "Ambiguous ordering: `column_order` contained duplicates." |
|
|
raise nx.NetworkXError(msg) |
|
|
|
|
|
row_index = dict(zip(row_order, itertools.count())) |
|
|
col_index = dict(zip(column_order, itertools.count())) |
|
|
|
|
|
if G.number_of_edges() == 0: |
|
|
row, col, data = [], [], [] |
|
|
else: |
|
|
row, col, data = zip( |
|
|
*( |
|
|
(row_index[u], col_index[v], d.get(weight, 1)) |
|
|
for u, v, d in G.edges(row_order, data=True) |
|
|
if u in row_index and v in col_index |
|
|
) |
|
|
) |
|
|
A = sp.sparse.coo_array((data, (row, col)), shape=(nlen, mlen), dtype=dtype) |
|
|
try: |
|
|
return A.asformat(format) |
|
|
except ValueError as err: |
|
|
raise nx.NetworkXError(f"Unknown sparse array format: {format}") from err |
|
|
|
|
|
|
|
|
@nx._dispatchable(graphs=None, returns_graph=True) |
|
|
def from_biadjacency_matrix(A, create_using=None, edge_attribute="weight"): |
|
|
r"""Creates a new bipartite graph from a biadjacency matrix given as a |
|
|
SciPy sparse array. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
A: scipy sparse array |
|
|
A biadjacency matrix representation of a graph |
|
|
|
|
|
create_using: NetworkX graph |
|
|
Use specified graph for result. The default is Graph() |
|
|
|
|
|
edge_attribute: string |
|
|
Name of edge attribute to store matrix numeric value. The data will |
|
|
have the same type as the matrix entry (int, float, (real,imag)). |
|
|
|
|
|
Notes |
|
|
----- |
|
|
The nodes are labeled with the attribute `bipartite` set to an integer |
|
|
0 or 1 representing membership in part 0 or part 1 of the bipartite graph. |
|
|
|
|
|
If `create_using` is an instance of :class:`networkx.MultiGraph` or |
|
|
:class:`networkx.MultiDiGraph` and the entries of `A` are of |
|
|
type :class:`int`, then this function returns a multigraph (of the same |
|
|
type as `create_using`) with parallel edges. In this case, `edge_attribute` |
|
|
will be ignored. |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
biadjacency_matrix |
|
|
from_numpy_array |
|
|
|
|
|
References |
|
|
---------- |
|
|
[1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph |
|
|
""" |
|
|
G = nx.empty_graph(0, create_using) |
|
|
n, m = A.shape |
|
|
|
|
|
G.add_nodes_from(range(n), bipartite=0) |
|
|
G.add_nodes_from(range(n, n + m), bipartite=1) |
|
|
|
|
|
|
|
|
triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A)) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
if A.dtype.kind in ("i", "u") and G.is_multigraph(): |
|
|
chain = itertools.chain.from_iterable |
|
|
triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples) |
|
|
G.add_weighted_edges_from(triples, weight=edge_attribute) |
|
|
return G |
|
|
|
