Bon, il y a quelques temps j'avais implémenté l'algo suivant, mais je n'avais pas posté car je ne sais pas prouver qu'il est bon. Mais bon voilà.
C'est sur l'idée de Jean-Marc Bourguet à la seconde page de cette discussion.
1) réduire la graphe à ses composants fortement connexes
2) si ce graphe ne contient qu'un seul noeud, on a fini
3) trouver un couple (puits, source) tel que la source ne domine pas le puits (c'est à dire tel qu'il n'existe pas de chemin de la source au puits)
- s'il un tel couple existe, ajouter cette arc et continuer en 3)
- sinon relier n'importe quel puits à n'importe quelle source et continuer en 1)
[edit: J'avais oublié le code]
Pour les fonctions annexes, voir premier post de Jedai dans cette discussion.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 smallestForSC g = applyReduce edgesToAdd g where edgesToAdd g' | null (drop 1 $ vertices g') = [] | null undominated = let newEdge = (head roots, head sinks) in newEdge : (smallestForSC $ buildG (bounds g') (newEdge:edges g')) | otherwise = let newEdge = head undominated in newEdge : (edgesToAdd $ buildG (bounds g') (newEdge:edges g')) where roots = [ix | (ix, deg) <- assocs (indegree g'), deg == 0] sinks = [ix | (ix, deg) <- assocs (outdegree g'), deg == 0] undominated = [(s,r) | [s,r] <- sequence [sinks, roots], not $ path g' r s]
[/edit]
Je vois qu'il n'y a toujours pas eu de réponse à ce fil depuis un moment.
Le défi est-il terminé ? Quelle serait la (ou les) solution ?
Je viens de tomber sur ça : http://hackage.haskell.org/packages/...Graph-SCC.html
Mon blog anglais - Mes articles et critiques de livres - FAQ C++0x, avec liste des nouveautés - Conseils sur le C++ - La meilleure FAQ du monde - Avant de créer des classes que vous réutiliserez, regardez si ça n'existe pas déjà - Le site du comité de normalisation du C++
Le guide pour bien débuter en C++ - Cours et tutoriels pour apprendre C++
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager