In [80]:

    

edges = [("v1", "v2"), ("v3", "v4"), ("v2", "v3"),  ("v4", "v1")]

class Node:
    def __init__(self, value):
        self.value = value
        self.neighbours = set()
    def __str__(self):
        return "Node: {0}".format(self.value)
    def __repr__(self):
        return "Node: {0}".format(self.value)

def graphify(L):
    d = dict()
    for left, right in L:
        if left not in d:
            d[left] = Node(left)
        if right not in d:
            d[right] = Node(right)
        d[left].neighbours.add(d[right])
        d[right].neighbours.add(d[left])
    return d.values()

def is_bipartite(G):
    nodes = graphify(G)
    stack = []
    stack.append(nodes[0])
    L, R = set(), set()
    L.add(nodes[0])
    
    while len(stack) != 0:
        node = stack.pop()
        for n in node.neighbours:
            if n not in L and n not in R:
                if node in L:
                    R.add(n)
                else:
                    L.add(n)
                stack.append(n)
            if n in L and node in L:
                return False
            if n in R and node in R:
                return False
    return True


    

In [81]:

    

nodes = graphify(edges)
for node in nodes:
    print node, node.neighbours


    

    




Node: v1 set([Node: v4, Node: v2])
Node: v2 set([Node: v1, Node: v3])
Node: v3 set([Node: v4, Node: v2])
Node: v4 set([Node: v1, Node: v3])

In [82]:

    

print is_bipartite(edges)


    

    




True

In [83]:

    

edges2 = [("v1", "v2"), ("v2", "v3"), ("v3", "v1")]
print is_bipartite(edges2)


    

    




False

In [84]:

    

print is_bipartite([("v1", "v2")])


    

    




True

In [89]:

    

print is_bipartite([("v1", "v2"), ("v2", "v1"), ("v2", "v3"), ("v1", "v3")])


    

    




False

In [ ]: