Discussion :

[cleth]

En fait, dès que le graphe est faiblement connexe, il y a une méthode vachement plus simple que de passer par des flots.

Laisse moi deviner: à partir du graphe réduit on cherche à compléter les arcs existants pour trouver un cycle hamiltonien ?

[dividee]

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]

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]

Pour les fonctions annexes, voir premier post de Jedai dans cette discussion.
[/edit]

[dest]

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 ?

[millie]

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 ?

Les défis ne se ferment jamais

Pour l'instant, il n'y a pas eu de solution complète sans erreurs (sauf la brute-force) (EDIT : ah si, celle de dividee doit être bonne )

Et il y a encore moins eu de réponses avec preuve.

[Alp]

Je viens de tomber sur ça : http://hackage.haskell.org/packages/...Graph-SCC.html