Graphs (in Python)

 Let's consider a Facebook Network. There are Nodes, which are people, and they are connected through a network of Facebook. It's going to be an Undirected Graph because they are connections between nodes. 

A graph is a complex data structures where you can connect any 2 nodes. One of the common utilities of graphs is finding the root between 2 cities in the case of our Flight Route Example. You might bo to websites which allows you to search for slice, that tells the routes between 2 cities. So those can be flight routes. 

There can be a graph where the edges are weighted, and this is a weighted graph. 

Google Maps are an example of graphs, another example is internet, talking to different computers and servers in any network. Those are connected using graphs. Facebook, Amazon Recommendation using Graph Data Structure, Etc. Let's write code to implement graph in Python now.

The first question is "How can we represent this class using a data structure"? Nodes are nothing but pairs, the connection is basically a pair between 2 cities/or items that you want the graph to represent. So we can use Tuples for this. We can also create a dictionary of adjacency lists. We can also make a get paths which takes the start and end as an input and will return all of the paths. For recursion, you need to think of the simplest case first. Simple case is if there is one node where we add some start key to the path. An edge case is if there is an edge node. To get the path, we'll have to perform depth-first search. So first we append the node then search for the children of the node, get the children of the node, and add this to the parent recursively. 

Now let's go to the shortest distance based on the minimum number of stops. How do we do that? Dijkstra's algorithm can be a good choice! 

class Graph:

    def __init__(self, edges): 

        self.edges = edges

        self.graph_dict in self.edges:

        for start, end in self.edges:

            if start in self.graph_dict: 

                self.graph_dict[start].append(end)

            else: 

                self.graph_dict[start] = [end]

           print("graph dict: " , self.graph_dict) 

    def get_path(start, end, path = []): 

        path = path + [start]

        if start == end: 

            return [path]

        if start not in self.graph_dict: 

            return []

        for node in self.graph_dict[start]: 

            if node not in path: 

                new_paths = self.get_paths(node, end, path)

                for p in new_paths:

                    paths.append(p)

        return paths

         def get_shortest_path(self, start, end, path = []):

        path = path + [start]

        if start == end: 

            return [path]

        if start not in self.graph_dict:

            return None

        shortest_path = None

        for node in self.graph_dict(start): 

            if node not in path:

                sp = self.get_shortest_path(node, end, path)

                if sp:

                    if shortest_path is None or len(sp) < len(shortest_path): 

                shortest_path = sp

            return shortest_path

    if__name__ == 'main': 

        routes = [

            ("Mumbai", "Paris"),

            ("Mumbai", "Dubai"),

            ("Paris", "Dubai"),

            ("Paris", "New York"),

            ("Dubai", "New York"),

            ("New York", "Toronto"),

        ]

        route_graph = Graph(routes)

        d = (

            "Mumbai": ["Paris", "Dubai"],

            "Paris": ["Dubai", "New York"]

        )

        start = "Mumbai"

        end = "Mumbai"

        print("Paths between {start} and {end} " route_graph.getPaths(start, end))

        print("Shortest Path between {start} and {end} " route_graph.get_shortest_paths(start, end))