Posted by Csaba Gabor on 12/03/07 13:33

Csaba Gabor wrote:
> Shane is given an edge array ($aEdges) and wants to
> know the distinct connected components. This can be done
> by my function connectedComponents($aEdges). The first
> part walks each edge once to build an adjacency array.
> The second part, which does the real work, picks an
> unvisited edge and visits each vertex it can get to from
> that selected vertex, processing each edge once, so that
> the total running time is O(E). It'd be O(V+E) for the
> second part, if singletons (isolated vertices) were
> to have been allowed.
>
> Csaba Gabor from Vienna
>
>
> function connectedComponents ($aEdges) {
> // given an edge array, $aEdges, this will return an array
> // of connected components. Each element of the returned
> // array, $aTrees, will correspond to one component and
> // have an array of the vertices in that component.
> $aAdj = array(); $aTree = array(); $ctr=-1;
> foreach ($aEdges as $br) // Construct V/E adjacancy array
> foreach ($br as $i=>$v) {
> if (!array_key_exists($v,$aAdj)) $aAdj[$v]=array($br[1-$i]);
> else array_push ($aAdj[$v], $br[1-$i]); }
>
> foreach ($aAdj as $v => &$aTrees[++$ctr]) // Now build distinct
> for ($i=0;$i<sizeof($aTrees[$ctr]);++$i) { // components
> $aV = array_keys(array_flip(array_merge(
> $aV = &$aTrees[$ctr], $aAdj[$aV[$i]])));
> unset ($aAdj[$aV[$i]]); }
>
> return $aTrees; }

Whoops, small typo, though code works as is.
In the initialization it should be $aTrees = array();



Note to self: the determine distinct connected components
section also works with:

// determine connected components from adjacency matrix:
// $aAdj: [$v => array of vertices connected to $v, ...]
foreach ($aAdj as $v => &$aTrees[++$ctr]) // Now build distinct
for ($i=0;$i<sizeof($aV=&$aTrees[$ctr]);++$i) // components
unset ($aAdj[current (array_slice(
$aV = array_keys (array_flip (array_merge(
$aV, $aAdj[$aV[$i]]))), $i, 1))]);

[Back to original message]