Enumerating all (non-cyclical) paths between two nodes

[David Drum]

Hello everyone,

I am a new user of NetworkX, so please forgive any naive questions. I
would like to identify all non-cyclical paths between two nodes in a
graph. I assume this would be called path enumeration, but I am not
finding anything in NetworkX that would accomplish this. Is there a
function to do this? Is there an algorithm to do this for two nodes,
or all nodes? Thanks in advance for any replies.

Example:
Edges: [(1,2), (2,3), (2,4), (3,4)]
Paths (by node):
1,2
1,2,3
1,2,4,3
1,2,4
1,2,3,4
2,3
2,4,3
2,4
2,3,4
3,4
3,2,4


Regards,

David

[jordi torrents]

Hi David,

2011/5/3 David Drum <david....@gmail.com>:

> Hello everyone,
>
> I am a new user of NetworkX, so please forgive any naive questions. I
> would like to identify all non-cyclical paths between two nodes in a
> graph. I assume this would be called path enumeration, but I am not
> finding anything in NetworkX that would accomplish this. Is there a
> function to do this? Is there an algorithm to do this for two nodes,
> or all nodes? Thanks in advance for any replies.

A few weeks ago an implementation to find all distinct and
non-cyclical paths between two nodes was posted to the mailing list
[1]. But you have to take into account that, in most networks, the
number of such paths is astronomical, thus computing *all* of them may
be difficult and not very useful. An alternative approach could be
restrict the search to node independent paths (see my reply in [1] for
details if you are interested).

Salut!

[1] http://groups.google.com/group/networkx-discuss/browse_thread/thread/36d6f63f3c9f6cdf

[David Drum]

Hello everyone,

Thank you for your replies. In the end, I found an example at http://codeidol.com/python/python3/Data-Structures/Graph-Searching/ and reworked it for NetworkX. Here it is:

def enumerate_all_paths(network, origin, destination):
    '''
    enumerate all paths between an origin and a destination
    http://codeidol.com/python/python3/Data-Structures/Graph-Searching/
    '''

    paths = []
    stack = ([origin], [])
    while stack:
        front, stack = stack
        end = front[-1]
        if end == destination:
            paths.append(front)
        else:
            for successor in network.successors(end):
                if successor not in front:
                    stack = (front + [successor]), stack

    return paths

Naturally, one would have to nest this inside two loops iterating over all nodes to get all paths between all nodes:

    # calculate the paths between all OD pairs
    for origin in network.nodes():
        for destination in network.nodes():
            if origin != destination:
                paths = enumerate_all_paths(network, origin, destination)

Please use this however you see fit.

Regards,

David