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 ???
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 ???
Tu peux regarder peut être de ce côté là : http://en.wikipedia.org/wiki/Cycle_detection
Je ne pense pas sachant que c'est pour la recherche des plus courts chemins dans un graphe.
Salut, je crois que l'article de Wikipedia parle des cycles des fonctions itérées.
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.
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 : 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
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.
Svp aidez moi à trouver une fonction qui trouve tous les cycles dans un graphe mais en matlab. Mezrci
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager