Find the paths between two given nodes?

Question

Say I have nodes connected in the below fashion, how do I arrive at the number of paths that exist between given points, and path details?

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

Find the paths from 1 to 7:

Answer: 2 paths found and they are

1,2,3,6,7
1,2,5,6,7

implementation found here is nice I am going to use the same

Here is the snippet from the above link in python

# a sample graph
graph = {'A': ['B', 'C','E'],
             'B': ['A','C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F','D'],
             'F': ['C']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = []
            else:
                self.holder = self.holder[1:]   
        except:
            pass

        return val  

    def IsEmpty(self):
        result = False
        if len(self.holder) == 0:
            result = True
        return result


path_queue = MyQUEUE() # now we make a queue


def BFS(graph,start,end,q):

    temp_path = [start]

    q.enqueue(temp_path)

    while q.IsEmpty() == False:
        tmp_path = q.dequeue()
        last_node = tmp_path[len(tmp_path)-1]
        print tmp_path
        if last_node == end:
            print "VALID_PATH : ",tmp_path
        for link_node in graph[last_node]:
            if link_node not in tmp_path:
                #new_path = []
                new_path = tmp_path + [link_node]
                q.enqueue(new_path)

BFS(graph,"A","D",path_queue)

-------------results-------------------
['A']
['A', 'B']
['A', 'C']
['A', 'E']
['A', 'B', 'C']
['A', 'B', 'D']
VALID_PATH :  ['A', 'B', 'D']
['A', 'C', 'D']
VALID_PATH :  ['A', 'C', 'D']
['A', 'E', 'F']
['A', 'E', 'D']
VALID_PATH :  ['A', 'E', 'D']
['A', 'B', 'C', 'D']
VALID_PATH :  ['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C']
['A', 'E', 'F', 'C', 'D']
VALID_PATH :  ['A', 'E', 'F', 'C', 'D']

Answer 1

Breadth-first search traverses a graph and in fact finds all paths from a starting node. Usually, BFS doesn't keep all paths, however. Instead, it updates a prededecessor function π to save the shortest path. You can easily modify the algorithm so that π(n) doesn't only store one predecessor but a list of possible predecessors.

Then all possible paths are encoded in this function, and by traversing π recursively you get all possible path combinations.

One good pseudocode which uses this notation can be found in Introduction to Algorithms by Cormen et al. and has subsequently been used in many University scripts on the subject. A Google search for “BFS pseudocode predecessor π” uproots this hit on Stack Exchange.

Answer 2

In Prolog (specifically, SWI-Prolog)

:- use_module(library(tabling)).

% path(+Graph,?Source,?Target,?Path)
:- table path/4.

path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
    dif(S,T),
    member(S-I, G), % directed graph
    path(G,I,T,Path).

test:

paths :- Graph =
    [ 1- 2  % node 1 and 2 are connected
    , 2- 3 
    , 2- 5 
    , 4- 2 
    , 5-11
    ,11-12
    , 6- 7 
    , 5- 6 
    , 3- 6 
    , 6- 8 
    , 8-10
    , 8- 9
    ],
    findall(Path, path(Graph,1,7,Path), Paths),
    maplist(writeln, Paths).

?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.

Answer 3

given the adjacency matrix:

{0, 1, 3, 4, 0, 0}

{0, 0, 2, 1, 2, 0}

{0, 1, 0, 3, 0, 0}

{0, 1, 1, 0, 0, 1}

{0, 0, 0, 0, 0, 6}

{0, 1, 0, 1, 0, 0}

the following Wolfram Mathematica code solve the problem to find all the simple paths between two nodes of a graph. I used simple recursion, and two global var to keep track of cycles and to store the desired output. the code hasn't been optimized just for the sake of code clarity. the "print" should be helpful to clarify how it works.

cycleQ[l_]:=If[Length[DeleteDuplicates[l]] == Length[l], False, True];
getNode[matrix_, node_]:=Complement[Range[Length[matrix]],Flatten[Position[matrix[[node]], 0]]];

builtTree[node_, matrix_]:=Block[{nodes, posAndNodes, root, pos},
    If[{node} != {} && node != endNode ,
        root = node;
        nodes = getNode[matrix, node];
        (*Print["root:",root,"---nodes:",nodes];*)

        AppendTo[lcycle, Flatten[{root, nodes}]];
        If[cycleQ[lcycle] == True,
            lcycle = Most[lcycle]; appendToTree[root, nodes];,
            Print["paths: ", tree, "\n", "root:", root, "---nodes:",nodes];
            appendToTree[root, nodes];

        ];
    ];

appendToTree[root_, nodes_] := Block[{pos, toAdd},
    pos = Flatten[Position[tree[[All, -1]], root]];
    For[i = 1, i <= Length[pos], i++,
        toAdd = Flatten[Thread[{tree[[pos[[i]]]], {#}}]] & /@ nodes;
        (* check cycles!*)            
        If[cycleQ[#] != True, AppendTo[tree, #]] & /@ toAdd;
    ];
    tree = Delete[tree, {#} & /@ pos];
    builtTree[#, matrix] & /@ Union[tree[[All, -1]]];
    ];
];

to call the code: initNode = 1; endNode = 6; lcycle = {}; tree = {{initNode}}; builtTree[initNode, matrix];

paths: {{1}} root:1---nodes:{2,3,4}

paths: {{1,2},{1,3},{1,4}} root:2---nodes:{3,4,5}

paths: {{1,3},{1,4},{1,2,3},{1,2,4},{1,2,5}} root:3---nodes:{2,4}

paths: {{1,4},{1,2,4},{1,2,5},{1,3,4},{1,2,3,4},{1,3,2,4},{1,3,2,5}} root:4---nodes:{2,3,6}

paths: {{1,2,5},{1,3,2,5},{1,4,6},{1,2,4,6},{1,3,4,6},{1,2,3,4,6},{1,3,2,4,6},{1,4,2,5},{1,3,4,2,5},{1,4,3,2,5}} root:5---nodes:{6}

RESULTS:{{1, 4, 6}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 3, 2, 4, 6}, {1, 3, 2, 5, 6}, {1, 4, 2, 5, 6}, {1, 3, 4, 2, 5, 6}, {1, 4, 3, 2, 5, 6}}

...Unfortunately I cannot upload images to show the results in a better way :(

http://textanddatamining.blogspot.com

Answer 4

For those who are not PYTHON expert ,the same code in C++

//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
    cout<<"[ ";
    for(int i=0;i<path.size();++i)
    {
        cout<<path[i]<<" ";
    }
    cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
    for(int i=0;i<path.size();++i)
    {
        if(path[i]==node)
        return false;
    }
    return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
    vector<int>path;
    path.push_back(source);
    queue<vector<int> >q;
    q.push(path);

    while(!q.empty())
    {
        path=q.front();
        q.pop();

        int last_nodeof_path=path[path.size()-1];
        if(last_nodeof_path==target)
        {
            cout<<"The Required path is:: ";
            print_path(path);
        }
        else
        {
            print_path(path);
        }

        for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
        {
            if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
            {

                vector<int>new_path(path.begin(),path.end());
                new_path.push_back(GRAPH[last_nodeof_path][i]);
                q.push(new_path);
            }
        }




    }
    return 1;
}
int main()
{
    //freopen("out.txt","w",stdout);
    int T,N,M,u,v,source,target;
    scanf("%d",&T);
    while(T--)
    {
        printf("Enter Total Nodes & Total Edges\n");
        scanf("%d%d",&N,&M);
        for(int i=1;i<=M;++i)
        {
            scanf("%d%d",&u,&v);
            GRAPH[u].push_back(v);
        }
        printf("(Source, target)\n");
        scanf("%d%d",&source,&target);
        findpaths(source,target,N,M);
    }
    //system("pause");
    return 0;
}

/*
Input::
1
6 11
1 2 
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4

output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]


*/

Answer 5

The original code is a bit cumbersome and you might want to use the collections.deque instead if you want to use BFS to find if a path exists between 2 points on the graph. Here is a quick solution I hacked up:

Note: this method might continue infinitely if there exists no path between the two nodes. I haven't tested all cases, YMMV.

from collections import deque

# a sample graph
  graph = {'A': ['B', 'C','E'],
           'B': ['A','C', 'D'],
           'C': ['D'],
           'D': ['C'],
           'E': ['F','D'],
           'F': ['C']}

   def BFS(start, end):
    """ Method to determine if a pair of vertices are connected using BFS

    Args:
      start, end: vertices for the traversal.

    Returns:
      [start, v1, v2, ... end]
    """
    path = []
    q = deque()
    q.append(start)
    while len(q):
      tmp_vertex = q.popleft()
      if tmp_vertex not in path:
        path.append(tmp_vertex)

      if tmp_vertex == end:
        return path

      for vertex in graph[tmp_vertex]:
        if vertex not in path:
          q.append(vertex)

Answer 6

Dijkstra's algorithm applies more to weighted paths and it sounds like the poster was wanting to find all paths, not just the shortest.

For this application, I'd build a graph (your application sounds like it wouldn't need to be directed) and use your favorite search method. It sounds like you want all paths, not just a guess at the shortest one, so use a simple recursive algorithm of your choice.

The only problem with this is if the graph can be cyclic.

With the connections:

• 1, 2
• 1, 3
• 2, 3
• 2, 4

While looking for a path from 1->4, you could have a cycle of 1 -> 2 -> 3 -> 1.

In that case, then I'd keep a stack as traversing the nodes. Here's a list with the steps for that graph and the resulting stack (sorry for the formatting - no table option):

current node (possible next nodes minus where we came from) [stack]

1. 1 (2, 3) [1]
2. 2 (3, 4) [1, 2]
3. 3 (1) [1, 2, 3]
4. 1 (2, 3) [1, 2, 3, 1] //error - duplicate number on the stack - cycle detected
5. 3 () [1, 2, 3] // back-stepped to node three and popped 1 off the stack. No more nodes to explore from here
6. 2 (4) [1, 2] // back-stepped to node 2 and popped 1 off the stack.
7. 4 () [1, 2, 4] // Target node found - record stack for a path. No more nodes to explore from here
8. 2 () [1, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes to explore from here
9. 1 (3) [1] //back-stepped to node 1 and popped 2 off the stack.
10. 3 (2) [1, 3]
11. 2 (1, 4) [1, 3, 2]
12. 1 (2, 3) [1, 3, 2, 1] //error - duplicate number on the stack - cycle detected
13. 2 (4) [1, 3, 2] //back-stepped to node 2 and popped 1 off the stack
14. 4 () [1, 3, 2, 4] Target node found - record stack for a path. No more nodes to explore from here
15. 2 () [1, 3, 2] //back-stepped to node 2 and popped 4 off the stack. No more nodes
16. 3 () [1, 3] // back-stepped to node 3 and popped 2 off the stack. No more nodes
17. 1 () [1] // back-stepped to node 1 and popped 3 off the stack. No more nodes
18. Done with 2 recorded paths of [1, 2, 4] and [1, 3, 2, 4]

Answer 7

If you want all the paths, use recursion.

Using an adjacency list, preferably, create a function f() that attempts to fill in a current list of visited vertices. Like so:

void allPaths(vector<int> previous, int current, int destination)
{
    previous.push_back(current);

    if (current == destination)
        //output all elements of previous, and return

    for (int i = 0; i < neighbors[current].size(); i++)
        allPaths(previous, neighbors[current][i], destination);
}

int main()
{
    //...input
    allPaths(vector<int>(), start, end);
}

Due to the fact that the vector is passed by value (and thus any changes made further down in the recursive procedure aren't permanent), all possible combinations are enumerated.

You can gain a bit of efficiency by passing the previous vector by reference (and thus not needing to copy the vector over and over again) but you'll have to make sure that things get popped_back() manually.

One more thing: if the graph has cycles, this won't work. (I assume in this case you'll want to find all simple paths, then) Before adding something into the previous vector, first check if it's already in there.

If you want all shortest paths, use Konrad's suggestion with this algorithm.

Answer 8

What you're trying to do is essentially to find a path between two vertices in a (directed?) graph check out Dijkstra's algorithm if you need shortest path or write a simple recursive function if you need whatever paths exist.