Trouver les cycles d'un graphe [Résolu]

[Onimaru]

Salut à tous.
Voici le problème :
Soit M une matrice d'adjacence d'un graphe orienté.
Comment faire pour extraire les cycles de ce graphe ???

[AuraHxC]

Tu peux regarder peut être de ce côté là : http://en.wikipedia.org/wiki/Cycle_detection

[Onimaru]

Envoyé par AuraHxC

Tu peux regarder peut être de ce côté là : http://en.wikipedia.org/wiki/Cycle_detection

Merci.
Une autre question : est ce que l'algorithme de Floyd-Warshall peut m'aider ?

[AuraHxC]

Je ne pense pas sachant que c'est pour la recherche des plus courts chemins dans un graphe.

[Onimaru]

Envoyé par AuraHxC

Je ne pense pas sachant que c'est pour la recherche des plus courts chemins dans un graphe.

Oui je vois merci.

[Onimaru]

Salut, je crois que l'article de Wikipedia parle des cycles des fonctions itérées.

[Onimaru]

Salut, j'ai trouvé cet algorithme sur un forum, est ce juste ?

- soit M une map<noeud, cycle>
- soit L une liste des noeuds du graph G
- tant que L n'est pas vide:
prendre N un noeud dans L:
- faire une recherche en largeur de N à partir de N dans G, elle retourne une trace T
- pour chaque noeud P de T:
- enlever P de L
- si M[P] n'existe pas ou si len(M[P]) < len(T):
- affecter T à M[P]

à la fin tu as ta map M qui associe à chaque noeud un cycle minimal qui passe par ce noeud.

tu peut ensuite lister ces cycles, virer les doublons et t'as une liste de cycles minimaux couvrant le graph.

[Onimaru]

Salut à tous,

J'ai réussi enfin à trouver une solution à ce problème, cette procédure donne les cycles d'un graphe représente par sa matrice d'adjacence :

Code Delphi :

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
procedure GenererCycles(MatriceAdjacence : TMatriceAdjacence; Elements : TVecteur; var Cycles : TCycles);
var I, J, K, L, M : integer;
    TempCycle : TCycle;
    TempCycles : TCycles;
begin
///////////////1//////////////////////
 SetLength(Cycles, Length(Elements));
 for I := 0 to High(Cycles) do
  begin
   SetLength(Cycles[I], 1);
   Cycles[I][0] := I
  end;
//////////////2//////////////////////
 repeat
  SetLength(TempCycles, 0);
  for I := 0 to High(Cycles) do
   for J := 0 to High(Elements) do
    if MatriceAdjacence[Cycles[I][High(Cycles[I])], J] then
     begin
      SetLength(TempCycles, Length(TempCycles) + 1);
      TempCycles[High(TempCycles)] := Copy(Cycles[I]);
      SetLength(TempCycles[High(TempCycles)], Length(TempCycles[High(TempCycles)]) + 1);
      TempCycles[High(TempCycles)][High(TempCycles[High(TempCycles)])] := J
     end;
  Cycles := Copy(TempCycles)
 until Length(Cycles[0]) = Length(Elements);
////////////3/////////////////////
 for I := 0 to High(Cycles) do
  begin
   L := 0;
   for J := 1 to High(Cycles[I]) do
    if Cycles[I][L] > Cycles[I][J] then
     L := J;
   for J := 1 to L do
    begin
     M := Cycles[I][0];
     for K := 1 to High(Cycles[I]) do
      Cycles[I][K - 1] := Cycles[I][K];
     Cycles[I][High(Cycles[I])] := M
    end
  end;
////////////////4/////////////////////////////
 SetLength(TempCycles, 1);
 TempCycles[0] := Copy(Cycles[0]);
 for I := 1 to High(Cycles) do
  begin
   for J := 0 to High(TempCycles) do
    begin
     K := 0;
     while (K <= High(Elements)) and (Cycles[I][K] = TempCycles[J][K]) do
      Inc(K);
     if K = Length(Elements) then
      Break
    end;
   if J = Length(TempCycles) then
    begin
     SetLength(TempCycles, Length(TempCycles) + 1);
     TempCycles[High(TempCycles)] := Cycles[I]
    end
  end;
////////////////5/////////////////////////////////
 Cycles := Copy(TempCycles);
 Setlength(TempCycles, 0);
 for I := 0 to High(Cycles) do
  begin
   SetLength(TempCycle, 1);
   TempCycle[0] := Cycles[I][0];
   for J := 1 to High(Cycles[I]) do
    begin
     for K := 0 to High(TempCycle) do
      if Cycles[I][J] = TempCycle[K] then
       Break;
      if K < Length(TempCycle) then
       Break;
     SetLength(TempCycle, Length(TempCycle) + 1);
     TempCycle[High(TempCycle)] := Cycles[I][J]
    end;
   if Length(TempCycle) = Length(Elements) then
    begin
     for J := 0 to High(Cycles[I]) - 1 do
      if not MatriceAdjacence[Cycles[I][J], Cycles[I][J + 1]] then
       Break;
     if (J = Length(Elements)) and MatriceAdjacence[Cycles[I][J - 1], Cycles[I][0]] then
      begin
       SetLength(TempCycles, Length(TempCycles) + 1);
       TempCycles[High(TempCycles)] := Copy(TempCycle)
      end
    end
   else
    begin
     for J := High(TempCycle) to High(Cycles[I]) do
      if TempCycle[J mod Length(TempCycle)] <> Cycles[I][J] then
       Break;
     if J = Length(Cycles[I]) then
      begin
       SetLength(TempCycles, Length(TempCycles) + 1);
       TempCycles[High(TempCycles)] := Copy(TempCycle)
      end
    end
  end;
 Cycles := Copy(TempCycles)
 Setlength(TempCycle, 0);
 Setlength(TempCycles, 0, 0)
end;

avec :
partie 1 : initialiser le tableau Cycles avec tout les nœuds du graphe.

partie 2 : on duplique chaque élément chaque fois qu'on trouve un nœud relié à lui. On s'arrête quand tous les cycles ont une longueur égale au nombre de nœuds, car il est impossible de trouver un cycle plus long que ça.

partie 3 : Cycles contient maintenant des cycles potentiels, pour chaque cycle potentiel on fait des décalages circulaires afin de rendre le plus petit indice à la première position du cycle. Ce travail permet par la suite de supprimer les répétitions.

partie 4 : supprimer les répétitions.

partie 5 : pour chaque cycle potentiel on génère un motif, si c'est un cycle alors ce motif se répète périodiquement.
Si le motif trouvé est de longueur égale au nombre d'éléments on doit vérifier que c'est un vrai cycle à l'aide de la matrice d'adjacence.
Les motifs vérifiant ces conditions forment l'ensemble des cycles du graphe.

Elements : tableau qui contient les nœuds du graphe.

[Roasma]

Svp aidez moi à trouver une fonction qui trouve tous les cycles dans un graphe mais en matlab. Mezrci