Trains @ Königsberg

It is clear that we could reduce this into a multigraph as follows:

We want to ask, How many walks are there from the red node to the blue node that does not repeat edges?

Suppose $\text{ways(bridges, node, target)}$ is the number of ways one can reach the target from the current node using the bridges currently available. Then, at this point, we could use one of the bridges accessible to us right now and try to reach the target from that node.

$\text{ways(bridges, node, target)} = \sum_{i \in bridges[node]} \text{ways(bridges} \backslash \left \{i \right \},\text{ node adjacent to i, target)}$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def ways(edgelist, node, target):
    if node == target:
        return 1
    total = 0
    for e in edgelist:
        if node in e:
            copylist = [i for i in edgelist]
            copylist.remove(e)
            total += ways(copylist, sum(e)-node, target) #sum(e)-node just picks the adjacent node
    return total

Now, we can run this with:

1
2

edgelist = [(1, 2), (1, 2), (2, 3), (2, 3), (1, 4), (2, 4), (3, 4)]
print(dptrack(edgelist, 1, 3))

For a small number of bridges, this problem can be solved easily with recursion. As the number grows, we might need to resort to dynamic programming or memoization techniques.