0001 function [elist, exists] = euler_trail(g)
0002
0003
0004
0005
0006
0007
0008 n = nv(g);
0009 d = deg(g);
0010 d = mod(d,2);
0011 if sum(d) > 2
0012 elist = [];
0013 exists = 0;
0014 return
0015 end
0016
0017
0018
0019 if ne(g) == 0
0020 elist = [];
0021 exists = 1;
0022 return
0023 end
0024
0025
0026
0027 c = components(g);
0028 nc = np(c);
0029 c = parts(c);
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
0044
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
0056 h = graph;
0057 copy(h,g);
0058
0059
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
0070 if (mod(length(next),2) == 0) | (length(next) == 1)
0071 w = next(1);
0072 else
0073 for w=next
0074
0075 delete(h,v,w);
0076 if (has_path(h,v,w))
0077 break
0078 else
0079 add(h,v,w)
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;