pathwithexact.py

def findPathWithExactStops(self, start, finish, exact):
        """
        Wrapper function to calculate the path with exact number of stops
        Args:
            start           (str):      Starting city
            end             (str):      Destination city
            maxDistance     (int):      exact number of stops

        Returns:
            int: number of routes
        """
        count = 0
        visited = []
        path = []

        path.append(start)
        visited.append(start)

        for adjacent_node in self.routesTable[start]:
            if adjacent_node not in visited:
                count = self.printAllPathsUtil(adjacent_node, finish, visited, path, exact, count)
        
        return count

    
    # util methods for cycle detection
    def printAllPathsUtil(self, start, finish, visited, path, exact, count):
        """
        Recursive function to calculate the number of routes within a given limit
        Args:
            start           (str):        Starting city
            end             (str):        Destination city
            visited         (str[]):      Maximum distance/limit 
            path            (str[]):      path so far
            exact           (int):        limit
            count           (int):        number of paths found so far 

        Returns:
            int: count 
        """
        visited.append(start)
        path.append(start)

        if start == finish:
            if len(path) < exact:
                count = self.findCycle(finish, path, exact, count)
            
            if len(path) == exact + 1:
                print(path)
                count = count + 1
        
        else:
            for adjacent_node in self.routesTable[start]:
                if adjacent_node not in visited:
                    count = self.printAllPathsUtil(adjacent_node, finish, visited, path, exact, count)
        
        path.pop()
        visited.remove(start)

        return count


    def findCycle(self, start, path, exact, count):
        """
        Wrapper function to detect cycle in the graph
        Args:
            start           (str):        Starting city
            end             (str):        Destination city
            path            (str[]):      path so far
            exact           (int):        limit
            count           (int):        number of paths found so far 

        Returns:
            int: count 
        """
        visited = []

        for adj_node in self.routesTable[start]:
            if adj_node not in visited:
                count = self.findCycleUtil(adj_node, start, path, visited, exact, count)
        return count
    

    def findCycleUtil(self, start, end, path, visited, exact, count):
        """
        recursive function to detect circular path in the graph
        Args:
            start           (str):        Starting city
            end             (str):        Destination city
            path            (str[]):      path so far
            visited         (str[]):      visited nodes so far 
            exact           (int):        limit
            count           (int):        number of paths found so far 

        Returns:
            int: count 
        """
        visited.append(start)
        path.append(start)

        if start == end:
            if len(path) == exact + 1:
                count = count + 1
                print(path)
        else:
            for adj_node in self.routesTable[start]:
                if adj_node not in visited:
                   count = self.findCycleUtil(adj_node, end, path, visited, exact, count)

        path.pop()
        visited.remove(start) 

        return count