python list path-finding undirected-graph

List of all possible path of edges between two nodes, showing edges multiplicity

I'm working on a algorithm that models a electric grid as a Undirected Multigraph so I can analyse the faults on the grid using python.

I have the functions that get me all the minimum paths (paths that do not loop) between two nodes and need to get the edges accounting for their multiplicity.

Say I have the source "LAG-138", and the load "SCA-24", my program finds a path:

["SCA-24", "SCA-69", "SCO-69", "PAA-69", "OCA-T4-69", "OCA-138", "LVR-138", "LAG-138"]

And many others, but for the sake of simplicity, here's one.

From this output, I can get all the edges between two nodes, and their multiplicity like this:

['SCA-24 <-> SCA-69 (1)', 'SCA-24 <-> SCA-69 (2)']
['SCO-69 <-> SCA-69 (1)']
['SCO-69 <-> PAA-69 (1)']
['PAA-69 <-> OCA-T4-69 (1)', 'PAA-69 <-> OCA-T4-69 (2)']
['OCA-T4-69 <-> OCA-138 (1)']
['OCA-138 <-> LVR-138 (1)']
['LVR-138 <-> LAG-138 (1)', 'LVR-138 <-> LAG-138 (2)']

I get this output from every pair of nodes in the sequence of the path. For every pair, I get all the edges between them.

Now, how can I get these outputs and get all the paths?

The output I need from this would be like this:

[
    ['SCA-24 <-> SCA-69 (1)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (1)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (1)'],
    ['SCA-24 <-> SCA-69 (1)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (1)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (2)'],
    ['SCA-24 <-> SCA-69 (1)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (2)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (1)'],
    ['SCA-24 <-> SCA-69 (1)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (2)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (2)'],
    ['SCA-24 <-> SCA-69 (2)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (1)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (1)'],
    ['SCA-24 <-> SCA-69 (2)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (1)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (2)'],
    ['SCA-24 <-> SCA-69 (2)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (2)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (1)'],
    ['SCA-24 <-> SCA-69 (2)', 'SCO-69 <-> SCA-69 (1)', 'SCO-69 <-> PAA-69 (1)', 'PAA-69 <-> OCA-T4-69 (2)', 'OCA-T4-69 <-> OCA-138 (1)', 'LVR-138 <-> LAG-138 (2)'],
]

A list of all the paths, arrenged among the edges. It's probably a simple problem, but right now I can't think of anything Please Help.

Solution

It sounds like you want itertools.product.

for path in itertools.product(a, b, c, d, ....):
    print(path)

will give you every possibility, taking one from a, one from b, etc.

If, as I suspect, you actually have a list, say paths_list where paths_list[0] are the paths from the first node to the second, path_lists[1] are the paths from the second node to the third, etc., then

for path in itertools.product(*paths_list):
    ...

Both of these return an iterator. If you just want the whole list, then

list(itertools.product(*paths_list))