"""Bipartite.py
Two-color graphs and find related structures.
D. Eppstein, May 2004.
"""
import unittest
from Biconnectivity import BiconnectedComponents
import Graphs
import DFS
class NonBipartite(Exception):
pass
def TwoColor(G):
"""
Find a bipartition of G, if one exists.
Raises NonBipartite or returns dict mapping vertices
to two colors (True and False).
"""
color = {}
for v,w,edgetype in DFS.search(G):
if edgetype is DFS.forward:
color[w] = not color.get(v,False)
elif edgetype is DFS.nontree and color[v] == color[w]:
raise NonBipartite
return color
def Bipartition(G):
"""
Find a bipartition of G, if one exists.
Raises NonBipartite or returns sequence of vertices
on one side of the bipartition.
"""
color = TwoColor(G)
for v in color:
if color[v]:
yield v
def isBipartite(G):
"""
Return True if G is bipartite, False otherwise.
"""
try:
TwoColor(G)
return True
except NonBipartite:
return False
def BipartiteOrientation(G,adjacency_list_type=set):
"""
Given an undirected bipartite graph G, return a directed graph in which
the edges are oriented from one side of the bipartition to the other.
The second argument has the same meaning as in Graphs.copyGraph.
"""
B = Bipartition(G)
return {v:adjacency_list_type(iter(G[v])) for v in B}
def OddCore(G):
"""
Subgraph of vertices and edges that participate in odd cycles.
Aka, the union of nonbipartite biconnected components.
"""
return Graphs.union(*[C for C in BiconnectedComponents(G)
if not isBipartite(C)])
# If run as "python Bipartite.py", run tests on various small graphs
# and check that the correct results are obtained.
class BipartitenessTest(unittest.TestCase):
def cycle(self,n):
return {i:[(i-1)%n,(i+1)%n] for i in range(n)}
def testEvenCycles(self):
for i in range(4,12,2):
self.assertEqual(isBipartite(self.cycle(i)), True)
def testOddCycles(self):
for i in range(3,12,2):
self.assertEqual(isBipartite(self.cycle(i)), False)
if __name__ == "__main__":
unittest.main()