Posted by LittleCake on 12/03/07 23:22

On Dec 3, 1:33 pm, Csaba Gabor <cs...@z6.com> wrote:
> 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))]);

Thanks for that. I was getting warning "The argument should be an
array", is it to do with the reference being unset?
All in all I have a better grasp now. Thanks again.
Shane

[Back to original message]