"""
==========================
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)
|