Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit e15a083

Browse files
committed
Remove unnecessary blank spaces
1 parent 7d6491a commit e15a083

File tree

20 files changed

+109
-109
lines changed

20 files changed

+109
-109
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# Graphs in Python
1+
# Graphs in Python
22
![graphs-in-python-course](https://s3.stackabuse.com/media/courses/graphs-in-python-theory-and-implementation-banner.jpg)
33

44
## Repo Structure

‎base_classes/graph.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,6 @@ def __init__(self, num_of_nodes):
55

66
def __str__(self):
77
return
8-
8+
99
def add_edge(self, node1, node2, weight):
1010
return

‎base_classes/node.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,10 +12,10 @@ def __repr__(self):
1212

1313
def set_id(self, id):
1414
self.m_id = id
15-
15+
1616
def get_id(self):
1717
return self.m_id
18-
18+
1919
def get_name(self):
2020
return self.m_name
2121

‎graph_implementations/graph_adj_list_dict.py

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
from queue import Queue
44

55
class AdjListGraph(Graph):
6-
6+
77
###################################
88
# Constructor
99
###################################
@@ -13,10 +13,10 @@ def __init__(self, num_of_nodes, directed=True):
1313

1414
self.m_directed = directed
1515

16-
self.m_graph = {}
16+
self.m_graph = {}
1717

1818
###################################
19-
# Add edge to a graph
19+
# Add edge to a graph
2020
###################################
2121
def add_edge(self, node1_name, node2_name, weight=1):
2222
node1 = Node(node1_name)
@@ -28,7 +28,7 @@ def add_edge(self, node1_name, node2_name, weight=1):
2828
self.m_graph[node1_name] = set()
2929
else:
3030
node1 = self.get_node_by_name(node1_name)
31-
31+
3232
if (node2 not in self.m_nodes):
3333
node2_id = len(self.m_nodes)
3434
node2.set_id(node2_id)
@@ -49,7 +49,7 @@ def get_node_by_name(self, name):
4949
search_node = Node(name)
5050
for node in self.m_nodes:
5151
if node == search_node:
52-
return node
52+
return node
5353
return None
5454

5555
###################################
@@ -68,7 +68,7 @@ def load_from_dict(self, dict):
6868
for node1 in dict.keys():
6969
for (node2, weight) in dict[node1]:
7070
self.add_edge(node1, node2, weight)
71-
71+
7272
###################################
7373
# Load a graph from a list of edges
7474
# For example:
@@ -102,7 +102,7 @@ def __str__(self):
102102

103103
def get_nodes(self):
104104
return self.m_nodes
105-
105+
106106
###################################
107107
# DFS Search
108108
###################################
@@ -122,7 +122,7 @@ def dfs(self, start_node_name, target_node_name, path = [], visited = set()):
122122
if result is not None:
123123
return result
124124
path.pop()
125-
return None
125+
return None
126126

127127
###################################
128128
# BFS Search
@@ -135,7 +135,7 @@ def bfs(self, start_node, target_node):
135135
# Add the start_node to the queue and visited list
136136
queue.put(start_node)
137137
visited.add(start_node)
138-
138+
139139
# start_node has not parents
140140
parent = dict()
141141
parent[start_node] = None
@@ -153,17 +153,17 @@ def bfs(self, start_node, target_node):
153153
queue.put(next_node)
154154
parent[next_node] = current_node
155155
visited.add(next_node)
156-
156+
157157
# Path reconstruction
158158
path = []
159159
if path_found:
160160
path.append(target_node)
161161
while parent[target_node] is not None:
162-
path.append(parent[target_node])
162+
path.append(parent[target_node])
163163
target_node = parent[target_node]
164164
path.reverse()
165-
return path
166-
165+
return path
166+
167167
###################################
168168
# BFS Traversal
169169
###################################
@@ -180,7 +180,7 @@ def bfs_traversal(self, start_node):
180180
for (next_node, weight) in self.m_graph[current_node]:
181181
if next_node not in visited:
182182
queue.put(next_node)
183-
visited.add(next_node)
183+
visited.add(next_node)
184184

185185
g = AdjListGraph(5)
186186
adjacency_list = {

‎graph_implementations/graph_adj_matrix.py

Lines changed: 13 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -11,9 +11,9 @@ def __init__(self, num_of_nodes, directed=True):
1111

1212
# A representation of a graph
1313
# i.e. adjacency matrix
14-
self.m_graph = [[0 for column in range(num_of_nodes)]
14+
self.m_graph = [[0 for column in range(num_of_nodes)]
1515
for row in range(num_of_nodes)]
16-
16+
1717
###################################
1818
# Assert node names
1919
###################################
@@ -44,26 +44,26 @@ def __str__(self):
4444
for i in range(self.m_num_of_nodes):
4545
out += str(self.m_graph[i]) + "\n"
4646
return out
47-
48-
###################################
47+
48+
###################################
4949
# Prims's MST Algorithm
5050
###################################
5151
def prims_mst(self):
5252
# Defining a really big number:
5353
postitive_inf = float('inf')
5454

55-
# This is a list showing which nodes are already selected
55+
# This is a list showing which nodes are already selected
5656
# so we don't pick the same node twice and we can actually know when stop looking
5757
selected_nodes = [False for vertex in range(self.m_num_of_nodes)]
5858

5959
# Matrix of the resulting MST
60-
result = [[0 for column in range(self.m_num_of_nodes)]
60+
result = [[0 for column in range(self.m_num_of_nodes)]
6161
for row in range(self.m_num_of_nodes)]
62-
62+
6363
indx = 0
6464
for i in range(self.m_num_of_nodes):
6565
print(self.m_graph[i])
66-
66+
6767
print(selected_nodes)
6868

6969
# While there are nodes that are not included in the MST, keep looking:
@@ -82,26 +82,26 @@ def prims_mst(self):
8282
if selected_nodes[i]:
8383
for j in range(self.m_num_of_nodes):
8484
# If the analyzed node have a path to the ending node AND its not included in the MST (to avoid cycles)
85-
if (not selected_nodes[j] and self.m_graph[i][j]>0):
85+
if (not selected_nodes[j] and self.m_graph[i][j]>0):
8686
# If the weight path analized is less than the minimum of the MST
8787
if self.m_graph[i][j] < minimum:
8888
# Defines the new minimum weight, the starting vertex and the ending vertex
8989
minimum = self.m_graph[i][j]
9090
start, end = i, j
91-
91+
9292
# Since we added the ending vertex to the MST, it's already selected:
9393
selected_nodes[end] = True
9494

9595

9696
# Filling the MST Adjacency Matrix fields:
9797
result[start][end] = minimum
98-
98+
9999
if minimum == postitive_inf:
100100
result[start][end] = 0
101101

102102
print("(%d.) %d - %d: %d" % (indx, start, end, result[start][end]))
103103
indx += 1
104-
104+
105105
result[end][start] = result[start][end]
106106

107107
# Print the resulting MST
@@ -110,7 +110,7 @@ def prims_mst(self):
110110
for j in range(0+i, len(result)):
111111
if result[i][j] != 0:
112112
print("%d - %d: %d" % (i, j, result[i][j]))
113-
113+
114114

115115
graph = Graph(5)
116116

‎graph_implementations/graph_edge_list.py

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -24,14 +24,14 @@ def __init__(self, num_of_nodes, directed=True):
2424
###################################
2525
def add_edge(self, node1_name, node2_name, weight=1):
2626
node1 = Node(node1_name)
27-
node2 = Node(node2_name)
27+
node2 = Node(node2_name)
2828
if (node1 not in self.m_nodes):
2929
node1_id = len(self.m_nodes)
3030
node1.set_id(node1_id)
3131
self.m_nodes.append(node1)
3232
else:
3333
node1 = self.get_node_by_name(node1_name)
34-
34+
3535
if (node2 not in self.m_nodes):
3636
node2_id = len(self.m_nodes)
3737
node2.set_id(node2_id)
@@ -41,12 +41,12 @@ def add_edge(self, node1_name, node2_name, weight=1):
4141

4242
# Add the edge from node1 to node2
4343
self.m_graph.append([node1, node2, weight])
44-
44+
4545
# If a graph is undirected, add the same edge,
4646
# but also in the opposite direction
4747
if not self.m_directed:
4848
self.m_graph.append([node2, node1, weight])
49-
49+
5050
###################################
5151
# Print a graph representation
5252
###################################
@@ -56,18 +56,18 @@ def __str__(self):
5656
for i in range(num_of_edges):
5757
out += "edge " + str(i+1) + ": " + str(self.m_graph[i]) + "\n"
5858
return out
59-
59+
6060
###################################
6161
# Find node in a graph using its name
6262
###################################
6363
def get_node_by_name(self, name):
6464
search_node = Node(name)
6565
for node in self.m_nodes:
6666
if node == search_node:
67-
return node
67+
return node
6868
return None
69-
70-
###################################
69+
70+
###################################
7171
# Kruskal's MST Algorithm
7272
###################################
7373
# Finds the root node of a subtree containing node `node`
@@ -108,7 +108,7 @@ def kruskals_mst(self):
108108

109109
# Sort edges by weight
110110
sorted_graph = sorted(self.m_graph, key=lambda item: item[2])
111-
111+
112112
# Important property of any MST
113113
# the number of edges is equal to the number of nodes minus 1
114114
while e < (self.m_num_of_nodes - 1):
@@ -124,9 +124,9 @@ def kruskals_mst(self):
124124

125125
print("Kruskal's MST:")
126126
for node1, node2, weight in result:
127-
print("%s - %s: %d" % (node1, node2, weight))
128-
129-
###################################
127+
print("%s - %s: %d" % (node1, node2, weight))
128+
129+
###################################
130130
# Borůvka's MST Algorithm
131131
###################################
132132
def find_component(self, node):

‎graphs_in_python_lessons/01_representing_graphs_in_code/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,6 @@ This folder contains implementations used in the article ["Graphs in Python: Rep
55
- `adj_matrix_graph_basic.py`
66
- `adj_list_graph_basic.py`
77

8-
Those are basic implementations we've used for illustrative purposes in the mentioned article. You can find more advanced implementations in the `advanced_implementations` folder.
8+
Those are basic implementations we've used for illustrative purposes in the mentioned article. You can find more advanced implementations in the `advanced_implementations` folder.
99

1010
The main difference between simple and advanced implementations for casual user is that you can arbitratily name nodes in advanced implementation.

‎graphs_in_python_lessons/01_representing_graphs_in_code/adj_list_graph_basic.py

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -6,21 +6,21 @@ def __init__(self, num_of_nodes, directed=True):
66
# Define the type of a graph
77
self.m_directed = directed
88

9-
self.m_adj_list = {node: set() for node in self.m_nodes}
9+
self.m_adj_list = {node: set() for node in self.m_nodes}
1010

1111
def add_edge(self, node1, node2, weight=1):
1212
self.m_adj_list[node1].add((node2, weight))
13-
13+
1414
if not self.m_directed:
1515
self.m_adj_list[node2].add((node1, weight))
16-
16+
1717
def print_adj_list(self):
1818
for key in self.m_adj_list.keys():
1919
print("node", key, ": ", self.m_adj_list[key])
2020

2121
def main():
2222
graph = Graph(5)
23-
23+
2424
graph.add_edge(0, 0, 25)
2525
graph.add_edge(0, 1, 5)
2626
graph.add_edge(0, 2, 3)

‎graphs_in_python_lessons/01_representing_graphs_in_code/adj_matrix_graph_basic.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ def __init__(self, num_of_nodes, directed=True):
55

66
# Initialize the adjacency matrix
77
# Create a matrix with `num_of_nodes` rows and columns
8-
self.m_adj_matrix = [[0 for column in range(num_of_nodes)]
8+
self.m_adj_matrix = [[0 for column in range(num_of_nodes)]
99
for row in range(num_of_nodes)]
1010

1111
def add_edge(self, node1, node2, weight=1):
@@ -17,7 +17,7 @@ def add_edge(self, node1, node2, weight=1):
1717
def print_adj_matrix(self):
1818
for i in range(self.m_num_of_nodes):
1919
print(self.m_adj_matrix[i])
20-
20+
2121
def main():
2222
graph = Graph(5)
2323

‎graphs_in_python_lessons/01_representing_graphs_in_code/advanced_implementations/adj_list_graph.py

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
from base_classes.graph import Graph
33

44
class AdjListGraph(Graph):
5-
5+
66
###################################
77
# Constructor
88
###################################
@@ -12,10 +12,10 @@ def __init__(self, num_of_nodes, directed=True):
1212

1313
self.m_directed = directed
1414

15-
self.m_graph = {}
15+
self.m_graph = {}
1616

1717
###################################
18-
# Add edge to a graph
18+
# Add edge to a graph
1919
###################################
2020
def add_edge(self, node1_name, node2_name, weight=1):
2121
node1 = Node(node1_name)
@@ -28,7 +28,7 @@ def add_edge(self, node1_name, node2_name, weight=1):
2828
self.m_graph[node1_name] = set()
2929
else:
3030
node1 = self.get_node_by_name(node1_name)
31-
31+
3232
if (node2 not in self.m_nodes):
3333
node2_id = len(self.m_nodes)
3434
node2.set_id(node2_id)
@@ -49,7 +49,7 @@ def get_node_by_name(self, name):
4949
search_node = Node(name)
5050
for node in self.m_nodes:
5151
if node == search_node:
52-
return node
52+
return node
5353
return None
5454

5555
###################################
@@ -68,7 +68,7 @@ def load_from_dict(self, dict):
6868
for node1 in dict.keys():
6969
for (node2, weight) in dict[node1]:
7070
self.add_edge(node1, node2, weight)
71-
71+
7272
###################################
7373
# Load a graph from a list of edges
7474
# For example:

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /