gistfile1.txt

#Graph G
#1 2
#2 4 3 5 6
#4 10
#
#u = 1
#v = 10

import random


graph = """
1 2
2 4 3 5 6
4 10
"""

class Node(object):

    def __init__(self, name):
        self.name = name
        self.children = set()

    def __repr__(self):
        return '<Node {name}>'.format(name=self.name)

    def random_child(self):
        return random.choice(list(self.children))

    def walk(self, depth):
        if depth > 0:
            random_child = self.random_child()
            return [self] + random_child.walk(depth - 1)
        else:
            return []


def parse_graph(graph):
    nodes = {}

    for line in graph.splitlines():
        node_names = line.split(' ')

        for node_name in node_names:
            if node_name not in nodes:
                nodes[node_name] = Node(node_name)

        line_nodes = [nodes[name] for name in node_names]

        parent = line_nodes[0]
        children = line_nodes[1:]

        parent.children = parent.children.union(children)

        for child in children:
            child.children = child.children.union(set([parent]))

    return nodes


def compute_probability(nodes, start, end, num_walks):
    start_node = nodes[start]

    hits = 0
    for walk_i in range(num_walks):
        walk = start_node.walk(10)
        if walk[-1].name == end:
            hits += 1

    return (hits, num_walks)