Function to count paths of a given length in a multigraph that do not include backtracking

Question

I'm trying to write a function to count a specific type of path in a multigraph (so my graph might have multiple edges between the same two vertices). I need to count paths of a given length n, between two given vertices v, w that do not include backtracking. What I mean by the last condition is that if a particular edge has been traversed from a vertex v0 to a vertex w0, then I do not want to include that edge going from w0 to v0 at any point in the same path.

I think this should be a relatively simple modification of a DFS, but I'm having trouble figuring out how to incorporate the fixed length, the backtracking condition, and the global count.

I've tried using a recursive algorithm, but I haven't been able to get everything working simultaneously.

Answer 1

First, let's settle on a representation. We need something that can encode:

by starting node
    by ending node
        count of edges

This can stored in Python by a dictionary of dictionaries of integers that has the symmetry where multigraph[x][y] == multigraph[y][x] for all x, y. And we can skip out on the ending node if the count of integers is missing. So, for example, if a, b, c, d are the vertices, the following represents a valid multigraph.

{
    a: {b: 3, c: 2, d: 3},
    b: {a: 3, c: 2, d: 1},
    c: {a: 2, b: 2},
    d: {a: 3, b: 1},
}

In this graph, note that there are many long paths from a to a meeting the condition. That's because there are many potential loops of length 2 and 3, and once a given loop has been traversed once in a direction, it can be traversed that direction any number of times without violating the condition. So we can swap back and forth between similar loops over and over again. So the number of paths grows exponentially with the length.

Note that @ravenspoint's answer is based on Dijkstra's algorithm. Which won't find paths that revisit the same node many times. It therefore cannot handle this graph.

Let's start with a small graph and brute force. If multi is a multigraph, and v a vertex, then here is a function that lists the edges.

def edges (multi, v):
    for w, c in multi[v].items():
        for i in range(c):
            yield (w, i)

If the length of the path n is very small, it makes sense to just do a brute force enumeration of all paths. Something like this. (Your original DFS idea.)

def count_paths (multi, n, start, target, seen=None):
    if seen is None:
        seen = {}

    if n == 0:
        if start == target:
            return 1
        else:
            return 0
    else:
        answer = 0
        for v, i in edges(multi, start):
            if (v, start, i) not in seen:
                if (start, v, i) in seen:
                    seen.add((start, v, i))
                    answer += count_paths(multi, v, target, seen)
                    seen.pop((start, v, i))
                else:
                    answer += count_paths(multi, v, target, seen)
        return answer

But...what if n is large?

The outline of a better algorithm is to try each orientation of the edges. Namely fill in seen such that for every possible v, w and i that could appear in seen exactly one of (v, w, i) or (w, v, i) appears in seen. And then use dynamic programming to find all of the paths. (If you're familiar with transition matrices, you can raise the right transition matrix to the right power for large n. This approach is only likely to be appropriate for some programming competitions though.)