1 files changed, 59 insertions, 0 deletions
diff --git a/ero1/src/drone/couverture_sommets.py b/ero1/src/drone/couverture_sommets.py
new file mode 100644
index 0000000..80a1fe6
--- /dev/null
+++ b/ero1/src/drone/couverture_sommets.py
@@ -0,0 +1,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