如何在PHP中打印每个子节点和孙子节点旁边的最高级父节点

Question

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.

Answer 1

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