0001 function [hlist, exists] = hamiltonian_cycle(g,h)
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011 if (nargin > 1)
0012 [hlist, exists] = hamiltonian_cycle(h);
0013 if (exists)
0014 n = nv(h);
0015 copy(g,h);
0016 clear_edges(g);
0017 for k=1:n-1
0018 add(g,hlist(k),hlist(k+1));
0019 end
0020 add(g,hlist(1),hlist(n));
0021 end
0022 return;
0023 end
0024
0025 n = nv(g);
0026 used = logical(zeros(n,1));
0027 path = zeros(n,1);
0028
0029
0030 if nv(g) == 0
0031 hlist = [];
0032 exists = true;
0033 return
0034 end
0035
0036
0037
0038
0039 c = components(g);
0040 if np(c) > 1
0041 hlist = [];
0042 exists = false;
0043 return
0044 end
0045
0046
0047 used(1) = true;
0048 path(1) = 1;
0049
0050
0051 [hlist,exists] = extend(g,1,n,used,path);
0052 return
0053
0054
0055
0056 function [hlist, exists] = extend(g,i,n,used,path)
0057
0058 for j=neighbors(g,path(i))
0059 if used(j)==false
0060 path(i+1) = j;
0061 used(j) = true;
0062 if ((i+1==n) & (has(g,j,path(1))))
0063 hlist = path;
0064 exists = true;
0065 return
0066 else
0067 [hlist,exists] = extend(g,i+1,n,used,path);
0068 if exists
0069 return
0070 end
0071 end
0072 used(j) = false;
0073 end
0074 end
0075 hlist = [];
0076 exists = false;
0077 return
0078