Discussion :

[TicTacToe]

Bonjour

Mon but: démarrer des taches dans l'ordre, avec comme seule contrainte, des couples (A implique B).

Entrée: Liste de couples ( A-> B)
Sortie: Liste des taches dans l'ordre selon les contraintes de précédence.
Eventuellement, prévenir en cas de bouclage (liste de couples non valide)

Exemple:
Entrée = (A->B), (A->C), (C->B)
Sortie = (A,C,B)

Je sais qu'il y a la méthode PERT pour effectuer cela (bien que je n'ai aucune contrainte de durée de tache).

1. J'ai fais ca il y a bien trop longtemps pour m'en rappeler, qq'un connait un site ou l'algo est clairement décris ?

2. Si ca se trouve ca ne s'appelle plus PERT comme il n'y a pas de contrainte de durée ? si c'est un autre nom, ca m'aiderait de le savoir pour rechercher l'algo...

Merci !

[Jean-Marc.Bourguet]

J'appelle ca un tri topologique.

[TicTacToe]

Merci !

j'ai trouvé mon bonheur grace à ce nom de méthode (pffiouu, c'est loin les études )

[Jimmy_S]

A l'occasion tu pourras me montrer à quoi ressemble ton algo ? Ca m'interesse pas mal

[TicTacToe]

Désolé Jimmy, j'avais pas vu ton Post...

J'ai traduit l'algo que j'ai trouvé en Delphi pour mes besoins.
(Je n'ai plus le lien ou j'avais l'algo brut)
Je vois que tu es plutot PHP, donc pas de problème si tu as des questions sur la syntaxe.

Voici le Code:

Une Fonction pour construire la liste d'elt.
LElts : La liste des elements en cours (non triées)
SDe et SVers: La contrainte SDe doit être fait AVANT SVers

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
procedure TriTopoAjouter( LElts: TStringList; SDe, SVers: string );
var
   IIndex : Integer;
begin
     if not LElts.Sorted
       then LElts.Sorted := True;
     // Ajout du predecesseur dans la liste
     if SDe = '' then Exit;
     if not LElts.Find( SDe, IIndex )
       then LElts.AddObject( SDe, TStringList.Create );
     // ajout de elt dans la liste
     if SVers = '' then Exit;
     if not LElts.Find( SVers, IIndex )
       then IIndex := LElts.AddObject( SVers, TStringList.Create );
     // ajout de l'arc
     if TStringList( LElts.Objects[ IIndex ] ).IndexOf( SDe ) = -1
       then TStringList( LElts.Objects[ IIndex ] ).Add( SDe );
end;

Une fonction pour détruire ma la liste initiale
LElts: Liste des élements non triées (la même qu'au dessus)

Code :

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

1
2
3
4
5
6
7
8
9
10
procedure TriTopoToutSupprimer( LElts: TStringList );
var
   i : Integer;
begin
     // Suppression des objets de la liste... et de la liste
     for i := 0 to LElts.Count - 1 do
       if Assigned( LElts.Objects[ i ] )
         then TStringList( LElts.Objects[ i ] ).Free;
     LElts.Clear;
end;

Et enfin, la fonction principale de tri, une fois la liste LElts alimentée
LElts: Listes des élements non triées (les contraintes sont inclus dans la liste sous forme d'objets)
LResultat: La liste des élements dans l'ordre topologique
Retour fonction: TRUE si pas de cycle, FALSE sinon

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
function TriTopologique( LElts: TStringList; LResultat: TStringList ): Boolean;
var
   i : Integer;
   LNoPreds: TStringList;
   SNoPred : string;
   IIndex : Integer;
begin
     // Inits
     Result := True;
     LResultat.Clear;
     if LElts.Count = 0 then Exit;
     LNoPreds := TStringList.Create;
     try
     // Listes initiales des elts sans prédecesseur
     for i := 0 to LElts.Count - 1 do
       if TStringList( LElts.Objects[ i ] ).Count = 0
         then LNoPreds.Add( LElts[ i ] );
     // boucle principale
     while LElts.Count > 0 do
       begin
       if LNoPreds.Count > 0 then
         try
         SNoPred := LNoPreds[ 0 ];
         if LElts.Find( SNoPred, IIndex ) // sup. de SNoPred de la liste
           then LElts.Delete( IIndex );
         for i := 0 to LElts.Count - 1 do // sup. des éleves de SNoPred
           begin
           IIndex := TStringList( LElts.Objects[ i ] ).IndexOf( SNoPred );
           if IIndex <> -1 then
             begin
             TStringList( LElts.Objects[ i ] ).Delete( IIndex ); // sup. de l'arc do'rigine SNoPred
             if TStringList( LElts.Objects[ i ] ).Count = 0
               then LNoPreds.Add( LElts[ i ] );
             end;
           end;
         LResultat.Add( SNoPred );
         finally LNoPreds.Delete( 0 ); end
       else
         Break;
       end;
     Result := LElts.Count = 0;
     finally LNoPreds.Free; TriTopoToutSupprimer( LElts ); end;
end;

Bon courage !