Bipartite.py

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