/* * Hamiltonian Cycle: * A graph consists of a set of vertices and a set of edges, where an edge * is a pair of distinct vertices. * Two vertices of a graph are adjacent if there is an edge from the first * to the second. * A path is a sequence of vertices, each adjacent to the next. * A cycle is a path containing at least three vertices such that the last * vertex is adjacent to the first. * A Hamiltonian cycle of a graph is a cycle containing all the vertices * of the graph. */ /* ham_cyc(Graph, HamiltonianCycle) is true if HamiltonianCycle is a */ /* Hamiltonian cycle of the undirected Graph. Due to the heuristics used, */ /* for some graphs it may be necessary to perform several runs in order to */ /* obtain a solution. And perhaps for some graphs, a solution will never */ /* be obtained. */ /* e.g. ham_cyc([g(1,[4,5,6]),g(2,[3,6]),g(3,[2,4,6]),g(4,[1,3,5]), */ /* g(5,[1,4]),g(6,[1,2,3])], [5,4,3,2,6,1]). */ ham_cyc(Graph, _):- member(g(_,[]), Graph), !, write(`Graph contains a degree-0 vertex`), nl, fail. ham_cyc(Graph, _):- member(g(_,[_]), Graph), !, write(`Graph contains a degree-1 vertex`), nl, fail. ham_cyc(Graph, HamiltonianCycle):- length(Graph, Order), rand_int(1, Order, Index), nth(Graph, Index, g(Vertex,Neighbours)), % Start at a random vertex Order1 is Order - 1, ham_cyc_1(Order1, Graph, Neighbours, [], [Vertex], HamiltonianCycle). ham_cyc_1(0, _, Neighbours, _, HamCyc, HamCyc):- % The path is complete last(HamCyc, FirstVertex), member(FirstVertex, Neighbours), !. % The path is a cycle ham_cyc_1(I, Graph, Neighbours, _, Path, HamCyc):- I > 0, I1 is I - 1, % The path is not complete extend_path(Neighbours, Graph, Path, Path1), % Try to extend the path Path1=[EndPoint|_], member(g(EndPoint,Neighbours1), Graph), !, ham_cyc_1(I1, Graph, Neighbours1, [], Path1, HamCyc). ham_cyc_1(I, Graph, Neighbours, _, Path, HamCyc):- I > 0, I1 is I - 1, % The path is not complete last(Path, FirstVertex), member(FirstVertex, Neighbours), % The path is a cycle extend_cycle(Path, Graph, Path1), % Try to extend the cycle Path1=[EndPoint|_], member(g(EndPoint,Neighbours1), Graph), !, ham_cyc_1(I1, Graph, Neighbours1, [], Path1, HamCyc). ham_cyc_1(I, Graph, Ns, EPs, Path, HamCyc):- % Complete or not complete, rotate_path(Ns, I, Graph, EPs, Path, HamCyc). % try to rotate the path /* extend_path(Ns, Graph, Path, ExtendedPath) is true if Ns are the */ /* neighbours of the endpoint of Path, and ExtendedPath is the result of */ /* extending Path at either end with a vertex from the Graph. */ extend_path(Ns, _, Path, [Neighbour|Path]):- % Try to extend from endpoint first_non_member(Ns, Path, Neighbour), !. extend_path(_, Graph, Path, [Neighbour|ReversedPath]):- reverse(Path, ReversedPath), % Reverse the path and try again ReversedPath=[Vertex|_], member(g(Vertex,Ns), Graph), !, first_non_member(Ns, ReversedPath, Neighbour). /* first_non_member(Neighbours, Path, Neighbour) is true if Neighbour is */ /* the first element of Neighbours which is not a member of the Path. */ first_non_member([Neighbour|_], Path, Neighbour):- \+ member(Neighbour, Path), !. first_non_member([_|Neighbours], Path, Neighbour):- first_non_member(Neighbours, Path, Neighbour). /* extend_cycle(Cycle, Graph, ExtendedPath) is true if ExtendedPath is the */ /* result of applying "cycle extension" to the Cycle in the Graph. */ extend_cycle(Cycle, Graph, ExtendedPath):- extend_cycle_1(Cycle, Graph, Cycle, ExtendedPath). extend_cycle_1([Vertex|_], Graph, Cycle, ExtendedPath):- member(g(Vertex,Neighbours), Graph), first_non_member(Neighbours, Cycle, NewEndPoint), !, before_and_after(Cycle, Vertex, Path1, Path2), append([NewEndPoint|Path2], Path1, ExtendedPath). extend_cycle_1([_|Vertices], Graph, Cycle, ExtendedPath):- extend_cycle_1(Vertices, Graph, Cycle, ExtendedPath). /* before_and_after(Cycle, V, Path1, Path2) is true if Path1 contains the */ /* elements preceding V in Cycle, and Path2 contains the remaining */ /* elements. */ before_and_after([V|Cycle], V, [], [V|Cycle]):-!. before_and_after([P|Cycle], V, [P|Path1], Path2):- before_and_after(Cycle, V, Path1, Path2). /* rotate_path(Ns, I, Graph, EPs, Path, HamCyc) is true if Ns are the */ /* neighbours of the endpoint of the Path, I is the number of vertices to */ /* be added to the Path, EPs are the previous endpoints generated by */ /* rotation for this path length, and HamCyc is a Hamiltonian cycle of the */ /* Graph. */ rotate_path([N|_], I, Graph, EPs, Path, HamCyc):- rotate(Path, N, [], Path1), Path1=[Vertex|_], \+ member(Vertex, EPs), member(g(Vertex,Neighbours), Graph), ham_cyc_1(I, Graph, Neighbours, [Vertex|EPs], Path1, HamCyc), !. rotate_path([_|Ns], I, Graph, EPs, Path, HamCyc):- rotate_path(Ns, I, Graph, EPs, Path, HamCyc). /* rotate(Ps, X, [], Qs) is true if Qs is the same as Ps except that the */ /* elements preceding X are reversed. */ /* e.g. rotate([1,2,3,4,5,6,7], 5, [], [4,3,2,1,5,6,7]). */ rotate([X|Xs], X, Qs0, Qs):-!, append(Qs0, [X|Xs], Qs). rotate([P|Ps], X, Qs0, Qs):- rotate(Ps, X, [P|Qs0], Qs). /* * Library predicates */ /* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs */ /* to the list Ys. */ %append([], Ys, Ys). %append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs). /* last(Xs, X) is true if X is the last element of the list Xs. */ last([X], X):-!. last([_|Xs], X):-last(Xs, X). /* length(Xs, L) is true if L is the number of elements in the list Xs. */ %length(Xs, L):-length_1(Xs, 0, L). /* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of */ /* elements in the list Xs. */ %length_1([], L, L). %length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L). /* member(X, Xs) is true if the element X is contained in the list Xs. */ %member(X, [X|_]). %member(X, [_|Xs]):-member(X, Xs). /* nth(+Xs, ?N, ?X) is true if X is the N-th (base 1) element of the list Xs.*/ nth(Xs, N, X):-nth_1(Xs, X, 1, N). nth_1([X|_], X, I, I):-!. nth_1([_|Xs], X, I0, I):- I1 is I0 + 1, nth_1(Xs, X, I1, I). /* rand_int(I, J, K) is true if K is a pseudo-random integer in the range */ /* I..J. */ rand_int(I, J, K):-K is int(rand(J - I + 1)) + I. /* reverse(Xs, Ys) is true if Ys is the result of reversing the order of */ /* the elements in the list Xs. */ %reverse(Xs, Ys):-reverse_1(Xs, [], Ys). %reverse_1([], As, As). %reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys). /* * Test predicates */ /* Create a random graph with I vertices each with, on average, J */ /* neighbouring vertices, and find a Hamiltonian cycle if there is one. */ /* e.g. go_ran(100, 10, X, Y). */ go_ran(I, J, Graph, HamCyc):- rand_graph(I, J, Graph), ham_cyc(Graph, HamCyc). /* rand_graph(I, J, Graph) is true if Graph is a random graph of I vertices, */ /* each with an average of J neighbours. */ rand_graph(I, J, Graph):- I > J, J > 0, initialize_graph(I, Graph0), % Create vertices with no neighbours N is I * J // 2, update_graph(N, I, Graph0, Graph). % Add N neighbours to the graph initialize_graph(0, []):-!. initialize_graph(I, [g(I,[])|Graph]):- I1 is I - 1, initialize_graph(I1, Graph). update_graph(0, _, Graph, Graph):-!. update_graph(N, I, Graph0, Graph):- rand_int(1, I, A), rand_int(1, I, B), A \= B, remove(g(A, Vs), Graph0, Graph1), \+ member(B, Vs), remove(g(B, Ws), Graph1, Graph2), !, N1 is N - 1, update_graph(N1, I, [g(A,[B|Vs]),g(B,[A|Ws])|Graph2], Graph). update_graph(N, I, Graph0, Graph):- update_graph(N, I, Graph0, Graph). /* remove(X, Ys, Zs) is true if Zs is the result of removing one */ /* occurrence of the element X from the list Ys. */ %remove(X, [X|Ys], Ys). %remove(X, [Y|Ys], [Y|Zs]):-remove(X, Ys, Zs).