Efficiently creating and storing all "valid" edge combinations of all sizes from a set of edges

Question

I think this is a fairly difficult question. So thank you ahead of time for any help.

I have a graph I am traversing, creating different paths, one at a time. I have a set of edges I "must" use, each is stored as a tuple of (to, from). I am avoiding repeat nodes, so we only go to each "to" once, and to each "from" once. I also don't want to create a cycle in the combination.

I want to create all combinations (where order matters) of edges. To be specific, I want all combinations of all valid sizes of tuples.

Some examples for clarity:

Valid combinations of edges:

((5,7))
((3,9),(9,11),(21,18))
((1,2),(2,3),(3,4),(4,5))

Invalid combinations:
((9,8),(9,6))
((2,5),(11,3),(8,5))
((1,2),(2,3),(3,4),(4,1))

So, one thing we can see, is that to make all combinations, we will make combinations of size 1, then of size 2, then of 3, ... 4....n

Don't worry, it's not quite this insane. The amount of edges I am creating combinations with is typically not that many. But it is variable, and who knows, maybe I could end up creating some combinations of size n.

So, I was thinking about using itertools to generate the combinations. I could put itertools combinations in a loop, and increment the size of the combinations of each pass.

But then I realized, that it is likely that the majority of combinations will actually end up invalid, and if I use itertools I don't think I can check their validity until the entire combination has been generated. This seems incredibly inefficient.

So, my thinking then went to using an adjacency list, where any edge (to, from) I want to force is stored in indices [to][from]. This allows me to iterate the adjacency list such that I avoid getting duplicate "to"s or duplicate "froms".

However, I still can't conceptualize how I can actually write a function that generates all of the combinations I want through traversal of the adjacency list.

Any Ideas?

Note: For now, I don't mind if anyone chooses to ignore the challenge of avoiding closed cycles, ie: 1,2,3,4,1

Answer 1

The following is a recursive generator function. It preprocesses the edges list into an adjacency dict. It will produce all paths of length l:

from collections import defaultdict

# preprocess for better performance
edges = [(1,2),(2,1),(2,3),(3,4),(4,5),(5,7), (3,9),(9,11),(11,18)]
graph = defaultdict(set)
for f, t in edges:
    graph[f].add(t)

def paths(graph, l, fr=None, avoid=None):
    avoid = avoid or set()  # avoid previous nodes
    if l == 0:  # base case: empty path
        yield ()
    from_nodes = [fr] if fr else graph.keys()
    for f in from_nodes:
        new_avoid = avoid | set([f])  # set union
        for t in graph[f]:  # for every adjacent node t...
            if t not in avoid:  # unless it has been seen
                # take all paths starting at t with length l-1
                for path in paths(graph, l-1, fr=t, avoid=new_avoid):
                    # and prepend the current edge
                    yield ((f, t),) + path 

>>> list(paths(graph, 2))
[((1, 2), (2, 3)),
 ((2, 3), (3, 9)),  # no cycle: ((1, 2), (2, 1))
 ((2, 3), (3, 4)),
 ((3, 9), (9, 11)),
 ((3, 4), (4, 5)),
 ((4, 5), (5, 7)),
 ((9, 11), (11, 18))]

>>> list(paths(graph, 3))
[((1, 2), (2, 3), (3, 9)),
 ((1, 2), (2, 3), (3, 4)),
 ((2, 3), (3, 9), (9, 11)),
 ((2, 3), (3, 4), (4, 5)),
 ((3, 9), (9, 11), (11, 18)),
 ((3, 4), (4, 5), (5, 7))]