Построение направленного ациклического графа

[nosfer]

Построение направленного ациклического графа

Имеем направленый ациклический граф
Это такая структура данных, в которой любой узел может иметь как много предков так и много потомков.
Таким образом у графа может быть множество вершин.

Структура БД:

tbl_nodes [узлы графа]
->id
->name

tbl_dependences [связи между узлами]
->id
->node_id [связь с tbl_nodes->id]
->parent_node_id [связь с tbl_nodes->id]

Необходимо отсортировать этот граф. Или, другими словами, построить его.

Может быть кто-то с таким сталкивался?
Спасибо.

 

[mustafa]

сталкивался, посмотри в разделе Вопрос-Ответ, там хорошая реализация Попова есть. В любом случае ты должен получить приблизительно такой массив

Array
(
    [0] => 
        (
            [nid] => 1
            [name] => node1
            [depth] => 0
            [parents] => Array
                (
                    [0] => 0
                )

        )

    [1] => 
        (
            [nid] => 2
            [name] => node2
            [depth] => 1
            [parents] => Array
                (
                    [0] => 1
                )

        )

    [2] => 
        (
            [tid] => 3
            [name] => node3
            [depth] => 1
            [parents] => Array
                (
                    [0] => 1
                )

        )

    [3] => 
        (
            [tid] => 4
            [name] => node4
            [depth] => 2
            [parents] => Array
                (
                    [0] => 3
                )

        )

    [4] =>
        (
            [tid] => 5
            [name] => node5
            [depth] => 2
            [parents] => Array
                (
                    [0] => 3
                )

        )

)

как по мне в таблице tbl_dependences у тебя лишнее поле id, имхо оно не нужно