Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.58 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
====================
4
Biadjacency matrices
5
====================
6
"""
7
#    Copyright (C) 2013-2019 by
8
#    Aric Hagberg <hagberg@lanl.gov>
9
#    Dan Schult <dschult@colgate.edu>
10
#    Pieter Swart <swart@lanl.gov>
11
#    All rights reserved.
12
#    BSD license.
13
import itertools
14
from networkx.convert_matrix import _generate_weighted_edges
15
import networkx as nx
16
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
17
                            'Aric Hagberg <aric.hagberg@gmail.com>'])
18
__all__ = ['biadjacency_matrix', 'from_biadjacency_matrix']
19

    
20

    
21
def biadjacency_matrix(G, row_order, column_order=None,
22
                       dtype=None, weight='weight',  format='csr'):
23
    r"""Returns the biadjacency matrix of the bipartite graph G.
24

25
    Let `G = (U, V, E)` be a bipartite graph with node sets
26
    `U = u_{1},...,u_{r}` and `V = v_{1},...,v_{s}`. The biadjacency
27
    matrix [1]_ is the `r` x `s` matrix `B` in which `b_{i,j} = 1`
28
    if, and only if, `(u_i, v_j) \in E`. If the parameter `weight` is
29
    not `None` and matches the name of an edge attribute, its value is
30
    used instead of 1.
31

32
    Parameters
33
    ----------
34
    G : graph
35
       A NetworkX graph
36

37
    row_order : list of nodes
38
       The rows of the matrix are ordered according to the list of nodes.
39

40
    column_order : list, optional
41
       The columns of the matrix are ordered according to the list of nodes.
42
       If column_order is None, then the ordering of columns is arbitrary.
43

44
    dtype : NumPy data-type, optional
45
        A valid NumPy dtype used to initialize the array. If None, then the
46
        NumPy default is used.
47

48
    weight : string or None, optional (default='weight')
49
       The edge data key used to provide each value in the matrix.
50
       If None, then each edge has weight 1.
51

52
    format : str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'}
53
        The type of the matrix to be returned (default 'csr').  For
54
        some algorithms different implementations of sparse matrices
55
        can perform better.  See [2]_ for details.
56

57
    Returns
58
    -------
59
    M : SciPy sparse matrix
60
        Biadjacency matrix representation of the bipartite graph G.
61

62
    Notes
63
    -----
64
    No attempt is made to check that the input graph is bipartite.
65

66
    For directed bipartite graphs only successors are considered as neighbors.
67
    To obtain an adjacency matrix with ones (or weight values) for both
68
    predecessors and successors you have to generate two biadjacency matrices
69
    where the rows of one of them are the columns of the other, and then add
70
    one to the transpose of the other.
71

72
    See Also
73
    --------
74
    adjacency_matrix
75
    from_biadjacency_matrix
76

77
    References
78
    ----------
79
    .. [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph
80
    .. [2] Scipy Dev. References, "Sparse Matrices",
81
       https://docs.scipy.org/doc/scipy/reference/sparse.html
82
    """
83
    from scipy import sparse
84
    nlen = len(row_order)
85
    if nlen == 0:
86
        raise nx.NetworkXError("row_order is empty list")
87
    if len(row_order) != len(set(row_order)):
88
        msg = "Ambiguous ordering: `row_order` contained duplicates."
89
        raise nx.NetworkXError(msg)
90
    if column_order is None:
91
        column_order = list(set(G) - set(row_order))
92
    mlen = len(column_order)
93
    if len(column_order) != len(set(column_order)):
94
        msg = "Ambiguous ordering: `column_order` contained duplicates."
95
        raise nx.NetworkXError(msg)
96

    
97
    row_index = dict(zip(row_order, itertools.count()))
98
    col_index = dict(zip(column_order, itertools.count()))
99

    
100
    if G.number_of_edges() == 0:
101
        row, col, data = [], [], []
102
    else:
103
        row, col, data = zip(*((row_index[u], col_index[v], d.get(weight, 1))
104
                               for u, v, d in G.edges(row_order, data=True)
105
                               if u in row_index and v in col_index))
106
    M = sparse.coo_matrix((data, (row, col)),
107
                          shape=(nlen, mlen), dtype=dtype)
108
    try:
109
        return M.asformat(format)
110
    # From Scipy 1.1.0, asformat will throw a ValueError instead of an
111
    # AttributeError if the format if not recognized.
112
    except (AttributeError, ValueError):
113
        raise nx.NetworkXError("Unknown sparse matrix format: %s" % format)
114

    
115

    
116
def from_biadjacency_matrix(A, create_using=None, edge_attribute='weight'):
117
    r"""Creates a new bipartite graph from a biadjacency matrix given as a
118
    SciPy sparse matrix.
119

120
    Parameters
121
    ----------
122
    A: scipy sparse matrix
123
      A biadjacency matrix representation of a graph
124

125
    create_using: NetworkX graph
126
       Use specified graph for result.  The default is Graph()
127

128
    edge_attribute: string
129
       Name of edge attribute to store matrix numeric value. The data will
130
       have the same type as the matrix entry (int, float, (real,imag)).
131

132
    Notes
133
    -----
134
    The nodes are labeled with the attribute `bipartite` set to an integer
135
    0 or 1 representing membership in part 0 or part 1 of the bipartite graph.
136

137
    If `create_using` is an instance of :class:`networkx.MultiGraph` or
138
    :class:`networkx.MultiDiGraph` and the entries of `A` are of
139
    type :class:`int`, then this function returns a multigraph (of the same
140
    type as `create_using`) with parallel edges. In this case, `edge_attribute`
141
    will be ignored.
142

143
    See Also
144
    --------
145
    biadjacency_matrix
146
    from_numpy_matrix
147

148
    References
149
    ----------
150
    [1] https://en.wikipedia.org/wiki/Adjacency_matrix#Adjacency_matrix_of_a_bipartite_graph
151
    """
152
    G = nx.empty_graph(0, create_using)
153
    n, m = A.shape
154
    # Make sure we get even the isolated nodes of the graph.
155
    G.add_nodes_from(range(n), bipartite=0)
156
    G.add_nodes_from(range(n, n + m), bipartite=1)
157
    # Create an iterable over (u, v, w) triples and for each triple, add an
158
    # edge from u to v with weight w.
159
    triples = ((u, n + v, d) for (u, v, d) in _generate_weighted_edges(A))
160
    # If the entries in the adjacency matrix are integers and the graph is a
161
    # multigraph, then create parallel edges, each with weight 1, for each
162
    # entry in the adjacency matrix. Otherwise, create one edge for each
163
    # positive entry in the adjacency matrix and set the weight of that edge to
164
    # be the entry in the matrix.
165
    if A.dtype.kind in ('i', 'u') and G.is_multigraph():
166
        chain = itertools.chain.from_iterable
167
        triples = chain(((u, v, 1) for d in range(w)) for (u, v, w) in triples)
168
    G.add_weighted_edges_from(triples, weight=edge_attribute)
169
    return G
170

    
171
# fixture for nose tests
172

    
173

    
174
def setup_module(module):
175
    from nose import SkipTest
176
    try:
177
        import scipy
178
    except:
179
        raise SkipTest("SciPy not available")