Convert a series of parent-child relationships into a hierarchical tree?
This requires a very basic recursive function to parse the child/parent pairs to a tree structure and another recursive function to print it out. Only one function would suffice but here's two for clarity (a combined function can be found at the end of this answer).
First initialize the array of child/parent pairs:
$tree = array(
'H' => 'G',
'F' => 'G',
'G' => 'D',
'E' => 'D',
'A' => 'E',
'B' => 'C',
'C' => 'E',
'D' => null
);
Then the function that parses that array into a hierarchical tree structure:
function parseTree($tree, $root = null) {
$return = array();
# Traverse the tree and search for direct children of the root
foreach($tree as $child => $parent) {
# A direct child is found
if($parent == $root) {
# Remove item from tree (we don't need to traverse this again)
unset($tree[$child]);
# Append the child into result array and parse its children
$return[] = array(
'name' => $child,
'children' => parseTree($tree, $child)
);
}
}
return empty($return) ? null : $return;
}
And a function that traverses that tree to print out an unordered list:
function printTree($tree) {
if(!is_null($tree) && count($tree) > 0) {
echo '<ul>';
foreach($tree as $node) {
echo '<li>'.$node['name'];
printTree($node['children']);
echo '</li>';
}
echo '</ul>';
}
}
And the actual usage:
$result = parseTree($tree);
printTree($result);
Here's the contents of $result:
Array(
[0] => Array(
[name] => D
[children] => Array(
[0] => Array(
[name] => G
[children] => Array(
[0] => Array(
[name] => H
[children] => NULL
)
[1] => Array(
[name] => F
[children] => NULL
)
)
)
[1] => Array(
[name] => E
[children] => Array(
[0] => Array(
[name] => A
[children] => NULL
)
[1] => Array(
[name] => C
[children] => Array(
[0] => Array(
[name] => B
[children] => NULL
)
)
)
)
)
)
)
)
If you want a bit more efficiency, you can combine those functions into one and reduce the number of iterations made:
function parseAndPrintTree($root, $tree) {
$return = array();
if(!is_null($tree) && count($tree) > 0) {
echo '<ul>';
foreach($tree as $child => $parent) {
if($parent == $root) {
unset($tree[$child]);
echo '<li>'.$child;
parseAndPrintTree($child, $tree);
echo '</li>';
}
}
echo '</ul>';
}
}
You'll only save 8 iterations on a dataset as small as this but on bigger sets it could make a difference.
Convert a series of parent-child relationships into a tree?
If I understand your problem correctly, this should work.
Notice how I call the orderMe function inside the function to make it recursive.
function orderMe($input, $parentId)
{
$return = array($parentId => array('itemGroupID' => $parentId));
$childs = array();
foreach ($input as $i)
{
if ($i['itemGroupID'] == $parentId)
{
$return[$i['itemGroupID']]['children'][$i['childItemGroupID']] = array('itemGroupID' => $i['childItemGroupID']);
$childs[] = $i['childItemGroupID'];
}
if (in_array($i['childItemGroupID'], $childs))
{
$allChilds = orderMe($input, $i['childItemGroupID']);
if (!empty($allChilds[$i['childItemGroupID']]['children']))
$return[$i['itemGroupID']]['children'][$i['childItemGroupID']] = $allChilds;
}
}
return $return;
}
print_r(orderMe($input, 1));
Outputs:
array (
1 =>
array (
'itemGroupID' => 1,
'children' =>
array (
2 =>
array (
'itemGroupID' => 2,
),
3 =>
array (
'itemGroupID' => 3,
),
4 =>
array (
'itemGroupID' => 4,
),
212 =>
array (
'itemGroupID' => 212,
),
339 =>
array (
'itemGroupID' => 339,
),
336 =>
array (
'itemGroupID' => 336,
),
6 =>
array (
6 =>
array (
'itemGroupID' => 6,
'children' =>
array (
8 =>
array (
'itemGroupID' => 8,
),
9 =>
array (
9 =>
array (
'itemGroupID' => 9,
'children' =>
array (
15 =>
array (
'itemGroupID' => 15,
),
),
),
),
10 =>
array (
10 =>
array (
'itemGroupID' => 10,
'children' =>
array (
16 =>
array (
'itemGroupID' => 16,
),
),
),
),
11 =>
array (
11 =>
array (
'itemGroupID' => 11,
'children' =>
array (
17 =>
array (
'itemGroupID' => 17,
),
),
),
),
12 =>
array (
12 =>
array (
'itemGroupID' => 12,
'children' =>
array (
18 =>
array (
'itemGroupID' => 18,
),
),
),
),
13 =>
array (
13 =>
array (
'itemGroupID' => 13,
'children' =>
array (
19 =>
array (
'itemGroupID' => 19,
),
),
),
),
74 =>
array (
74 =>
array (
'itemGroupID' => 74,
'children' =>
array (
75 =>
array (
'itemGroupID' => 75,
),
),
),
),
),
),
),
5 =>
array (
'itemGroupID' => 5,
),
),
),
)
How can I convert a hierarchical tree to parent-child relationships?
For those who are interested in my final code. It works for storing the data in the database and build it again into a hierarchical tree + a printable tree for HTML.
JavaScript code for the nestable plugin:
var nestable_update = function(e){
$(".dd-item").each(function(index){
$(this).data("id", index+1);
});
var list = e.length ? e : $(e.target),
output = list.data("output");
if (window.JSON) {
output.val(window.JSON.stringify(list.nestable("serialize")));
} else {
output.val("JSON browser support required for this demo.");
}
};
$(".dd").nestable({
maxDepth:5
}).on("change", nestable_update);
nestable_update($(".dd").data("output", $("#nestable_output")));
Database structure:
menuitem_id
menu_id
menuitem_order
menuitem_name
menuitem_page_id
parent_menuitem_id
PHP functions for building trees (format storing data in database + format getting data from database):
function create_flatten_hierarchical_tree($tree, $parent_id=0) {
$items = array();
foreach ($tree as $item) {
$items[] = array("id" => $item["id"], "parent_id" => $parent_id);
if (isset($item["children"])) $items = array_merge($items, create_flatten_hierarchical_tree($item["children"], $item["id"]));
}
return $items;
}
function create_hierarchical_tree($tree, $root=0) {
$return = array();
foreach($tree as $child => $parent) {
if($parent["parent_menuitem_id"] == $root) {
if(isset($tree[$child]["menuitem_id"]) === true){
$parent['children'] = create_hierarchical_tree($tree, $tree[$child]["menuitem_id"]);
}
unset($tree[$child]);
$return[] = $parent;
}
}
return empty($return) ? null : $return;
}
function print_hierarchical_tree($tree, $rows_pages) {
if(!is_null($tree) && count($tree) > 0) {
$return .= "<ol class='dd-list'>";
foreach($tree as $item){
$options = "";
foreach($rows_pages as $row_pages){
$selected = "";
if($row_pages["page_id"] == $item["menuitem_page_id"]){
$selected = "selected";
}
$options .= "<option value='".$row_pages["page_id"]."' $selected>".$row_pages["friendly_url"]."</option>";
}
$return .= "<li class='dd-item' data-id='".$item["menuitem_id"]."'><div class='dd-handle'>drag</div><div class='item_wrapper'><div class='item'><div class='item_title'>".$item["menuitem_name"]."</div></div><div class='item_sub'><div class='label_input'><label for='menuitem_name".$item["menuitem_id"]."'>Menuitem name</label><input type='text' id='menuitem_name".$item["menuitem_id"]."' name='menuitem_name[]' value='".$item["menuitem_name"]."' /></div><div class='label_input'><label for='page_link".$item["menuitem_id"]."'>Page link</label><label class='select'><select id='page_link".$item["menuitem_id"]."' name='menuitem_page_id[]'>".$options."</select></label></div> <a onClick='delete_menuitem(".$item["menuitem_id"].");' class='button red_bg delete'>Delete</a></div></div>";
$return .= print_hierarchical_tree($item["children"], $rows_pages);
$return .= "</li>";
}
$return .= "</ol>";
}
return empty($return) ? null : $return;
}
Core code of menu_edit.php page:
<?php
$stmt_menuitems = $dbh->prepare("SELECT * FROM inno_mw_thurs_menuitems mi WHERE mi.menu_id=:menu_id");
$stmt_menuitems->bindParam(":menu_id", $_GET["menu_id"]);
$stmt_menuitems->execute();
if (!empty($stmt_menuitems->rowCount())) {
?>
<div class="dd">
<?php
$result = $stmt_menuitems->fetchAll();
$tree = create_hierarchical_tree($result);
$stmt_pages = $dbh->prepare("SELECT * FROM inno_mw_thurs_pages");
$stmt_pages->execute();
$rows_pages = $stmt_pages->fetchAll();
$tree = print_hierarchical_tree($tree, $rows_pages);
echo $tree;
?>
</div>
<?php
}
Core code of menu_edit_process.php page:
if(isset($_POST["menu_id"])){
$menu_id = $_POST["menu_id"];
$nestable_output = json_decode($_POST["nestable_output"], true);
$parent_menuitem_ids_arr = create_flatten_hierarchical_tree($nestable_output);
$stmt = $dbh->prepare("TRUNCATE TABLE inno_mw_thurs_menuitems");
$stmt->execute();
$stmt = $dbh->prepare("INSERT INTO inno_mw_thurs_menuitems (menu_id, menuitem_order, menuitem_name, menuitem_page_id, parent_menuitem_id) VALUES (:menu_id, :menuitem_order, :menuitem_name, :menuitem_page_id, :parent_menuitem_id)");
$menuitem_order_arr = array();
foreach($_POST["menuitem_name"] as $f => $name){
$menuitem_name = $_POST["menuitem_name"][$f];
$menuitem_page_id = $_POST["menuitem_page_id"][$f];
$parent_menuitem_id = $parent_menuitem_ids_arr[$f]["parent_id"];
if(array_key_exists($parent_menuitem_id, $menuitem_order_arr) && $parent_menuitem_id != 0){
$menuitem_order_arr[$parent_menuitem_id] += 1;
}
else{
$menuitem_order_arr[$parent_menuitem_id] = 0;
}
$stmt->bindParam(":menu_id", $menu_id);
$stmt->bindParam(":menuitem_order", $menuitem_order_arr[$parent_menuitem_id]);
$stmt->bindParam(":menuitem_name", $menuitem_name);
$stmt->bindParam(":menuitem_page_id", $menuitem_page_id);
$stmt->bindParam(":parent_menuitem_id", $parent_menuitem_id);
$stmt->execute();
}
header("location: menus_list.php");
}
Please, feel free to improve this code.
How to flatten a hierarchical data structure given parent child relationships in R
I would think about it like a graph problem. There are 2 changes to make to the original data to fit this approach: switch the order of columns to show the hierarchical direction (parent to child), and add a top-level node (I'm calling it "Items") that links to the major groups (food & not food). You could probably do that second part programmatically but it seems like more of a pain than it's worth.
library(dplyr)
df <- tibble::tribble(
~Child, ~Parent,
"Fruit", "Food",
"Vegetable", "Food",
"Apple", "Fruit",
"Banana", "Fruit",
"Pear", "Fruit",
"Carrot", "Vegetable",
"Celery", "Vegetable",
"Bike", "Not Food",
"Car", "Not Food"
) %>%
select(Parent, Child) %>%
add_row(Parent = "Items", Child = c("Food", "Not Food"))
The first method is with data.tree, which is designed to work with this type of data. It creates a tree representation, which you can then convert back to a data frame with one of a few shapes.
library(data.tree)
g1 <- FromDataFrameNetwork(df)
g1
#> levelName
#> 1 Items
#> 2 ¦--Food
#> 3 ¦ ¦--Fruit
#> 4 ¦ ¦ ¦--Apple
#> 5 ¦ ¦ ¦--Banana
#> 6 ¦ ¦ °--Pear
#> 7 ¦ °--Vegetable
#> 8 ¦ ¦--Carrot
#> 9 ¦ °--Celery
#> 10 °--Not Food
#> 11 ¦--Bike
#> 12 °--Car
ToDataFrameTypeCol(g1)
#> level_1 level_2 level_3 level_4
#> 1 Items Food Fruit Apple
#> 2 Items Food Fruit Banana
#> 3 Items Food Fruit Pear
#> 4 Items Food Vegetable Carrot
#> 5 Items Food Vegetable Celery
#> 6 Items Not Food Bike <NA>
#> 7 Items Not Food Car <NA>
The second method is more convoluted and probably only makes sense if there are other graph operations you need to do. Make a graph with igraph, then get all the paths in the graph starting from the top node Items. That gives you a list of vertex objects; for each of those, extract IDs. One example of those is below.
library(igraph)
g2 <- graph_from_data_frame(df)
all_simple_paths(g2, from = "Items") %>%
purrr::map(as_ids) %>%
`[[`(4)
#> [1] "Items" "Food" "Fruit" "Banana"
Create data frames from all those vectors, bind, and reshape to get one column per level.
all_simple_paths(g2, from = "Items") %>%
purrr::map(as_ids) %>%
purrr::map_dfr(tibble::enframe, .id = "row") %>%
tidyr::pivot_wider(id_cols = row, names_prefix = "level_")
#> # A tibble: 11 × 5
#> row level_1 level_2 level_3 level_4
#> <chr> <chr> <chr> <chr> <chr>
#> 1 1 Items Food <NA> <NA>
#> 2 2 Items Food Fruit <NA>
#> 3 3 Items Food Fruit Apple
#> 4 4 Items Food Fruit Banana
#> 5 5 Items Food Fruit Pear
#> 6 6 Items Food Vegetable <NA>
#> 7 7 Items Food Vegetable Carrot
#> 8 8 Items Food Vegetable Celery
#> 9 9 Items Not Food <NA> <NA>
#> 10 10 Items Not Food Bike <NA>
#> 11 11 Items Not Food Car <NA>
In either case, drop the level 1 column if you don't actually want it.
Converting parent-child relations into a tree with attributes
Apparantly you just add a vector with the columns that you want to include.
tree <- FromDataFrameNetwork(data, c("FolderName", "Values1", "Values2"))
> print(tree, "FolderName", "Values2", "Values1")
levelName FolderName Values2 Values1
1 a NA NA
2 °--b N1 2 1
3 ¦--d N2 1 2
4 °--e N3 4 3
5 °--f N4 2 4
Turning a set of parent-child relationships into a hierarchical structure
What you need is a directed graph, and I suggest using the Graph::Directed module, whose methods are documented in Graph
This program will build the graph for you, but without any data I couldn't test it beyond making sure it compiles
use strict;
use warnings 'all';
use feature 'say';
use Net::LDAP;
use Graph::Directed;
use Data::Dumper;
my $ldap = Net::LDAP->new('my_ldap_server');
my $result = $ldap->bind('bind_dn');
die if $result->code;
my $search = $ldap->search(
base => 'ou=yaddayadda',
scope => 'subtree',
filter => 'objectClass=person',
attrs => ['manager'],
);
my $g = Graph::Directed->new;
for my $found ( $search->entries ) {
my $mgr = $found->get_value('manager');
my $dn = $result->dn;
$g->add_edge($mgr, $dn);
}
say $g;
The resulting Graph::Directed object has a stringification overload so you can examine it superficially by simply printing it, but when you want to interrogate the structure further you will need to know some of the terms of graph theory. For instance, $g->source_vertices will return a list of all nodes that have descendants but no parents—in this case, a list of senior management, or $g->is_cyclic will return true if your data has any loops anywhere
Here's an example of a program that uses your brief sample data to display a hierarchical tree of nodes
use strict;
use warnings 'all';
use Graph::Directed;
my $data = {
'cn=Firstname Lastname,ou=OrgUnit' => [
'cn=Personame Lastname,ou=OrgUnit',
'cn=AnotherPerson NameHere,ou=OrgUnit',
],
'cn=AnotherPerson NameHere,ou=OrgUnit' =>
[ 'cn=Someone Else,ou=OrgUnit', ]
};
my $g = Graph::Directed->new;
for my $mgr ( keys %$data ) {
$g->add_edge($mgr, $_) for @{ $data->{$mgr} };
}
dump_tree($_) for $g->source_vertices;
sub dump_tree {
my ($node, $level) = ( @_, 0);
print ' ' x $level, $node, "\n";
dump_tree($_, $level+1) for $g->successors($node);
}
output
cn=Firstname Lastname,ou=OrgUnit
cn=AnotherPerson NameHere,ou=OrgUnit
cn=Someone Else,ou=OrgUnit
cn=Personame Lastname,ou=OrgUnit
How to derive a parent-child table from a hierarchical table using R?
library(zoo)
library(data.table)
library(dplyr)
rbindlist(lapply(as.data.frame(rollapply(names(df), 2, c), stringsAsFactors = F),
function(x) select(df, c(x)))) %>%
distinct() %>%
`colnames<-`(c("parent", "child"))
Output is:
parent child
1: A a
2: A b
3: B c
4: B d
5: C e
6: a 1
7: a 2
8: b 3
9: c 4
10: d 5
11: e 6
Sample data:
df <- structure(list(lev1 = structure(c(1L, 1L, 1L, 2L, 2L, 3L), .Label = c("A",
"B", "C"), class = "factor"), lev2 = structure(c(1L, 1L, 2L,
3L, 4L, 5L), .Label = c("a", "b", "c", "d", "e"), class = "factor"),
lev3 = 1:6), .Names = c("lev1", "lev2", "lev3"), row.names = c(NA,
-6L), class = "data.frame")
Related Topics
What Is the Size Limit of a Post Request
Htmlentities() Vs. Htmlspecialchars()
How to Convert Xml into Array in PHP
How to Convert Json String to Array
PHP Display Image Blob from MySQL
PHP - Should I Call Exit() After Calling Location: Header
Creating Default Object from Empty Value in PHP
PHP Fatal Error: Using $This When Not in Object Context
Passing Base64 Encoded Strings in Url
How to Find Where I Will Be Redirected Using Curl in PHP
Warning: a Non-Numeric Value Encountered
Strange Behavior of Foreach When Using Reference: Foreach ($A as &$V) { ... }
How to Filter an Array by a Condition