How to Count all possible paths between two vertices in Python

In this tutorial, we will learn how to count all possible paths between two vertices in Python with some cool and easy examples. In many situations, you might have to come up with this type of requirement.

I know you are here just because you are in need of this awesome trick to count all possible paths between two vertices in Python by using the backtracking method.

If you don’t know how to use the backtracking method then you are at the right place. Because in this tutorial we gonna find out how to use the backtracking method in Python.
Study this for backtracking:
How to implement Depth First Search algorithm in Python

count all possible paths

Let’s learn this with some easy examples,
At first, write a function for adding edge:

def addEdge(self, a, b):
    self.adjacent[a].append(b)

Now let’s write the code:

class Code:
    def __init__(self, Vertices):
        self.Vertices = Vertices
        self.adjacent = [[] for i in range(Vertices)]
    def addEdge(self, a, b):
        self.adjacent[a].append(b)
    def countWays(self, x, y):
        visited = [False] * self.Vertices
        count = [0]
        self.countWaysUtil(x,y, visited, count)
        return count[0]
    def countWaysUtil(self, a, y,
                       visited, count):
        visited[a] = True
        if (a == y):
            count[0] += 1
        else:
            i = 0
            while i < len(self.adjacent[a]):
                if (not visited[self.adjacent[a][i]]):
                    self.countWaysUtil(self.adjacent[a][i], y,
                                        visited, count)
                i += 1
        visited[a] = False
if __name__ == '__main__':
    g = Code(4)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(0, 3)
    g.addEdge(2, 0)
    g.addEdge(1, 2)
    g.addEdge(2, 3)
    x = 0
    y = 3
    print(g.countWays(x, y))

Output:

3

Here in the above code, we have used the backtracking method. We have used four methods. One method is for adding edges, one is for initializing vertices and the other two are to find all possible ways.

The example we have used here has four vertices and six edges.
0, 1, 2, 3 and 0 -> 1, 0 -> 2, 0 -> 3, 2 -> 0, 1 -> 2, 2 -> 3.