-
Notifications
You must be signed in to change notification settings - Fork 0
/
Prim.py
162 lines (132 loc) · 4.66 KB
/
Prim.py
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
"""
Algorithme de Prim :
Etant donné un graph non orienté pondéré, trouver l'arbre couvrant de poids mi-
nimal.
Je représente mes graphes en python dans un dictionnaire (map):
exemple :
G = {'a': {'b': 4, 'c': 2},
'b': {'a':5, 'c': 1},
'c': {'a': 2}}
Il y a un arc entre a et b de poid 4, un entre a et c de poid 2, un entre b et
a de poid 5 etc.
J'ai ainsi créé plusieurs méthodes permettant de manipuler les graphes, décrites
ci-dessous.
Il faut préciser à l'algorithme de Prim le sommet de départ, on peut le choisir
aléatoirement.
La sortie de l'algorithme est un autre dictionnaire (map) ayant pour clé un
sommet et en valeur son prédécesseur. Le premier sommet n'a pas de prédecesseur
c'est donc -1.
Remarque :
- On stocke les points restants (et leur distance) sous forme de tas pour
augmenter la complexité, accès ajout et tri très rapide.
Rafael Cartenet
"""
import heapq
import operator
def prim(graph, start):
# Dictionnaire des prédecesseurs.
prev = {}
# Dictionnaire des distances des sommets par rapport à l'arbre construit.
dist = {}
# Set permettant de stocker les sommets déjà visités.
visited = set()
# On initialise les dictionnaires.
for node in graph:
prev[node] = -1 # -1 pour tous les sommets
dist[node] = float('inf') # +Inf pour tous les sommets ..
dist[start] = 0 # .. sauf le premier
# On stocke les sommets restants avec leur distance dans une liste de tuple
# ce qui va nous permettre de trier les sommets restants par rapport à leur
# distance. Passage par des tas (heaps).
remaining_nodes = [(dist[node], node) for node in graph]
while remaining_nodes: # Tant qu'il y a des sommets non reliés à l'arbre.
# Passage en heap (+tri à chaque fois).
heapq.heapify(remaining_nodes)
# Extraction du sommet le plus prêt.
closest_node = heapq.heappop(remaining_nodes)[1]
visited.add(closest_node)
# On met à jour les distances des voisins si besoin, ainsi que les
# sommets précédents.
for node in get_neighbours(graph, closest_node):
if node not in visited:
if graph[closest_node][node] < dist[node]:
dist[node] = graph[closest_node][node]
prev[node] = closest_node
# On supprime le sommet des sommets restants.
ind = list(map(operator.itemgetter(1), remaining_nodes)).index(node)
remaining_nodes[ind] = (dist[node], node)
# on renvoit le dictionnaire de prédecesseurs.
return prev
"""
Méthode permettant d'ajouter un arc entre les sommets edge d'un poid weight.
Nous sommes dans le cas des graphes non orientés donc on ajoute cette arrête aux
deux sommets.
"""
def add_edge(graph, edge, weight):
edge = set(edge)
node1 = edge.pop()
if edge:
node2 = edge.pop()
else:
node2 = node1
graph[node1][node2] = weight
graph[node2][node1] = weight
"""
Méthode permettant d'ajouter un nouveau sommet à mon graphe.
"""
def add_node(graph, node):
if node not in graph:
graph[node] = {}
"""
Méthode permettant de renvoyer tous les sommets voisins d'un noeud.
Sortie : une liste de sommets
"""
def get_neighbours(graph, node):
nodes = []
if node in graph:
for neighbour in graph[node]:
if neighbour not in nodes:
nodes.append(neighbour)
return nodes
"""
Méthode permettant de créer un graphe à partir d'arrêtes. On suppose que notre
graphe ne peux alors pas contenir de points non connectés (pas important).
Les arrêtes sont en entrée sous forme d'une liste d'arrêtes :
[sommet1, sommet2, poid]
Sortie : un graphe
"""
def edges_to_graph(edges):
graph = dict()
for edge in edges:
weight = edge.pop()
node1 = edge.pop()
if node1 not in graph:
add_node(graph, node1)
if edge:
node2 = edge.pop()
if node2 not in graph:
add_node(graph, node2)
else:
node2 = node1
graph[node2][node1] = weight
graph[node1][node2] = weight
return graph
"""
Méthode d'affichage d'un graphe
"""
def to_string(graph):
res = "Graph :\n"
for k in graph:
res += str(k) + " : " + str(graph[k]) + "\n"
return res
E = [['A', 'B', 3],
['A', 'C', 5],
['B', 'C', 6],
['B', 'D', 7],
['C', 'D', 1],
['D', 'C', 2],
['E', 'F', 3],
['F', 'C', 5]]
H = edges_to_graph(E) # Création d'un graphe à partir d'arrêtes.
print(to_string(H)) # Affichage du graphe.
print(prim(H,'A')) # Affichage des prédecesseurs de l'arbre obtenu.