Home > matgraph > @graph > euler_trail.m

euler_trail

PURPOSE ^

euler_trail(g) --- find an euler trail in g (if one exists)

SYNOPSIS ^

function [elist, exists] = euler_trail(g)

DESCRIPTION ^

 euler_trail(g) --- find an euler trail in g (if one exists)
 This can be called with two output arguments: 
    [elist, exists] = euler_trail(g)
 the 2nd output argument is set to 0 if no trail exists.
 Bug fix by Brian Towne.

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [elist, exists] = euler_trail(g)
0002 % euler_trail(g) --- find an euler trail in g (if one exists)
0003 % This can be called with two output arguments:
0004 %    [elist, exists] = euler_trail(g)
0005 % the 2nd output argument is set to 0 if no trail exists.
0006 % Bug fix by Brian Towne.
0007 
0008 n = nv(g);
0009 d = deg(g);
0010 d = mod(d,2);
0011 if sum(d) > 2
0012     elist = []; % no trail possible, too many odd vertices
0013     exists = 0;
0014     return
0015 end
0016 
0017 % if there are no edges in the graph, return an empty list, too
0018 
0019 if ne(g) == 0
0020     elist = [];
0021     exists = 1;
0022     return
0023 end
0024 
0025 % we have to make sure there is exactly one nontrivial component
0026 
0027 c = components(g);
0028 nc = np(c);
0029 c = parts(c); % convert to cell array
0030 counts = zeros(nc,1);
0031 for k=1:nc
0032     counts(k) = length(c{k});
0033 end
0034 
0035 big = find(counts > 1);
0036 if (length(big) > 1)
0037     elist = [];
0038     exists = 0;
0039     return
0040 end
0041 
0042 
0043 % if there are two odd vertices, we have to start on one of those.
0044 % otherwise, we start at the first vertex in the big component.
0045 
0046 if sum(d)==2
0047     odds = find(d);
0048     start = odds(1);
0049 else
0050     start = c{big};
0051     start = start(1);
0052 end
0053 
0054 
0055 % we make an "erasable" copy of g
0056 h = graph;
0057 copy(h,g);
0058 
0059 % and now we start the tour
0060 
0061 m = ne(g);
0062 elist = zeros(m,2);
0063 step = 0;
0064 v = start;
0065 
0066 while ne(h)
0067     step = step+1;
0068     next = neighbors(h,v);
0069     % if v has even degree (or only one neighbor) any neighbor will do
0070     if (mod(length(next),2) == 0) | (length(next) == 1)
0071         w = next(1);
0072     else
0073         for w=next
0074             % make sure vw is not a cut edge
0075             delete(h,v,w);
0076             if (has_path(h,v,w))
0077                 break
0078             else
0079                 add(h,v,w) % restore the edge
0080             end
0081         end
0082     end
0083     delete(h,v,w);
0084     elist(step,:) = [v,w];
0085     v = w;
0086 end
0087 free(h)
0088 exists = 1;

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