1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
"""
==========================
Bipartite Graph Algorithms
==========================
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
# Copyright (C) 2008 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
__all__=['project','is_bipartite','bipartite_color','bipartite_sets']
import networkx as nx
def project(B,nodes,create_using=None):
"""Return the projection of the graph onto a subset of nodes.
The nodes retain their names and are connected in the resulting
graph if have an edge to a common node in the original graph.
Parameters
----------
B : NetworkX graph
The input graph should be bipartite.
nodes : list or iterable
Nodes to project onto.
Returns
-------
Graph : NetworkX graph
A graph that is the projection onto the given nodes.
Examples
--------
>>> B=nx.path_graph(4)
>>> G=nx.project(B,[1,3])
>>> print G.nodes()
[1, 3]
>>> print G.edges()
[(1, 3)]
Notes
------
Returns a graph that is the projection of the bipartite graph B
onto the set of nodes given in list nodes.
No attempt is made to verify that the input graph B is bipartite.
See Also
--------
is_bipartite(), bipartite_sets()
"""
if create_using==None:
create_using=nx.Graph()
G=nx.empty_graph(0,create_using)
for v in nodes:
G.add_node(v)
for nbr in B[v]:
G.add_edges_from([(v,u) for u in B[nbr] if u!=v])
return G
def bipartite_color(G):
"""Returns a two-coloring of the graph.
Raises an exception if the graph is not bipartite.
Parameters
----------
G : NetworkX graph
Returns
-------
color : dictionary
A dictionary keyed by node with a 1 or 0 as data for each node color.
Examples
--------
>>> G=nx.path_graph(4)
>>> c=nx.bipartite_color(G)
>>> print c
{0: 1, 1: 0, 2: 1, 3: 0}
"""
color={}
for n in G: # handle disconnected graphs
if n in color: continue
queue=[n]
color[n]=1 # nodes seen with color (1 or 0)
while queue:
v=queue.pop()
c=1-color[v] # opposite color of node v
for w in G[v]:
if w in color:
if color[w]==color[v]:
raise nx.NetworkXError("Graph is not bipartite.")
else:
color[w]=c
queue.append(w)
return color
def is_bipartite(G):
""" Returns True if graph G is bipartite, False if not.
Parameters
----------
G : NetworkX graph
Examples
--------
>>> G=nx.path_graph(4)
>>> print nx.is_bipartite(G)
True
See Also
--------
bipartite_color()
"""
try:
bipartite_color(G)
return True
except:
return False
def bipartite_sets(G):
"""Returns bipartite node sets of graph G.
Raises an exception if the graph is not bipartite.
Parameters
----------
G : NetworkX graph
Returns
-------
(X,Y) : two-tuple of sets
One set of nodes for each part of the bipartite graph.
Examples
--------
>>> G=nx.path_graph(4)
>>> X,Y=nx.bipartite_sets(G)
>>> print X
set([0, 2])
>>> print Y
set([1, 3])
See Also
--------
bipartite_color()
"""
color=bipartite_color(G)
X=set(n for n in color if color[n]==1)
Y=set(n for n in color if color[n]==0)
return (X,Y)
|
