Besoin d'aide pour algo de génération d'arbre

[lemouix]

Bonjour,

Je suis en train de bosser sur un algo de génération d'arbre (algo de ford fulkerson). Ceci servira à afficher une arborescence de technologies, batiments, unités, ... selon une base de donnée qui contient les dépendances de chacun des batiments:
0= RACINE
IdBatiment Depend_De:
1 0
2 0
3 1
4 1
5 4
5 3

Pour le moment mon algo fonctionne bien pour:
- Ordonner les niveaux (ford fulkerson)

En recherche pour:
- Afficher l'arbre avec des positions

J'ai utilisé cette méthode pour placer les objets sur l'écran:
Soit tabl1 le tableau contenant la liste des éléments classés par niveau hiérarchique

Initialidsatino du tableau avec ses X et Y.
Récupération de Tabl1[Id] et recherche de ses dépendances.
- Si l'élément ne possède qu'un antécédent, X= Xantécédent
- Si l'élément possède plus d'un antécédent, décalage du niveau supérieur X+170, et on ajoute...

Perso je bloque un peu sur l'algo de représentation.... le résultat voulu est un arbre des technos à la warcraft ou age of empire,...

Donc, si vous avez des idées, merci !

[jo_link_noir]

salut,

Je suis pas sûr d'avoir comprit ton problème, suffit d'afficher l'arbre des techno ?
Si c'est bien ça, -d'après les dépendance donné au début- il faut que 1 et 2 soit sur la même ligne, 3 et 4 dessous et 5 encore plus bas ?

Et j'avoue n'avoir presque rien comprit au dernier paragraphe ><
En même temps j'ai pas trop regarder l'algo de ford fulkerson...

[lemouix]

Je m'explique un peu mieux:
Je possède ma table avec mes antécédents.
J'ai réussi à construire un tableau avec les différents niveaux.
J'ai réussi à afficher un truc du style:
1
2 3
4 5 6

A la base, tous les éléments sont avec un X de 0 et j'ajoute 160 à chaque élément pour le décalage d'origine.
Le tableau que j'ai généré (avec ford fulkerson) est à l'image de ce qui est affiché juste au dessus


Le soucis, c'est que si 2 et 3 dépendent de 1 il faut afficher:
1
2 3

Ensuite 4 dépend de 3:
1
2 3
4

5 et 6 dépendent de 4
1
2 3
4
5 6

Ceci sera fait pour éviter que les traits ne passent dessus les images ou les éléments. J'ai essayé de faire un algo pour faire ces décalages, mais je voudrai voir si vous avez des idées et les comparer à ce que j'ai fais !

En espérant que ce soit plus clair pour tout le monde.

[jo_link_noir]

ok, maintenant c'est bien comprit.
J'te dit ce que je trouve d'ici quelque jours.

PS : entoure les exemples des balises php, sinon on ne voit pas le décalage.

[lemouix]

Infos sur les antécédents:
ID DEPEND_DE
3 1
2 1
4 3
6 4
5 4

Lalgo de l'arbre est fait... à vous de jouer :p (j'ai déjà un résultat pour l'affichage, mais on va voir si vous faites mieux !)

[jo_link_noir]

Bonsoir,

J'ai terminer un truc un peu bancale et qui ne marche pas si un élément à plusieurs parents...
Sinon ils sont bien positionner (mais pas relier ici)



Je suis parti du principe que les enfants de l'arbre on une place disponible de plus en plus mince. Ce qui fait que les enfants sont toujours sous les parents et ne passe pas sous le voisin.



Par curiosité, quel étais ton idée de départ ?

Code PHP :

<?php

error_reporting(E_ALL);



/*calcule le décalage à gauche de chaque case et le rentre dans la variable $parent

    forme [elemnt]=>taille de la case, ...*/

function calcule_positionx_arbre(&$arbre, &$parent, $enfants, $taille=1)

{

    $taille_return = $taille;

    //on traverse chaque rangé

        foreach($enfants as $element)

        {

            //on calcul le décalge des enfants par rapport au point d'origine (et à leur parents)

                if(count($arbre[$element]) > 0)

                {

                    //nombre d'enfant

                    $nb_enfant = count($arbre[$element]);

                    //taille d'un enfant

                    $taille /= $nb_enfant;

                    //position de l'element le plus à gauche

                    $decalage = $parent[$element] - $taille * ($nb_enfant -1) / 2 ;



                    //on enregistre les enfants avec leur décalage et leurs tailles

                        foreach($arbre[$element] as $enfant)

                        {

                            $parent[$enfant] = $decalage;

                            $decalage += $taille;

                        }



                    //repere la case avec le moins d'espace

                    $taille_e = calcule_positionx_arbre($arbre, $parent, $arbre[$element], $taille);

                        if($taille_e < $taille_return)

                            $taille_return = $taille_e;

                }

        }



    //retourne la case avec le moins d'espace

    return $taille_return;

}



/*calcule le décalage du haut de chaque case et le rentre dans la variable $positions

    forme : [0] => tableau des elements de cette lignes, [1] => tableau des elments de cette ligne....*/

function calcule_positiony_arbre(&$arbre, &$positions, $idparent = 0, $indice=0)

{

        foreach($arbre[$idparent] as $id)

        {

            $positions[$indice][] = $id;

            calcule_positiony_arbre($arbre, $positions, $id, $indice+1);

        }

}



function affiche_arbre(&$arbre, $largeur=50, $hauteur=30)

{

    $positions = array();

    calcule_positiony_arbre($arbre, $positions);



    //chiffre qui correspont à la taille du parent avec comme indice le premier parent(0)

    $parent = array(0=>1);

    $taille_plus_petit = calcule_positionx_arbre($arbre, $parent, array(0)); //array(0) => 1er parent



    //affiche l'arbre

    $a = array(); //tableau comprtant le decalage en pixel

    $i=0;

    $min = current($parent)*$largeur/$taille_plus_petit; //coefficient multiplicateur pour séparer les cases

        foreach($positions as $values)

        {

                foreach($values as $value)

                {

                    $a[$i][$value] = $parent[$value]*$largeur/$taille_plus_petit;

                }



                //recherche l'element positionner le plus à gauche pour pouvoir décaller le graph

                if($parent[$values[0]]*$largeur/$taille_plus_petit < $min)

                {

                    $min = $parent[$values[0]]*$largeur/$taille_plus_petit;

                }



            $i++;

        }



        foreach($positions as $key=>$values)

        {

                foreach($values as $value)

                {

                    echo '<div style="outline:1px green solid;position:absolute;width:'.$largeur.'px;height:'.($hauteur-10).'px;background-color:orange;margin-top:'.($hauteur*$key).'px;margin-left:'.($a[$key][$value]-$min)."px;\">$value <!--[{$a[$key][$value]}]--></div>\n";

                }

        }

}



$arbre = array(

    0 => array(14),

    14 => array(1, 2),

    1 => array(3),

    2 => array(4, 5),

    3 => array(6, 7),

    4 => array(),

    5 => array(8),

    6 => array(),

    7 => array(12, 13),

    8 => array(9,10,11),

    9 => array(),

    10 => array(),

    11 => array(),

    12 => array(),

    13 => array(),

);

affiche_arbre($arbre);

?>