By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,853 Members | 1,027 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,853 IT Pros & Developers. It's quick & easy.

Multidimensional array - search for relationships

P: n/a
Hi All,
I have a multidimensional array where each sub-array contains just two
entries, which indicates a relationship between those two entries. for
example the first sub-array:
[0] =Array
(
[0] =30
[1] =31
)

This states that value 30 is related to 31. I would like to search
through the entire multidimensional array (it could be empty or
contain hundreds of entries), to see if multiple relationships exist
and hence group these relationships into one entry. so for the array
below:

Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
)

[2] =Array
(
[0] =29
[1] =27
)

[3] =Array
(
[0] =29
[1] =28
)

[4] =Array
(
[0] =26
[1] =27
)

[5] =Array
(
[0] =27
[1] =28
)
)

This should be represented as:
Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
[2] =27
[3] =28
)
)

I am new enough to PHP so I would appreciate your help.
Thanks

Dec 2 '07 #1
Share this Question
Share on Google+
5 Replies


P: n/a
MW
LittleCake wrote:
Hi All,
I have a multidimensional array where each sub-array contains just two
entries, which indicates a relationship between those two entries. for
example the first sub-array:
[0] =Array
(
[0] =30
[1] =31
)

This states that value 30 is related to 31. I would like to search
through the entire multidimensional array (it could be empty or
contain hundreds of entries), to see if multiple relationships exist
and hence group these relationships into one entry. so for the array
below:

Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
)

[2] =Array
(
[0] =29
[1] =27
)

[3] =Array
(
[0] =29
[1] =28
)

[4] =Array
(
[0] =26
[1] =27
)

[5] =Array
(
[0] =27
[1] =28
)
)

This should be represented as:
Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
[2] =27
[3] =28
)
)

I am new enough to PHP so I would appreciate your help.
Thanks
while not exactly your solution, the following code will parse the first
array to another array that looks like:

Array
(
[29] =Array
(
[0] =26
[1] =27
[2] =28
)

[30] =Array
(
[0] =31
)
)

i.e. the array index would be the index term, and the sub-array would
contain all the terms that are related to the index term.

$result_array=array();
foreach ($master_array as $sub_array)
$result_array[{$sub_array[0]}][]=$sub_array[1];
MW
Dec 2 '07 #2

P: n/a
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; }
//Example usage:
$aEdges = array(array (30, 31), array (29, 26),
array (29, 27), array (29, 28),
array (26, 27), array (27, 28));
$aComponents = connectedComponents ($aEdges);
//Example 2:
$aEdges = array(
array (a, b), array (b, d), array (b, e),
array (d, g), array (c, i), array (e, h),
array (h, j), array (c, f), array (f, i),
array (g, j), array (j, k), array(j, b));
$aComponents = connectedComponents ($aEdges);

On Dec 2, 6:33 pm, LittleCake <shaneda...@gmail.comwrote:
Hi All,
I have a multidimensional array where each sub-array contains just two
entries, which indicates a relationship between those two entries. for
example the first sub-array:
[0] =Array
(
[0] =30
[1] =31
)

This states that value 30 is related to 31. I would like to search
through the entire multidimensional array (it could be empty or
contain hundreds of entries), to see if multiple relationships exist
and hence group these relationships into one entry. so for the array
below:

Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
)

[2] =Array
(
[0] =29
[1] =27
)

[3] =Array
(
[0] =29
[1] =28
)

[4] =Array
(
[0] =26
[1] =27
)

[5] =Array
(
[0] =27
[1] =28
)
)

This should be represented as:
Array
(
[0] =Array
(
[0] =30
[1] =31
)

[1] =Array
(
[0] =29
[1] =26
[2] =27
[3] =28
)
)

I am new enough to PHP so I would appreciate your help.
Thanks
Dec 2 '07 #3

P: n/a
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))]);
Dec 3 '07 #4

P: n/a
On Dec 2, 9:24 pm, MW <m...@w.invalidwrote:
LittleCake wrote:
Hi All,
I have a multidimensional array where each sub-array contains just two
entries, which indicates a relationship between those two entries. for
example the first sub-array:
[0] =Array
(
[0] =30
[1] =31
)
This states that value 30 is related to 31. I would like to search
through the entire multidimensional array (it could be empty or
contain hundreds of entries), to see if multiple relationships exist
and hence group these relationships into one entry. so for the array
below:
Array
(
[0] =Array
(
[0] =30
[1] =31
)
[1] =Array
(
[0] =29
[1] =26
)
[2] =Array
(
[0] =29
[1] =27
)
[3] =Array
(
[0] =29
[1] =28
)
[4] =Array
(
[0] =26
[1] =27
)
[5] =Array
(
[0] =27
[1] =28
)
)
This should be represented as:
Array
(
[0] =Array
(
[0] =30
[1] =31
)
[1] =Array
(
[0] =29
[1] =26
[2] =27
[3] =28
)
)
I am new enough to PHP so I would appreciate your help.
Thanks

while not exactly your solution, the following code will parse the first
array to another array that looks like:

Array
(
[29] =Array
(
[0] =26
[1] =27
[2] =28
)

[30] =Array
(
[0] =31
)
)

i.e. the array index would be the index term, and the sub-array would
contain all the terms that are related to the index term.

$result_array=array();
foreach ($master_array as $sub_array)
$result_array[{$sub_array[0]}][]=$sub_array[1];

MW
Thanks for your reply, it was much appreciated.
Keep the flag flying.
Shane
Dec 3 '07 #5

P: n/a
On Dec 3, 1:33 pm, Csaba Gabor <cs...@z6.comwrote:
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
Dec 3 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.