Amazing-Python-Scripts

1
"""
2
Graph Visualization
3

4
                member1--member5
5
                   |
6
        member3--member0--member2
7
                   |
8
                 member4
9

10

11
            |------city1----city3
12
            |        |       |
13
         city4----city2------|
14
                           city5
15

16

17
Graph Usage
18
    Facebook Friends Suggestion
19
        [m0 is friend of m1 & m5 is friend of m1; it is likely that m0 is friend of m5 too...
20
            FB will suggest m5 as friend suggestion to m0]
21
    Flight Routes : To find shortest path between two nodes
22
        [(city1,city2),(city1,city3),(city1,city4),
23
         (city2,city1),(city2,city4),(city2,city5),
24
         (city3,city1),(city3,city5),
25
         (city4,city1),(city4,city2),
26
         (city5,city2),(city5,city3)]
27
    Google Maps
28
    Internet
29
    E-commerce shopping Recommendation
30

31
Difference between TREE and GRAPH:
32
    In TREE, there is only one path between two nodes. GRAPH is a complex DS where two nodes can randomly be connected
33

34
"""
35

36

37
class Graph:
38
    def __init__(self, edges):
39
        self.edges = edges
40
        # Transform route tuple to route dictionary
41
        self.graph_dict = {}  # blank dictionary
42
        for start, end in self.edges:
43
            if start in self.graph_dict:  # element1 is already in dictionary
44
                # add another element associated to element1 in graph_dictionary
45
                self.graph_dict[start].append(end)
46
            else:
47
                # if element1 is not present, add it to graph_dictionary
48
                self.graph_dict[start] = [end]
49
        print("Graph dictionary: ", self.graph_dict)  # print route dictionary
50

51
    # get paths between start-point and end-point
52
    def getpath(self, start, end, path=[]):
53
        path = path + [start]
54
        if start == end:
55
            return [path]
56

57
        if start not in self.graph_dict:  # if one-way between one node, say Chennai; return []
58
            # Chennai is not as a starting point, so it has no route associated
59
            return []
60

61
        paths = []
62
        for node in self.graph_dict[start]:
63
            if node not in path:
64
                new_path = self.getpath(node, end, path)
65
                for p in new_path:
66
                    paths.append(p)
67
        return paths
68

69
    # method to find shortest path between start-point and end-point
70
    def getShortestPath(self, start, end, path=[]):
71
        path = path + [start]
72

73
        # if starting-point and end-point are same
74
        if start == end:
75
            return path
76

77
        # If no path available from a point, return None
78
        if start not in self.graph_dict:
79
            return None
80

81
        # searching for shortest path
82
        shortest_path = None  # shortest path initialised
83
        for node in self.graph_dict[start]:
84
            if node not in path:
85
                sp = self.getShortestPath(node, end, path)
86
                if sp:
87
                    # if no shortest path is available; but in later iteration, we may have a path
88
                    # so check if it is shorter than original path (array of routes) or not
89
                    if shortest_path is None or len(sp) < len(shortest_path):
90
                        shortest_path = sp  # shortest path returned
91

92
        return shortest_path
93

94

95
if __name__ == '__main__':
96

97
    routes = [
98
        ("Mumbai", "Pune"),
99
        ("Mumbai", "Surat"),
100
        ("Surat", "Bangaluru"),
101
        ("Pune", "Hyderabad"),
102
        ("Pune", "Mysuru"),
103
        ("Hyderabad", "Bangaluru"),
104
        ("Hyderabad", "Chennai"),
105
        ("Mysuru", "Bangaluru"),
106
        ("Chennai", "Bangaluru")
107
    ]
108

109
    routes = [
110
        ("Mumbai", "Paris"),
111
        ("Mumbai", "Dubai"),
112
        ("Paris", "Dubai"),
113
        ("Paris", "New York"),
114
        ("Dubai", "New York"),
115
        ("New York", "Toronto"),
116
    ]
117

118
    route_graph = Graph(routes)
119

120
    ''' start == end
121
    start = "Mumbai"
122
    end = "Mumbai"
123
    [op]: [['Mumbai']]'''
124

125
    ''' start not in self.graph_dict
126
    start = "Chennai"
127
    end = "Mumbai"
128
    [op]: []'''
129

130
    start = "Mumbai"
131
    end = "New York"
132

133
    print(f"All paths between: {start} and {end}: ",
134
          route_graph.getpath(start, end))
135
    print(f"Shortest path between {start} and {end}: ",
136
          route_graph.getShortestPath(start, end))
137

138
    start = "Dubai"
139
    end = "New York"
140

141
    print(f"All paths between: {start} and {end}: ",
142
          route_graph.getpath(start, end))
143
    print(f"Shortest path between {start} and {end}: ",
144
          route_graph.getShortestPath(start, end))
145