Discussion :

[Luc Hermitte]

Bonsoir,

Je suis en train de fignoler un (ft)plugin [1] pour vim [2] pour lequel j'aurais besoin d'ordonner des classes (C++) selon leurs relations d'héritages entre-elles.

Si on prend les définitions de classes suivantes,

Code C++ :

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

1
2
3
4
5
6
struct V {};
struct Z {};
struct C1 : virtual V {};
struct C2 : virtual V, Z {};
struct C3 : C2{};
struct D : C1, C3 {};

en gros je veux pouvoir construire une liste, à plat, de D vers ses ancêtres. Mon but étant de pouvoir parcourir les éléments dans un ordre tel que l'on ne regarde jamais un fils avant un de ses ancêtres.
P.ex. [C1, C3, C2, V], [C3, C1, C2, V] ou [C3, C2, C1, V] sont valides, mais pas [C1, C3, V, C2] car C2 doit être < V. (j'arrive à construire la dernière forme sans difficulté)

Tous mes liens, je les obtiens en analysant les résultats de ctags, j'ai ainsi moyen de construire des relations 1 fils -> {parents} et 1 parent -> {n fils}.
Dans la mesure où je suis capable d'établir un ordre partiel 2 à 2, en propageant la transitivité à la main, je pourrais appliquer des procédures de tri un peu furieusement "complexes". Mais voilà, le résultat ne va vraiment pas être beau.

Même si au fond je n'aurais jamais plus de 10-20 classes multiplement liées ensembles, je préfèrerai tout de même avoir quelque chose de propre et de moindre complexité.

Je soupçonne que c'est un problème "classique" et que je ne sois pas le premier à avoir eu ce besoin de mettre à plat et dans un ordre ce genre de graphe orienté et acyclique. Est-ce que quelqu'un aurait une piste en littérature, voire une idée fulgurante?

Hum ...
A propos de trucs 2D, j'ai l'impression que si je construis la matrice booléenne des "j'hérite de", me problème semble pouvoir se résoudre par une mise en forme triangulaire supérieure de la matrice ... Je vais creuser, même si je sens que je n'ai absolument pas les bons outils pour faire ce genre de transformations... :-(

[1] Le but étant de pouvoir proposer à l'utilisateur de choisir les fonctions membre virtuelles héritées qu'il veut redéfinir -- et ce n'est donc absolument pas pour le boulot, ni un devoir à la maison

[2] Qui dispose d'un langage de script, le VimL, plus ou moins limité. On a enfin les listes et les tables associatives, mais toujours pas de vrais tableaux. (Il faut un peu d'huile de coude pour faire des accès en O(1) sur des tables 2D)

[HanLee]

Un genre de tri topologique peut-être ?

Ce que fait l'analyse des dépendances d'un Makefile.

[Luc Hermitte]

Merci pour ces mots clés. Je vais voir ce que je peux en tirer.
(Pfff... qu'est-ce qu'il sont vieux mes cours d'algo )

[pseudocode]

J'ai pas bien cerné le probleme...

C'est juste une liste à 2 elements (noeud,profondeur) triée sur le 2nd élément.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
     D        ----> depth=0
   __|__
  |     |
 C1     C3    ----> depth=1
  |     |
  |     |
  V     C2    ----> depth=2
      __|__
     |     |
     V     Z  ----> depth=3

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Liste des couples (Node,MaxDepth):
---------------------------------
L = { (D,0) , (C1,1) , (C2,2) , (C3,1) , (V,3) , (Z,3) }
 
 
Liste Triée par MaxDepth
------------------------
L = { (D,0) , (C1,1) , (C3,1) , (C2,2) , (V,3) , (Z,3) }
 
Liste Finale:
-----------
{D,C1,C3,C2,V,Z}

[Luc Hermitte]

Je n'avais pas envisagé le problème sous cette forme (au départ, je n'ai qu'un ensemble de relations (à demander) 1 fils->n parents, et je construis le reste à partir d'un fils donné).

Effectivement cela a l'air pas mal, seulement il reste une petite subtilité: V peut elle même dériver d'un W. Du coup la mise à jour de la profondeur max de V doit se propager jusqu'à ses enfants, dont W, qui soyons fous, pourrait dériver de Z. Pour l'instant, mon algo de construction évitait de reparcourir un noeud -- l'appel aux fonctions d'obtention des noeuds parent n'est pas instantané, ceci dit, il est simple de de mettre en place une évaluation paresseuse.

[pseudocode]

Effectivement cela a l'air pas mal, seulement il reste une petite subtilité: V peut elle même dériver d'un W. Du coup la mise à jour de la profondeur max de V doit se propager jusqu'à ses enfants,

C'est géré implicitement par la recherche de la profondeur max.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
   (...)
  |     |
  V     C2    ----> depth=2
  |   __|__
  |  |     |
  W  V     Z  ----> depth=3
     |
     |
     W        ----> depth=4
 
L = { (...) , (C2,2) , (V,3) , (Z,3), (W,4) }

dont W, qui soyons fous, pourrait dériver de Z.

Attention au Diamond of Death.