Description of bipartition

Home > matgraph > @graph > bipartition.m

bipartition

PURPOSE

part = bipartition(g) --- find bipartition of a bipartite graph

SYNOPSIS

function p = bipartition(g)

DESCRIPTION

 part = bipartition(g) --- find bipartition of a bipartite graph
 If the graph is bipartite, this function finds a bipartition X,Y of the
 vertex set; these are returned in a partition object.
 If the graph is not bipartite, an empty partition is returned.

CROSS-REFERENCE INFORMATION

This function calls:

• components components(g) --- find the components of the graph g
• matrix matrix(g) --- return (a copy of) the adjacency matrix of g
• ne ne(g) --- number of edges in g or ne(g,h) --- check for inequality
• nv nv(g) --- number of vertices in g

This function is called by:

SOURCE CODE

0001 function p = bipartition(g)
0002 % part = bipartition(g) --- find bipartition of a bipartite graph
0003 % If the graph is bipartite, this function finds a bipartition X,Y of the
0004 % vertex set; these are returned in a partition object.
0005 % If the graph is not bipartite, an empty partition is returned.
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);  % convert to cell array
0027 
0028 % set up the X-seed vector
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 % kludge to deal with isolated vertices
0048 %idx = find((x==0)&(y==0));
0049 %if ~isempty(idx)
0050 %    x(idx) = 1;
0051 %end
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

---

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