если входные ребра имеют повторяющиеся поддеревья, как отобразить входные данные корневого ациклического графа (DAG) в качестве узловых ребер

Question

Наглядный пример моей действительной древовидной структуры приведен ниже.

Как видите, у меня есть 2 p4 поддеревьев на уровне 2.

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

мой начальный ввод для представления дерева по краям:

$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' ],
];

Мне нужно отобразить мое исходное дерево в виде узлов, таких как (массив и визуальное представление):

$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

Я попытался с помощью алгоритма поиска в ширину (BFS) и потерпел неудачу.Я знаю, почему я потерпел неудачу.( 2-й набор 'p4', 'c1', 'c2' уже был посещен. ) Возможно, я надеялся настроить алгоритм, но я не смог.

как мне достичьэто отображение?Мне это нужно для моей личной работы, связанной с php-приложением, поэтому я могу делать все что угодно.Я инженер, но не программный / компьютерный.Ответ с кодом является идеальным, однако для меня очень ценны также названия возможных правильных алгоритмов в качестве комментария.спасибо, с наилучшими пожеланиями.

мой код ошибки ниже:

<code>$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 '

';