Find the paths between two given nodes?

Question

Say that I have nodes connected below, how can I get the number of paths existing between given points, and path data?

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 paths 1 to 7:

Answer: 2 ways were found, and they

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

found implementation here , I will use the same

Here is a 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

A width search in the first place bypasses the graph and actually finds all the paths from the starting node. However, BFS does not support all paths. Instead, it updates the π predecessor function to preserve the shortest path. You can easily change the algorithm so that π(n) not only saves one predecessor, but also a list of possible predecessors.

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

One good pseudo-code that uses this notation can be found in the Introduction to Algorithms by Cormen et al. and was subsequently used in many university scenarios on this subject. A Google search for the “predecessor of the BFS π pseudorange” disables this hit on Stack Exchange .

Answer 2

For those who are not PYTHON experts, 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 3

Dijkstra's algorithm is used more for weighted paths, and it looks like the poster wanted to find all the paths, not just the shortest ones.

For this application, I would build a graph (your application will look like it will not need to be directed) and use your favorite search method. It seems like you want all the paths and not just guess the shortest, so use a simple recursive algorithm of your choice.

The only problem with this is that the schedule can be cyclical.

At connections:

• 12
• 13
• 2, 3
• 2, 4

When searching for a path from 1-> 4 you can have a cycle 1 → 2 → 3 → 1.

In this case, I would save the stack by moving nodes. Here is a list with steps for this graph and the final stack (sorry for formatting - there is no table option):

current node (the following nodes are possible minus where we came from) [stack]

• 1 (2, 3) [1]
• 2 (3, 4) [1, 2]
• 3 (1) [1, 2, 3]
• 1 (2, 3) [1, 2, 3, 1] // error - duplicate number in the detected stack loop
• 3 () [1, 2, 3] // stepped over node three and pulled 1 from the stack. There are no more nodes here.
• 2 (4) [1, 2] // back to node 2 and pulled 1 from the stack.
• 4 () [1, 2, 4] // Target node found - stack record for the path. There are no more nodes here.
• 2 () [1, 2] // back to node 2 and pulled 4 from the stack. There are no more nodes here.
• 1 (3) [1] // back to node 1 and popped 2 from the stack.
• 3 (2) [1, 3]
• 2 (1, 4) [1, 3, 2]
• 1 (2, 3) [1, 3, 2, 1] // error - duplicate number in the detected stack
• 2 (4) [1, 3, 2] // back to node 2 and jumped 1 from the stack
• 4 () [1, 3, 2, 4] Target node found - stack record for the path. There are no more nodes here.
• 2 () [1, 3, 2] // back to node 2 and pulled 4 from the stack. More nodes
• 3 () [1, 3] // back to node 3 and pops 2 from the stack. More nodes
• 1 () [1] // stepped back to node 1 and pulled 3 from the stack. More nodes
• Done with two recorded tracks [1, 2, 4] and [1, 3, 2, 4]

Answer 4

The original code is a bit cumbersome, and you might want to use collection.deque instead if you want to use BFS to determine if there is a path between two points on the graph. Here is a quick solution that I hacked:

Note. This method can continue indefinitely if there is no path between the two nodes. I have not 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 5

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(SI, 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 6

taking into account 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 solves the problem to find all the simple paths between two nodes of a graph. I used simple recursion and two global var to track loops and save the desired result. The code has not been optimized for clarity only. "print" should help figure out how this 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}

: {{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 can’t upload images to better show the results :(

http://textanddatamining.blogspot.com

Answer 7

If you need all the paths, use recursion.

Using the adjacency list, preferably create a function f () that tries to populate the current list of visited vertices. For example:

 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, therefore, any changes made later in the recursive procedure are not constant), all possible combinations are listed.

You can get a bit of efficiency by passing the previous vector by reference (and therefore, you don't need to copy the vector over and over), but you will need to make sure that all things get popped_back () manually.

One more thing: if the chart has cycles, it will not work. (I assume that in this case you will want to find all the simple paths, then). Before adding something to the previous vector, first check to see if it is already there.

If you need all the shortest paths, use the Konrad clause with this algorithm.

Answer 8

What you are trying to do is find the path between the two vertices in the graph (directional?) To check Dijkstra's algorithm if you need the shortest path or write a simple recursive function if you need any paths.