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