Discussion :

[ImmoTPA]

Bonjour,

Je remercie par avance tous ceux qui voudront bien s'intéresser à mon problème. J'essaie comme l'intitulé l'indique d'implémenter l'algorithme minCut sur un graphe pour trouver la coupe minimale. Mon code tel quel ne donne pas cette coupe minimale, mais il devrait renvoyer la partition de la coupe (les deux ensembles qu'on appelle généralement A et B). Je vous poste mon code sur lequel j'ai passé la majeure partie de ma journée. J'ai ajouté des print pour détecter les problèmes et si vous le lancez vous verrez que mon programme fait par moment plein de fois la même chose sans que je comprenne pourquoi. Mais ce qui l'arrête c'est qu'il ne trouve plus un sommet dans mon graphe alors que je ne suis pas censé avoir supprimé ce sommet avant.

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
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
# *-coding:Utf-8 -*
 
import random
 
f = open("/home/eisti/Documents/cour sera/IntegerArrayMinCut.txt", "r")
 
 
 
class Graph:
 
    def __init__(self, edges):
        self.edges = edges
        self.cuts = dict()
        for i in range(200): # au départ tout le monde est dans une coupe différente
            self.cuts[i+1] = [i+1]
 
    def pickEdge(self):
        vertex = random.choice(self.edges.keys())
        edgesList = self.edges[vertex]
        numEdge = random.randint(0, len(edgesList)-1)
        return (edgesList[numEdge], numEdge)
 
    def contract(self, e):
        for edge in self.edges[e[0][1]]:
            edge = (e[0][0],edge[1])
            self.edges[e[0][0]].append(edge)
 
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[1]==e[0][1]):
                    print "edge avant", edge
                    edge = (edge[0], e[0][0])
                    print "edge ap", edge
 
        print "remove 1", e[0][1]
        del self.edges[e[0][1]]
        self.edges[e[0][0]].remove(e[0]) 
 
        self.cuts[e[0][0]].append(e[0][1])
        del self.cuts[e[0][1]]
 
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[1] == e[0][1]):
                    self.edges[vertex].remove(edge)
 
 
 
    def delLoops(self):
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[0] == edge[1]):
                    print "edge boucle", edge
                    self.edges[vertex].remove(edge)
 
 
    def minCut(self):
            while len(self.edges.keys())>2:
                e = self.pickEdge()
                print e[0]
                self.contract(e)
                G.delLoops()
 
            return self.cuts
 
G = Graph(dict())    
 
for line in f:
    l = line.split()
    G.edges[int(l[0])] = [(int(l[0]), int(x)) for x in l[1:]]
 
 
G.minCut()

Le problème se trouve très probablement dans la fonction contract mais je ne sais pas où. Merci de votre aide

Immo

[Invité]

Bonjour,

Je remercie par avance tous ceux qui voudront bien s'intéresser à mon problème. J'essaie comme l'intitulé l'indique d'implémenter l'algorithme minCut sur un graphe pour trouver la coupe minimale. Mon code tel quel ne donne pas cette coupe minimale, mais il devrait renvoyer la partition de la coupe (les deux ensembles qu'on appelle généralement A et B). Je vous poste mon code sur lequel j'ai passé la majeure partie de ma journée. J'ai ajouté des print pour détecter les problèmes et si vous le lancez vous verrez que mon programme fait par moment plein de fois la même chose sans que je comprenne pourquoi. Mais ce qui l'arrête c'est qu'il ne trouve plus un sommet dans mon graphe alors que je ne suis pas censé avoir supprimé ce sommet avant.

Le problème se trouve très probablement dans la fonction contract mais je ne sais pas où. Merci de votre aide

Immo

Bonjour,

Avez-vous vérifié que G.minCut() retourne bien le résultat attendu ?

Code :

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

1
2
3
4
5
6
7
8
9
G = Graph(dict())    
 
for line in f:
    l = line.split()
    G.edges[int(l[0])] = [(int(l[0]), int(x)) for x in l[1:]]
 
 
#G.minCut()
print "min cut:", G.minCut()

PS : je n'ai pas saisi la subtilité de l'usage de dict() pour Graph.edges et Graph.cuts.

Etes-vous sûr de ne pas pouvoir utiliser list() à la place de dict(), tout simplement ?

@+.

[fred1599]

edges semble bien être un type dict

Code :

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

vertex = random.choice(self.edges.keys())

Ce qui m'inquiète plus ou que je n'ai pas vu, c'est l'endroit où l'on détermine que les valeurs des clés du dictionnaire self.edges sont des listes.

Quel est le message d'erreur ?

[Invité]

edges semble bien être un type dict

Code :

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

vertex = random.choice(self.edges.keys())

Pas entièrement d'accord, doc.

Code :

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

1
2
3
4
5
    def pickEdge(self):
        vertex = random.choice(self.edges.keys())
        edgesList = self.edges[vertex]
        numEdge = random.randint(0, len(edgesList)-1)
        return (edgesList[numEdge], numEdge)

peut aussi s'écrire ainsi (pour le cas d'un objet list()) :

Code :

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

1
2
3
4
5
6
    def pickEdge(self):
        #vertex = random.choice(self.edges.keys())
        #edgesList = self.edges[vertex]
        edgesList = random.choice(self.edges) # tout simplement
        numEdge = random.randint(0, len(edgesList)-1)
        return (edgesList[numEdge], numEdge)

tu ne crois pas ?

[fred1599]

peut aussi s'écrire ainsi (pour le cas d'un objet list())

Si tu retires les deux lignes du dessus, dont la plus importante, celle que je présente dans ma 1ère réponse, on peut croire à n'importe quel type

La méthode keys, retourne une liste, on voit bien qu'il demande à choisir au hasard une clé de son dictionnaire self.edges ou alors j'ai pas compris ?

edgesList est une liste, valeur d'une clé de self.edges, mais ces listes sont définies où dans le dictionnaire défini comme paramètre d'initialisation de la classe Graph ?

Maintenant sans le traceback complet, on peut croire à tout, le débat est lancé

[Invité]

Si tu retires les deux lignes du dessus, dont la plus importante, celle que je présente dans ma 1ère réponse, on peut croire à n'importe quel type

La méthode keys, retourne une liste, on voit bien qu'il demande à choisir au hasard une clé de son dictionnaire self.edges ou alors j'ai pas compris ?

c'est bien ce que je dis : il utilise un dict() de manière injustifiée, en réalité. Il aurait très bien pu utiliser une list() à la place.

regarde ce que je mets en commentaires :

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
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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import random
 
# j'appelle ça l'art de se compliquer la vie :
 
class Graph:
 
    def __init__(self, edges):
        # param inits
        self.edges = edges
        # crée un dictionnaire :
        # {1:[1], 2:[2], ..., 200:[200]}
        self.cuts = dict()
        for i in range(200):
            self.cuts[i+1] = [i+1]
        # aurait pu faire simplement
        # (à un index - 1 près) :
        # self.cuts = [[i] for i in range(1, 201)]
 
    def pickEdge(self):
        # extrait une clé de dict() au pif
        vertex = random.choice(self.edges.keys())
        # extrait l'élément indexé par cette clé
        # en l'occurrence une list() de edges ici
        edgesList = self.edges[vertex]
        # revient à choisir directement
        # un élément au pif dans une list()
        # peu importe si cet élément est
        # lui-même une list() ou non
        # edgesList = random.choice(self.edges)
        numEdge = random.randint(0, len(edgesList)-1)
        return (edgesList[numEdge], numEdge)
 
    def contract(self, e):
        # pareil ici : on peut réajuster
        # l'index (e[0][1] - 1) pour une list()
        for edge in self.edges[e[0][1]]:
            edge = (e[0][0],edge[1])
            self.edges[e[0][0]].append(edge)
        # ici on peut faire directement (avec une list())
        # for edge in self.edges:
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[1]==e[0][1]):
                    print "edge avant", edge
                    edge = (edge[0], e[0][0])
                    print "edge ap", edge
 
        print "remove 1", e[0][1]
        # réajuster l'index => self.edges[e[0][1]-1]
        del self.edges[e[0][1]]
        self.edges[e[0][0]].remove(e[0])
        # pareil
        self.cuts[e[0][0]].append(e[0][1])
        # pareil
        del self.cuts[e[0][1]]
        # ici on peut faire directement (avec une list())
        # for (index, edge) in enumerate(self.edges):
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[1] == e[0][1]):
                    self.edges[vertex].remove(edge)
 
 
 
    def delLoops(self):
        # ici on peut faire directement (avec une list())
        # for (index, edge) in enumerate(self.edges):
        for vertex in self.edges.keys():
            for edge in self.edges[vertex]:
                if(edge[0] == edge[1]):
                    print "edge boucle", edge
                    self.edges[vertex].remove(edge)
 
 
    def minCut(self):
        # idem ici avec une list()
        # while len(self.edges) > 2:
        while len(self.edges.keys())>2:
            e = self.pickEdge()
            print e[0]
            self.contract(e)
            G.delLoops()
 
        return self.cuts
 
G = Graph(dict())
 
f = open("/home/eisti/Documents/coursra/IntegerArrayMinCut.txt", "r")
 
for line in f:
    l = line.split()
    # crée edges[i] = [(i, x) for x ...]
    # avec un dict()
    G.edges[int(l[0])] = [(int(l[0]), int(x)) for x in l[1:]]
    # pourrait faire (avec list())
    # G.edges[int(l[0]) - 1] = [(int(l[0]), int(x)) for x in l[1:]]
 
print G.minCut()

l'utilisation de dict() n'est pas justifiée, AMHA.

Maintenant sans le traceback complet, on peut croire à tout, le débat est lancé

J'avais testé son script en générant un mini-fichier test.txt contenant une ligne data "1 2 3 4".

mais le script n'a pas levé d'exception.

donc mes interrogations sur la pertinence de l'emploi de dict() dans ce script étaient justifiées.

EDIT: au temps pour moi, je viens de trouver au moins une bonne raison d'utiliser des dict() : la discontinuité des indices.

@+.