This repository has been archived by the owner on Jan 23, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
98 lines (88 loc) · 2.59 KB
/
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
import argparse
import matplotlib.pyplot as plot
from graph import Graph
if __name__ == '__main__':
parser = argparse.ArgumentParser(
description = 'Randomized Algorithms for Combinatorial Problems'
)
parser.add_argument(
'-f',
'--file',
metavar = 'FILE',
type = argparse.FileType('r'),
help = 'Load a graph from a given file'
)
parser.add_argument(
'-r',
'--random',
metavar = 'SEED',
type = int,
help = 'create a random graph given a seed'
)
parser.add_argument(
'-n',
'--nodes',
metavar = 'N',
default = 15,
type = int,
required = False,
help = 'number of nodes of the graph (default: %(default)s)'
)
parser.add_argument(
'-e',
'--edges',
metavar = 'N',
default = 0.25,
type = float,
required = False,
help = 'maximum number of edges (%%) (default: %(default)s)'
)
parser.add_argument(
'-s',
'--solutions',
metavar = 'N',
default = 1,
type = float,
required = False,
help = 'maximum number of candidate solutions (%%) computed (default: %(default)s)'
)
parser.add_argument(
'-t',
'--time',
metavar = 'N',
default = None,
type = float,
required = False,
help = 'maximum computation time threshold (%%) spent solving the problem (default: %(default)s)'
)
parser.add_argument(
'-d',
'--draw',
action = 'store_true',
required = False,
help = 'draw graph'
)
args = vars(parser.parse_args())
seed = args["random"]
size = args["nodes"]
maximum_edges_number = args["edges"]
if args["solutions"]:
max_solutions = args["solutions"]
else:
max_solutions = None
if args["time"]:
max_time = args["time"] if 0 <= args["time"] <= 1 else 1
else:
max_time = None
if seed:
g = Graph().random_graph(size, seed, maximum_edges_number)
else:
g = Graph().read_graph(args["file"].name, seed)
minimum_weighted_closure, iterations, execution_time, solutions_number = \
g.find_minimum_weighted_closure(seed, max_solutions, max_time, maximum_edges_number)
print("\nMinimum Weighted Closure:", minimum_weighted_closure)
print("Iterations: ", iterations)
print("Execution time: ", execution_time)
print("Number of solutions found: ", solutions_number)
if args["draw"]: g.draw_graph()
plot.show()