Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bipartite / matrix.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```""" ``` ```==================== ``` ```Biadjacency matrices ``` ```==================== ``` ```""" ``` ```# Copyright (C) 2013-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```import itertools ``` ```from networkx.convert_matrix import _generate_weighted_edges ``` ```import networkx as nx ``` ```__author__ = """\n""".join(['Jordi Torrents ', ``` ``` 'Aric Hagberg ']) ``` ```__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): ``` ``` raise nx.NetworkXError("Unknown sparse matrix format: %s" % format) ``` ```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_matrix ``` ``` ``` ``` 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 ``` ```# fixture for nose tests ``` ```def setup_module(module): ``` ``` from nose import SkipTest ``` ``` try: ``` ``` import scipy ``` ``` except: ``` ``` raise SkipTest("SciPy not available") ```