problème d'algorithme pour trouver les circuit d'un graphe

Version imprimable

10/08/2006, 16h50
marc_dd

problème d'algorithme pour trouver les circuit d'un graphe

Bonjour à tous ,
Voilà j ai un probléme d'algorithme, je fais une application qui travaille sur des graphes, j'ai tout sauf le moyen pour arriver à trouver les circuits dans une matrice booléenne, j'ai déjà essayer plusieurs choses mais rien ne marche
C'est sur des graphes orientés
Quelqu'un pourrait-il m'éclairer??

D'avance merci
Marc
10/08/2006, 17h11
progfou

Qu'as tu essayé comme algorithmes ?
Tu travailles avec les listes ou les matrices ?
10/08/2006, 17h12
roulious

Que fais-tu dans le cas d'un graphe ayant 3 somments a,b et c avec des arêtes a->b, b->c et c->a ?

Puisque tu travailles sur un graphe orienté, un parcours en profondeur peut servir : si tu retombes sur un sommet déjà parcouru, tu as un circuit.
10/08/2006, 18h28
marc_dd

en premier lieu je travil avec des matrice

et j ai essayer ce que tu a dis masi je n arrive pas je travail avec un parcour en profondeur comme tu me le propose mais je ne trouve pas
Ca fait aussi toute la journée que je suis la dessus je n' ai donc peut être plus les idées très claire

merci de votre aide
Marc
10/08/2006, 20h23
millie

Les matrices sont-ils imposées ?

Car il me semble que réaliser des parcours en profondeur sur une matrice est beaucoup plus lent qu'avec une liste (de successeur par exemple).

Car pour obtenir l'ensemble des successeurs d'un sommet (utile pour le parcours), on passe d'une complexité constante (ou à peu près) à une complexité = nombre de sommets.
10/08/2006, 20h28
millie

Si ça t'interesse, j'avais répondu à qqn qui voulait réaliser un parcours en profondeur ici :

http://www.developpez.net/forums/sho...ghlight=graphe
10/08/2006, 20h57
marc_dd

Ce n 'est pas que c'est imposé mais c 'est que j' ai deja fait tout mon programme comme ca, je fait un parcour en profondeur pour le chemin et la ca marche mais avec les circuits je ne sais pas j'arrive pas à trouver la solution
j'utilise aussi un parcours en profondeur mais y a un bug
Faut dire aussi que ca fait depuis hier que je suis sur les 2 même méthodes je n 'y vois plus très clair

Merci de votre aide
Marc
11/08/2006, 10h12
Matthieu Brucher

Dans ce livre : http://algo.developpez.com/livres/index.php#L2212113854 il y a la réposne, si tu y as accès, j'ai oublié de regarder hier le nom des algos qu'ils analysent pour ces questions.
11/08/2006, 15h02
Feeder_Fan

Une manière simple de procéder est de faire un tableau de la longueure du nombre de sommet. On initialise le tableau à false.

Ensuite, on effectue un parcours en largeure du graphe, et on met à jour la table des sommets pour chaque sommet rencontré à true.

Si on tombe sur true, alors le chemin actuel est un cycle, sinon on continue le parcours.

(je sais pas si c'est très clair lol)

Bonjour à tous,
voilà j'ai retesté avec un parcour en profondeur, mais je ne trouve toujours pas mon problème, pourtant j'utilise le parcours en profondeur pour les chemins

voilà mon code

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
 
public int Circuit() {
		tmpcirc = new String[100];
		artmp = new ArrayList();
		arcirc = new ArrayList();
		int n = 0;
 
		for (int a = 0; a < count; a++) {
			if (matbool[0][a] == 1)
				n += profcirc(a, 0);
			for (int i = 0; i < count; i++)
				tabsommet[i].initnbp();
			artmp = new ArrayList();
			lignecircuit = "";
		}
		Iterator it = arcirc.iterator();
		while (it.hasNext()) {
			String li = (String) it.next();
			System.out.println(li + "\n");
		}
 
		return n;
	}
 
	public int profcirc(int l, int c) {
		int n = 0, k = 0;
 
		n = artmp.size();
 
		if (tabsommet[c].getnbp() > 0) {
 
			n = artmp.size();
			if (artmp.indexOf(tabsommet[c].getNom()) != n - 1) {
				int nb = artmp.indexOf(tabsommet[c].getNom());
				artmp.add(tabsommet[c].getNom());
				n = 0;
				for (int i = 0; i < artmp.size(); i++) {
					if (i >= nb) {
						lignecircuit += artmp.get(i) + " ";
					}
				}
				arcirc.add(lignecircuit);
				lignecircuit = "";
				artmp = new ArrayList();
				return k = 1;
			}
		} else if (tabsommet[c].getnbp() == 0) {
			artmp.add(tabsommet[c].getNom());
			tabsommet[c].incnbp();
		}
		for (int a = 0; a < count; a++) {
			test++;
			System.out.println(test);
 
			if (matbool[l][a] == 1
					&& artmp.indexOf(tabsommet[a].getNom()) == n - 1) {
				profcirc(l, a);
			}
		}
 
		return k;
 
	}

voilà si quelqu'un pouvait m'aider
Merci d'avance
Marc

Bonjour,

Il y a essentiellement deux methodes pour vérifier qu'un graphe est acyclique.

La première qui t'a déjà été cité consiste à faire un parcours en profonddeur, en coloriant les sommets. Sa complexité est en O(n+m) ou n est le nombre de sommet et m le nombre d'arc (si les acces aux succeesseurs sont en temps constant). Dans ton cas puisque tu travaille avec une matrice d'adjacence tu sera simplement en O(n^2), ce n'est pas génant si ton graphe est dense.
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 final static int OPEN = 0, USED = 1, CLOSED = 2; static boolean acyclic (Graph G) { int n = G.vertices.length; int[] status = new int[n]; for (int x=0; x<n; x++) status[x] = OPEN; for (int x=0; x<n; x++) if (status[x] == OPEN && cycle(G, x, status) return false; } static boolean cycle (Graph G, int x, int[] status) { status[x] = USED; for (int i=0; i < G.edgesFrom[x].length; i++) { int y = G.edgesFrom[x][i]; if (status[y]==USED || status[y]==OPEN && cycle(G,y,status)) return true; } status[x] = CLOSED; return false; }
La deuxième methode est plus pratique dans ton cas, mais moins performante en O(n^3). Elle consiste à calculer la fermeture transitive du graphe G+, puis à regarder si un element apparait dans la diagonale, si oui on a un cycle.
Code:

1 2 3 4 5 6 7 8 9 static Relation transitiveClosure (Relation R) { Relation S = new Relation(R); int n = S.m.length; for (int k=0; k<n; k++) for (int i=0; i<n; i++) for (int j=0; j<n; j++) S.m[i][j] = S.m[i][j] || S.m[i][k] && S.m[k][j]; }
si ton graphe a relativement peu de sommet, la deuxième solution est beacoup plus pratique. Par contre, si tu veut récupérer tous les cycles, alors la première méthode est pllus indiqué.

Pour un compilateur j'ai du être capable de trouver les cycles a travers un graphe et voici ce que j'avais écrit 3x classes m'aidant a reperer des cycles.

L'objectif etant de ne pas ecrire ce code directement dans mes objets "metiers".

Exemple d'utilisation pour le graphe orienté suivant A ---> B ----> C ----A

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
GraphPoint pA = new GraphPoint( "A" );
GraphPoint pB = new GraphPoint( "B" );
GraphPoint pC = new GraphPoint( "C");
 
GraphSegment pAB = new GraphSegment( pA , pB );
GraphSegment pBC = new GraphSegment( pB , pC );
GraphSegment pCA = new GraphSegment( pC , pA );
 
GraphSegment[] segments = new GraphSegment[3];
segments[0] = pAB;
segments[1] = pBC;
segments[2] = pCA;
 
Graph graph = new Graph(segments);
 
boolean hasCycles = graph.hasCycles();
 
// ou pour retrouver les segments responsables des cycles
GraphSegment[] segmentsFautifs = graph.getSegmentsToRemove();

Le getSegmentsToRemove() donne une liste de segments qui une fois supprimés donnera un graphe acyclique. Mais souvent ce choix n'est pas exaustifs et d'autres segments auraient pus etre enlever pour effectuer la transformation. Cette liste en est donc une parmis d'autre choisie arbitrairement.

Les classes ci-dessous sont dans mon projets des inner-classes, il faut sans doute changer certaines visions de methodes pour les externaliser.

la classe representant un graphe (ou plusieurs graphes disjoint):

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
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
/** Represente un graphe sur lequel nous pourrons verifier si il posséde des cycles
     */
    private static class Graph
    {
        // Liste des points du graphe
        private List<GraphPoint>   points           = new ArrayList<GraphPoint>();
 
        // Liste de tout les segments
        private List<GraphSegment> segments         = new ArrayList<GraphSegment>();
 
        // Liste résultat donnant les segments a supprimer afin d'eviter tout cycle */
        private Set<GraphSegment> segmentsToRemove  = null;
 
        /** Construction du graphe a partir d'une liste de segments
         */
        public Graph( GraphSegment[] s )
        {   
            for(int i = 0 ; i < s.length ; i++ )
            {
                segments.add( s[i] );
                if( ! points.contains( s[i].getSourcePoint() ) ) points.add( s[i].getSourcePoint() );
                if( ! points.contains( s[i].getDestPoint() ) )   points.add( s[i].getDestPoint() );
            }
        }
 
        /** Indique si des cycles sont présents dans le graphe
         */
        public boolean hasCycles()
        {
            /** First all, reset all attributes */
            this.initSearch();
            return !this.segmentsToRemove.isEmpty();
        }
 
        /** récupere la liste des segments à supprimer afin de ne plus avoir de cycles dans le graphe
         */
        public GraphSegment[] getSegmentsToRemove()
        {   if( this.segmentsToRemove == null ) this.hasCycles();
            return this.segmentsToRemove.toArray( new GraphSegment[]{} );
        }
 
        /** lance searchCycle sur le 1er point. Une fois sa recherche terminé, relancer pour le prochain point non encore visité, etc...
         */
        private void initSearch()
        {
            for(int i = 0 ; i < points.size() ; i ++)
                points.get(i).setAsVisited(false);
 
            if( this.segmentsToRemove != null ) 
            {
                this.segmentsToRemove.clear();
                this.segmentsToRemove = null;
            }
 
            this.segmentsToRemove = new HashSet<GraphSegment>();
            for(int i = 0 ; i < this.points.size() ; i++ )
            {
                if( ! this.points.get(i).isVisited() )
                    this.searchCycle( this.points.get(i) , new HashSet<GraphPoint>() );
            }
        }
 
        /** Parcours le graphe à partir d'un point donné
         *  Si un cycle est determiné, on met a jour la liste des segments a supprimer
         *  @param point Point a partir duquel on parcours le graph
         *  @param ctx Contexte du chemin déja parcourus (points sur lesquels on est déja passé)
         *  
         */
        private void searchCycle( GraphPoint point , Set<GraphPoint> ctx )
        {
            // On sera passé au moins une fois sur ce point
            point.setAsVisited(true);
 
            // Rajoute le point dans le contexte
            ctx.add( point );
 
            // Parcours tout les successeurs
            Iterator<GraphSegment> i = point.path();
            while( i.hasNext() )
            {
                GraphSegment path = i.next();
 
                // Si le chemin est déja supprimé, ne plus le parcourir
                if( this.segmentsToRemove.contains( path ) ) continue;
 
                // Récupere le successeur
                GraphPoint successor = path.getDestPoint();
 
                if( ctx.contains(successor) )
                {
                    this.segmentsToRemove.add( path );
                    continue;
                }
 
                // Récursion
                this.searchCycle( successor , ctx );
            }
 
            // Restauration du contexte
            ctx.remove( point );
        }
 
    }

L'objet representant un point dans le graphe (je sais je n'utilise pas les vrais terme)

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
50
51
   /** Represente un point d'un graphe
     */
    private static class GraphPoint
    {
        /** Objet utilisateur representant le point */
        private Object              userObject = null;
 
        /** Liste des segments "chemin" parcourable a partir de ce point */
        private List<GraphSegment>  segments  = new ArrayList<GraphSegment>();
 
        /** Indique si on a marqué le point comme visité */
        private boolean             marked    = false;
 
        /** Constructeur */
        public GraphPoint(Object userObject)
        {
            this.userObject = userObject;
        }
 
        /** Ajoute un segment comme parcourable a partir de ce point,
         *  la source de ce segment doit etre "this" sinon léve IllegalArgumentException
         */
        private void addSegment(GraphSegment s) throws IllegalArgumentException
        {   if( s.getSourcePoint() != this ) throw new IllegalArgumentException("Le segment doit démarrer du point courant");
            this.segments.add(s);
        }
 
        /** Parcours tout les chemins accessibles à partir de ce point
         *  @return iteration sur les chemins accessibles à partir de ce point
         */
        public Iterator<GraphSegment> path()
        {  return this.segments.iterator();  }
 
        /** Marque le point comme visité
         *  @param v true pour marquer le point comme visité
         */
        public void setAsVisited(boolean v)
        {  this.marked = v; }
 
        /** Indique si le point est marqué comme visité
         *  @return true si le point est marqué comme visité
         */
        public boolean isVisited()
        {  return this.marked; }
 
        /** Retourne l'objet-utilisateur representant le point dans le graph
         *  @return objet utilisateur lié au point du graphe
         */
        public Object getUserObject()
        {   return this.userObject; }
    }

Et la classe representant un segment

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
 
   /** Liaison orientée entre deux points d'un graphe
     */
    private static class GraphSegment
    {
        /** Point source */
        private GraphPoint src = null;
 
        /** Point destination */
        private GraphPoint dest = null;
 
        /** Construction d'un segment allant de "src" ---> "dest"
         *  @param src point d'origine
         *  @param dest point d'arrivé
         */
        private GraphSegment(GraphPoint src,GraphPoint dest)
        {
            this.src  = src;
            this.dest = dest;
            this.src.addSegment(this);
        }
 
        /** Récupere le point d'origine
         *  @return point d'origine
         */
        public GraphPoint getSourcePoint()
        {   return this.src; }
 
        /** Récupere le point d'arrivé
         *  @return point d'arrivé
         */
        public GraphPoint getDestPoint()
        {   return this.dest; }
    }