# factor a graph G on A x B into
# a lists L and list of pairs G2 on int x int
# such that (a,b) in G iff (i,j) in G2 where L[i], L[j] == a,b
#
#  got that?
#
# The basic idea is that if the elements of G are (say)
# large strings and G is dense, then it saves space to
# marshal G to a file as a sequence of indices, rather
# than storing G directly.
#
# for greater space efficiency the list of pairs is spit
# into two lists (leftmembers, rightmembers)

def factor(G):
    from kjbuckets import kjSet, kjGraph
    allnodes = kjSet(G.keys()) + kjSet(G.values())
    allnodelist = allnodes.items()
    allnodemap = map(None, allnodelist, range(len(allnodelist)))
    nodetoindex = kjGraph(allnodemap)
    pairs = G.items()
    left = pairs[:]
    right = left[:]
    for i in xrange(len(left)):
        (l, r) = pairs[i]
        left[i], right[i] = nodetoindex[l], nodetoindex[r]
    return (left, right), allnodelist

# and back again

def unfactor(indexpairs, allnodelist):
    from kjbuckets import kjGraph
    from time import time
    now = time()
    (left, right) = indexpairs
    size = len(left)
    result = kjGraph(size)
    for i in xrange(size):
        result[allnodelist[left[i]]] = allnodelist[right[i]]
    #print time() - now
    return result

def test():
    from kjbuckets import kjGraph
    G = kjGraph( map(None, "pumpernickle", "nicklepumppp") )
    print G
    (iG, l) = factor(G)
    print iG, l
    G2 = unfactor(iG, l)
    print G2
    if G!=G2: print "OOPS"

if __name__=="__main__": test()