Debian Codegraph @

examples/python/hamiltonian/hamiltonian.py

raw
1 ############################################
2 # Copyright (c) Microsoft Corporation. All Rights Reserved.
3 #
4 # Check if the given graph has a Hamiltonian cycle.
5 #
6 # Author: Ganesh Gopalakrishnan [email protected]
7 ############################################
8 from z3 import *
9
10 def gencon(gr):
11 """
12 Input a graph as an adjacency list, e.g. {0:[1,2], 1:[2], 2:[1,0]}.
13 Produces solver to check if the given graph has
14 a Hamiltonian cycle. Query the solver using s.check() and if sat,
15 then s.model() spells out the cycle. Two example graphs from
16 http://en.wikipedia.org/wiki/Hamiltonian_path are tested.
17
18 =======================================================
19
20 Explanation:
21
22 Generate a list of Int vars. Constrain the first Int var ("Node 0") to be 0.
23 Pick a node i, and attempt to number all nodes reachable from i to have a
24 number one higher (mod L) than assigned to node i (use an Or constraint).
25
26 =======================================================
27 """
28 L = len(gr)
29 cv = [Int('cv%s'%i) for i in range(L)]
30 s = Solver()
31 s.add(cv[0]==0)
32 for i in range(L):
33 s.add(Or([cv[j]==(cv[i]+1)%L for j in gr[i]]))
34 return s
35
36 def examples():
37 # Example Graphs: The Dodecahedral graph from http://en.wikipedia.org/wiki/Hamiltonian_path
38 grdodec = { 0: [1, 4, 5],
39 1: [0, 7, 2],
40 2: [1, 9, 3],
41 3: [2, 11, 4],
42 4: [3, 13, 0],
43 5: [0, 14, 6],
44 6: [5, 16, 7],
45 7: [6, 8, 1],
46 8: [7, 17, 9],
47 9: [8, 10, 2],
48 10: [9, 18, 11],
49 11: [10, 3, 12],
50 12: [11, 19, 13],
51 13: [12, 14, 4],
52 14: [13, 15, 5],
53 15: [14, 16, 19],
54 16: [6, 17, 15],
55 17: [16, 8, 18],
56 18: [10, 19, 17],
57 19: [18, 12, 15] }
58 import pprint
59 pp = pprint.PrettyPrinter(indent=4)
60 pp.pprint(grdodec)
61
62 sdodec=gencon(grdodec)
63 print(sdodec.check())
64 print(sdodec.model())
65 # =======================================================
66 # See http://en.wikipedia.org/wiki/Hamiltonian_path for the Herschel graph
67 # being the smallest possible polyhedral graph that does not have a Hamiltonian
68 # cycle.
69 #
70 grherschel = { 0: [1, 9, 10, 7],
71 1: [0, 8, 2],
72 2: [1, 9, 3],
73 3: [2, 8, 4],
74 4: [3, 9, 10, 5],
75 5: [4, 8, 6],
76 6: [5, 10, 7],
77 7: [6, 8, 0],
78 8: [1, 3, 5, 7],
79 9: [2, 0, 4],
80 10: [6, 4, 0] }
81 pp.pprint(grherschel)
82 sherschel=gencon(grherschel)
83 print(sherschel.check())
84 # =======================================================
85
86 if __name__ == "__main__":
87 examples()
88