I have a PHP code which enables me to create an array of Parent nodes mapped with child nodes and grand child nodes. Here is the code that i used:
<?php
function parent_map( &$a, $parent_key, $children_key )
{
$orphans = true; $i;
while( $orphans )
{
$orphans = false;
foreach( $a as $k=>$v )
{
// is there $a[$k] sons?
$sons = false;
foreach( $a as $x=>$y )
if( isset($y[$parent_key]) and $y[$parent_key]!=false and $y[$parent_key]==$k )
{
$sons=true;
$orphans=true;
break;
}
// $a[$k] is a son, without children, so i can move it
if( !$sons and isset($v[$parent_key]) and $v[$parent_key]!=false )
{
$a[$v[$parent_key]][$children_key][$k] = $v;
unset( $a[$k] );
}
}
}
}
$ARRAY = array(
1 => array( 'label' => "A" ),
2 => array( 'label' => "B" ),
3 => array( 'label' => "C" ),
4 => array( 'label' => "D" ),
5 => array( 'label' => "one", 'father' => '1' ),
6 => array( 'label' => "two", 'father' => '1' ),
7 => array( 'label' => "three", 'father' => '1' ),
8 => array( 'label' => "node 1", 'father' => '2' ),
9 => array( 'label' => "node 2", 'father' => '2' ),
10 => array( 'label' => "node 3", 'father' => '2' ),
11 => array( 'label' => "I", 'father' => '9' ),
12 => array( 'label' => "II", 'father' => '9' ),
13 => array( 'label' => "III", 'father' => '9' ),
14 => array( 'label' => "IV", 'father' => '9' ),
15 => array( 'label' => "V", 'father' => '9' ),
);
parent_map( $ARRAY, 'father', 'children' );
echo "<pre>"; print_r( $ARRAY);
?>
This is able to give me a tree structure of the parent nodes and their child nodes and the child node's children and so on.
What i needed is data transformed from this form:
Parent Child
AAA BBB
AAA CCC
AAA DDD
BBB EEE
BBB FFF
CCC GGG
FFF HHH
III JJJ
JJJ KKK
JJJ LLL
to this form:
Node 1st Level Node
AAA Root
BBB AAA
CCC AAA
DDD AAA
EEE AAA
FFF AAA
GGG AAA
HHH AAA
III Root
JJJ III
KKK III
LLL III
in essence I wish to populate the child nodes with their respective highest level roots nodes such that all child nodes have a root level data/parent mapped to them.
I have tried using VBA in excel which works but hangs in large data sets. a solution to that is taking all data in at once and write out together but im not looking at a Macros solution.
here is my VBA code:
Option Explicit
Sub Main_Function_SuperManager()
Dim i, re
Root_Parent
Replace
Replace_Name
i = 1
While Cells(i, 22) <> ""
Cells(i, 22) = ""
Cells(i, 23) = ""
i = i + 1
Wend
End Sub
Sub Root_Parent()
Dim i, re, k
i = 2
While Cells(i, 1) <> ""
Set re = Range("B:B").Find(Cells(i, 1))
If re Is Nothing Then
Set re = Range("V:V").Find(Cells(i, 1))
If re Is Nothing Then
k = k + 1
Cells(k, 22) = Cells(i, 1)
Cells(k, 23) = "Super Manager"
findchild Cells(k, 22).Value, k
End If
End If
i = i + 1
Wend
End Sub
Sub findchild(parent, ByRef k)
Dim i, s, re
i = 1
While Cells(i, 2) <> ""
s = i
Do
Set re = Range("B:B").Find(Cells(s, 1))
If re Is Nothing Then
If Cells(s, 1) = parent Then
k = k + 1
Cells(k, 22) = Cells(i, 2)
Cells(k, 23) = Cells(s, 1)
End If
Exit Do
Else
s = re.Row
End If
Loop
i = i + 1
Wend
End Sub
Sub Replace()
Dim i, re, s
i = 2
While Cells(i, 22) <> ""
Set re = Range("B:B").Find(Cells(i, 22))
If re Is Nothing Then
Cells(10, 24) = ""
Else
s = re.Row
Cells(s, 19) = Cells(i, 23)
End If
i = i + 1
Wend
End Sub
Sub Replace_Name()
Dim i, re, s
i = 2
While Cells(i, 19) <> ""
Set re = Worksheets("Sheet2").Range("A:A").Find(Cells(i, 19))
If re Is Nothing Then
Cells(10, 24) = ""
Else
s = re.Row
Cells(i, 20) = Worksheets("Sheet2").Cells(s, 2)
End If
i = i + 1
Wend
End Sub
I'm hoping i can transform the same functionality into PHP. I shall populate the array from the DB but how to create a list of Unique ids/children to their highest level parent/ super parent node is something im unable to figure out.
Looking forward to advice on the same. Thanks in advance.
You should probably use Disjoint-set data structure. Each node in this data structure holds a reference to its parent and each set will be represented by its root node. If you use this algorithm along with path compression improvement, the final parent array will be exactly what you want.
For this problem you should first initialize parent array like this:
parent[A] = A
parent[B] = B
...
then write the find function which recursively finds the root of each set and assigns that as the parent of the all the nodes in the path:
function find(x)
if parent[x] == x: // x is root
return x
root = find(parent[x])
parent[x] = root
Next step is to process the edges
for each U->V
parent[V] = find(U) // finds the root of the tree that U belongs to
// and assign that as parent of V
A->B, find(A)=A, parent[B] <- A
A->C, find(A)=A, parent[C] <- A
A->D, find(A)=A, parent[D] <- A
B->E, find(B)=A, parent[E] <- A
B->F, find(B)=A, parent[F] <- A
C->G, find(C)=A, parent[G] <- A
F->H, find(C)=A, parent[F] <- H
I->J, find(I)=I, parent[J] <- I
J->K, find(J)=I, parent[K] <- J
J->L, find(J)=I, parent[L] <- J
Alter table it should be look like below
CREATE TABLE `parent_child` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`parent` varchar(255) DEFAULT NULL,
`child` varchar(255) DEFAULT NULL,
`parent_id` int(11) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=9 DEFAULT CHARSET=latin1
Create function for getting parent child element
DELIMITER $$
USE `yourdatabase`$$
DROP FUNCTION IF EXISTS `GetAllNode1`$$
CREATE DEFINER=`root`@`localhost` FUNCTION `GetAllNode1`(GivenID INT) RETURNS TEXT CHARSET latin1
DETERMINISTIC
BEGIN
DECLARE rv,q,queue,queue_children TEXT;
DECLARE queue_length,front_id,pos INT;
SET rv = '';
SET queue = GivenID;
SET queue_length = 1;
WHILE queue_length > 0 DO
SET front_id = queue;
IF queue_length = 1 THEN
SET queue = '';
ELSE
SET pos = LOCATE(',',queue) + 1;
SET q = SUBSTR(queue,pos);
SET queue = q;
END IF;
SET queue_length = queue_length - 1;
SELECT IFNULL(qc,'') INTO queue_children
FROM (SELECT GROUP_CONCAT(id) AS qc
FROM `parent_child` WHERE `parent_id` = front_id) A ;
IF LENGTH(queue_children) = 0 THEN
IF LENGTH(queue) = 0 THEN
SET queue_length = 0;
END IF;
ELSE
IF LENGTH(rv) = 0 THEN
SET rv = queue_children;
ELSE
SET rv = CONCAT(rv,',',queue_children);
END IF;
IF LENGTH(queue) = 0 THEN
SET queue = queue_children;
ELSE
SET queue = CONCAT(queue,',',queue_children);
END IF;
SET queue_length = LENGTH(queue) - LENGTH(REPLACE(queue,',','')) + 1;
END IF;
END WHILE;
RETURN rv;
END$$
DELIMITER ;
write query for desire output
SELECT GetAllNode1(id) FROM parent_child
or
SELECT GetAllNode1(id) FROM parent_child where id =1 //for specific parent's child element