if input edges has repeating subtrees, how to map

问题:

a visual example of my valid tree structure is given below.

as you see I have 2 p4 subtrees at level 2.

                            level
             p1               0
             /\
            /  \
           /    \
          /      \
         /        \
        /          \
       /            \
      p2            p3        1
     /  \          /  \
    /    \        /    \
   p4     c3     p4     c4    2
  /  \          /  \
c1    c2       c1   c2        3

my initial input to represent the tree by edges is:

$edges =
[
    [ 'pid' => 'p1', 'cid' => 'p2' ],
    [ 'pid' => 'p1', 'cid' => 'p3' ],

    [ 'pid' => 'p2', 'cid' => 'p4' ],
    [ 'pid' => 'p2', 'cid' => 'c3' ],

    [ 'pid' => 'p3', 'cid' => 'p4' ],
    [ 'pid' => 'p3', 'cid' => 'c4' ],

    [ 'pid' => 'p4', 'cid' => 'c1' ],
    [ 'pid' => 'p4', 'cid' => 'c2' ],
];

What I need is to map my initial tree as nodes like (array & visual repr.):

$edges_mapped =
[
    [ 'pid' => 'n1', 'cid' => 'n2' ],
    [ 'pid' => 'n1', 'cid' => 'n3' ],

    [ 'pid' => 'n2', 'cid' => 'n4' ],
    [ 'pid' => 'n2', 'cid' => 'n5' ],

    [ 'pid' => 'n3', 'cid' => 'n6' ],
    [ 'nid' => 'n3', 'cid' => 'n7' ],

    [ 'nid' => 'n4', 'cid' => 'n8' ],
    [ 'nid' => 'n4', 'cid' => 'n9' ],

    [ 'nid' => 'n6', 'cid' => 'n10' ],
    [ 'nid' => 'n6', 'cid' => 'n11' ],
];

                            level
             n1               0
             /\
            /  \
           /    \
          /      \
         /        \
        /          \
       /            \
      n2            n3        1
     /  \          /  \
    /    \        /    \
   n4     n5     n6     n7    2
  /  \          /  \
n8    n9       n10  n11       3

I tried with breadth-first-search (BFS) algorithm and failed. I know why I failed. (2nd set of 'p4','c1','c2' were already visited.) My hope was maybe to adjust the algorithm but I couldn't.

how can I achieve this mapping? I need this for my personal job related php-app so I am free to do anything. i am an engineer but not a software/computer one. answer with code is perfect however name of possible proper algorithms as a comment are very valuable for me also. thanks, best regards.

my failed code is below:

$edges =
[
    [ 'pid' => 'p1', 'cid' => 'p2' ],
    [ 'pid' => 'p1', 'cid' => 'p3' ],

    [ 'pid' => 'p2', 'cid' => 'p4' ],
    [ 'pid' => 'p2', 'cid' => 'c3' ],

    [ 'pid' => 'p3', 'cid' => 'p4' ],
    [ 'pid' => 'p3', 'cid' => 'c4' ],

    [ 'pid' => 'p4', 'cid' => 'c1' ],
    [ 'pid' => 'p4', 'cid' => 'c2' ],
];

function findChildrenIds($edges_element, $edges)
{
    $ch = [];

    if ('p' === substr($edges_element, 0, 1))
    {
        foreach ($edges as $r)
        {
            if ($edges_element == $r['pid'])
            {
                $ch[] = $r['cid'];
            }
        }
    }

    return $ch;
}

// using BFS algorithm
function mapAsNodes($edges, $starting_element)
{
    $visited[] = $starting_element;
    $queue[]   = $starting_element;

    $i = 1;
    $parent[]  = 'n' . $i;

    $j = 0;

    while ($queue)
    {
        $visited_element = array_shift($queue);
        $children = findChildrenIds($visited_element, $edges);

        if ($children)
        {
            // parent node id like 'n1'
            $pid = array_shift($parent);

            foreach($children as $child)
            {
                $i++;

                // child node id like 'n2'
                $cid = 'n' . $i;

                $noded_edges[$j]['pid'] = $pid;
                $noded_edges[$j]['cid'] = $cid;

                if (!in_array($child, $visited))
                {
                    $visited[] = $child;
                    $queue[]   = $child;
                }

                $j++;
            }
        }
    }

    return $noded_edges;
}

echo '<pre>';
print_r(mapAsNodes($edges, 'p1'));
echo '</pre>';