0001 function p = bipartition(g)
0002
0003
0004
0005
0006
0007 n = nv(g);
0008
0009 if n < 2
0010 p = partition(n);
0011 return
0012 end
0013
0014 if ne(g) == 0
0015 p1 = 1:2:n;
0016 p2 = 2:2:n;
0017 p = partition({p1,p2});
0018 return
0019 end
0020
0021 c = components(g);
0022 x = zeros(n,1);
0023 y = x;
0024
0025 nc = np(c);
0026 c = parts(c);
0027
0028
0029 for k=1:nc
0030 j = min(c{k});
0031 x(j) = 1;
0032 end
0033
0034 A = matrix(g);
0035
0036 last_sum = 0;
0037 while sum(x) > last_sum
0038 last_sum = sum(x) ;
0039 xx = A*(A*x)+x;
0040 x = double(xx>0);
0041 end
0042
0043
0044 yy = A*x;
0045 y = double(yy>0);
0046
0047
0048
0049
0050
0051
0052
0053
0054
0055
0056 if sum(x) + sum(y) ~= n
0057 p = partition(0);
0058 else
0059 part = cell(1,2);
0060 part{1} = find(x)';
0061 part{2} = find(y)';
0062 p = partition(part);
0063 end