| 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 |
|