Défi N°5 : Forte connexité et graphes

[millie]

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

[Jedai]

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ï

[Jedai]

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ï

[dividee]

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 ?

[millie]

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

[dividee]

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

[Jedai]

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ï

[millie]

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

[millie]

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 ?

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 :-\

[millie]

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.

Envoyé par millie

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.

Ah oui effectivement là, pour la minimalité on repassera ;-)

[dividee]

Envoyé par millie

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.

Mais ce graphe n'est pas connexe... C'est bien pour ça que j'avais précisé.
Oui c'est vrai il faudrait une preuve que le graphe résultant est fortement connexe, mais il faudrait pour ça que je me replonge dans la théorie des graphes... La minimalité ça me parait évident...

[Jedai]

Envoyé par dividee

Mais ce graphe n'est pas connexe... C'est bien pour ça que j'avais précisé.
Oui c'est vrai il faudrait une preuve que le graphe résultant est fortement connexe, mais il faudrait pour ça que je me replonge dans la théorie des graphes... La minimalité c'est effectivement assez évident...

Non, le graphe résultant est bien fortement connexe, mais la minimalité ne marche pas (va falloir que je regarde de plus près l'algo). Par ailleurs le contre exemple donné par millie marcherait sur ton algo mais c'est plus un hasard qu'autre chose. Tu as négligé le fait que plusieurs composantes faiblement connexes pouvaient avoir le même sink. De mon côté je me suis bien cassé la tête la dessus aussi. J'ai rajouté un test de minimalité à mon quickcheck, en supposant que max(N / in = 0, N / out = 0) soit bien atteignable.

--
Jedaï

[dividee]

Je comprends pas comment plusieurs composants faiblement connexe pourrait avoir un même sink... Par définition, ils ne peuvent pas avoir de noeud en commun... Un "sink", c'est juste un noeud avec un degré sortant de 0, non ?

[Jedai]

Envoyé par dividee

Je comprends pas comment plusieurs composants faiblement connexe pourrait avoir un même sink... Par définition, ils ne peuvent pas avoir de noeud en commun... Un "sink", c'est juste un noeud avec un degré sortant de 0, non ?

Je confonds mes tentatives avec ton algorithme, oublie ça.

--
Jedaï

[dividee]

Mais c'est vrai que pour la minimalité, j'ai été un peu vite... A chaque étape j'élimine un "sink" et un "root", mais je peux réintroduire l'un des deux, mais pas les deux, car le graphe a préalablement été rendu connexe, ce qui implique qu'il y aura obligatoirement soit des arêtes entrantes soit des arêtes sortantes du nouveau noeud résultant de la contraction du CFC qui peut être introduite (sauf à la dernière étape ou il n'y pas plus qu'un seul noeud bien sûr). Du coup, il se pourrait que l'algorithme introduise jusqu'à (N | in = 0) + (N | out = 0) - 1 nouvelles arêtes dans le pire des cas.

Maintenant, y a-t'il toujours une solution en n'introduisant que max (N | in = 0, N | out = 0) arêtes ?

PS: je sais que je devrais dire "arc" plutôt que "arête". Mais c'est trop tard, je vais pas corriger tous mes posts précédents, et je continuerais de toute façon à me tromper

Comment choisis-tu les arcs qui rendent ton graphe connexe ? Parce que dans l'exemple de millie, (trois sommets, A B C, un arc A->B), si tu as eu la mauvaise idée de choisir un arc A->C, il te faudra encore deux arcs, alors qu'un arc B->C fera que tu n'en as plus besoin que d'un. Donc cette phase aussi est importante !

[dividee]

Non de ce côté là ça va.
Avec cet exemple (3 noeuds A B C et une arête A->B), d'abord je calcule le graphe des CFC, qui est dans ce cas ci identique au graphe original. Je ne travaille que sur celui-là par la suite. Ensuite, je calcule les composants (faiblement) connexes. Il y en a 2: (AB) et (C). Je relie chaque fois un noeud de degré sortant 0 d'un composant connexe avec un noeud de degré entrant 0 dans le composant suivant (en les prenant dans un ordre arbitraire), jusqu'à avoir fait le tour des composants faiblement connexe. Donc ici, si (AB) est le premier composant et (C) le second, je choisirais B->C et pas A->C. A l'étape suivante, je choisirais C -> A et j'ai fini la boucle. Dans ce cas-ci ça se termine ici et tout va bien.
Le problème serait plutôt après, pour traiter les "sink" et les "root" qui restent.

[bredelet]

Je propose un algo de type impératif

1. Étant donné une liste d'arêtes, créer un tableau associatif de noeuds qui ont la structure suivante:

• Arêtes sortantes
• Nombre d'arêtes entrantes
• Marqueur "visité"

2. Parcourir le graphe en utilisant le marqueur "visité" pour détecter un cycle
Note: seuls les noeuds avec nombre d'arêtes entrantes supérieur à 0 peuvent appartenir à un cycle
3. Réduire le cycle en appliquant aux noeuds:
Pour toutes les arêtes sortantes

• Si le noeud destination est marqué "visité"
• Alors réduire le nombre d'arêtes entrantes du noeud destination
• Sinon ajouter l'arête sortante au noeud combiné

Le nombre d'arêtes entrantes du noeud combiné est la somme du nombre d'arêtes entrantes des noeuds du cycle.
4. Associer tous les noeuds du cycle au noeud combiné dans le tableau associatif
5. Répéter depuis le point 2 jusqu'à éliminer tous les cycles
6. Trouver un noeud avec nombre d'arêtes entrantes = 0 (source)
7. Parcourir le graphe depuis ce noeud jusqu'à un noeud avec nombre d'arêtes sortantes = 0 (sink) en marquant les noeuds visités
8. Ajouter une arête depuis ce noeud jusqu'à une source non marquée
9. Répéter depuis 7 jusqu'à ce qu'il n'y ait plus de source non marquée
10. Ajouter une nouvelle arête depuis le sink jusqu'à la source du point 6
11. Réduire le cycle créé en 10.
On a maintenant un graphe en étoile: il y a une seule source, le noeud combiné
12. Rechercher tous les noeuds avec nombre d'arêtes sortantes = 0 (sink) et ajouter une arête vers la source-
Fini!