Description of hamiltonian_cycle

Home > matgraph > @graph > hamiltonian_cycle.m

hamiltonian_cycle

PURPOSE

hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)

SYNOPSIS

function [hlist, exists] = hamiltonian_cycle(g,h)

DESCRIPTION

 hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)
 This can be called with two output arguments: 
    [hlist, exists] = hamiltonian_cycle(g)
 the 2nd output argument is set to 0 if no trail exists.
 This can also be called hamiltonian_cycle(h,g). In this case, h is
 overwritten with a Hamiltonian cycle of g (if one exists).

 The important part of this function was written by Brian Towne.

CROSS-REFERENCE INFORMATION

This function calls:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• components components(g) --- find the components of the graph g
• copy copy(g,h) --- overwrite g with a copy of h
• hamiltonian_cycle hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)
• has has --- check if the graph has a particular vertex or edge
• neighbors neighbors(g,v) --- neighbors of v as a list.
• nv nv(g) --- number of vertices in g
• path path(g,n) --- make g a path on n vertices

This function is called by:

• hamiltonian_cycle hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)

SUBFUNCTIONS

• function [hlist, exists] = extend(g,i,n,used,path)

SOURCE CODE

0001 function [hlist, exists] = hamiltonian_cycle(g,h)
0002 % hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)
0003 % This can be called with two output arguments:
0004 %    [hlist, exists] = hamiltonian_cycle(g)
0005 % the 2nd output argument is set to 0 if no trail exists.
0006 % This can also be called hamiltonian_cycle(h,g). In this case, h is
0007 % overwritten with a Hamiltonian cycle of g (if one exists).
0008 %
0009 % The important part of this function was written by Brian Towne.
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)); % used(i)==true if i is in partially constructed cycle
0027 path = zeros(n,1); % partially constructed cycle
0028 
0029 % if there are no vertices in the graph, return an empty list, too
0030 if nv(g) == 0
0031     hlist = [];
0032     exists = true;
0033     return
0034 end
0035 
0036 
0037 % We have to make sure there is exactly one component
0038 
0039 c = components(g);
0040 if np(c) > 1
0041     hlist = [];
0042     exists = false;
0043     return
0044 end
0045 
0046 % Since we are looking for a cycle, we can start w/ vertex 1 wolog:
0047 used(1) = true;
0048 path(1) = 1;
0049 
0050 % Recursively try to extend path
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

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003