Contrôle de cyclicité - Page 1

J'ai un problème d'optimisation.

J'ai une liste d'éléments (je vais utiliser des nombres par la suite) et chaque élément peut être lié à N autres éléments

donc 1 peut être lié à 2, 3, 4 et 5 mais si 3 est lié à 6 et que 6 est lié à 7 et 1 alors on a un test cyclique vérifié (1=>3=>7=>1=>3=>7=>1=>3=>7=>1=>3=>7=>1=>3=>7=>1...)

l'idée c'est d'afficher cette liste sous forme d'arborescence pour un élément choisi, c'est à dire que je fais un niveau racine avec 1, un niveau fils avec 2, 3, 4 et 5, un niveau petit fils avec 6, et un niveau arrière petit fils avec 7 et là, au lieu de faire un sous niveau avec 1, j'aimerais indiquer qu'on a un cycle (genre 1*)

ça parait simple à faire mais le pb c'est que je vais avoir énormément de ces listes très profondes à produire très souvent, et je ne dois pas saturer le proco pour ça.

Pour le moment, j'ai trouvé uniquement ça et je me demandais si vous n'aviez pas trouver mieux :

- lister les éléments liés
- pour chaque élément lié vérifié s'il y a des enfants (et dans ce cas on les liste)
- pour chaque élément enfant, vérifier les aïeux et si l'enfant est l'un des aïeux alors on met "*" et on ne cherche pas les petits enfants


le problème c'est que revérifier pour chaque entité la chaine qui remonte jusqu'à Adam, je sais pas si c'est pas cpufage...

Ps : c'est à coder avec un langage procédural NON objet

je pige pas trop: c'est une liste ou un arbre?

et les éléments sont uniques? ie si je retrouve 1, je suis SÛR que j'ai un cycle?

c'est une liste normalement représentable sous forme d'arbre à ceci près que tu peux avoir des branches qui dont aussi des racines, galère pour l'affichage...


un élément est unique mais peut être lié à rien, à certains autres ou à tous les autres. pas à luimême.


si tu as un arrière arrière arrière arrière arrière arrière ... arrièrearrière petit fils qui est toi, alors tu as un cycle et il n'est pas nécessaire de boucler...

./1> tu as conscience que tu peux avoir une sortie exponentielle ? i.e. que le graphe n -> n+1 et n -> n+2 et 42 -> 0 te générerait environ 2^42 éléments ?
- si c'est pas ce que tu veux, tu peux modifier l'énoncé pour chercher si l'enfant est un des éléments déjà affichés plutôt que l'un des aïeux
- si c'est ce que tu veux, je suis pas sûr qu'un facteur linéaire entre la recherche naïve et un truc plus efficace changerait grand-chose à la complexité de l'algorithme
Dans les deux cas pour répondre à ta question tu crées juste un tableau de booléen pour l'ensemble des noeuds à ne pas revisiter, le test et la mise à jour est en O(1).

je suis conscient de la sortie exponentielle mais trois enfants peuvent avoir le même petit enfant

tu veux dire qu'en sortie tu aurais un graphe acyclique plutôt qu'un arbre ?

si tu veux, je sais pas comment appeler ça

heuuu si t'as énormément d'éléments à trier/ordonner pour faire ton "arbre", et que tu veux t'arrêter au plus tot à chaque fois, tu risques pas d'avoir des pbs de mémoire à devoir prévoir à l'avance à quelle niveau minimal il va apparaitre ?

je m'explique

imaginons les liens suivants

1-2
2-3
3-4
4-5
5-6
6-7
1-6
1-4
7-1

on a donc

1
|-2
| |-3
|   |-4
|     |-5
|       |-6
|         |-7
|           |-1
|              ....
| 
|-6
| |-7
|   |-1
|    ....
|
|-4
| |-5
|   |-6
|     |-7
|       |-1
|         ....

tu voudrais ca :

1
|-2
| |-3
|   |-4
|     |-5
|       |-6
|         |-7
|           |-1*
| 
|-6*
|
|-4*

ou ca :

1
|-2
| |-3
|   |-4*
| 
|-6
| |-7
|   |-1*
|
|-4
| |-5
|   |-6*

car le premier est facile à construire

le 2em l'est moins...

un mix entre les deux :

1-2,4,6
2-3
3-4
4-5
5-6
6-7
7-1
doit donner :

1
   2
      3
         4
            5
               6
                  7
                     1*
  4
     5
        6
           7
              1*
  6
     7
        1*
2
   3
      4
         5
            6
               7
                  1*
3
   4
      5
         6
            7
               1*
4
   5
      6
         7
            1*
5
  6
     7
        1*
6
  7
    1*
7
  1*

vince (./8) :
si tu veux, je sais pas comment appeler ça

OK, à ce moment-là la sortie devient linéaire puisque tu ne sors jamais deux fois le même noeud ; mais en contrepartie tu ne peux pas le représenter aussi facilement qu'un arbre en mode texte. Si c'est ça ton problème consiste à trier les noeuds du graphe en fonction de leur distance à la racine, et remplacer les arêtes qui reviennent en arrière par une étoile.


./10> alors non, là c'est pas un graphe acyclique sans noeuds répétés c'est un arbre...

le graphe acyclique ce serait comme le graphe de départ mais avec 7-1 remplacé par une étoile (là ce que tu donnes c'est l'arbre des chemins de ce graphe acyclique partant de la racine, qui est exponentiellement plus gros mais qui contient exactement la même information)