"""Bipartite.py

Two-color graphs and find related structures.
<NAME>, May 2004.
"""

import unittest
from sets import Set
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 dict([(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 dict([(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()

"""Bipartite.py

Two-color graphs and find related structures.
<NAME>, May 2004.
"""

import unittest
from sets import Set
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 dict([(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 dict([(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()

Bipartite.py  Two-color graphs and find related structures. <NAME>, May 2004. Find a bipartition of G, if one exists.     Raises NonBipartite or returns dict mapping vertices     to two colors (True and False). Find a bipartition of G, if one exists.     Raises NonBipartite or returns sequence of vertices     on one side of the bipartition. Return True if G is bipartite, False otherwise. 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. Subgraph of vertices and edges that participate in odd cycles.     Aka, the union of nonbipartite biconnected components. # If run as "python Bipartite.py", run tests on various small graphs # and check that the correct results are obtained.