Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (7.85 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
==========================
4
Bipartite Graph Algorithms
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 networkx as nx
14
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
15
                            'Aric Hagberg <aric.hagberg@gmail.com>'])
16
__all__ = ['is_bipartite',
17
           'is_bipartite_node_set',
18
           'color',
19
           'sets',
20
           'density',
21
           'degrees']
22

    
23

    
24
def color(G):
25
    """Returns a two-coloring of the graph.
26

27
    Raises an exception if the graph is not bipartite.
28

29
    Parameters
30
    ----------
31
    G : NetworkX graph
32

33
    Returns
34
    -------
35
    color : dictionary
36
       A dictionary keyed by node with a 1 or 0 as data for each node color.
37

38
    Raises
39
    ------
40
    exc:`NetworkXError` if the graph is not two-colorable.
41

42
    Examples
43
    --------
44
    >>> from networkx.algorithms import bipartite
45
    >>> G = nx.path_graph(4)
46
    >>> c = bipartite.color(G)
47
    >>> print(c)
48
    {0: 1, 1: 0, 2: 1, 3: 0}
49

50
    You can use this to set a node attribute indicating the biparite set:
51

52
    >>> nx.set_node_attributes(G, c, 'bipartite')
53
    >>> print(G.nodes[0]['bipartite'])
54
    1
55
    >>> print(G.nodes[1]['bipartite'])
56
    0
57
    """
58
    if G.is_directed():
59
        import itertools
60

    
61
        def neighbors(v):
62
            return itertools.chain.from_iterable([G.predecessors(v),
63
                                                  G.successors(v)])
64
    else:
65
        neighbors = G.neighbors
66

    
67
    color = {}
68
    for n in G:  # handle disconnected graphs
69
        if n in color or len(G[n]) == 0:  # skip isolates
70
            continue
71
        queue = [n]
72
        color[n] = 1  # nodes seen with color (1 or 0)
73
        while queue:
74
            v = queue.pop()
75
            c = 1 - color[v]  # opposite color of node v
76
            for w in neighbors(v):
77
                if w in color:
78
                    if color[w] == color[v]:
79
                        raise nx.NetworkXError("Graph is not bipartite.")
80
                else:
81
                    color[w] = c
82
                    queue.append(w)
83
    # color isolates with 0
84
    color.update(dict.fromkeys(nx.isolates(G), 0))
85
    return color
86

    
87

    
88
def is_bipartite(G):
89
    """ Returns True if graph G is bipartite, False if not.
90

91
    Parameters
92
    ----------
93
    G : NetworkX graph
94

95
    Examples
96
    --------
97
    >>> from networkx.algorithms import bipartite
98
    >>> G = nx.path_graph(4)
99
    >>> print(bipartite.is_bipartite(G))
100
    True
101

102
    See Also
103
    --------
104
    color, is_bipartite_node_set
105
    """
106
    try:
107
        color(G)
108
        return True
109
    except nx.NetworkXError:
110
        return False
111

    
112

    
113
def is_bipartite_node_set(G, nodes):
114
    """Returns True if nodes and G/nodes are a bipartition of G.
115

116
    Parameters
117
    ----------
118
    G : NetworkX graph
119

120
    nodes: list or container
121
      Check if nodes are a one of a bipartite set.
122

123
    Examples
124
    --------
125
    >>> from networkx.algorithms import bipartite
126
    >>> G = nx.path_graph(4)
127
    >>> X = set([1,3])
128
    >>> bipartite.is_bipartite_node_set(G,X)
129
    True
130

131
    Notes
132
    -----
133
    For connected graphs the bipartite sets are unique.  This function handles
134
    disconnected graphs.
135
    """
136
    S = set(nodes)
137
    for CC in nx.connected_component_subgraphs(G):
138
        X, Y = sets(CC)
139
        if not ((X.issubset(S) and Y.isdisjoint(S)) or
140
                (Y.issubset(S) and X.isdisjoint(S))):
141
            return False
142
    return True
143

    
144

    
145
def sets(G, top_nodes=None):
146
    """Returns bipartite node sets of graph G.
147

148
    Raises an exception if the graph is not bipartite or if the input
149
    graph is disconnected and thus more than one valid solution exists.
150
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
151
    for further details on how bipartite graphs are handled in NetworkX.
152

153
    Parameters
154
    ----------
155
    G : NetworkX graph
156

157
    top_nodes : container
158

159
      Container with all nodes in one bipartite node set. If not supplied
160
      it will be computed. But if more than one solution exists an exception
161
      will be raised.
162

163
    Returns
164
    -------
165
    (X,Y) : two-tuple of sets
166
       One set of nodes for each part of the bipartite graph.
167

168
    Raises
169
    ------
170
    AmbiguousSolution : Exception
171

172
      Raised if the input bipartite graph is disconnected and no container
173
      with all nodes in one bipartite set is provided. When determining
174
      the nodes in each bipartite set more than one valid solution is
175
      possible if the input graph is disconnected.
176

177
    NetworkXError: Exception
178

179
      Raised if the input graph is not bipartite.
180

181
    Examples
182
    --------
183
    >>> from networkx.algorithms import bipartite
184
    >>> G = nx.path_graph(4)
185
    >>> X, Y = bipartite.sets(G)
186
    >>> list(X)
187
    [0, 2]
188
    >>> list(Y)
189
    [1, 3]
190

191
    See Also
192
    --------
193
    color
194

195
    """
196
    if G.is_directed():
197
        is_connected = nx.is_weakly_connected
198
    else:
199
        is_connected = nx.is_connected
200
    if top_nodes is not None:
201
        X = set(top_nodes)
202
        Y = set(G) - X
203
    else:
204
        if not is_connected(G):
205
            msg = 'Disconnected graph: Ambiguous solution for bipartite sets.'
206
            raise nx.AmbiguousSolution(msg)
207
        c = color(G)
208
        X = {n for n, is_top in c.items() if is_top}
209
        Y = {n for n, is_top in c.items() if not is_top}
210
    return (X, Y)
211

    
212

    
213
def density(B, nodes):
214
    """Returns density of bipartite graph B.
215

216
    Parameters
217
    ----------
218
    G : NetworkX graph
219

220
    nodes: list or container
221
      Nodes in one node set of the bipartite graph.
222

223
    Returns
224
    -------
225
    d : float
226
       The bipartite density
227

228
    Examples
229
    --------
230
    >>> from networkx.algorithms import bipartite
231
    >>> G = nx.complete_bipartite_graph(3,2)
232
    >>> X=set([0,1,2])
233
    >>> bipartite.density(G,X)
234
    1.0
235
    >>> Y=set([3,4])
236
    >>> bipartite.density(G,Y)
237
    1.0
238

239
    Notes
240
    -----
241
    The container of nodes passed as argument must contain all nodes
242
    in one of the two bipartite node sets to avoid ambiguity in the
243
    case of disconnected graphs.
244
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
245
    for further details on how bipartite graphs are handled in NetworkX.
246

247
    See Also
248
    --------
249
    color
250
    """
251
    n = len(B)
252
    m = nx.number_of_edges(B)
253
    nb = len(nodes)
254
    nt = n - nb
255
    if m == 0:  # includes cases n==0 and n==1
256
        d = 0.0
257
    else:
258
        if B.is_directed():
259
            d = m / (2.0 * float(nb * nt))
260
        else:
261
            d = m / float(nb * nt)
262
    return d
263

    
264

    
265
def degrees(B, nodes, weight=None):
266
    """Returns the degrees of the two node sets in the bipartite graph B.
267

268
    Parameters
269
    ----------
270
    G : NetworkX graph
271

272
    nodes: list or container
273
      Nodes in one node set of the bipartite graph.
274

275
    weight : string or None, optional (default=None)
276
       The edge attribute that holds the numerical value used as a weight.
277
       If None, then each edge has weight 1.
278
       The degree is the sum of the edge weights adjacent to the node.
279

280
    Returns
281
    -------
282
    (degX,degY) : tuple of dictionaries
283
       The degrees of the two bipartite sets as dictionaries keyed by node.
284

285
    Examples
286
    --------
287
    >>> from networkx.algorithms import bipartite
288
    >>> G = nx.complete_bipartite_graph(3,2)
289
    >>> Y=set([3,4])
290
    >>> degX,degY=bipartite.degrees(G,Y)
291
    >>> dict(degX)
292
    {0: 2, 1: 2, 2: 2}
293

294
    Notes
295
    -----
296
    The container of nodes passed as argument must contain all nodes
297
    in one of the two bipartite node sets to avoid ambiguity in the
298
    case of disconnected graphs.
299
    See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
300
    for further details on how bipartite graphs are handled in NetworkX.
301

302
    See Also
303
    --------
304
    color, density
305
    """
306
    bottom = set(nodes)
307
    top = set(B) - bottom
308
    return (B.degree(top, weight), B.degree(bottom, weight))