This repository was archived by the owner on Jan 24, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsolution_verifier.py
136 lines (102 loc) · 4.23 KB
/
solution_verifier.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
import sys
import os.path
import re
# GLOBAL VARIABLES
vertex_count = None
edge_count = None
vertex_weights = []
adjacency_matrix = [[]]
# noinspection PyUnusedLocal
def read_file(file_name):
# Global variables...
global vertex_count, edge_count, vertex_weights, adjacency_matrix
file = open(file_name, 'r')
# Read the file till the end...
while True:
# Read the line and remove the newline character at the end
line = file.readline().rstrip('\n\r')
if not line:
# Means we reached to the end of file...
break
if vertex_count is None:
# Then this is the line for indicating the number of vertices...
vertex_count = int(line)
# After we get the vertex count, we initialize adjacency matrix with zeros...
adjacency_matrix = [[0 for i in range(vertex_count)] for i in range(vertex_count)]
elif edge_count is None:
# Then this is the line for indicating the number of edges...
edge_count = int(float(line))
elif len(vertex_weights) == 0:
# These are the lines indicating vertex weights...
for i in range(vertex_count):
# Get only the second part of the string...
_, _, line = line.partition(' ')
# Convert comma separated values into dot separated...
line = line.replace(',', '.')
# Add the value into vertex weights list as float type...
vertex_weights.append(float(line))
# We will read the next line, if this is not the last vertex's weight...
if i + 1 != vertex_count:
line = file.readline().rstrip('\n\r')
else:
# These are the lines indicating edges between vertices...
line = line.split()
# The first element of line is row and second element of line is column...
adjacency_matrix[int(line[0])][int(line[1])] = 1
# Close the file...
file.close()
def check_solution_length(solution):
# Check if solution contains some other characters except 0s and 1s...
if re.search("[^0-1]", solution):
print("Your solution contains some other characters except 0s and 1s!")
exit(-1)
# If the string length is not the same as vertex count, return error...
if len(solution) != vertex_count:
print("Error: Solution's length must equal to the vertex count...")
exit(-1)
def check_edges(solution):
global vertex_count, adjacency_matrix
# We will convert all edges from one to zero for each included vertex...
for row in range(vertex_count):
# If that vertex is not included, move on...
if solution[row] == '0':
continue
# Loop the row...
for i in range(vertex_count):
adjacency_matrix[row][i] = 0
# Loop the column...
for i in range(vertex_count):
adjacency_matrix[i][row] = 0
# Lastly, we will check if adjacency matrix contains ones...
if 1 in (1 in i for i in adjacency_matrix):
print("Solution is not feasible!")
exit(-1)
else:
print("Solution is feasible!")
def get_weight_sum(solution):
global vertex_count, vertex_weights
weight_sum = 0.0
for i in range(vertex_count):
# If that vertex is not included, move on...
if solution[i] == '0':
continue
weight_sum += vertex_weights[i]
print("Solution's weight sum is", weight_sum)
if __name__ == '__main__':
# Checking if the program has run with the CORRECT NUMBER of command-line arguments...
if len(sys.argv) != 3:
print("You didn't run the program with the CORRECT NUMBER of command-line arguments!")
print("Usage: python solution_verifier.py graph.txt solution")
exit(-1)
file_name = sys.argv[1]
# After getting the file name, we need to check if that file exists...
if not os.path.isfile(file_name):
print("Cannot found the graph file with the filename you provided!")
exit(-1)
# Read the graph
read_file(file_name)
solution = sys.argv[2]
# Verify solution...
check_solution_length(solution)
check_edges(solution)
get_weight_sum(solution)