Participez au Défi sur les graphes

Expert éminent

Le 31/01/2009 à 6:24

Pour commencer par une solution de référence, exploration exhaustive des solutions :

Code Haskell :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import Data.Graph 
import qualified Data.Set as S 
import Data.Array 
import Data.List 
import Control.Arrow 
import Data.Maybe 
  
smallestForSC g =  
    snd . fromJust . find (isSC . fst)  
            . concatMap (map (addEdges g &&& id) . flip combi absentEdges) $ [0..] 
        where  
          absentEdges =  
              S.elems $ S.fromList (pairs $ vertices g) S.\\ S.fromList (edges g) 
  
addEdges g es = buildG b es' 
    where b = bounds g 
          es' = es ++ edges g 
  
isSC = null . drop 1 . scc 
  
combi 0 _ = [[]] 
combi n [] = [] 
combi n (x:xs) = map (x:) (combi (n-1) xs) ++ combi n xs 
  
pairs xs = concat [ [(x,y),(y,x)] | x:ys <- tails xs, y <- ys ]

Bien sûr, c'est légèrement trop lent pour être utilisable

--
Jedaï

0

0

Jedai

Expert éminent

Le 31/01/2009 à 10:10

Ceux qui l'ont essayé ont dû pouvoir constater que la solution ci-dessus était parfaitement inutilisable sur des graphes de taille raisonnable. Nous pouvons néanmoins examiner la structure du problème et nous rendre compte qu'en réalité nous pouvons réduire tous les éléments d'un même composant fortement connexe à un seul noeud sans changer la solution :

Code Haskell :

Sélectionner tout

1
2
3
4
5
6
7
8
9
10
11
reduceToSCC g = (g', translate) 
    where 
      roots = map rootLabel . scc $ g 
      m = M.fromList couples 
      couples = zip [1..] roots 
      translate = (m M.!) 
      g' = buildG (1, M.size m)  
           $ [ (x,y) | ((x,x'),(y,y')) <- pairs couples, path g x' y' ] 
  
applyReduce f g = map (tr *** tr) . f $ g' 
    where (g', tr) = reduceToSCC g

Je ferais remarquer que applyReduce ne présuppose rien à propos de f sinon qu'elle renvoie la solution comme une liste d'arêtes, on peut l'appliquer sur n'importe quel algorithme pour l'améliorer.

--
Jedaï

0

dividee

Membre expérimenté

Le 01/02/2009 à 19:03

Cet algo devrait être plus performant. L'idée est la suivante:
D'abord, réduire le graphe à ses composants fortement connexe, comme l'a expliqué Jedai. Cet graphe ne contient pas de cycles, c'est un DAG. De fait, certains noeuds n'ont pas d'arc entrant et d'autres pas d'arc sortant. Pour que ce graphe (et le graphe original) soit fortement connexe, le degré entrant et sortant de chaque noeud doit être au moins 1. Si N noeuds ont un degré sortant 0 et M un degré entrant de 0, le nombre minimum d'arêtes à ajouter est max(N,M). C'est suffisant, mais il faut également que le graphe soit (faiblement) connexe.

Le principe est de toujours connecter un noeud avec un degré sortant de 0 (attention, toujours dans le graphe des composants fortement connexes, pas dans le graphe original) à un noeud avec un degré entrant de 0.

La première chose à faire est donc d'ajouter des arêtes pour le rendre connexe. La façon la plus économique (en nombre d'arêtes) est bien sûr de constituer un seul cycle. Donc choisir un noeud de d° entrant 0 et un noeud de d° sortant 0 dans chaque composant (faiblement) connexe (il y en a forcément au moins un dans chaque composant) et ajouter ces arêtes.

Ensuite, lorsque le graphe est connexe, le plus simple est de procéder récursivement: ajouter une arête en choisissant un noeud de d° 0 entrant et un sortant, les connecter, ce qui crée un cycle, donc on recalcule le graphe des composants fortement connexes et on recommence (il y a certainement moyen d'améliorer l'algo à ce niveau-là). On continue jusqu'à ce que le graphe se réduise à un seul noeud.

Pour l'implémentation, j'ai continué sur la lancée de Jedai (après avoir passé 2 heures à comprendre son code). Mais je suis nul en Haskell alors c'est pas aussi élégant... J'espère seulement que c'est correct. Toute amélioration est bienvenue.

Voilà le code complet:

Code :

Sélectionner tout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
module Main where

import Data.Graph
import qualified Data.Set as S
import Data.Array
import Data.List
import Control.Arrow
import Data.Maybe

import Data.Tree
import qualified Data.Map as M

addEdges g es = buildG b es'
    where b = bounds g
          es' = es ++ edges g

pairs xs = concat [ [(x,y),(y,x)] | x:ys <- tails xs, y <- ys ]

reduceToSCC g = (g', translate)
    where
      roots = map rootLabel . scc $ g
      m = M.fromList couples
      couples = zip [1..] roots
      translate = (m M.!)
      g' = buildG (1, M.size m) 
           $ [ (x,y) | ((x,x'),(y,y')) <- pairs couples, path g x' y' ]

applyReduce f g = map (tr *** tr) . f $ g'
    where (g', tr) = reduceToSCC g

smallestForSC g = applyReduce edgesToAdd g
    where edgesToAdd g' | length (vertices g') == 1 = []
                        | isConnected = newEdge : (smallestForSC $ addEdges g' [newEdge])
                        | otherwise = edgesForConn ++ (smallestForSC $ addEdges g' edgesForConn)
                        where
                isConnected = null $ drop 1 comp
                comp = map flatten $ components g'
                newEdge = (outVertex &&& inVertex) (head comp)
                outVertex = fromJust . find ((==0) . (outdegree g' !))
                inVertex = fromJust . find ((==0) . (indegree g' !))
                edgesForConn = map (outVertex *** inVertex) $ zip comp (tail comp ++ [head comp])                        

graph1 = buildG (1,5) [(1,2),(1,3),(3,4),(4,1)]
graph2 = buildG (1,7) [(1,2),(1,3),(2,4),(4,5),(3,5),(6,3),(6,7),(7,5),(4,1)]

main = do
    print $ smallestForSC graph1
    print $ smallestForSC graph2

Quelqu'un aurait-il de gros graphes avec les solutions précalculées pour tester mon programme ?

0

millie

Rédacteur

Le 01/02/2009 à 19:13

Envoyé par dividee

Le principe est de toujours connecter un noeud avec un degré sortant de 0 (attention, toujours dans le graphe des composants fortement connexes, pas dans le graphe original) à un noeud avec un degré entrant de 0.

Si ceci est ton principe. Cela ne marche pas à tous les coups

0

dividee

Membre expérimenté

Le 01/02/2009 à 19:32

Euh... Sous réserve que le graphe des CFC résultant est connexe, cela ne suffit pas ? Tu as un contre-exemple ?

0

Jedai

Expert éminent

Le 01/02/2009 à 19:33

Envoyé par dividee

Quelqu'un aurait-il de gros graphes avec les solutions précalculées pour tester mon programme ?

Je n'ai pas vérifié en détail l'implémentation, mais a priori vu ta description tu n'ajoute jamais plus d'arêtes que max(N / in = 0 , N / out = 0) donc la minimalité va de soi. Pour la correction, une joli preuve serait mieux, mais pour s'en convaincre on peut essayer QuickCheck. J'avais déjà concocté un petit module de test pour mes essais (qui allaient dans le même sens que toi mais je n'ai pas eu l'intuition de travailler sur la connexité faible) donc je l'ai appliqué à ton algorithme (une simple propriété d'une ligne) et le résultat semble valider ton algorithme et le trouver relativement rapide même !!

Félicitation !

--
Jedaï

0

millie

Rédacteur

Le 01/02/2009 à 19:36

Envoyé par dividee

Euh... Sous réserve que le graphe des CFC résultant est connexe, cela ne suffit pas ? Tu as un contre-exemple ?

Comment ça sous réserve que le graphe des CFC résultant est connexe ?

Bah, si t'as un graphe non fortement connexe et que t'ajoutes un arc et qu'il est fortement connexe, c'est que ça va

0

millie

Rédacteur

Le 01/02/2009 à 19:42

Avec ça, je suis OK :

La façon la plus économique (en nombre d'arêtes) est bien sûr de constituer un seul cycle. Donc choisir un noeud de d° entrant 0 et un noeud de d° sortant 0 dans chaque composant (faiblement) connexe (il y en a forcément au moins un dans chaque composant) et ajouter ces arêtes.

Mais la ligne du dessus ne suffisait pas tout seul

Mais pourquoi est-ce le nombre minimal ?

0

Le 01/02/2009 à 19:44

Envoyé par millie

Si ceci est ton principe. Cela ne marche pas à tous les coups

Il me semble que si à chaque fois que tu obtiens une composante fortement connexe, tu l'écrase en un seul sommet, ça devrait marcher, nan ? En effet, si on suppose qu'on a un graphe sans aucune composante fortement connexe (et où on vire tout lien de type "S -> S" avec S un sommet) et tel que tout les sommets ont au moins un lien sortant, on a forcément un graphe fortement connexe. En effet, si on suit les lien sortants, soit on arrive à un sommet sans lien sortant (contradictoire), soit on revient sur un lien déjà visité, et donc on a une composante fortement connexe non écrasée.
Et pour les connexion entrante, c'est pareil, il suffit de retourner tout les liens.

Donc je pense que ça marche ! Pas forcément que ça donne l'optimum par contre :-\

0

millie

Rédacteur

Le 01/02/2009 à 19:46

Si c'était le seul principe, mon contre exemple est le suivant :

Graphe de 3 sommets, (A,B,C) et un seul arc (A,B)

Tu peux choisir A comme ayant un degré entrant de 0 et B comme ayant un degré sortant de 0. Ce qui est un mauvais plan évidemment.

0

Identifiez-vous

Créer un compte

Participez au Défi sur les graphes

Identifiant
Mot de passe

Mot de passe oublié ?