DSA-python/Graph.py at main · haideratGitHub/DSA-python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
DIRECTED = 'directed_graph'
UNDIRECTED = 'undirected_graph'


class GraphAdjacencyList:
    def __init__(self, typeOfGraph=UNDIRECTED):
        self.graph = {}
        self.type = typeOfGraph

    def addNode(self, value):
        if value in self.graph:
            print(f"Node with value {value} already exists")
        else:
            self.graph[value] = []

    def addEdge(self, node1, node2):

        def addEdgeInDirectedGraph(graph):
            if node1 in graph and node2 in graph:
                graph[node1].append(node2)
            else:
                print("Edge cannot be made because given node values does not exist in graph")

        def addEdgeInUnDirectedGraph(graph):
            if node1 in graph and node2 in graph:
                graph[node1].append(node2)
                graph[node2].append(node1)
            else:
                print("Edge cannot be made because given node values does not exist in graph")

        if self.type == DIRECTED:
            addEdgeInDirectedGraph(self.graph)
        elif self.type == UNDIRECTED:
            addEdgeInUnDirectedGraph(self.graph)

    def printGraph(self):
        for key, value in self.graph.items():
            print(f'{key}: ', end="")
            for node in value:
                print(f"{node},", end="")
            print()

    def createDummyGraph(self):
        graph.addNode(1)
        graph.addNode(2)
        graph.addNode(3)
        graph.addNode(4)
        graph.addEdge(1, 2)
        graph.addEdge(1, 4)
        graph.addEdge(2, 3)
        graph.addEdge(4, 3)
        graph.printGraph()

    def iterativeDFS(self, source):
        print("Iterative DFS")
        if not self.graph or source not in self.graph:
            return
        stack = []
        visited = set()

        stack.append(source)
        visited.add(source)

        while stack:

            curr = stack.pop()
            print(curr)

            for node in self.graph[curr]:
                if node not in visited:
                    stack.append(node)
                    visited.add(node)

    def recursiveDFS(self, source):
        print("Recursive DFS")
        if not self.graph or source not in self.graph:
            return

        def DFS(node, visited):
            visited.add(node)
            print(node)

            for node in self.graph[node]:
                if node not in visited:
                    DFS(node, visited)

        visited = set()
        DFS(source, visited)


class GraphAdjacencyMatrix:
    def __init__(self):
        self.graph = []


# TODO
# 1. BFS in adjacency matrix
# 2. BFS in adjacency list
# 3. DFS in adjacency matrix
# 4. BFS in adjacency list
# 5. Connected components in graph
# 6. Detect cycle in undirected graph [BFS, DFS]
# 7. Detect cycle in directed graph [BFS, DFS]
# 8. Bipartite graph [BFS, DFS]
# 9. Topological sort DFS
# 10. Topological sort BFS (kahn's algorithm)
# 11. Smallest distance in undirected graph ?!?!
# 12. Shortest path in DAG (direct acyclic graph)
# 13. Shortest path in undirected graph (dijkstra algorithm)
# 14. Minimum spanning tree (prim's algorithm)
# 15. Disjoint set / union by rank & path compression
# 16. Kruskal's algorithm

if __name__ == '__main__':
    graph = GraphAdjacencyList(typeOfGraph=UNDIRECTED)
    graph.createDummyGraph()
    graph.iterativeDFS(1)
    graph.recursiveDFS(1)