Find all paths between two vertices (nodes) in a graph using Python

Question

I have the following Python code, and it works perfect with the directed graph. My question is how to modify the code in such way to find all the paths with ignoring the directions of the edges.

For example, if we have the following connections:

1->2

3->2

My code will not return a path between 1 and 3, which is expected as it is directed. But with ignoring the directions of edges the code should find a path from 1 to 3.

I want the code to ignore the direction and finds all the paths between the two given nodes.

I tried the proposed solution and it works really nice, the solution is: "The simplest solution might be to pre-process your graph by adding the arc B->A for every A->B that's in the graph."

What I really wanted is to modify the algorithm itself to deal with the graph as is.

Python Code:

# 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)

-------------Output of the Code-------------------

['A', 'B', 'D'] 
['A', 'C', 'D']
['A', 'E', 'D']
['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C', 'D']

Note: I taged Java, in case someone has a solution to the same problem in Java

this is more of an algorithm based question did you search on google? — Bhavik Shah, Dec 14 '12 at 17:21
Yes, I was looking for any algorithm that would solve the problem. I found tons of them, I wasn't able to find one that works with undirected graphs to find ALL paths between two nodes. For example: All shortest paths, BFS, DFS, etc. they all work with directed edges as the one here in the question. — user1899713, Dec 14 '12 at 19:52
why not use the already available solutions like `networkx` and `igraph` or you just want to use your code? — namit, Dec 15 '12 at 05:11
@Namit Kewat, honestly I didn't try networkx or igraph as while my search I couldn't find any clue for algorithm in their documentation to find all paths in undirected graphs. — user1899713, Dec 15 '12 at 05:39
check this post for the solution; it is using both `igraph` and `networkx` modules: http://stackoverflow.com/questions/2606018/python-path-between-two-nodes — namit, Dec 15 '12 at 05:44

score 3 · Accepted Answer · answered Dec 14 '12 at 17:22

3

The simplest solution might be to pre-process your graph by adding the arc B->A for every A->B that's in the graph. Then you should be able to use your algorithm as-is.

answered Dec 14 '12 at 17:22

NPE

486,780
108
951
1,012

I tried your approach and it works fine. But what I really wanted is to modify the algorithm itself for this task. I'm new to the graph theories but searching for a solution to this problem gave me the chance to learn about different graph algorithms. – user1899713 Dec 14 '12 at 20:26

stuhlo · Answer 2 · 2012-12-16T11:37:59.753

Each algorithm works with specific data structure and with definite graph that this data structure is representing. Also specific data structures are good choice for representing specific types of graphs.

E.g. if you have(as you have) adjacency list which represents directed graph and you want your algorithm use it as data structure which represents undirected graph you can do it but it would be very ineffective, just because find out if there exists edge between node 'A' and node 'B' means determine if 'B' is located in row representing adjacent nodes for 'A', as well as if 'A' is located in row representing adjacent nodes for 'B'. Therefore if you want to identify all nodes that are adjacent to node 'A' using just data structure you have without some pre-processing it takes time for searching complete adjacency list.

That is in your case replace line for link_node in graph[last_node]: by some more complicated expression which goes through whole adjacency list.

EDIT: Another idea came to my mind you can also "pre-process" your graph on-the-fly. I mean whenever your algorithm comes to edge 'A' -> 'B' it adds edge 'B' -> 'A' to your graph as well. One disadvantage is you need additional data structure which holds information if some edge have already been added, on the contrary you have to add only interesting edges.

Find all paths between two vertices (nodes) in a graph using Python

2 Answers2