@@ -0,0 +1,2532 @@
+# This is PADS, a library of Python Algorithms and Data Structures%0A# implemented by David Eppstein of the University of California, Irvine.%0A#%0A# The current version of PADS may be found at%0A# %3Chttp://www.ics.uci.edu/~eppstein/PADS/%3E, as individual files or as a%0A# git repository that may be copied by the command line%0A#%0A# 02/24/14 Modified by Wei Zhang%0A%0A##############################%0A# DFS%0A##############################%0A# Types of edges in DFS traversal.%0A# The numerical values are used in DepthFirstSearcher, change with care.%0Aforward = 1     # traversing edge (v,w) from v to w%0Areverse = -1    # returning backwards on (v,w) from w to v%0Anontree = 0     # edge (v,w) is not part of the DFS tree%0A%0Aclass NonBipartite(Exception):%0A    pass%0A%0Adef DFS_search(G):%0A    %22%22%22%0A    Generate sequence of triples (v,w,edgetype) for DFS of graph G.%0A    The subsequence for each root of each tree in the DFS forest starts%0A    with (root,root,forward) and ends with (root,root,reverse).%0A    If the initial vertex is given, it is used as the root and vertices%0A    not reachable from it are not searched.%0A    %22%22%22%0A    visited = set()%0A    initials = G%0A%0A    for v in initials:%0A        if v not in visited:%0A            yield v,v,forward%0A            visited.add(v)%0A            stack = %5B(v, iter(G%5Bv%5D))%5D%0A            while stack:%0A                parent,children = stack%5B-1%5D%0A                try:%0A                    child = children.__next__()%0A                    if child in visited:%0A                        yield parent,child,nontree%0A                    else:%0A                        yield parent,child,forward%0A                        visited.add(child)%0A                        stack.append((child,iter(G%5Bchild%5D)))%0A                except StopIteration:%0A                    stack.pop()%0A                    if stack:%0A                        yield stack%5B-1%5D%5B0%5D,parent,reverse%0A%0A            yield v,v,reverse%0A%0A##############################%0A# Bipartite%0A##############################%0Adef TwoColor(G):%0A    %22%22%22%0A    Find a bipartition of G, if one exists.%0A    Raises NonBipartite or returns dict mapping vertices%0A    to two colors (True and False).%0A    %22%22%22%0A    color = %7B%7D%0A    for v,w,edgetype in DFS_search(G):%0A        if edgetype is forward:%0A            color%5Bw%5D = not color.get(v,False)%0A        elif edgetype is nontree and color%5Bv%5D == color%5Bw%5D:%0A            raise NonBipartite%0A    return color%0A%0Adef create_cycle_graph(n):%0A    return %7Bi:%5B(i-1)%25n,(i+1)%25n%5D for i in range(n)%7D%0A%0Adef main():%0A%09graph = create_cycle_graph(4)%0A%09color = TwoColor(graph)%0A%09print(color)%0A%0Amain()%0A

Add benchmark pads-bipartite