Skip to content

Commit 7cdda93

Browse files
cclausscclauss
authored
Travis CI: Add pytest --doctest-modules graphs (TheAlgorithms#1018)
1 parent 267b5ef commit 7cdda93

9 files changed

Lines changed: 148 additions & 135 deletions

‎.travis.yml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ script:
2121
digital_image_processing
2222
divide_and_conquer
2323
dynamic_programming
24+
graphs
2425
hashes
2526
linear_algebra_python
2627
matrix

‎graphs/basic_graphs.py‎

Lines changed: 39 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -10,42 +10,44 @@
1010
except NameError:
1111
xrange = range # Python 3
1212

13-
# Accept No. of Nodes and edges
14-
n, m = map(int, raw_input().split(" "))
1513

16-
# Initialising Dictionary of edges
17-
g = {}
18-
for i in xrange(n):
19-
g[i + 1] = []
20-
21-
"""
22-
--------------------------------------------------------------------------------
23-
Accepting edges of Unweighted Directed Graphs
24-
--------------------------------------------------------------------------------
25-
"""
26-
for _ in xrange(m):
27-
x, y = map(int, raw_input().split(" "))
28-
g[x].append(y)
29-
30-
"""
31-
--------------------------------------------------------------------------------
32-
Accepting edges of Unweighted Undirected Graphs
33-
--------------------------------------------------------------------------------
34-
"""
35-
for _ in xrange(m):
36-
x, y = map(int, raw_input().split(" "))
37-
g[x].append(y)
38-
g[y].append(x)
14+
if __name__ == "__main__":
15+
# Accept No. of Nodes and edges
16+
n, m = map(int, raw_input().split(" "))
3917

40-
"""
41-
--------------------------------------------------------------------------------
42-
Accepting edges of Weighted Undirected Graphs
43-
--------------------------------------------------------------------------------
44-
"""
45-
for _ in xrange(m):
46-
x, y, r = map(int, raw_input().split(" "))
47-
g[x].append([y, r])
48-
g[y].append([x, r])
18+
# Initialising Dictionary of edges
19+
g = {}
20+
for i in xrange(n):
21+
g[i + 1] = []
22+
23+
"""
24+
----------------------------------------------------------------------------
25+
Accepting edges of Unweighted Directed Graphs
26+
----------------------------------------------------------------------------
27+
"""
28+
for _ in xrange(m):
29+
x, y = map(int, raw_input().strip().split(" "))
30+
g[x].append(y)
31+
32+
"""
33+
----------------------------------------------------------------------------
34+
Accepting edges of Unweighted Undirected Graphs
35+
----------------------------------------------------------------------------
36+
"""
37+
for _ in xrange(m):
38+
x, y = map(int, raw_input().strip().split(" "))
39+
g[x].append(y)
40+
g[y].append(x)
41+
42+
"""
43+
----------------------------------------------------------------------------
44+
Accepting edges of Weighted Undirected Graphs
45+
----------------------------------------------------------------------------
46+
"""
47+
for _ in xrange(m):
48+
x, y, r = map(int, raw_input().strip().split(" "))
49+
g[x].append([y, r])
50+
g[y].append([x, r])
4951

5052
"""
5153
--------------------------------------------------------------------------------
@@ -168,9 +170,10 @@ def topo(G, ind=None, Q=[1]):
168170

169171

170172
def adjm():
171-
n, a = raw_input(), []
173+
n = raw_input().strip()
174+
a = []
172175
for i in xrange(n):
173-
a.append(map(int, raw_input().split()))
176+
a.append(map(int, raw_input().strip().split()))
174177
return a, n
175178

176179

‎graphs/bellman_ford.py‎

Lines changed: 20 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -12,15 +12,15 @@ def printDist(dist, V):
1212
def BellmanFord(graph, V, E, src):
1313
mdist=[float('inf') for i in range(V)]
1414
mdist[src] = 0.0
15-
15+
1616
for i in range(V-1):
1717
for j in range(V):
1818
u = graph[j]["src"]
1919
v = graph[j]["dst"]
2020
w = graph[j]["weight"]
2121

2222
if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:
23-
mdist[v] = mdist[u] + w
23+
mdist[v] = mdist[u] + w
2424
for j in range(V):
2525
u = graph[j]["src"]
2626
v = graph[j]["dst"]
@@ -29,26 +29,26 @@ def BellmanFord(graph, V, E, src):
2929
if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:
3030
print("Negative cycle found. Solution not possible.")
3131
return
32-
33-
printDist(mdist, V)
3432

35-
33+
printDist(mdist, V)
34+
35+
36+
37+
if __name__ == "__main__":
38+
V = int(input("Enter number of vertices: ").strip())
39+
E = int(input("Enter number of edges: ").strip())
3640

37-
#MAIN
38-
V = int(input("Enter number of vertices: "))
39-
E = int(input("Enter number of edges: "))
41+
graph = [dict() for j in range(E)]
4042

41-
graph = [dict() for j in range(E)]
43+
for i in range(V):
44+
graph[i][i] = 0.0
4245

43-
for i in range(V):
44-
graph[i][i] = 0.0
46+
for i in range(E):
47+
print("\nEdge ",i+1)
48+
src = int(input("Enter source:").strip())
49+
dst = int(input("Enter destination:").strip())
50+
weight = float(input("Enter weight:").strip())
51+
graph[i] = {"src": src,"dst": dst, "weight": weight}
4552

46-
for i in range(E):
47-
print("\nEdge ",i+1)
48-
src = int(input("Enter source:"))
49-
dst = int(input("Enter destination:"))
50-
weight = float(input("Enter weight:"))
51-
graph[i] = {"src": src,"dst": dst, "weight": weight}
52-
53-
gsrc = int(input("\nEnter shortest path source:"))
54-
BellmanFord(graph, V, E, gsrc)
53+
gsrc = int(input("\nEnter shortest path source:").strip())
54+
BellmanFord(graph, V, E, gsrc)

‎graphs/dijkstra_2.py‎

Lines changed: 20 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -22,36 +22,36 @@ def Dijkstra(graph, V, src):
2222
mdist=[float('inf') for i in range(V)]
2323
vset = [False for i in range(V)]
2424
mdist[src] = 0.0
25-
25+
2626
for i in range(V-1):
2727
u = minDist(mdist, vset, V)
2828
vset[u] = True
29-
29+
3030
for v in range(V):
3131
if (not vset[v]) and graph[u][v]!=float('inf') and mdist[u] + graph[u][v] < mdist[v]:
32-
mdist[v] = mdist[u] + graph[u][v]
32+
mdist[v] = mdist[u] + graph[u][v]
33+
34+
3335

34-
36+
printDist(mdist, V)
3537

36-
printDist(mdist, V)
3738

38-
3939

40-
#MAIN
41-
V = int(input("Enter number of vertices: "))
42-
E = int(input("Enter number of edges: "))
40+
if __name__ == "__main__":
41+
V = int(input("Enter number of vertices: ").strip())
42+
E = int(input("Enter number of edges: ").strip())
4343

44-
graph = [[float('inf') for i in range(V)] for j in range(V)]
44+
graph = [[float('inf') for i in range(V)] for j in range(V)]
4545

46-
for i in range(V):
47-
graph[i][i] = 0.0
46+
for i in range(V):
47+
graph[i][i] = 0.0
4848

49-
for i in range(E):
50-
print("\nEdge ",i+1)
51-
src = int(input("Enter source:"))
52-
dst = int(input("Enter destination:"))
53-
weight = float(input("Enter weight:"))
54-
graph[src][dst] = weight
49+
for i in range(E):
50+
print("\nEdge ",i+1)
51+
src = int(input("Enter source:").strip())
52+
dst = int(input("Enter destination:").strip())
53+
weight = float(input("Enter weight:").strip())
54+
graph[src][dst] = weight
5555

56-
gsrc = int(input("\nEnter shortest path source:"))
57-
Dijkstra(graph, V, gsrc)
56+
gsrc = int(input("\nEnter shortest path source:").strip())
57+
Dijkstra(graph, V, gsrc)

graphs/floyd_warshall.py renamed to graphs/graphs_floyd_warshall.py

File renamed without changes.

‎graphs/minimum_spanning_tree_kruskal.py‎

Lines changed: 25 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,34 @@
11
from __future__ import print_function
2-
num_nodes, num_edges = list(map(int,input().split()))
32

4-
edges = []
3+
if __name__ == "__main__":
4+
num_nodes, num_edges = list(map(int, input().strip().split()))
55

6-
for i in range(num_edges):
7-
node1, node2, cost = list(map(int,input().split()))
8-
edges.append((i,node1,node2,cost))
6+
edges = []
97

10-
edges = sorted(edges, key=lambda edge: edge[3])
8+
for i in range(num_edges):
9+
node1, node2, cost = list(map(int, input().strip().split()))
10+
edges.append((i,node1,node2,cost))
1111

12-
parent = [i for i in range(num_nodes)]
12+
edges = sorted(edges, key=lambda edge: edge[3])
1313

14-
def find_parent(i):
15-
if(i != parent[i]):
16-
parent[i] = find_parent(parent[i])
17-
return parent[i]
14+
parent = list(range(num_nodes))
1815

19-
minimum_spanning_tree_cost = 0
20-
minimum_spanning_tree = []
16+
def find_parent(i):
17+
if i != parent[i]:
18+
parent[i] = find_parent(parent[i])
19+
return parent[i]
2120

22-
for edge in edges:
23-
parent_a = find_parent(edge[1])
24-
parent_b = find_parent(edge[2])
25-
if(parent_a != parent_b):
26-
minimum_spanning_tree_cost += edge[3]
27-
minimum_spanning_tree.append(edge)
28-
parent[parent_a] = parent_b
21+
minimum_spanning_tree_cost = 0
22+
minimum_spanning_tree = []
2923

30-
print(minimum_spanning_tree_cost)
31-
for edge in minimum_spanning_tree:
32-
print(edge)
24+
for edge in edges:
25+
parent_a = find_parent(edge[1])
26+
parent_b = find_parent(edge[2])
27+
if parent_a != parent_b:
28+
minimum_spanning_tree_cost += edge[3]
29+
minimum_spanning_tree.append(edge)
30+
parent[parent_a] = parent_b
31+
32+
print(minimum_spanning_tree_cost)
33+
for edge in minimum_spanning_tree:
34+
print(edge)

‎graphs/minimum_spanning_tree_prims.py‎

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -100,12 +100,13 @@ def deleteMinimum(heap, positions):
100100
Nbr_TV[ v[0] ] = vertex
101101
return TreeEdges
102102

103-
# < --------- Prims Algorithm --------- >
104-
n = int(input("Enter number of vertices: "))
105-
e = int(input("Enter number of edges: "))
106-
adjlist = defaultdict(list)
107-
for x in range(e):
108-
l = [int(x) for x in input().split()]
109-
adjlist[l[0]].append([ l[1], l[2] ])
110-
adjlist[l[1]].append([ l[0], l[2] ])
111-
print(PrimsAlgorithm(adjlist))
103+
if __name__ == "__main__":
104+
# < --------- Prims Algorithm --------- >
105+
n = int(input("Enter number of vertices: ").strip())
106+
e = int(input("Enter number of edges: ").strip())
107+
adjlist = defaultdict(list)
108+
for x in range(e):
109+
l = [int(x) for x in input().strip().split()]
110+
adjlist[l[0]].append([ l[1], l[2] ])
111+
adjlist[l[1]].append([ l[0], l[2] ])
112+
print(PrimsAlgorithm(adjlist))

‎graphs/multi_hueristic_astar.py‎

Lines changed: 14 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@ def minkey(self):
1818
return self.elements[0][0]
1919
else:
2020
return float('inf')
21-
21+
2222
def empty(self):
2323
return len(self.elements) == 0
2424

@@ -48,10 +48,10 @@ def remove_element(self, item):
4848
(pro, x) = heapq.heappop(self.elements)
4949
for (prito, yyy) in temp:
5050
heapq.heappush(self.elements, (prito, yyy))
51-
51+
5252
def top_show(self):
5353
return self.elements[0][1]
54-
54+
5555
def get(self):
5656
(priority, item) = heapq.heappop(self.elements)
5757
self.set.remove(item)
@@ -65,7 +65,7 @@ def consistent_hueristic(P, goal):
6565

6666
def hueristic_2(P, goal):
6767
# integer division by time variable
68-
return consistent_hueristic(P, goal) // t
68+
return consistent_hueristic(P, goal) // t
6969

7070
def hueristic_1(P, goal):
7171
# manhattan distance
@@ -74,13 +74,13 @@ def hueristic_1(P, goal):
7474
def key(start, i, goal, g_function):
7575
ans = g_function[start] + W1 * hueristics[i](start, goal)
7676
return ans
77-
77+
7878
def do_something(back_pointer, goal, start):
7979
grid = np.chararray((n, n))
8080
for i in range(n):
8181
for j in range(n):
8282
grid[i][j] = '*'
83-
83+
8484
for i in range(n):
8585
for j in range(n):
8686
if (j, (n-1)-i) in blocks:
@@ -94,7 +94,7 @@ def do_something(back_pointer, goal, start):
9494
grid[(n-1)-y_c][x_c] = "-"
9595
x = back_pointer[x]
9696
grid[(n-1)][0] = "-"
97-
97+
9898

9999
for i in xrange(n):
100100
for j in range(n):
@@ -112,7 +112,7 @@ def do_something(back_pointer, goal, start):
112112
print("PATH TAKEN BY THE ALGORITHM IS:-")
113113
x = back_pointer[goal]
114114
while x != start:
115-
print(x, end=' ')
115+
print(x, end=' ')
116116
x = back_pointer[x]
117117
print(x)
118118
quit()
@@ -153,7 +153,7 @@ def expand_state(s, j, visited, g_function, close_list_anchor, close_list_inad,
153153
if key(neighbours, var, goal, g_function) <= W2 * key(neighbours, 0, goal, g_function):
154154
# print("why not plssssssssss")
155155
open_list[j].put(neighbours, key(neighbours, var, goal, g_function))
156-
156+
157157

158158
# print
159159

@@ -212,7 +212,7 @@ def multi_a_star(start, goal, n_hueristic):
212212
for i in range(n_hueristic):
213213
open_list.append(PriorityQueue())
214214
open_list[i].put(start, key(start, i, goal, g_function))
215-
215+
216216
close_list_anchor = []
217217
close_list_inad = []
218218
while open_list[0].minkey() < float('inf'):
@@ -263,4 +263,7 @@ def multi_a_star(start, goal, n_hueristic):
263263
print()
264264
print("# is an obstacle")
265265
print("- is the path taken by algorithm")
266-
multi_a_star(start, goal, n_hueristic)
266+
267+
268+
if __name__ == "__main__":
269+
multi_a_star(start, goal, n_hueristic)

0 commit comments

Comments
 (0)