graphs.py

#!/usr/bin/env python
# vim: set ts=4 sw=4 et foldmethod=indent:
#
import random
from itertools import chain
import sys

_DEBUG = 0


def load_graph_from_stream(stream):
    # Load in dict d all nodes and its connections
    d = {}
    for l in [line.strip() for line in stream]:
        node, l_nodes = [_.strip() for _ in l.split('->')]
        d[node] = []
        for n in l_nodes.split(','):
            d[node].append(n)

    # The AM is a hash of hashes
    # We trade complexity and time cost for space cost
    am = {}
    nodes = d.keys()
    for from_node in nodes:
        am[from_node] = {}
        for to_node in nodes:
            if to_node in d[from_node]:
                am[from_node][to_node] = 1

    return am


def debug(g, d_unused, cycle, trav_cycle=None, rnd_cycle=None):
    sys.stderr.write("(%s %s %s)\n" % (len(cycle), len(edges(g)), len(d_unused)))
    if _DEBUG:
        print "CYCLE: " + str(trav_cycle)
        if trav_cycle:
            print "TRAV: " + str(trav_cycle)
        if rnd_cycle:
            print "RND: " + str(rnd_cycle)
            print "NEW CYCLE: " + str(trav_cycle + rnd_cycle)
        print "UNUSED: " + str(d_unused.keys())


def eulerian_cycle(g, debug=-1):
    d_unused = {}
    cycle = random_walk(g)
    update_unused(d_unused, cycle, g)
    while len(cycle) < len(edges(g)):
        un = select_unexplored_node_from_edges(g, cycle)
        cycle = form_new_cycle(un, g, cycle, d_unused)
        update_unused(d_unused, cycle, g)
    return cycle


def update_unused(d_unused, edge_cycle, g):
    for e in edge_cycle:
        node = e[0]
        if node not in d_unused:
            d_unused[node] = len(connections(g, node))
        d_unused[node] -= 1

    for node in [n for n in d_unused.keys() if not d_unused[n]]:
        del d_unused[node]


def form_new_cycle(start, g, cycle, d_unused):
    trav_cycle = traverse_cycle(start, g, cycle) 
    rnd_cycle = random_walk(g, trav_cycle[-1][1], trav_cycle)
    debug(g, d_unused, cycle, trav_cycle, rnd_cycle)
    return trav_cycle + rnd_cycle


def traverse_cycle(start_node, g, cycle):
    first_edge = [e for e in cycle if e[0] == start_node]
    if len(first_edge) == 0:
        return cycle

    first_idx = cycle.index(first_edge[0])

    new_cycle = []
    prev_edge = None
    for edge in cycle[first_idx:] + cycle[0:first_idx]:
        if prev_edge and prev_edge[1] != edge[0]:
            break
        new_cycle.append(edge)
        prev_edge = edge
    return new_cycle
        

def edges(g):
    e = set([])
    for _from in nodes(g):
        for _to in connections(g, _from):
            e.add((_from, _to))
    return list(e)


def select_unexplored_node_from_edges(g, cycle):
    nodes = [e[0] for e in cycle]
    for node in nodes:
        for cn in connections(g, node):
            if cn not in nodes:
                return node
    return None


def new_edge(g, _from=None):
    edge = [_from, None] if _from else [pick_random_node(g), None]
    edge[1] = pick_random_node(g, start=edge[0])
    return tuple(edge)


def random_walk(g, start_node=None, visited_edges=[]):
    new_edges = []
    edge = new_edge(g, start_node)
    while True:
        if edge in visited_edges or edge in new_edges:
            break
        new_edges.append(edge)
        edge = new_edge(g, edge[1])

    return new_edges


def pick_random_node(g, start=None):
    l_nodes = g[start].keys() if start else nodes(g)
    return l_nodes[random.randrange(0, len(l_nodes))]


def nodes(g):
    return g.keys()


def connected(g, n_from, n_to):
    return g[n_from][n_to] == 1


def connections(g, n):
    return g[n].keys()


def print_graph(g):
    for n in nodes(g):
        print n, connections(g, n)


def pretty_cycle(edge_cycle):
    o = "%s->%s" % edge_cycle[0]
    for e in edge_cycle[1:]:
        o += "->%s" % e[1]
    return o


if __name__ == "__main__":
    stream = open('/tmp/foo.txt')
    g = load_graph_from_stream(stream)

    """
    truth = [ (6, 8),(8, 7),(7, 9), (9, 6), (6, 5), (5, 4), (4, 2), (2, 1), (1, 0), \
              (0,3), (3, 2), (2,6) ]
    truth = [(str(e[0]), str(e[1])) for e in truth]

    for i in range(100):
        print "-->>> START"
        ec = eulerian_cycle(g, debug=-1)
        assert (len(ec) == len(truth))
        prev = None
        for e in ec:
            if prev:
                if prev[1] != e[0]:
                    print ">> Failed! :" + str(ec)
                    print ">> Failed! :" + pretty_cycle(ec)
                    sys.exit(1)
            assert(e in truth)
            prev = e
        # print pretty_cycle(ec)

        #print truth
        #print ec
        #print "T: ", pretty_cycle(truth)

    """

    #"""
    g = load_graph_from_stream(sys.stdin)
    ec = eulerian_cycle(g, debug=10)
    print pretty_cycle(ec)
    #"""