построение дерева

[berkut]

построение дерева

подскажите с алгоритмом построения дерева, для ситуации, когда есть таблица категорий(cat_id), и таблица отношений cat_id->parent_id. при том, что одна категория(под-категория) может иметь более одного родителя. всё небольшое количество мозга уже переломал

 

[A1x]

когда больше одного родителя это блин уже не дерево. это более общий случай графа

 

[Popoff]

(parent_id) -> (id)
1 -> 2
1 -> 3
1 -> 4
2 -> 3
2 -> 4

сколько родителей у вершин 3 и 4?

 

[berkut]

чооррт... не пойму, в чём подвох.
у 3-ки 2 и у четвёрки 2.

1
    2
        3
        4
    3
    4

-~{}~ 27.12.07 22:39:

я даже код накалякал, и даже вроде как-то работает

 

[Wicked]

berkut
дак и в каком виде тебе надо такой граф вывести? Начинать надо с этого, а с алгоритмом разберемся.

 

[berkut]

да банально в виде дерева каталога, например товаров

-~{}~ 27.12.07 22:51:

set_time_limit(3);

$sql = 'SELECT * FROM categories c';
$cats = $dAtAbAse->getResultSet($sql);
$sql = 'SELECT * FROM category_relations';
$rels = array();
$dAtAbAse->execute($sql);
while ($row = $dAtAbAse->fetchAssoc())
    $rels[] = array('p'=>$row['parent_id'], 'c'=>$row['category_id']);

$sql = 'SELECT c.id FROM categories c
            LEFT JOIN category_relations cr ON c.id = cr.category_id
        WHERE cr.category_id IS NULL'; // get root nodes
$dAtAbAse->execute($sql);
$tree = array();
while ($row = $dAtAbAse->fetchAssoc())
    $tree[$row['id']] = array();

$next = true;
while ($next) {
    $tree = treeTraverse($tree, $rels, $next);
}    

function treeTraverse($tree, $rels, &$next)
{
    $next = $inner_next = false;
    $tree_copy = $tree;
    foreach ($tree_copy as $k=>$v) {
        foreach ($rels as $r) {
            if ($k == $r['p'] && !isset($tree[$k][$r['c']])) {
                $tree[$k][$r['c']] = array();
                $next = true;
            }
        } //var_dump($tree);
        if ($v)
            $tree[$k] = treeTraverse($v, $rels, $inner_next);
    }
    $next = $next || $inner_next;
    return $tree;
}

var_dump($tree);

палюсь, индус

-~{}~ 27.12.07 22:58:

ооо.. я великий идус! LEFT JOIN category_relations cr ON c.id = cr.category_id - тут по идее должно быть parent_id, но ведь работает!

-~{}~ 27.12.07 23:00:

а всё. я тормоз. но это в принципе и так очевидно

 

[Mr_Max]

[офтоп]

$dAtAbAse

Буквы отжимаются что-ли?
(c) башорг

 

[berkut]

эт я так... в реале я так не делаю...