Je recherche un algorithme de tri topologique qui ne serait pas
r=E9cursif, mais it=E9ratif. J'ai en effet cod=E9 le premier, mais mon
nombre de noeuds fait exploser la pile du programme. J'ai cod=E9 ceci,
qui repose sur une descente en profondeur avec des piles que je g=E8re
moi m=EAme :
L'algo converge bien, mais son temps d'ex=E9cution est loin d=EAtre
lin=E9aire en nombre de noeuds + arr=EAtes. Ma premi=E8re version r=E9cursi=
ve
=E9tait par contre tr=E8s 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=E9j=E0 visit=E9s
size_t stack_size;
vector<node> node_list // contient la liste
finale des noeuds =E0 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 =3D 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 =3D=3D top_node_stack.size() )
{
while ( visited_node_set.find( top_node_stack.back() ) !=3D
visited_node_set.end() )
{
node_list.push_back( top_node_stack.back() );
top_node_stack.pop_back();
}
}
}
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
espie
In article , Gégé wrote:
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); } }
In article <4ff57107-2178-47e4-b63d-7c124481eb16@s20g2000yqh.googlegroups.com>,
Gégé <valasg@gmail.com> wrote:
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);
}
}
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é
> 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
> 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 ?
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
In article , Gégé wrote:
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*).
In article <9a1b24ab-0eb0-4262-9ae8-c38d5aa7bf13@i24g2000prf.googlegroups.com>,
Gégé <valasg@gmail.com> wrote:
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*).
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é
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.
//! 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 ); }
}
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.
//! 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 );
}
//! 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
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.
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.
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
In article <49641089$0$15306$, candide wrote:
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.
In article <49641089$0$15306$426a74cc@news.free.fr>,
candide <candide@free.invalid> wrote:
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.
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
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.
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.
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
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 !
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 !
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
In article <49647bfe$0$27605$, candide wrote:
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.
In article <49647bfe$0$27605$426a34cc@news.free.fr>,
candide <candide@free.invalid> wrote:
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.
