Discussion :

[arundel]

Bonjour à tous,

Je développe en Access VBA et je bute sur la difficulté algorithmique suivante. A partir d'une base de données je construis un arbre à l'aide de deux modules de classe:

Classe Sommet:

Code VBA :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Option Compare Database
Option Explicit
Option Base 1
 
Public lngIDSommet As Long
Public intRank As Integer
Public lngIDPere As Long, colFils As New Collection
 
Property Let SetColFils(objNode As Sommet)
 colFils.Add objNode
End Property
 
Private Sub Class_Terminate()
 Set colFils = Nothing
End Sub

Classe Graphe :

Code VBA :

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

1
2
3
4
5
6
7
8
9
10
11
Option Compare Database
Option Explicit
Option Base 1
 
Public colSommet As New Collection
Public dicSommet As New Dictionary 'Collections des identifiants des sommets
 
Private Sub Class_Terminate()
 dicSommet.RemoveAll
 Set colSommet = Nothing: Set dicSommet = Nothing
End Sub

Comme j'ai par ailleurs une relation de chronologie entre les feuilles de l'arbre, j'ai un traitement qui numérote celles-ci. Je stocke ce numéro dans la variable intRank des sommets de type feuille.

Grâce à un parcours en largeur d'abord je peux numéroter les sommets de l'arbre de manière lexicographique (comme les n° de paragraphes en Word). Le pb c'est que je voudrais que cette numérotation respecte l'ordre des feuilles terminales comme le montrent les deux schémas suivants :



Bref cela revient à actualiser le n° lexicographique en fonction de l'ordre qu'on veut (comme dans le mode Plan de Word).

Si quelqu'un peut me suggérer une piste, cela me rendrait un grand service.

Merci d'avance pour votre aide.

[yahiko]

Je ne suis pas sûr d'avoir saisi ton besoin, mais il semble qu'il s'agit simplement d'inverser récursivement toutes les branches de ton arbre.
Ça peut se faire via ton parcours en largeur d'abord, par exemple.

[arundel]

Merci de t'intéresser à mon problème.

Il ne s'agit pas d'inverser l'ordre des feuilles (le schéma volontairement simplifié a pu le laisser croire), il s'agit de piloter la numérotation de tous les sommets de l'arbre en cohérence avec la chronologie des feuilles.

A mon sens le défaut de la récursivité c'est qu'il faut partir de la racine de l'arbre alors que les infos de base pour le tri sont aux extrémités.

[yahiko]

Dans ce cas, à vue de nez, je pense qu'il te faut des fonctions auxiliaires comme :

Hauteur(nœud) --> hauteur du nœud dans l'arbre
Frères(nœud) --> ensemble des nœuds ayant le même père
Père(nœud) --> père du nœud
Min(nœuds) --> nœud ayant l'ordre chronologique le plus faible parmi les autres nœuds

Par rapport à ton exemple avec trois niveaux, la numérotation de chaque feuille est de la forme x.y.z, sachant que le nombre d'indices pour un nœud quelconque est égal à sa hauteur dans l'arbre.

Il te faut donc déterminer la feuille F ayant l'ordre chronologique le plus petit.
Les indices x, y et z de F vaut donc 1 (1.1.1).
Cela implique que les frères de F ont les mêmes indices x et y qui valent 1 (1.1.z). Seul l'indice z change suivant leur ordre chronologique.
Tu peux aussi en déduire la numérotation de tous les ascendants (père, grand-père, etc) de F.

Une fois cela fait, tu peux t'attaquer aux cousins de F en remontant par le père de F puis les frères du père de F.
En appliquant la même logique pour chaque cousin de F que celle appliquée pour F, tu peux en déduire la numérotation de toutes les feuilles de F et par extension de tous les nœuds de ton arbre.

[arundel]

OK, je regarde ça de près et ferai un retour sur ce qu'il en est.
Merci et à bientôt.

[tbc92]

Reste un point qui n'est pas clairement décrit dans l'énoncé.

Dans ton illustration, les 2 fils de 1.2 sont D et E ; les 2 fils de 1.1 sont F et G ; il n'y a donc pas d'ambiguïté, 1.2 doit venir avant 1.1.

Maintenant, imaginons cette configuration :
1.2 a 2 fils : D et G ; 1.1 a 2 fils E et F
Qui doit venir en premier ?

On classe les individus selon l'âge des fils aînés ( D est plus âgé que F ... et donc 1.2 est avant 1.1)
Ou bien on classe les individus selon l'âge des fils cadets ( G est plus jeune que F, et donc 1.2 est après 1.1)

Il faudra arbitrer ce point avant de mettre en place la solution proposée par Yahiko.

[yahiko]

Même si je pense que la solution évoquée précédemment doit fonctionner, il me semble qu'un parcours récursif en largeur de ton arbre soit plus efficace pour (re)numéroter correctement tes nœuds.
C'est de loin la solution la plus simple.

Code :

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

1
2
3
4
5
6
7
8
9
Numeroter(N: noeud, num: numerotation)
  N.numero := num
  Fils := TrierFils(N)
 
  Pour k = 1 à NbFils(N) Faire
    numFils := num || "." || k    // concaténation
    Numeroter(Fils[k], numFils)
  Fin Pour
Fin Numeroter

La fonction TrierFils() doit renvoyer un tableau des nœuds fils d'un nœud triés par ordre chronologique croissant.
La fonction NbFils() doit renvoyer le nombre de fils d'un nœud

Si tu appliques cette procédure Numeroter() sur la racine de ton arbre, alors, par construction, ta feuille ayant le plus petit ordre chronologique sera nécessairement numéroté 1.1. ... .1.

[arundel]

Merci à vous deux pour vos suggestions.

J'ai terminé la mise au point et ça fonctionne parfaitement. Comme promis je reviens vers vous pour vous l'exposer.

Rappel du problème :
L'utilisateur :

• décrit d'abord l'arbre dans un ordre quelconque,
• définit ensuite la chronologie des feuilles en indiquant pour chacune d'elles ses prédécesseurs.

Le système doit donc restructurer l'arbre et bâtir une numérotation lexicographique de tous les sommets.

Principe de la solution :

1. Je numérote les sommets (intRank) par un tri topologique du sous-graphe limité aux feuilles de l'arbre.
2. Pour chaque ensemble de sommets de même père (donc une fratrie), j'indique au niveau du père le rang maxi de ses fils, et ceci étage par étage jusqu'au sommet. Pour réaliser cela j'utilise un parcours DFS postfixé en partant de la racine de l'arbre.
3. La numérotation lexicographique est réalisée via un BFS dans lequel j'utilise une file de priorité de manière à traiter les rangs dans l'ordre croissant (je traite le somme qui a le rang minimal).

Code VBA :

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
'Parcours en largeur pour calcul du code lexicographique des sommets de l'arbre
Sub BFSwbs(ByRef objGraphe As Graphe)
 
Dim colFile As New Collection, colWrk As New Collection
Dim objCurr As Sommet, objSucc As Sommet
Dim i As Integer, j As Integer, k As Integer
 
'Réinitialisation des états de marquage
For Each objCurr In objGraphe.colSommet
 i = i + 1
 objCurr.SetState = WHITE
Next objCurr
 
'On marque le sommet racine de l'arbre puis on le met dans la file
With objGraphe: Set objCurr = .colSommet(.dicSommet(.lngIDRacine)): End With
objCurr.SetState = BLACK: objCurr.strWBSCode = "1"
colFile.Add objCurr
 
'colFile est une file de priorité : on traite le sommet qui a le rang minimum
While colFile.Count > 0
 j = MinRank(colFile): Set objCurr = colFile.Item(j): colFile.Remove (j)
 
 k = 0
 Set colWrk = objCurr.colSucc 'Collection annexe pour traitement par ordre croissant de rang
 While colWrk.Count > 0
  j = MinRank(colWrk): Set objSucc = colWrk(j): colWrk.Remove (j) 'ontraite le succseeur de rang minimal
 
  If objSucc.GetState = WHITE Then 'si ce successeur est non marqué
   objSucc.SetState = BLACK ' on le marque
   colFile.Add objSucc 'on le met dans la file
   k = k + 1
   'Le code WBS de ce successeur est égal au code WBS de son père auquel on ajoute le n° de séquence k
   objSucc.strWBSCode = objCurr.strWBSCode & "." & k
  End If
 Wend
Wend
 
Set colFile = Nothing: Set colWrk = Nothing
 
End Sub

Encore merci à vous tous.

Bien cordialement.