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
|
from src.helper.debug_printer import debug_print
import parameters as params
import networkx as nx
def vertex_cover_glouton(graph):
"""
Renvoie un ensemble de sommets couvrant toutes les arêtes du graphe.
Approche gloutonne.
"""
G = graph.copy()
cover = set()
while G.number_of_edges() > 0:
u = max(G.degree, key=lambda x: x[1])[0] # Max degree
cover.add(u)
G.remove_node(u)
return cover
def get_snowed_edges(graph, cover_nodes, snow_min, snow_max):
"""
Retourne les arêtes enneigées couvertes par les sommets sélectionnés.
"""
snowy_edges = []
no_snowy_edges = []
for u, v, key in graph.edges(keys=True): # toutes les arretes du graphe
if u in cover_nodes or v in cover_nodes:
data = graph.get_edge_data(u, v, key)
if 'snow' in data and snow_min <= data['snow'] <= snow_max:
snowy_edges.append((u, v, key))
else:
no_snowy_edges.append((u, v, key))
return (snowy_edges, no_snowy_edges)
def vertex_cover(graph, debug_mode=False):
"""
Stratégie :
Trouver un ensemble minimum de sommets pour couvrir toutes les arêtes.
"""
debug_print(f"Passage du graphe en mode : undirected", debug_mode)
graph = nx.to_undirected(graph)
# debug_print(f"List Sommets total : {graph.nodes}", debug_mode)
# debug_print(f"List Routes total : {graph.edges}", debug_mode)
debug_print(f"Nombre de sommets total : {len(graph.nodes)}", debug_mode)
debug_print(f"Nombre de routes total : {len(graph.edges)}", debug_mode)
debug_print("Calcul de la couverture par sommet ...", debug_mode)
nodes = vertex_cover_glouton(graph)
debug_print(f"Nombre de sommets sélectionnés : {len(nodes)}", debug_mode)
snowy_edges = get_snowed_edges(graph,
nodes,
params.SNOW_THRESHOLD,
params.SNOW_MAX)
return snowy_edges
|
