diff 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
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/bipartite/matrix.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,166 @@
+"""
+====================
+Biadjacency matrices
+====================
+"""
+import itertools
+from networkx.convert_matrix import _generate_weighted_edges
+import networkx as nx
+
+__all__ = ["biadjacency_matrix", "from_biadjacency_matrix"]
+
+
+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 matrix
+        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
+    """
+    from scipy import sparse
+
+    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
+            )
+        )
+    M = sparse.coo_matrix((data, (row, col)), shape=(nlen, mlen), dtype=dtype)
+    try:
+        return M.asformat(format)
+    # From Scipy 1.1.0, asformat will throw a ValueError instead of an
+    # AttributeError if the format if not recognized.
+    except (AttributeError, ValueError) as e:
+        raise nx.NetworkXError(f"Unknown sparse matrix format: {format}") from e
+
+
+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 matrix.
+
+    Parameters
+    ----------
+    A: scipy sparse matrix
+      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
+    # Make sure we get even the isolated nodes of the graph.
+    G.add_nodes_from(range(n), bipartite=0)
+    G.add_nodes_from(range(n, n + m), bipartite=1)
+    # Create an iterable over (u, v, w) triples and for each triple, add an
+    # edge from u to v with weight w.
+    triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A))
+    # If the entries in the adjacency matrix are integers and the graph is a
+    # multigraph, then create parallel edges, each with weight 1, for each
+    # entry in the adjacency matrix. Otherwise, create one edge for each
+    # positive entry in the adjacency matrix and set the weight of that edge to
+    # be the entry in the matrix.
+    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