Vala, j'ai un graphe (non-orienté) genre :
 

 
et je voudrais trouver les boucles la dedans. L'arc pointé est l'arc qui fait chier et qu'il faudrait supprimer, mais je ne vois pas trop comment faire
 
une idée ?
help

google, rtfm, ta gueule, recherche

Je comprends même pas comment tu détermines que c'est celui-là que tu veux gicler...

Méthode assez simple :
pour chaque arc de ton graphe, tu regarde s'il existe un chemin (autre que ce même arc) qui relie les 2 sommets (avec un quelconque algo de parcours, avec marquage des arcs pour ne pas boucler). Si ce n'est pas le cas, tu le vires. Ce n'est certainement pas la méthode la plus efficace, mais elle devrait fonctionner ...

Oui, tu prends un arc, tu l'enleves, et si le graphe n'est plus connexe, alors tu peux le virer.
 
Un arc qui augmente le nombre de connexité d'un graphe si on l'enlève s'appelle un isthme il me semble. Un petit google sur la détection d'isthme devrait te donner des résultats intéressants !
 
Y'a une méthode qui donne l'ensemble des composantes connexes d'un graphes, et est linéaire en fonction du nombre d'arcs. Ca sent une complexité en O(n²) ton histoire là . Y'a peut-être une méthode plus efficace, je sais pas trop !
 
@+

 
ca risque d'etre bien lent si y'a bcp de neoud ou d'arcs non ?

Tu peux regarder les arcs arrières après application de l'algo de parcours en profondeur (histoire de compliquer l'affaire)

pareil. Si tu le vires, il reste... 2 boucles.

C'est cool comme truc, c'est comme ça qu'Internet fonctionne mine de rien (éviter que les messages n'arrivent en double ou ne se perdent à cause des liens redondants).
 
C'est un problème de recherche de minimum spanning tree. L'algo de Kruskal a l'air de faire l'affaire.

 
C'est pas justement le contraire ? Les isthmes représente plutôt les points faibles d'un réseau, non ? Si ce lien disparaît, alors deux parties du réseau ne pourront plus communiquer.
 
Je pense que je n'ai pas compris ce que tu as voulu dire
 
@+

Nan nan, c'est moi. Je m'ai trompé.
 
Je pensais qu'il recherchait un algo de recherche de boucles, pas de recherche d'isthme. En l'occurence, le MST enlèverait non pas l'isthme, mais le segment en haut à gauche et celui en bas à droite.

je cherche effectivement un algo de recherche de boucle

Tu réécris ton truc en C++ et tu utilises Boost::Graph (bonne chance pour comprendre la doc)

nan

heuh bin, up quoi

J'ai pas du comprendre qqchose
 
Tu appelles boucle l'arc que tu as désigné sur ton dessin ? Si c'est le cas, ca s'appelle un isthme, et tu peux utiliser ce que dsls et moi avons conseillé, mais ca ne risque pas d'être très efficace (enfin ca reste à voir si c'est acceptable pour la taille de ton graphe).
 
Dans la terminologie des graphes, on appelle boucle un arc qui part et qui arrive à un même sommet. Sinon, un cycle est un chemin fermé qui part et qui arrive à un même sommet. J'enfonce surement des portes ouvertes, le prend pas mal, c'est juste pour être certain qu'on parle bien des mêmes choses
 
Edit :
J'imagine que tu appelles "boucle" les deux objets résultant de la suppression de cet arc. Il s'agit finalement de deux composantes connexes (deux composantes d'un seul tenant - une "boucle" -). Le nombre de composantes connexe d'un graphe est désigné par le nombre de connexité. Si on enlève un isthme d'un graphe, on augment ce nombre. Par exemple sur ton dessin, si on enlève l'arc pointé, ce nombre passe de 1 à 2. L'algo proposé par dsls te permet de déterminer justement la connexité d'un graphe (est-il d'un seul bloc ou non)
 
 
@+

non bin alors, pour etre plus clair. Dans le graphe plus haut, mon cerveau me dit que j'ai deux boucles (une sur la droite, et une sur la gauche) et finalement le seul arc qui ne fait pas partie d'une boucle, c'est celui pointé par la fleche.
 
Ce que je veux c'est retrouver les arcs faisant partie d'une boucle. La je viens de finir la methode par recherche exhaustive, mais j'ai un peu perde de la vitesse au cas ou le nb de sommets et d'arcs augmente trop (genre 50sommets, 70arcs, ca fait deja une bonne brouette de possibilité)

J'ai mangé des graphes durant tout l'été, mais c'est resté assez basique, je peux pas plus t'aider.
 
Il faut peut-être bidouiller un peu (une heuristique quoi ).  
 
Tu prends un échantillon de points de part et d'autre d'un supposé isthme, tu regardes si il y a un chemin qui passent par ce fameux arc pour tous les couples de points que tu as considéré Si oui, y'a une bonne chance que ca soit un isthme (au pire tu confirmes çà avec l'algo de dsls). Un dijkstra avec tas, ca doit couter du O( nombre d'arcs log (nombre de sommets) ), enfin c'est pas super propre tout çà, on n'est pas certain du résultat
 
Bref, j'espère que quelqu'un va passer te donner un coup de main !
 
@+

ouais nan mais nan c'est moi qui suit un gros con, en fait
j'avais skippé ton interessante reponse
jvais me plonger dans un bain de sangsue

C'est pas grave
 
Moi je viens de me rendre compte que dsls et moi on parlait pas tout à fait de la même chose, uhu !
 
La recherche d'un chemin pour chaque arc sera plus lourd (d'un facteur log(nombre d'arc) à gros coup de louche) qu'un algorithme de recherche de composantes connexes dans un graphe. Il faut voir ce que ca donne en pratique.
 
Tiens nous au courant ! @+

 
Hum... Pas trop en fait Dans la terminologie anglaise ca se dit "bridge", ce qui est bien plus parlant. Là, y'a tout de suite plus de résultat !

http://www2.toki.or.id/book/AlgDes [...] ODE166.HTM

C'est ce que je proposais.

Ca sent bon le sable chaud çà !

merci, t'es un chef !

C'est cool !
 
Je reste sur le cul qu'on puisse faire çà en temps linéaire. Va falloir que j'appelle mon maître de stage !

 
Cela est possible en utilisant le tri topologique (TT) sur ton graphe :
Je connais un algo du TT qui permet de detecter les cycles dans un graphe. Les noeuds renvoyés par le TT dans le cas d'un graphe avec cycle sont ceux n'appartenant pas à un cycle !
Pour ce qui est de l'efficacité, plus ton graphe a de cycles et plus il sera rapide (car les noeuds n' appartenant pas a un cycle sont peu nombreux). Sinon, il restera plus rapide que la recherche exhaustive (= prendre les arcs un a un et regarder tous ses successeurs, puis les successeurs des successeurs, etc...jusqu'a voir si on ne retombe pas sur cet arc).
Par exemple sur le graphe de ton 1er post, je trouve l'arc oriente (le seul n'appartenant pas aux cycles) en 0(n) avec n nb de noeuds du graphe.

oué juste pour dire que la méthode par recherche de connexité (?) marche au poil, et niveau perfo ca me suffit amblement
(juste mon graphe de base qui est pourri a debugguer, mais sinon ca roule )
 
thks