Problème avec une fonction récursive de construction de graphe [Résolu]

[reynum]

Bonjour

Pour commencer merci pour ce site qui m'a de nombreuses fois aidé.

Voila mon problème : je souhaite faire une fonction php qui construit une structure de graphe simple c'est à dire un tableau contenant des doublets (String, array), les array du doublet étant des tableaux de doublets etc.

voici mon code :

la classe doublet :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
/*******************************************************************************
Cette classe définie un type doublet prévu pour être une string et un array
is_feuille indique is le noeud est une feuille
*******************************************************************************/
class doublet
{
    private $str;
    private $tab;
    private $is_feuille;
 
    // constructor
    public function __construct($str,$tab) {
        $this->str = $str;
        $this->tab = $tab;
        $this->is_feuille = false;//faux par défaut
    } 
    public function get_str(){
        return $this->str;
    }
    public function get_tab(){
        return $this->tab;
    }
    public function set_tab($var,$i){
        $this->tab[$i]=$var;
    }
    public function set_feuille($value){
        $this->is_feuille=$value;
    }
    public function is_feuille(){
        return $this->is_feuille;
    }
}

La fonction de construction de la structure d'arbre (graphe)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
/*******************************************************************************
Cette fonction crée une structure arborescente (graphe) composée de tableaux de 
doublet (string,array) avec chaque array étant aussi un tableau de doublet.
$tab_doublets() est le tableau qui comportera l'arborescence
$tab_item contient les valeurs (string) à ajouter (racine fils1 fils2 ...)
*******************************************************************************/
function add_item($tab_doublets,$tab_item)
{
    $in_array=false;
    $size_tab=count($tab_doublets);
    $nb_item=count($tab_item);
    $offset;
    $it_tmp;
    $find_it=0;
 
    if($nb_item>0)
    {
        while(!isset($tab_item[$find_it])){$find_it++;}//recherche le premier item valide
        $it_tmp=$tab_item[$find_it];//memorise le premier item valide
        unset($tab_item[$find_it]);//le supprime du tableau
 
        for($i=0;$i<$size_tab;$i++)//cherche si la valeur existe déjà dans le tableau courant
        {
            if(strcasecmp($tab_doublets[$i]->get_str(), $it_tmp)==0)
            {
                $in_array=true;
                $offset=$i;
            }
        }
        if($in_array)//si elle est déjà présente
        {
            add_item($tab_doublets[$offset]->get_tab(),$tab_item);//appel récursif sur la case concernée
        }
        else//sinon
        {
            $tab_doublets[$size_tab] = new doublet($it_tmp,add_item(array(),$tab_item));//on crée un nouvel élément
            echo " nouvelle taille :".count($tab_doublets)."<br/>";
            if($nb_item==1)
            {
                $tab_doublets[$size_tab]->set_feuille(true);//informe que cet élément est le dernier de l'arborescence
            }
        }
    }
    return $tab_doublets;
}

La fonction pour lire et afficher cette structure

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/*******************************************************************************
Cette fonction affiche une structure arborescente (graphe) crée par add_item()
*******************************************************************************/
function affiche_item($tab_doublets)
{
    foreach($tab_doublets as $indice=>$value)
    {
        if($value->is_feuille())
        {
            echo $value->get_str()." est une feuille<br/> ";
        }
        else
        {
            echo $value->get_str()."<br />";
            affiche_item($value->get_tab());
        }
    }
}

Et l'appel de ces fonction :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
$rep = "pages_appel/";//répertoire à parcourir
$dir = opendir($rep);
$file_num=0;
$tab_doublets=array();//création du tableau d'arborescence
 
while ($f = readdir($dir)) {//boucle de parcours du répertoire
    if(is_file($rep.$f)) 
    {       
            $pos_pt = strrpos($f,'.');//position du dernier point dans la chaine
            if($pos_pt!=false)
            {
                $f = substr($f, 0, $pos_pt);//vire l'extension du fichier
            }
            $tab_item = explode("+++",$f);//sépare le nom du fichier en items
 
            add_item(&$tab_doublets,$tab_item);//on construit la structure arborescente
            $file_num++;
    }
}
echo "<br/><br/>";
affiche_item($tab_doublets);
closedir($dir);

Le but étant de lire le contenu d'un répertoire, le nom des fichiers ayant cette syntaxe :

racine+++fils1+++fils2.html (ou autre extension osef)
racine+++fils_a+++fils_b+++fils_c.html
racine2+++fils_omega.html

dans cet exemple le résultat devrait être un arbre (graphe) de cette forme:

racine
|-fils1
|-|-fils2
|-fils_a
|-|-fils_b
|-|-|-fils_c
racine2
|-fils_omega

mais cela ne marche que pour les racines et la première branche ici le résultat serait :

racine
|-fils1
|-|-fils2
racine2
|-fils_omega

Sachant que quand je place des "echo" pour voir ce qu'il se passe, à la construction tout semble bien se passer (les tableaux de chaque niveaux ont le bon nombre d'éléments) mais quand vient le moment d'afficher, les noeuds (normalement) ajoutés à une branche déjà existante ont disparus.
je me demande si il n'y a pas un problème de portée de variable mais en essayant de mettre les tableaux en "global" ça n'a rien changé.

Si quelqu'un voit ce qui pose problème, car je sèche et c'est pas faute d'avoir essayé des choses.
Merci d'avance.

[Benjamin Delespierre]

Hello

Essaie plutôt ça:
- http://www.php.net/manual/en/class.r...ryiterator.php
- http://www.php.net/manual/en/class.r...eeiterator.php

Exemple:

Code :

1
2
3
4
5
6
7
$root = new RecursiveDirectoryIterator('C:\\wamp2\\');
 
$it = new RecursiveTreeIterator($root, RecursiveTreeIterator::PREFIX_MID_HAS_NEXT);
 
foreach ($it as $dir) {
  echo $dir . '<br />';
}

[reynum]

Merci pour cette réponse, ce code fonctionne bien sûr mais ne fait pas ce que je veux

[Benjamin Delespierre]

Voila mon problème : je souhaite faire une fonction php qui construit une structure de graphe simple c'est à dire un tableau contenant des doublets (String, array), les array du doublet étant des tableaux de doublets etc.

C'est caractéristique d'un ReccursiveTreeIterator.

Quel est ton besoin concrètement ?

[reynum]

C'est ce que j'ai expliqué en bas de message, faire un explode() du nom de fichier et que chaque item soit une partie d'une arborescence.
J'ai même mis un exemple, pourtant il me semblait avoir détaillé mon problème. DSL

[Benjamin Delespierre]

Je crois que c'est la façon que tu as de construire ton arbre qui est incorrecte. De plus tu n'as pas vraiment besoin de tout ça, un arbre en PHP se modélise très bien avec des tableaux associatifs et se parcours en récursion avec un ReccursiveIterator. L'algo pour implémenter ça manuellement n'est d'ailleurs pas franchement complexe.

ça peut se faire comme ça:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$fic_list = array(
	'racine+++fils1+++fils2.html',
	'racine+++fils_a+++fils_b+++fils_c.html',
	'racine2+++fils_omega.html',
);
 
$tree = array();
foreach ($fic_list as $filename) {
  $split = explode('+++', $filename);
 
  $current = &$tree;
  foreach ($split as $value) {
	if (!isset($current[$value])) $current[$value] = array();
	$current[$value] += array($value);
	$current = &$current[$value];
  }
}
 
var_dump($tree);

-- Edit

Si ton but est plus de trouver les feuilles que de parcourir l'arbre, tu peux faire:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$fic_list = array(
	'racine+++fils1+++fils2.html',
	'racine+++fils_a+++fils_b+++fils_c.html',
	'racine2+++fils_omega.html',
);
 
$tree = array();
foreach ($fic_list as $filename) {
  $split = explode('+++', $filename);
  $leaf = array_pop($split);
 
  $current = &$tree;
  foreach ($split as $value) {
	if (!isset($current[$value])) $current[$value] = array();
	$current = &$current[$value];
  }
  $current[] = $leaf;
}
 
var_dump($tree);
 
var_dump($tree['racine']['fils1'][0]);

[reynum]

Merci pour ta réponse, lire le code que tu as mis m'a fait penser à un truc, qui, par effet boule de neige m'a permis de trouver ou était mon erreur, il s'agissait d'un retour de récursivité que je n'enregistrais pas, donc du coup le parcours était correct mais pas sauvegardé en intégralité.
@Benjamin Delespierre Je suis conscient qu'il y a de meilleurs moyens de faire que le mien, si je n'étais pas arrivé à débogger mon code j'aurais sûrement creusé dans le sens de ta proposition, merci encore .

pour ceux qui serait curieux de voir ou était l'erreur je reposte mon code fonctionnel :

la classe doublet qui est devenue noeud :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
/*******************************************************************************
Cette classe définie un type noeud prévu pour être une string et un array
is_feuille indique is le noeud est une feuille
*******************************************************************************/
class noeud
{
    private $str;
    private $arbre;
    private $is_feuille;
 
    // constructor
    public function __construct($str,$arbre) 
    {
        $this->str = $str;
        $this->arbre = &$arbre;
        $this->is_feuille = false;//faux par défaut
    } 
    public function get_str()
    {
        return $this->str;
    }
    public function get_arbre()
    {
        return $this->arbre;
    }
    public function set_arbre($var)
    {
        $this->arbre=&$var;
    }
    public function set_feuille($value)
    {
        $this->is_feuille=$value;
    }
    public function is_feuille()
    {
        return $this->is_feuille;
    }
}

La fonction de construction de la structure d'arbre (graphe)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/*******************************************************************************
Cette fonction crée une structure arborescente (graph) composée de tableaux de 
noeud (string,array) avec chaque array étant aussi un tableau de noeud.
$tab_noeuds() est le tableau qui comportera l'arborescence
$tab_item contient les valeurs (string) à ajouter (racine fils1 fils2 ...)
*******************************************************************************/
function add_item($tab_noeuds,$tab_item)
{
    $in_array=false;
    $size_tab=count($tab_noeuds);
    $nb_item=count($tab_item);
    $offset;
    $it_tmp;
    $find_it=0;
 
    if($nb_item>0)
    {
        while(!isset($tab_item[$find_it])){$find_it++;}//recherche le premier item valide
        $it_tmp=$tab_item[$find_it];//memorise le premier item valide
        unset($tab_item[$find_it]);//le supprime du tableau
 
        for($i=0;$i<$size_tab;$i++)//cherche si la valeur existe déjà dans le tableau courant
        {
            if(strcasecmp($tab_noeuds[$i]->get_str(), $it_tmp)==0)
            {
                $in_array=true;
                $offset=$i;
            }
        }
        if($in_array)//si elle est déjà présente
        {
            $tab_noeuds[$offset]->set_arbre(add_item($tab_noeuds[$offset]->get_arbre(),$tab_item));//appel récursif sur la case concernée
        }
        else//sinon
        {
            $tab_noeuds[$size_tab] = new noeud($it_tmp,add_item(array(),$tab_item));//on crée un nouvel élément
            if($nb_item==1)
            {
                $tab_noeuds[$size_tab]->set_feuille(true);//informe que cet élément est le dernier de l'arborescence
            }
        }
    }
    return $tab_noeuds;
}

La fonction pour lire et afficher cette structure

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
/*******************************************************************************
Cette fonction affiche une structure arborescente (graph) crée par add_item()
*******************************************************************************/
function affiche_item($tab_noeuds,$profondeur)
{
    $separator="";
    for($i=0;$i<$profondeur;$i++){$separator.="|-";}
 
    foreach($tab_noeuds as $indice=>$value)
    {
        if($value->is_feuille())
        {
 
            echo $separator.$value->get_str()."<br/> ";
        }
        else
        {
            echo $separator.$value->get_str()."<br /> ";
            affiche_item($value->get_arbre(),$profondeur+1);
        }
    }
}

Et l'appel de ces fonction :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
$rep = "pages_test/";//répertoire à parcourir
$dir = opendir($rep);
$file_num=0;
$arb=array();
 
while ($f = readdir($dir)) {//boucle de parcours du répertoire
    if(is_file($rep.$f)) 
    {       
        $pos_pt = strrpos($f,'.');//position du dernier point dans la chaine
        if($pos_pt!=false)
        {
            $f = substr($f, 0, $pos_pt);//vire l'extension du fichier
        }
        $tab_item = explode("+++",$f);//sépare le nom du fichier en items
        $arb = add_item($arb,$tab_item);//on construit la structure arborescente
        $file_num++;
    }
}
echo "<br/><br/>";
affiche_item($arb,0);//on affiche la structure d'arbre
closedir($dir);

Voilou

[Benjamin Delespierre]

N'oublie pas le