CODEWITHSUNDEEP
pythonlistfunctionrecursiongraph
user14385051
user14385051

Reputation:

How to store results of recursive function instead of printing

The code below prints Hamilton paths in a graph (Hamiltonian Path is a path that visits each vertex of graph exactly once). since output of function printAllHamiltonianPaths(g, start, visited, path, N) is nontype, I cannot store it. I want to store the output of function as a list and then use it in other place. I am not sure what changes should be done in function.

Here is the code:

class Graph:
 
    # Constructor
    def __init__(self, edges, N):
 
        # A List of Lists to represent an adjacency list
        self.adjList = [[] for _ in range(N)]
 
        # add edges to the undirected graph
        for (src, dest) in edges:
            self.adjList[src].append(dest)
            self.adjList[dest].append(src)
 
 
def printAllHamiltonianPaths(g, v, visited, path, N):
 
    # if all the vertices are visited, then hamiltonian path exists
    if len(path) == N:
        # print hamiltonian path
        print(path)
        return 
 
    # Check if every edge starting from vertex v leads to a solution or not
    for w in g.adjList[v]:
 
        # process only unvisited vertices as hamiltonian
        # path visits each vertex exactly once
        if not visited[w]:
            visited[w] = True
            path.append(w)
 
            # check if adding vertex w to the path leads to solution or not
            printAllHamiltonianPaths(g, w, visited, path, N)
 
            # Backtrack
            visited[w] = False
            path.pop()
if __name__ == '__main__':
 
    # List of graph edges as per above diagram
    edges = [(0, 2), (0, 3), (1, 3), (1, 4), (2, 4), (3, 4)]
    
    # Set number of vertices in the graph
    N = 5
 
    # create a graph from edges
    g = Graph(edges, N)
 
    # starting node
    start = 0
 
    # add starting node to the path
    path = [start]
 
    # mark start node as visited
    visited = [False] * N
    visited[start] = True
 
    a=printAllHamiltonianPaths(g, start, visited, path, N)

Upvotes: 0

Views: 104

Answers (1)

Pierre D
Pierre D

Reputation: 26211

You can turn your function into a generator (which is also very convenient if the actual result is very large):

def hamiltonianPaths(g, v, visited, path, N):
    # if all the vertices are visited, then hamiltonian path exists
    if len(path) == N:
        # print hamiltonian path
        yield path.copy()
        return 

    # Check if every edge starting from vertex v leads to a solution or not
    for w in g.adjList[v]:
 
        # process only unvisited vertices as hamiltonian
        # path visits each vertex exactly once
        if not visited[w]:
            visited[w] = True
            path.append(w)
 
            # check if adding vertex w to the path leads to solution or not
            yield from hamiltonianPaths(g, w, visited, path, N)
 
            # Backtrack
            visited[w] = False
            path.pop()

Usage: a = list(hamiltonianPaths(g, start, visited, path, N)).

Upvotes: 1

Related Questions