tri topologique

Le
Gégé
Salut,

Je recherche un algorithme de tri topologique qui ne serait pas
récursif, mais itératif. J'ai en effet codé le premier, mais mon
nombre de noeuds fait exploser la pile du programme. J'ai codé ceci,
qui repose sur une descente en profondeur avec des piles que je gère
moi même :

L'algo converge bien, mais son temps d'exécution est loin dêtre
linéaire en nombre de noeuds + arrêtes. Ma première version récursi=
ve
était par contre très rapide.

Auriez-vous des suggestions ? Merci d'avance

Germain

//! structures
vector<node> top_node_stack; // contient la liste des
sommets
set<node> visited_node_set; // contient la liste des
noeuds déjà visités
size_t stack_size;
vector<node> node_list // contient la liste
finale des noeuds à parcourir

//! init
top_node_stack.push_back( root_node );

//! topologic sorting
while ( !top_node_stack.empty() )
{

//! last top node is added to stack
visited_node_set.insert( top_node_stack.back() );

//! getting dependencies
stack_size = top_node_stack.size();
top_node_stack.back()->GetNextNodes( top_node_stack ); //
retourne la liste des successeurs d'un noeud

//! no new dependency -> unstack nodes till not visited
if ( stack_size == top_node_stack.size() )
{
while ( visited_node_set.find( top_node_stack.back() ) !=
visited_node_set.end() )
{
node_list.push_back( top_node_stack.back() );
top_node_stack.pop_back();
}
}
}
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
espie
Le #18061601
In article Gégé
Salut,

Je recherche un algorithme de tri topologique qui ne serait pas
récursif, mais itératif. J'ai en effet codé le premier, mais mon
nombre de noeuds fait exploser la pile du programme. J'ai codé ceci,
qui repose sur une descente en profondeur avec des piles que je gère
moi même :

L'algo converge bien, mais son temps d'exécution est loin dêtre
linéaire en nombre de noeuds + arrêtes. Ma première version récursive
était par contre très rapide.



Comment tu as fait ton compte ?

C'est non recursif, un tri topologique, normalement.
Et c'est lineaire uniquement si tu as deja ton graphe en memoire, souvent
ca prend plus de temps si tu dois identifier les noeuds a partir d'info
externes.

Ca existe en C dans tout tsort(1) qui se respecte, j'ai reecrit celui
d'OpenBSD, et il marche de facon rapide sans recursion (par contre, il gere
pas mal d'options supplementaires, il y a pas mal de code en plus du
sort de base).
Ca marchera quasi pareil en C++.

- tu fais une premiere passe pour calculer le nombre d'aretes sortantes de
chaque noeud, tu places ceux qui donnent 0 a l'ecart (dans une file, une pile,
un n'importe quoi).
- tant que ta file n'est pas vide:
tu sors le 1er noeud
pour chaque arete entrante vers ce noeud
tu enleves 1 au compte d'aretes sortantes a l'autre bout.
si le resultat vaut 0, tu ajoutes le noeud dans ta file

Si ton graphe est ordonnable, tu vas finir avec tous tes noeuds.
Sinon, il y a un cycle, et il suffit de suivre les noeuds jusqu'a tomber
sur un noeud deja visite pour exhiber le cycle en question.

Mon coeur de tri topo ressemblait a ca:

split_nodes(&pairs, &aux, &remaining);

/* Standard topological sort. */
while (aux.entries) {
struct link *l;
struct node *n;

n = DEQUEUE(&aux);
printf("%sn", n->k);
left--;
/* We can't free nodes, as we don't know which
* entry we can remove in the hash table. We
* rely on refs == 0 to recognize live nodes.
* Decrease ref count of live nodes, enter new
* candidates into the unrefed list. */
for (l = n->arcs; l != NULL; l = l->next)
if (l->node->refs != 0 &&
--l->node->refs == 0) {
ENQUEUE(&aux, l->node);
}
}
Gégé
Le #18062721
>     pour chaque arete entrante vers ce noeud



Mon arbre est constitué de noeuds ne connaissant que leur successeurs,
dois-je reparcourir tous les noeuds pour trouver les arêtes entrantes?
Dois-je créer temporairement une autre structure doublement chainée ?
ou chainée dans l'autre sens ?

Merci
Germain
espie
Le #18063311
In article Gégé
    pour chaque arete entrante vers ce noeud



Mon arbre est constitué de noeuds ne connaissant que leur successeurs,
dois-je reparcourir tous les noeuds pour trouver les arêtes entrantes?
Dois-je créer temporairement une autre structure doublement chainée ?
ou chainée dans l'autre sens ?



Ah oui, ca pourrait etre utile... ca m'explique d'un coup pourquoi tu es
tombe sur un algo recursif.

Ca ne changera rien a la complexite de l'algorithme, qui est lineaire en
nombre d'*arcs* (et non pas en nombre de *noeuds*).
Gégé
Le #18068351
Salut,

Bon, après avoir un peu plus réfléchi sur mon algo et en ayant lu et
relu l'algo de Marc, je suis arrivé à un bien meilleur résultat.

Merci

Germain


//! structures
vector<node> top_node_stack;
set<node> visited_node_set;
size_t stack_size;

//! init
top_node_stack.push_back( root );
string id;

//! topologic sorting
while ( !top_node_stack.empty() )
{

node N = top_node_stack.back();
top_node_stack.pop_back();

//! already visited -> nothing todo
if ( visited_node_set.find( N ) == visited_node_set.end() )
{
N->GetDateDependencies( top_node_stack );
node_list.push_back( N );
visited_node_set.insert( N );
}

}
candide
Le #18321101
Marc Espie a écrit :

C'est non recursif, un tri topologique, normalement.



Si tu fais un parcours en profondeur d'un graphe acyclique G ayant n sommets, ce
qui se fait typiquement et facilement de manière récursive, tu obtiens le
parcours post-ordre du graphe (on numérote les sommets par ordre de sortie de
la pile). Alors, tu obtiens un tri topologique de G en numérotant le sommet de
numéro de post-ordre k par t(k)=n+1-k.

De toute façon, une méthode récursive d'obtention d'un tri topo est assez
naturelle : tu cherches un source du graphe, tu la numérotes pour le tri topo et
tu lances la recherche d'un tri topo sur le graphe privé de cette source.
espie
Le #18321301
In article candide
Marc Espie a écrit :

C'est non recursif, un tri topologique, normalement.



Si tu fais un parcours en profondeur d'un graphe acyclique G ayant n sommets, ce



Non, parce que ca ne correspond pas aux hypotheses usuelles du tri topologique.
Tu n'as aucune garantie que ton graphe soit reellement acyclique, et dans ce
cas ton parcours en profondeur va foirer, et la ca devient non naturel dans
un cadre recursif (dans les hypotheses habituelles, un tri topologique te
prend une relation, et te sort un ordre total compatible avec cette relation,
ou une violation d'anti-symetrie qui indique que la relation de depart n'est
pas une relation d'ordre).

qui se fait typiquement et facilement de manière récursive, tu obtiens le
parcours post-ordre du graphe (on numérote les sommets par ordre de sortie de
la pile). Alors, tu obtiens un tri topologique de G en numérotant le sommet de
numéro de post-ordre k par t(k)=n+1-k.



De toute façon, une méthode récursive d'obtention d'un tri topo est assez
naturelle : tu cherches un source du graphe, tu la numérotes pour le tri topo et
tu lances la recherche d'un tri topo sur le graphe privé de cette source.



Oui, mais elle n'est pas plus recursive qu'iterative. C'est une recursion
"artificielle" (terminale evidente, si tu preferes), du meme ordre que
"pour parcourir une liste, je regarde le premier element et je parcours
le reste". On sait passer de l'un a l'autre sans souci, et normalement
quasiment sans reflechir. En l'occurence: tant que ton graphe n'est pas
vide, tu extrais une source du graphe, tu l'ajoutes en fin de ta liste
d'elements tries, et tu recommences. La seule difficulte algorithmique,
c'est de maintenir de facon efficace des structures annexes qui te permettent
de trouver simplement une source de ton graphe.

Bref, t'es en train de pinailler, comme toujours... l'annee 2009 commence
sur des bases stables, a defaut d'etre saines.
candide
Le #18322431
Marc Espie a écrit :

Si tu fais un parcours en profondeur d'un graphe acyclique G ayant n sommets, ce



Non, parce que ca ne correspond pas aux hypotheses usuelles du tri topologique.
Tu n'as aucune garantie que ton graphe soit reellement acyclique,




On ne doit pas avoir la même définition d'un tri topologique.

Soit G=(V,E) un graphe orienté (V : ensemble des sommets, E : ensemble des
arcs). On dit qu'une application t: G->N est un tri topologique si pour tous
sommets distincts x, y dans V tels que (x,y) soit dans E alors t(x)< t(y)
autrement dit l'ordre de numérotation est compatible avec l'adjacence.


Dans ces conditions, il est évident que G est acyclique car si on avait un cycle
(x_1, x_2, ... , x_n=x_1), on aurait :
t(x_1) < t(x_2) < ... < t(x_n) = t(x_1) ce qui est absurde.


Maintenant concernant le tri topologique, comme je l'ai expliqué, je trouve que
l'algorithme est naturellement est récursif. [c'est d'ailleurs ainsi qu'on
arrive à lister _tous_ les tris topologiques d'un graphe acyclique donné].
Maintenant, ça ne veut pas dire que tu vas l'implémenter ainsi. Et
effectivement, la façon la plus courante de le faire est itérative.
candide
Le #18322581
Marc Espie a écrit :

Non, parce que ca ne correspond pas aux hypotheses usuelles du tri topologique.
Tu n'as aucune garantie que ton graphe soit reellement acyclique, et dans ce
cas ton parcours en profondeur va foirer,



Je ne vois pas comment un parcours en profondeur peut "foirer", graphe acyclique
ou pas.




un cadre recursif (dans les hypotheses habituelles, un tri topologique te
prend une relation,



Tu veux dire une relation d'ordre (antisymétrique et transitive) ? Ce n'est
qu'un cas particulier.

et te sort un ordre total compatible avec cette relation,
ou une violation d'anti-symetrie qui indique que la relation de depart n'est
pas une relation d'ordre).




Et comme tu le laisses entendre, le graphe sous-jacent sera bien acyclique.

Oui, mais elle n'est pas plus recursive qu'iterative. C'est une recursion
"artificielle" (terminale evidente, si tu preferes), du meme ordre que
"pour parcourir une liste, je regarde le premier element et je parcours
le reste".



Tout à fait.

On sait passer de l'un a l'autre sans souci, et normalement
quasiment sans reflechir.



Teste avec tes étudiants et tu verras si c'est si naturel de passer de l'un à
l'autre pour un tri topo.

La seule difficulte algorithmique,
c'est de maintenir de facon efficace des structures annexes qui te permettent
de trouver simplement une source de ton graphe.



Et tu choisis quoi toi ? une liste chainée ?


Bref, t'es en train de pinailler, comme toujours...



Absolument ;)


l'annee 2009 commence
sur des bases stables, a defaut d'etre saines.



Mes meilleurs voeux pour 2009, que l'inspiration soit avec toi !
espie
Le #18324211
In article candide
Marc Espie a écrit :

Non, parce que ca ne correspond pas aux hypotheses usuelles du tri


topologique.
Tu n'as aucune garantie que ton graphe soit reellement acyclique, et dans ce
cas ton parcours en profondeur va foirer,



Je ne vois pas comment un parcours en profondeur peut "foirer", graphe acyclique
ou pas.



Si tu oublies d'annoter les sommets par lesquels tu passes, si, ca foire.
Et c'est pas si simple pour un debutant de combiner mutables et recursivite.
Publicité
Poster une réponse
Anonyme