Reputation: 673
Search in multidimensional array recursive for key/value pair and return the path
i am working on a navigation structure. i am using the parent-model, so i put all the child-navigation-nodes into a array and append them to the parent navigation.
the array structure looks like this:
$navigation = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '4',
'parent_id' => '3',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
1 =>
array(
'id' => '6',
'parent_id' => '0',
'name' => 'Foobar',
'subNavigation' =>
array(
0 => array(
'id' => '7',
'parent_id' => '6',
'name' => 'ASDF',
'subNavigation' =>
array(),
),
),
),
);
now i want to search for a navigation-ID for example ID = 5 (Navigation-Name = bar) and the result should be a array to this child navigation.
the result:
$result = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
);
what is the fastest way and which recursive function will do this job?
Edit: i edit the parent_id of the navigation-node 5 ... where was a wrong parent_id
Upvotes: 1
Views: 350
Answers (1)
Reputation: 1169
Very interesting question. Here's a solution:
function search($navitation_tree, $id, $temp_branch = array()) {
for ($i = 0; $i < sizeof($navitation_tree); $i++) {
$nav_element = $navitation_tree[$i];
if($nav_element['parent_id'] === '0') {
$temp_branch = array();
} else if($i > 0) {
for ($y = 0; $y < 1; $y++) {
array_pop($temp_branch);
}
}
$cloned_nav_element = array('id' => $nav_element['id'],
'parent_id' => $nav_element['parent_id'],
'name' => $nav_element['name'],
'subNavigation' => array());
$temp_branch[] = $cloned_nav_element;
if($nav_element['id'] === $id) {
return $temp_branch;
}
if(sizeof($nav_element['subNavigation'] > 0)) {
$result = search($nav_element['subNavigation'], $id, $temp_branch);
}
if($result != null) {
return $result;
}
}
}
function getNavigationBranch($navitation_tree, $id) {
$branch = search($navitation_tree, $id);
if($branch !== null) {
$final_nav_element = array();
foreach($branch as $temp_nav_element) {
if(empty($final_nav_element)) {
$final_nav_element = array(array_pop($branch));
} else {
$temp_nav_element = array_pop($branch);
$temp_nav_element['subNavigation'] = $final_nav_element;
$final_nav_element = array($temp_nav_element);
}
}
return $final_nav_element;
}
}
$result = getNavigationBranch($navigation, '5');
The search function performs a depth-first search (DFS) into the navigation tree. As soon as it locates the desired id, it returns the path (represented by an ordered array of navigation elements) to the getNavigationBranch, which re-constructs the data to the format you requested in your question, and returns them (it will return null if the id is not found.
By the way, although DFS can have issues when searching in large graphs, but I think it will work fine for (if not all then) most of the cases of a navigation tree.
To test it, I used the following data:
$navigation = array(
0 =>
array(
'id' => '2',
'parent_id' => '0',
'name' => 'abouts us',
'subNavigation' =>
array(
0 => array(
'id' => '3',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '4',
'parent_id' => '3',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '5',
'parent_id' => '3',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
1 => array(
'id' => '8',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '9',
'parent_id' => '8',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '10',
'parent_id' => '8',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
2 => array(
'id' => '11',
'parent_id' => '2',
'name' => 'Foo',
'subNavigation' =>
array(
0 => array(
'id' => '12',
'parent_id' => '8',
'name' => 'test',
'subNavigation' =>
array(),
),
1 => array(
'id' => '13',
'parent_id' => '8',
'name' => 'bar',
'subNavigation' =>
array(),
),
),
),
),
),
1 =>
array(
'id' => '6',
'parent_id' => '0',
'name' => 'Foobar',
'subNavigation' =>
array(
0 => array(
'id' => '7',
'parent_id' => '6',
'name' => 'ASDF',
'subNavigation' =>
array(),
),
),
),
);
Here are a couple of test results:
$result = getNavigationBranch($navigation, '5');
var_dump($result);
The above produces:
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "2"
["parent_id"]=>
string(1) "0"
["name"]=>
string(9) "abouts us"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "3"
["parent_id"]=>
string(1) "2"
["name"]=>
string(3) "Foo"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "5"
["parent_id"]=>
string(1) "3"
["name"]=>
string(3) "bar"
["subNavigation"]=>
array(0) {
}
}
}
}
}
}
}
And another one:
$result = getNavigationBranch($navigation, '13');
var_dump($result);
The above produces:
array(1) {
[0]=>
array(4) {
["id"]=>
string(1) "2"
["parent_id"]=>
string(1) "0"
["name"]=>
string(9) "abouts us"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(2) "11"
["parent_id"]=>
string(1) "2"
["name"]=>
string(3) "Foo"
["subNavigation"]=>
array(1) {
[0]=>
array(4) {
["id"]=>
string(2) "13"
["parent_id"]=>
string(1) "8"
["name"]=>
string(3) "bar"
["subNavigation"]=>
array(0) {
}
}
}
}
}
}
}
Upvotes: 1
Related Questions
- Filter a 2d array to only keep rows with a specified value in a specified column
- Search a multidimensional array by key in PHP
- PHP - Searching a multidimensional array and returning a reference to the result
- Searching for key in multidimensional array and returning path to it
- PHP recursive array searching
- recursive multiple match in multidimensional php array
- Searching for a value and returning its path in a nested associative array in PHP
- Recursive search return all keys where value is present
- How to make an Array Find function recursive
- Search array path with related values