Discussion :

[manik971]

bonjour,

Je travaille sur un logiciel qui calcule les chutes de tension sur un réseau électrique, j'ai utilisé une structure de données en graphe et je dois vérifier que le réseau ne boucle pas sur lui même.

En terme de graphe je dois vérifier que mon graphe orienté ne contient pas de circuit, mais je n'ai pas trouvé d'algorithme me permettant de le faire.

j'ai trouvé ça mais je ne comprend pas la logique à suivre :
http://w3.bretagne.ens-cachan.fr/DIT...ours7_algo.pdf page 7

Je crois qu'il existe aussi une technique en faisant des calculs sur la matrice d'adjacence.

Merci de votre aide.

[Biribibi]

Un algorithme (du moins le principe) pour tester l'acyclicité d'un graphe.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
fonction acyclicité (G):
     tant que G n'est pas vide:
           si G possède une feuille x  // c'est à dire un sommet sans arète sortante)
                  supprimer x de G (ainsi que ses arêtes entrantes)
           sinon
                  renvoyer Faux // G n'est pas acyclique
           fin si
       fin tant que
       renvoyer Vrai // G est acyclique
fin

Une implémentation "naïve" de cet algorithme donne du O( n m) où n est le nombre de sommets et m le nombre d'arêtes.
Cependant il est possible de faire du O(n + m) avec une structure de données adaptée (on peut déterminer en temps constant s'il existe une feuille dans G à chaque étape sauf la première).

[manik971]

Tout d'abord merci,

Je comprend le déroulement de l'algorithme et il convient mais en quoi ma structure de données peut elle me permettre de réduire le nombre de calculs?

J'utilise un liste d'adjacence sur mes noeuds afin de connaitre leurs successeurs.

Merci quand même

[Biribibi]

Le choix de la structure de données permet de diminuer le temps nécessaire pour déterminer s'il existe une feuille.
Naïvement, le temps nécessaire est O(n) voire O(n+m).

Obtenir du temps constant n'est pas évident à implémenter mais un bon compromis consiste à utiliser une priority queue où les éléments sont les sommets du graphe et la priorité d'un sommet est son nombre d'arêtes sortantes.
http://en.wikipedia.org/wiki/Priority_queue

Donc une implémentation de l'algorithme que j'ai donné peut être la suivante.

Tout d'abord, on représente le graphe en stockant pour chaque sommet une liste doublement chaînée de ses voisins sortants ainsi qu'une pour ses voisins entrants. On stock également le nombre de voisins entrants et le nombre de voisins sortants.

L'algo est le suivant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
acyclicité (G):
    queue <- priorityQueue vide
    pour chaque sommet x de G:
          ajouter x dans queue avec son nombre d'arêtes sortantes comme priorité
    fin pour
    tant que G n'est pas vide
           choisir dans queue le sommet x de plus petite priorité
           si x n'est pas une feuille
                 renvoyer Faux // G n'est pas acyclique
           sinon
                retirer x de G et de queue
                pour chaque sommet y voisin entrant de x
                        supprimer l'arête (x, y) dans G
                        baisser la priorité de y de 1 dans queue
                fin pour
          fin si
     fin tant que
     renvoyer Vrai
fin

La complexité pour choisir l'élement de plus faible priorité et celle pour mettre à jour un sommet dans la priority queue est log(n).

Donc au final, ça te donne un algorithme en O((n+m) log(n))


Bon dans tous les cas, si l'implémentation "naïve" a un temps d'exécution suffisant pour ce que tu as traité, ce n'est pas la peine de chercher à optimiser.

[manik971]

Merci beaucoup je vais essayer d'utiliser la deuxième méthode car mon réseau peut être très grand.

Je voulais surtout noter le fait que tu expliques vraiment bien tes algos et pour ça je te remercie encore plus. Je te tiens au courant dès que ça marche

[Biribibi]

Après relecture, je me suis aperçu que je demandais plus d'informations à la structure de données que nécessaire (pas gênant en soit mais ça rend les choses plus difficiles à implémenter).

Tout d'abord, on représente le graphe en stockant pour chaque sommet une liste doublement chaînée de ses voisins sortants ainsi qu'une pour ses voisins entrants. On stock également le nombre de voisins entrants et le nombre de voisins sortants.

En fait seulement la liste des sommets sortants et le nombre de voisin entrant est nécessaire.
Par contre, on va plutôt supprimer les "sources" (les sommets sans arêtes entrantes) plutôt que les feuilles (que j'aurais plutôt dû appeler puits pour reprendre la terminologie classique).
Du coup, il faut inverser les termes entrants/sortants dans l'algorithme.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
acyclicité (G):
    queue <- priorityQueue vide
    pour chaque sommet x de G:
          ajouter x dans queue avec son nombre d'arêtes entrantes comme priorité
    fin pour
    tant que G n'est pas vide
           choisir dans queue le sommet x de plus petite priorité
           si x n'est pas un puits
                 renvoyer Faux // G n'est pas acyclique
           sinon
                retirer x de G et de queue
                pour chaque sommet y voisin sortant de x
                        supprimer l'arête (x, y) dans G
                        baisser la priorité de y de 1 dans queue
                fin pour
          fin si
     fin tant que
     renvoyer Vrai
fin

Pour précalculer le nombre de sommets entrants de G, tu peux utiliser un algo du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
calculDuNombreDeSommetsEntrants(G) : renvoyer une table associative (sommet -> nombre de sommets sortants du sommet)
début
  dict <- liste associative vide    
   pour chaque sommet x de G:
      dict[x] <- 0
   fin pour
 
   pour chaque sommet x de G:
        pour chaque sommet y voisin sortant de x:
            dict[y] = dict[y] +1
        fin pour
   fin pour              
   renvoyer dict
fin