bonjour,

J'ai une ch'tite question d'algorithmie, dans le domaine des graphes orienté.

J'ai un graph orienté. Je sais que ce graph contient au moins un cycle. D'ailleurs, je l'ai deja reduit pour qu'il ne contienne que des noeuds appartenant a au moins un cycle (par suppression des noeuds uniquement departs et uniquement arrivée).
Mais maintenant, je veux donner une information sympa a mon utilisateur, qu'il sache qu'il y a des cycles (ce qui est mal).

Comment faire pour sortir un ensemble de cycle de mon sac de noeud ? Existe t'il des algos deja biens connus ?

Et si vous avez un bon shampoing pour lews cheveux longs et bouclés, j'suis preneur aussi

Si je me trompe pas, faut que tu raffine ta définition sinon l'ensemble des cycles de ton graphe peut représenter un ensemble infini.
 
Par ex, l'ensemble infini des chemins de la forme ABC(DEFC)*GA sont des cycles ici.

 

kad > dans mon dernier compilo, j'utilisais une pile pour poser les noeuds que je voyais (et pop quand je sors d'un noeud), si je re-tombais sur un des éléments de la pile, le cycle c'est tout le haut de la pile, du premier noeud répété jusqu'au sommet.

edit : et sans même optimiser la recherche, parce que dans mon cas (les inclusions de fichiers) il faut y aller pour avoir des chemins super-longs.

0x90> bah oui. Mon probleme est qu'a partir de mon ensemble, j'aimerais donner un ensemble de cycles utilisables pour l'utilisateur qu'il puisse agir et les supprimer.

ray> Ca ne me donnerais qu'un seul cycle ca non ? Optimisations pas utiles dans mon cas : le machin a pas tendance a faire des cycles, et mon sous graphe devrai deja etre bien diminué

kad> c'est quoi ton domaine ? parce que plusieurs cycles, c'est un merdier complet à détecter et à gérer.

modelisation systeme ( ). Les cycles sont interdits selon la methode. Donc la proba de m'en manger plusisuers d'un coup ...

Donc des cycles minimaux idéalement.

je dirais un truc du genre

- soit M une map<noeud, cycle>
- soit L une liste des noeuds du graph G
- tant que L n'est pas vide:
    prendre N un noeud dans L:
       - faire une recherche en largeur de N à partir de N dans G, elle retourne une trace T
       - pour chaque noeud P de T:
           - enlever P de L
           - si M[P] n'existe pas ou si len(M[P]) < len(T):
              - affecter T à M[P]

à la fin tu as ta map M qui associe à chaque noeud un cycle minimal qui passe par ce noeud.

Tu peut ensuite lister ces cycles, virer les doublons et t'as une liste de cycles minimaux couvrant le graph.

dans ces cas-là, j'ai toujours fait l'autruche : si y'en a plusieurs je lui en donne 1, il le casse et on verra après pour le suivant.  
 
Y'a des techniques super-bordéliques pour simplifier un graphe arbitraire en ses composantes cycliques, mais je te les déconseille, d'autant plus que pour représenter les résultats ensuite, une interface texte sera insuffisante, il faudra dessiner un schéma.
 
Bref, je vote autruche à moins que tu aies *vraiment* les moyens niveau temps.

Ça valait le coup de se décarcasser

surtout que j'ai un algo de complexité moindre dans ma manche  

 
Envoie alors, j'ai improvisé sur le tas, je veut bien voir la version clean.

tu fais un parcours classique de recherche de cycle avec une pile, sauf que quand tu trouve un cycle, tu le sauve dans un set et tu backtrack.
 
ensuite dans ton set, tu as tous les cycles possibles dans le graphe. donc là tu les partitionne en fonction de leur noeud d'entrée (et de sortie donc vu que c'est par celui-ci que ça a bouclé). Dans chaque partition tu fais un Dijkstra et tu sors le vainqueur.

merci a tous les deuxx, je vais voir combien, en €, mon employeur met sur la table

 
Mettons qu'on démarre à A, ton algo va pas commencer à trouver ABCGA, backtracker à C, puis trouver ABCDEFGA et enfn s'arréter, et ainsi ignorer le cycle minimal CDEFC ? Ou alors j'ai mal compris "un parcours classique de recherche de cycle avec une pile" ?

non, il va faire :
ABCGA -> je stocke ABCGA
ABCDEFC -> je stocke CDEFC

là pas de baston au Dijkstra pour trouver le vainqueur.

edit : par contre, ça prend pas en compte tous les chemins effectivement, mais ça un certain avantage quand ils sont infinis ...

donc quand tu backtrack, en fait tu redémarre ta recherche de cycle en partant de C, tu ignore les noeuds A et B ( ceux d'avant le restart dans la pile) ou pas pendant cette recherche ?
 
Ou alors carrément à chaque ajout de noeud, tu le compare à tout les éléments de la pile, et dans ce cas, tu trouve aussi CDEFC, mais le cout à chaque ajout de noeud me semble un peu gros.

le backtrack se fait au noeud qui constitue le haut de la pile, c'est un parcours en profondeur, sauf que là la majorité des noeuds n'ont qu'un seul arc sortant à part C.
 
à la base si ton graphe ne contient pas de cycle et une seule racine, c'est un arbre sur lequel tu tentes une descente en profondeur classique, avec l'algo que je propose, pas d'embrouilles de comlexité si y'avait pas d'embrouilles dans le graphe.