Description of components

Home > matgraph > @graph > components.m

components

PURPOSE

components(g) --- find the components of the graph g

SYNOPSIS

function p = components(g)

DESCRIPTION

 components(g) --- find the components of the graph g
 If g has n vertices, this returns a partition of the [n] based on the
 components of g.

CROSS-REFERENCE INFORMATION

This function calls:

• component component(g,v) -- find vertices in v's component of g
• nv nv(g) --- number of vertices in g

This function is called by:

• bipartition part = bipartition(g) --- find bipartition of a bipartite graph
• euler_trail euler_trail(g) --- find an euler trail in g (if one exists)
• hamiltonian_cycle hamiltonian_cycle(g) --- find a Hamiltonian cycle in g (if one exists)
• iso [yn,p] = iso(g,h,options) --- is g isomorphic to h?

SUBFUNCTIONS

• function p = ind2part(ind)

SOURCE CODE

0001 function p = components(g)
0002 % components(g) --- find the components of the graph g
0003 % If g has n vertices, this returns a partition of the [n] based on the
0004 % components of g.
0005 
0006 n = nv(g);
0007 indicator = zeros(n,1);
0008 c = 0;
0009 
0010 while (nnz(indicator)<n)
0011     c = c+1;
0012     % find first zero entry in indicator
0013     i = find(indicator==0);
0014     i = i(1);
0015     
0016     % get i's component
0017     ci = component(g,i);
0018     
0019     indicator(ci) = c;
0020 end
0021 %p = indicator;
0022 p = ind2part(indicator);
0023 
0024 
0025 
0026 function p = ind2part(ind)
0027 % convert indicator vector to a partition
0028 
0029 np = max(ind);
0030 A = cell(np,1);
0031 for k=1:np
0032     A{k} = find(ind == k);
0033 end
0034 p = partition(A);

---

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