Participez au Défi sur les graphes

Le 2009-01-31 02:31:52, par millie, Rédacteur

Bonjour,

Pour ce cinquième défi, l'équipe de developpez.com vous propose un challenge un peu plus difficile.

Le problème est composé de 2 problèmes assez proches. Vous pouvez donc proposer une solution pour le problème que vous souhaitez.

Challenge :

Il y a 2 versions possibles (la première ayant l'avantage d'avoir une formulation plus clair et une solution unique)

Variante 1 :
Pour un graphe orienté donné, donner le nombre minimal d'arc à ajouter afin qu'il devienne fortement connexe.

Variante 2 :
Pour un graphe orienté donné, chercher un ensemble d'arcs de taille minimal tel que l'ajout des arcs au graphe le rende fortement connexe.

Par exemple, pour le graphe suivant :

Une solution serait : (BF, FA).

On entend par taille minimal, la taille tel que pour tout ensemble d'arc de taille strictement inférieur, l'ajout de ces arcs au graphe ne le rende pas fortement connexe.

Il n'y a pas de règles quand à la représentation d'un graphe, cela peut être une implémentation récursive ou encore tout simplement [sommet: [A,B,C,D,E,F], arc: [[A,B], [B,C]] ]

La proposition peut être avec ou sans preuve.

Les règles

Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :

la maintenabilité
la simplicité
le fait qu'il soit optimisé

Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

Pour répondre, il vous suffit de poster à la suite.

A vos claviers
de votre participation.

__________________________
Sujet proposé par millie

Discussion forum

44 commentaires

Jedai

Expert éminent

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ï

le 31/01/2009 à 6:24

Jedai

Expert éminent

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 :

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ï

le 31/01/2009 à 10:10

dividee

Membre expérimenté

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 :

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 ?

le 01/02/2009 à 19:03

millie
Rédacteur

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

le 01/02/2009 à 19:13
dividee
Membre expérimenté

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

le 01/02/2009 à 19:32
Jedai
Expert éminent

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ï

le 01/02/2009 à 19:33
millie
Rédacteur

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

le 01/02/2009 à 19:36
millie
Rédacteur

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 ?

le 01/02/2009 à 19:42
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 :-\

le 01/02/2009 à 19:44
millie
Rédacteur

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.

le 01/02/2009 à 19:46

Poster une réponse