Discussion :

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]);