-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraphcoloring.py
78 lines (61 loc) · 2.46 KB
/
graphcoloring.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
#-------------------------------------------------------------------------------
# Copyright (c) 2013 Jose Antonio Martin H. ([email protected]).
# All rights reserved. This program and the accompanying materials
# are made available under the terms of the GNU Public License v3.0
# which accompanies this distribution, and is available at
# http://www.gnu.org/licenses/gpl.html
#
# Contributors:
# Jose Antonio Martin H. ([email protected]) - initial API and implementation
#-------------------------------------------------------------------------------
#import pyximport
#pyximport.install(pyimport = True)
import graphio as gio
import reduce3col as r3
import sys
import testutil as tu
import time
#-----------------------------------------------------------------------------------------------
#from numba import autojit
def main(strFileName, alpha = 5):
print " *** Starting *** "
G = gio.load_from_edge_list_named(strFileName)
V, E, avgdeg = G.order(), G.size(), G.avg_degree()
t1 = time.clock()
Q, G, P, max_alpha = r3.incremental_depth_3COL(G, alpha)
t2 = time.clock()
strScreen = "3-COL: %d N: %d M: %d time1: %3.3f average degree: %2.2f alpha: %s" % (bool(Q), V, E, t2 - t1, avgdeg, max_alpha)
print strScreen
if not Q:
witness = r3.UNCOL_witness(P)
else:
witness = r3.COL_witness(G, P)
tu.save_witness("", Q, witness, "", strFileName)
def main2(strFileName, alpha = 5):
print " *** Starting *** "
G = gio.load_from_edge_list_named(strFileName)
V, E, avgdeg = G.order(), G.size(), G.avg_degree()
t1 = time.clock()
Q, G, P = r3.general_3COL(G, alpha)
t2 = time.clock()
strScreen = "3-COL: %d N: %d M: %d time1: %3.3f average degree: %2.2f alpha: %s" % (Q, V, E, t2 - t1, avgdeg, alpha)
print strScreen
if not Q:
witness = r3.UNCOL_witness(P)
elif Q == 1:
witness = r3.COL_witness(G, P)
else:
return
tu.save_witness("", Q, witness, "", strFileName)
if __name__ == "__main__":
if len(sys.argv) == 3: main(sys.argv[1], int(sys.argv[2]))
if len(sys.argv) == 4: main2(sys.argv[1], int(sys.argv[2]))
elif len(sys.argv) == 2: main(sys.argv[1])
#main("kinstances/IF.col", 5)
#main("kinstances/frucht.col.txt", 5)
# main("to_3coloring_uf50-0955.cnf.col", 5)
#main("to_3coloring_IF.col", 5)
# main("kinstances/planar_IF.col", 2)
#main("kinstances/1-insertions_4.col", 5)
main("kinstances/gc_20_1.col-1.txt", 5)
#main("hardinstances/gr6.txt", 5)