-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph_main.py
150 lines (112 loc) · 4 KB
/
graph_main.py
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from graph.bipartite_graph import is_bipartite_graph
from graph.clone_undirected_graph import clone_graph
from graph.delete_edge import delete_edge
from graph.graph import Graph
from graph.traversal.BFS import graph_bfs_traversal
from graph.traversal.DFS import graph_dfs_traversal
from graph.find_mother_vertex import find_mother_vertex_naive
from graph.shortest_path.BFS_SSSP import shortest_path_find
from graph.topological_sort.khans_algorithm import topological_sort_bfs
from graph.number_of_edges_of_a_undirected_graph import count_edges
from graph.find_path_exist import bfs_traversal_path_exist, dfs_traversal_path_exist
from graph.topological_sort.topological_sort_dfs import topological_sort_dfs
from graph.undirected_graph_is_a_tree_or_not import is_tree
def bfs_dfs_traversal():
vertices = ["A", "B", "C", "D", "E", "F", "G"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("C", "E"), ("D", "E"), ("F", "G")]
gp = Graph(vertices)
for u, v in edges:
gp.add_edge(u, v)
gp.print_graph()
graph_bfs_traversal(gp, source="A")
graph_dfs_traversal(gp, source="A")
def find_mother_vertex():
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (2, 3), (3, 0), (3, 4), (4, 2)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v)
g1.print_graph()
print(find_mother_vertex_naive(g1))
def find_shortest_path():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (3, 5), (5, 4)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v)
# g1.print_graph()
print(shortest_path_find(g1, source=0))
def count_edges_of_a_undirected_graph():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (3, 5), (5, 4)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=False)
print(count_edges(g1))
def path_exist_bfs():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (3, 5), (5, 4)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=True)
g1.print_graph()
print(bfs_traversal_path_exist(g1, start=0, destination=5))
def path_exist_dfs():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (3, 5), (5, 4)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=True)
g1.print_graph()
print(dfs_traversal_path_exist(g1, start=2, destination=3))
def is_a_tree():
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (0, 2), (2, 1), (0, 3), (3, 4)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=False)
g1.print_graph()
print(is_tree(g1, start=0))
def remove_edge():
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (0, 2), (1, 3), (2, 4), (4, 0)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v)
g1.print_graph()
print(delete_edge(g1, start=0, end=1))
g1.print_graph()
def clone_undirected_graph():
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (0, 2), (1, 3), (2, 4), (4, 0)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=False)
g1.print_graph()
res = clone_graph(0, g1)
print(res.neighbours)
def check_bipartite_graph():
vertices = [1, 2, 3, 4]
edges = [(1, 2), (2, 3), (3, 4), (4, 1)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v, directed=False)
g1.print_graph()
print(is_bipartite_graph(g1))
def khans_algorithm_topological_sort_using_bfs():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(1, 2), (0, 2), (2, 4), (2, 3), (4, 5), (3, 5)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v)
g1.print_graph()
print(topological_sort_bfs(g1))
def topological_sort_using_dfs():
vertices = [0, 1, 2, 3, 4, 5]
edges = [(1, 2), (0, 2), (2, 4), (2, 3), (4, 5), (3, 5)]
g1 = Graph(vertices)
for u, v in edges:
g1.add_edge(u, v)
g1.print_graph()
print(topological_sort_dfs(g1))
topological_sort_using_dfs()