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() |
