CODEWITHSUNDEEP
pythongraph
prabh
prabh

Reputation: 396

Find path in graphs

I am trying to learn python, and started few weeks back. I was reading about graphs today and found the below code:

class Graph(object):
    def __init__(self, graph_dict=None):
        if graph_dict == None:
            graph_dict = {}
        self.__graph_dict = graph_dict

    def find_path(self, start_vertex, end_vertex, path=None):
        """Find a path from start_vertex to end_vertex in graph."""
        if path == None:
            path = []

        graph = self.__graph_dict
        print(self.__graph_dict)

        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return path
        if start_vertex not in graph:
            return None
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_path = self.find_path(vertex, end_vertex, path)
                if extended_path:
                    return extended_path
        return None


if __name__ == "__main__":
    g = {"a" : ["c"],
         "b" : ["c", "e"],
         "c" : ["b", "d", "e"]}

    graph = Graph(g)

    graph.find_path("a", "d")

here i am not able to understand when i print print(self.__graph_dict) i get the below as print output:

{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}
{'a': ['c'], 'b': ['c', 'e'], 'c': ['b', 'd', 'e']}

What i am not able to understand why it is repeated 5 times and not just once which is the dictionary value of the graph. Does it have any significance also? Am i missing something here. Thanks in advance for valuable inputs and time.

Upvotes: 3

Views: 376

Answers (1)

David Kaftan
David Kaftan

Reputation: 2174

You are getting the print out 5 times because you are recursively calling find_path.

See the code: 

for vertex in graph[start_vertex]:
    if vertex not in path:
        extended_path = self.find_path(vertex, end_vertex, path) #this is being hit 4 times

I don't see that as an issue as far as your code working or not. It seems to make sense to me.

Upvotes: 3

Related Questions