Skip to content

Commit 35b4513

Browse files
stamdstamd
committed
Implement Graph class hierarchy
1 parent d5247ed commit 35b4513

File tree

9 files changed

+108
-46
lines changed

9 files changed

+108
-46
lines changed

‎Classes/__pycache__/graph.cpython-310.pyc

727 Bytes
Binary file not shown.

‎Classes/__pycache__/node.cpython-310.pyc

99 Bytes
Binary file not shown.

‎Classes/graph.py

+10
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
# Base class for graph representation
2+
class Graph:
3+
def __init__(self, num_of_nodes):
4+
return
5+
6+
def __str__(self):
7+
return
8+
9+
def add_edge(self, node1, node2, weight):
10+
return

‎Classes/graph_adj_list_dict.py

+20-8
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,17 @@
11
from node import Node
2+
from graph import Graph
23
from queue import Queue
34

4-
class Graph:
5+
class AdjListGraph(Graph):
56
###################################
67
# Constructor
78
###################################
89
def __init__(self, num_of_nodes, directed=True):
910
self.m_num_of_nodes = num_of_nodes
10-
# self.m_nodes = range(self.m_num_of_nodes)
11-
self.m_nodes = set()
11+
self.m_nodes = []
1212

1313
self.m_directed = directed
1414

15-
# self.m_graph = {node: set() for node in self.m_nodes}
1615
self.m_graph = {}
1716

1817
###################################
@@ -23,20 +22,34 @@ def add_edge(self, node1_name, node2_name, weight=1):
2322
node2 = Node(node2_name)
2423
if (node1 not in self.m_nodes):
2524
node1_id = len(self.m_nodes)
26-
node1.change_id(node1_id)
25+
node1.set_id(node1_id)
2726
self.m_nodes.add(node1)
2827
self.m_graph[node1_name] = set()
28+
else:
29+
node1 = self.get_node_by_name(node1_name)
2930

3031
if (node2 not in self.m_nodes):
3132
node2_id = len(self.m_nodes)
32-
node2.change_id(node2_id)
33+
node2.set_id(node2_id)
3334
self.m_nodes.add(node2)
3435
self.m_graph[node2_name] = set()
36+
else:
37+
node2= self.get_node_by_name(node2_name)
38+
3539
self.m_graph[node1_name].add((node2, weight))
3640

3741
if not self.m_directed:
3842
self.m_graph[node2_name].add((node1, weight))
3943

44+
###################################
45+
# Find node in a graph using its name
46+
###################################
47+
def get_node_by_name(self, name):
48+
search_node = Node(name)
49+
for node in self.m_nodes:
50+
if node == search_node:
51+
return node
52+
return None
4053

4154
###################################
4255
# Load a graph from a dictionary
@@ -83,7 +96,6 @@ def load_from_edge_list(self, edge_list):
8396
def __str__(self):
8497
out = ""
8598
for key in self.m_graph.keys():
86-
# TODO:
8799
out += "node " + str(key) + ": " + str(self.m_graph[key]) + "\n"
88100
return out
89101

@@ -164,7 +176,7 @@ def bfs_traversal(self, start_node):
164176
queue.put(next_node)
165177
visited.add(next_node)
166178

167-
g = Graph(5)
179+
g = AdjListGraph(5)
168180
adjacency_list = {
169181
'A': [('B', 1), ('C', 3), ('D', 7)],
170182
'B': [('D', 5)],

‎Classes/graph_adj_matrix.py

+1-1
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ def __init__(self, num_of_nodes, directed=True):
66
self.m_num_of_nodes = num_of_nodes
77
self.m_directed = directed
88

9-
# Different representations of a graph
9+
# A representation of a graph
1010
# i.e. adjacency matrix
1111
self.m_graph = [[0 for column in range(num_of_nodes)]
1212
for row in range(num_of_nodes)]

‎Classes/graph_edge_list.py

+72-35
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
from node import Node
2-
class Graph:
2+
from graph import Graph
3+
4+
class EdgeListGraph(Graph):
35
###################################
46
# Constructor
57
###################################
@@ -55,6 +57,9 @@ def __str__(self):
5557
out += "edge " + str(i+1) + ": " + str(self.m_graph[i]) + "\n"
5658
return out
5759

60+
###################################
61+
# Find node in a graph using its name
62+
###################################
5863
def get_node_by_name(self, name):
5964
search_node = Node(name)
6065
for node in self.m_nodes:
@@ -99,9 +104,7 @@ def kruskals_mst(self):
99104
# Add zero to the `subtree_sizes` array
100105
# => initialize `parent` and `subtree_sizes`
101106
for node in self.m_nodes:
102-
print(str(node) + " id is " + str(node.get_id()))
103107
parent[node.get_id()] = node
104-
# subtree_sizes.append(0)
105108

106109
# Sort edges by weight
107110
sorted_graph = sorted(self.m_graph, key=lambda item: item[2])
@@ -110,10 +113,8 @@ def kruskals_mst(self):
110113
# the number of edges is equal to the number of nodes minus 1
111114
while e < (self.m_num_of_nodes - 1):
112115
# Pick an edge with the minimum weight at the moment
113-
# print(str(i) + ": " + str(sorted_graph[i]))
114116
node1, node2, weight = sorted_graph[i]
115117
i = i + 1
116-
print(node1, node1.get_id())
117118
x = self.find_subtree(parent, node1)
118119
y = self.find_subtree(parent, node2)
119120
if x != y:
@@ -159,8 +160,8 @@ def boruvkas_mst(self):
159160

160161
cheapest_edge = [-1] * self.m_num_of_nodes
161162

162-
for vertex in range(self.m_num_of_nodes):
163-
self.m_components.update({vertex : vertex})
163+
for node in self.m_nodes:
164+
self.m_components.update({node.get_name() : vertex})
164165
component_size.append(1)
165166

166167
num_of_components = self.m_num_of_nodes
@@ -207,11 +208,6 @@ def boruvkas_mst(self):
207208
print("The weight of MST is " + str(mst_weight))
208209

209210

210-
211-
212-
213-
214-
215211
# graph = Graph(5)
216212

217213
# graph.add_edge('A', 'A', 25)
@@ -230,26 +226,67 @@ def boruvkas_mst(self):
230226
# graph.add_edge(4, 2, 7)
231227
# graph.add_edge(4, 3, 11)
232228

233-
graph = Graph(9)
234-
graph.add_edge("A", "B", 4)
235-
graph.add_edge("A", "C", 7)
236-
graph.add_edge("B", "C", 11)
237-
graph.add_edge("B", "D", 9)
238-
graph.add_edge("B", "F", 20)
239-
graph.add_edge("C", "F", 1)
240-
graph.add_edge("D", "G", 6)
241-
graph.add_edge("D", "E", 2)
242-
graph.add_edge("E", "G", 10)
243-
graph.add_edge("E", "I", 15)
244-
graph.add_edge("E", "H", 5)
245-
graph.add_edge("E", "F", 1)
246-
graph.add_edge("F", "H", 3)
247-
graph.add_edge("G", "I", 5)
248-
graph.add_edge("H", "I", 12)
249-
250-
251-
# print(graph)
252-
253-
graph.kruskals_mst()
254-
255-
229+
###################################
230+
# Kruskal qith letter nodes
231+
#
232+
# graph = EdgeListGraph(9)
233+
#
234+
# graph.add_edge("A", "B", 4)
235+
# graph.add_edge("A", "C", 7)
236+
# graph.add_edge("B", "C", 11)
237+
# graph.add_edge("B", "D", 9)
238+
# graph.add_edge("B", "F", 20)
239+
# graph.add_edge("C", "F", 1)
240+
# graph.add_edge("D", "G", 6)
241+
# graph.add_edge("D", "E", 2)
242+
# graph.add_edge("E", "G", 10)
243+
# graph.add_edge("E", "I", 15)
244+
# graph.add_edge("E", "H", 5)
245+
# graph.add_edge("E", "F", 1)
246+
# graph.add_edge("F", "H", 3)
247+
# graph.add_edge("G", "I", 5)
248+
# graph.add_edge("H", "I", 12)
249+
#
250+
# graph.kruskals_mst()
251+
###################################
252+
253+
###################################
254+
# Kruskal qith letter nodes
255+
#
256+
# graph = EdgeListGraph(9)
257+
258+
# graph.add_edge(0, 1, 4)
259+
# graph.add_edge(0, 2, 7)
260+
# graph.add_edge(1, 2, 11)
261+
# graph.add_edge(1, 3, 9)
262+
# graph.add_edge(1, 5, 20)
263+
# graph.add_edge(2, 5, 1)
264+
# graph.add_edge(3, 6, 6)
265+
# graph.add_edge(3, 4, 2)
266+
# graph.add_edge(4, 6, 10)
267+
# graph.add_edge(4, 8, 15)
268+
# graph.add_edge(4, 7, 5)
269+
# graph.add_edge(4, 5, 1)
270+
# graph.add_edge(5, 7, 3)
271+
# graph.add_edge(6, 8, 5)
272+
# graph.add_edge(7, 8, 12)
273+
#
274+
# graph.kruskals_mst()
275+
###################################
276+
277+
g = EdgeListGraph(9)
278+
g.add_edge(0, 1, 4)
279+
g.add_edge(0, 6, 7)
280+
g.add_edge(1, 6, 11)
281+
g.add_edge(1, 7, 20)
282+
g.add_edge(1, 2, 9)
283+
g.add_edge(2, 3, 6)
284+
g.add_edge(2, 4, 2)
285+
g.add_edge(3, 4, 10)
286+
g.add_edge(3, 5, 5)
287+
g.add_edge(4, 5, 15)
288+
g.add_edge(4, 7, 1)
289+
g.add_edge(4, 8, 5)
290+
g.add_edge(5, 8, 12)
291+
292+
g.boruvkas_mst()

‎Classes/node.py

+5-2
Original file line numberDiff line numberDiff line change
@@ -5,13 +5,16 @@ def __init__(self, name, id=-1):
55

66
def __str__(self):
77
return self.m_name
8-
8+
99
def __repr__(self):
1010
return self.m_name
1111

1212

13-
def change_id(self, id):
13+
def set_id(self, id):
1414
self.m_id = id
15+
16+
def get_id(self):
17+
return self.m_id
1518

1619
def __eq__(self, other):
1720
return self.m_name == other.m_name

‎Lessions/README.md

Whitespace-only changes.

‎Lessions/Representing Graphs in Code/README.md

Whitespace-only changes.

0 commit comments

Comments
 (0)