From 967be9e750221ab2ab783f95df79bb26d290a45e Mon Sep 17 00:00:00 2001 From: Martial Simon Date: Mon, 15 Sep 2025 01:07:58 +0200 Subject: add: added projects --- ero1/.gitignore | 13 + ero1/AUTHORS | 5 + ero1/README.md | 108 ++++++++ ero1/clear.sh | 27 ++ ero1/demo.py | 111 ++++++++ ero1/parameters.py | 47 ++++ ero1/rapport ERO1.pdf | Bin 0 -> 396792 bytes ero1/requirements.txt | 31 +++ ero1/run.sh | 3 + ero1/setup.sh | 36 +++ ero1/src/README.md | 88 +++++++ ero1/src/demo/ask_variable.py | 26 ++ ero1/src/demo/demo_cost.py | 41 +++ ero1/src/demo/demo_exec.py | 229 +++++++++++++++++ ero1/src/demo/demo_final_report.py | 110 ++++++++ ero1/src/demo/demo_stats.py | 64 +++++ ero1/src/demo/print_demo.py | 20 ++ ero1/src/deneigeuses/basic_euler.py | 48 ++++ ero1/src/deneigeuses/directed_cpp.py | 294 ++++++++++++++++++++++ ero1/src/deneigeuses/drone_path.py | 23 ++ ero1/src/deneigeuses/hangar_to_deneigeuse.py | 35 +++ ero1/src/deneigeuses/hierholzer_v1.py | 128 ++++++++++ ero1/src/deneigeuses/hierholzer_v2.py | 168 +++++++++++++ ero1/src/deneigeuses/maps/verdun.py | 37 +++ ero1/src/drone/couverture_sommets.py | 59 +++++ ero1/src/drone/postier_chinoisV1.py | 209 +++++++++++++++ ero1/src/drone/postier_chinoisV2.py | 258 +++++++++++++++++++ ero1/src/drone/postier_chinoisV3.py | 253 +++++++++++++++++++ ero1/src/drone/postier_chinois_Martial.py | 122 +++++++++ ero1/src/drone/postier_chinois_montreal.py | 89 +++++++ ero1/src/generation/graph_generation.py | 17 ++ ero1/src/generation/habitation_generation.py | 24 ++ ero1/src/generation/snow_generation.py | 85 +++++++ ero1/src/generation/suburb_snowplow_generation.py | 88 +++++++ ero1/src/helper/check_eulerian.py | 77 ++++++ ero1/src/helper/color_suburbs.py | 70 ++++++ ero1/src/helper/debug_printer.py | 13 + ero1/src/helper/display_graph.py | 116 +++++++++ ero1/src/helper/duplicate_removal.py | 16 ++ ero1/src/helper/export_cost.py | 60 +++++ ero1/src/helper/export_import_yaml.py | 20 ++ ero1/src/helper/export_to_kml.py | 95 +++++++ ero1/src/helper/main_parcours.py | 137 ++++++++++ ero1/src/helper/output_debug.py | 36 +++ ero1/src/helper/partitions.py | 129 ++++++++++ ero1/src/helper/prune_maps.py | 76 ++++++ ero1/src/tests/snow_testing.py | 17 ++ ero1/start_dev.py | 42 ++++ ero1/temp/README.md | 18 ++ 49 files changed, 3818 insertions(+) create mode 100644 ero1/.gitignore create mode 100644 ero1/AUTHORS create mode 100644 ero1/README.md create mode 100755 ero1/clear.sh create mode 100644 ero1/demo.py create mode 100644 ero1/parameters.py create mode 100644 ero1/rapport ERO1.pdf create mode 100644 ero1/requirements.txt create mode 100755 ero1/run.sh create mode 100755 ero1/setup.sh create mode 100644 ero1/src/README.md create mode 100644 ero1/src/demo/ask_variable.py create mode 100644 ero1/src/demo/demo_cost.py create mode 100644 ero1/src/demo/demo_exec.py create mode 100644 ero1/src/demo/demo_final_report.py create mode 100644 ero1/src/demo/demo_stats.py create mode 100644 ero1/src/demo/print_demo.py create mode 100644 ero1/src/deneigeuses/basic_euler.py create mode 100644 ero1/src/deneigeuses/directed_cpp.py create mode 100644 ero1/src/deneigeuses/drone_path.py create mode 100644 ero1/src/deneigeuses/hangar_to_deneigeuse.py create mode 100644 ero1/src/deneigeuses/hierholzer_v1.py create mode 100644 ero1/src/deneigeuses/hierholzer_v2.py create mode 100644 ero1/src/deneigeuses/maps/verdun.py create mode 100644 ero1/src/drone/couverture_sommets.py create mode 100644 ero1/src/drone/postier_chinoisV1.py create mode 100644 ero1/src/drone/postier_chinoisV2.py create mode 100644 ero1/src/drone/postier_chinoisV3.py create mode 100644 ero1/src/drone/postier_chinois_Martial.py create mode 100644 ero1/src/drone/postier_chinois_montreal.py create mode 100644 ero1/src/generation/graph_generation.py create mode 100644 ero1/src/generation/habitation_generation.py create mode 100644 ero1/src/generation/snow_generation.py create mode 100644 ero1/src/generation/suburb_snowplow_generation.py create mode 100644 ero1/src/helper/check_eulerian.py create mode 100644 ero1/src/helper/color_suburbs.py create mode 100644 ero1/src/helper/debug_printer.py create mode 100644 ero1/src/helper/display_graph.py create mode 100644 ero1/src/helper/duplicate_removal.py create mode 100644 ero1/src/helper/export_cost.py create mode 100644 ero1/src/helper/export_import_yaml.py create mode 100644 ero1/src/helper/export_to_kml.py create mode 100644 ero1/src/helper/main_parcours.py create mode 100644 ero1/src/helper/output_debug.py create mode 100644 ero1/src/helper/partitions.py create mode 100644 ero1/src/helper/prune_maps.py create mode 100644 ero1/src/tests/snow_testing.py create mode 100644 ero1/start_dev.py create mode 100644 ero1/temp/README.md (limited to 'ero1') diff --git a/ero1/.gitignore b/ero1/.gitignore new file mode 100644 index 0000000..7feb27b --- /dev/null +++ b/ero1/.gitignore @@ -0,0 +1,13 @@ +cache/* +venv/* +venv +cache +__pycache__/ +*.png +*.jpg +export_cost.txt +parcours_deneigeuses.kml +test.py +test2.py +*.kml +*.yml \ No newline at end of file diff --git a/ero1/AUTHORS b/ero1/AUTHORS new file mode 100644 index 0000000..daeca38 --- /dev/null +++ b/ero1/AUTHORS @@ -0,0 +1,5 @@ +Martial SIMON +Arthur MAGNIN +Maxence MONCEL +Emilien DUCIEL +Samuel MARTINEZ diff --git a/ero1/README.md b/ero1/README.md new file mode 100644 index 0000000..3e1343f --- /dev/null +++ b/ero1/README.md @@ -0,0 +1,108 @@ +# ERO1 + +## Le projet + +### Descriptif rapide du projet + +La ville de Montréal demande une étude pour rendre le déneigement plus efficace et moins coûteux. +Il faut organiser le survol des routes par drone, planifier les trajets des véhicules et proposer +différents scénarios de coûts selon le matériel utilisé. + +### Récapitulatif des attentes + +#### Science et outils d'ingénieurie + +- Données, variables et contraintes clairement définies, + +- Modèle détaillé & justifié, + +- Optimisation expliquées en lien avec le contexte + +#### Identification des ressources et outils + +- Recherche de méthodes variées, + +- Comparaison argumentée avec le contexte + +#### Prototype + +- Programme lisible | testable, + +- Interface, + +- Plusieurs cas testés, + +- Identification des goulets d'étranglement + +#### Qualité + +- Comparatifs avec des indicateurs variés + justifiés, + +- Plusieurs scénarios + +### Architecture du projet + +Les détails donnés sont en lien avec le code produit et les résultats obtenus. +Ne seront pas mentionnés dans ces descriptifs: `venv`, les dossiers cache, `AUTHORS` et `README.md` + +#### Description des dossiers : + +- `src` : Ce dossier contient l'ensemble des dossiers dédiés au code source. + Un détail de chaque dossier est présent dans `./src/README.md` + +- `temp` : Ce dossier contient les fichiers temporaires générés pendant l'exécution du programme. + Un détail de chaque fichier est présent dans `./temp/README.md` + +- `paths` : Ce dossier contient des fichiers YAML qui correspondent aux résultats des différents + parcous de drône avec les différentes versions du postier chinois + +#### Description des fichiers : + +- `setup.sh` : Script shell qui initialise un venv et télécharge les modules pythons à partir de `requirements.txt` + +- `clear.sh` : Script shell qui supprime le venv créé par `setup.sh` + +- `run.sh` : Script shell qui permet de lancer la démo de notre projet + +- `requirements.txt` : L'ensemble des modules/libs python utilisés directement et indirectement pour ERO1 + +- `start_dev.py` : L'ANCIEN fichier à executer, il controlait et mettais en commun les grandes étapes du projet, + A NE PAS UTILISER + +- `parameters.py` : Contient nos 'variables d'environnement' pour ce projet afin de pouvoir + modifier chaque paramètre du projet facilement et d'avoir des comparaisons plus exhaustives + +- `demo.py` : Le nouveau fichier de test; lance une démonstration intercative où vous pouvez choisir + le parcours du drone, le parcours des déneigeuses, le nombre de déneigeuses ... + Voici quelques précision: + => l'implémentation naive ne permet pas de gérer plusieurs déneigeuses, elle ne peut pas non plus gérer les 5 quartiers en même temps + => l'implémantion du chinese postman problem pour les déneigeuses est limité à seul quartier + +## Mode d'emploi + +### Installation +Pré-requis: `requirements.txt`, `setup.sh`, le package `python3`, un shell fonctionnel +Exécuter `./setup.sh` + +Une fois l'éxecution de `setup.sh` terminée, vous pouvez : +1. utiliser `./venv/bin/python` comme interpreteur python +2. OU activer manuellement le venv avec la commande : `source ./venv/bin/activate` + +### Execution +Pré-requis: `run.sh`, un shell fonctionnel +Exécuter `./run.sh` + +Ce fichier lancera la démonstration (`demo.py`), il est nécessaire d'avoir réaliser l'étape d'installation car le fichier `run.sh` utilise lui même l'environemment `./venv/bin/python` + +A l'issue de cette démo, vous pourrez retrouver le path du drone dans `paths` et les résultats de la déneigeuse sous format KML dans `temp` + +### Désinstallation +Pré-requis: `clear.sh`, un shell fonctionnel +Exécuter `./clear.sh` + +Ce fichier supprimera le dossier `venv`. Les dossiers de cache comme `cache` et +`__pycache__` ne sont pas automatiquement supprimés pour éviter de devoir re-télécharger +chaque module python se trouvant dans `requirements.txt` à chaque initialisation du venv. + +*Attention*: Si le venv a manuellement été activé, il est recommandé d'utiliser la commande +`deactivate` avant d'exectuer le script `clear.sh` diff --git a/ero1/clear.sh b/ero1/clear.sh new file mode 100755 index 0000000..91b685e --- /dev/null +++ b/ero1/clear.sh @@ -0,0 +1,27 @@ +#!/bin/sh + +echo "Starting the deactivation and clearing process" + +# echo "Deactivating the venv" +# +# deactivate +# +# res_code=$? +# +# if [ $res_code -ne 0 ]; +# then +# echo "failed to deactivate the venv" +# return; +# fi + +rm -r venv + +res_code=$? + +if [ $res_code -ne 0 ]; +then + echo "failed to delete the venv directory" + return; +fi + +echo "venv correctly cleared at $PWD" diff --git a/ero1/demo.py b/ero1/demo.py new file mode 100644 index 0000000..d8042be --- /dev/null +++ b/ero1/demo.py @@ -0,0 +1,111 @@ +# IMPORT FOR DEMO +from src.demo.ask_variable import ask_variable +from src.demo.print_demo import print_demo +from src.demo.demo_exec import demo_exec + +# LIB IMPORT +import os, time + +def display_status(drone=None, déneigeuse=None, arrondissement=None, debug=None): + ''' + Affiche le statut de la démonstration. + Parameters: + arrondissement : L'arrondissement choisi. + drone : Le drone choisi. + déneigeuse : La déneigeuse choisie. + debug : Le mode debug choisi. + ''' + os.system('cls' if os.name == 'nt' else 'clear') + print("") + if arrondissement: + print_demo("Arrondissement choisi : " + arrondissement, 1) + if drone: + print_demo("Drone choisi : " + drone, 1) + if déneigeuse: + print_demo("Déneigeuse choisi : " + déneigeuse, 1) + if debug is not None: + print_demo("Debug : " + ("Oui" if debug else "Non"), 1) + print("") + + +if __name__ == "__main__": + ''' + Départ de la démonstration. + ''' + try: + os.system('cls' if os.name == 'nt' else 'clear') + + # ---------------------- CHOIX DU PARCOURS DE DRONE --------------------------- + + Q_drone = "Quel parcours de drone voulez-vous faire ?" + A_drone = [ + ("Postier Chinois V1 : Cette version est la version naïve avec NetworkX qui est plus longue mais distances plus optimisées. (Environ 30min)", "postier_chinoisV1"), + ("Postier Chinois V2 : Cette version le plus rapide mais les distances sont moins optimisées. (Environ 3min)", "postier_chinoisV2"), + ("Postier Chinois V3 : Cette version est une version intermédiaire entre la V1 et la V2 avec une distance optimisée et un calcul rapide. (Environ 4min)", "postier_chinoisV3"), + ("Drones Sauvegardés : Charger un fichier sauvegarde des chemins générés par les algorithmes ci-dessus en YML.", "fichier") + ] + drone = ask_variable(Q_drone, A_drone) + if drone == "fichier": + Q_drone = "Quel fichier souhaitez-vous charger ?" + A_drone = [] + num=0 + display_status(drone) + for racine, repertoires, fichiers in os.walk("paths"): + for fichier in fichiers: + if fichier.endswith(".yml"): + num+=1 + (mode, ino, dev, nlink, uid, gid, size, atime, mtime, ctime) = os.stat(f"paths/{fichier}") + A_drone.append((f"{fichier} - {time.ctime(mtime)}",f"paths/{fichier}")) + + drone = ask_variable(Q_drone, A_drone) + + display_status(drone) + + # ---------------------- CHOIX DU PARCOURS DE DÉNEIGEUSE --------------------------- + + Q_déneigeuse = "Quel parcours de déneigeuse voulez-vous faire ?" + A_déneigeuse = [ + ("Hierholzer V1 : Cette première version est rapide à l'exécution mais reste bloquée dans les impasses/cycles.", "hierholzer_v1"), + ("Hierholzer V2 : Cette deuxième version est rapide à l'exécution mais les distances ne sont pas optimisées.", "hierholzer_v2"), + ("Postier Chinois orienté : Cet algorithme est un glouton qui cherche à équilibrer le graphe pour en extraire un circuit eulérien. (Uniquement sur 1 arrondissement)", "oriented_cpt"), + ("Implémentation naïve : Une implémentation simple mais qui fournit un parcours très peu optimal, basée sur le parcours du drone. (Uniquement sur 1 arrondissement | Uniquement sur 1 déneigeuse)", "naive"), + ] + déneigeuse = ask_variable(Q_déneigeuse, A_déneigeuse) + + display_status(drone, déneigeuse) + + # ---------------------- CHOIX DE L'ARRONDISSEMENT --------------------------- + + Q_arrondissement = "Sur quel arrondissement voulez-vous faire le parcours ?" + A_arrondissement = [ + ("Outremont", "Outremont"), + ("Verdun", "Verdun"), + ("Anjou", "Anjou"), + ("Rivière-des-Prairies–Pointe-aux-Trembles","Rivière-des-Prairies–Pointe-aux-Trembles"), + ("Le Plateau-Mont-Royal", "Le Plateau-Mont-Royal") + ] + if déneigeuse == "naive" or déneigeuse == "oriented_cpt": + print_demo("/!\\ L'algorithme de déneigeuse choisi ne dispose pas de la possibilité d'effectuer les 5 arrondissements en une seule fois.") + else: + A_arrondissement.append(("Tous les secteurs ci-dessus", "all")) + + arrondissement = ask_variable(Q_arrondissement, A_arrondissement) + arrondissements = ["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"] if arrondissement == "all" else [arrondissement] + + display_status(drone, déneigeuse, arrondissement) + + + # ---------------------- CHOIX DU MODE DEBUG --------------------------- + + Q_debug = "Voulez-vous activer le mode debug ?" + A_debug = [("Oui", True), ("Non", False)] + debug = ask_variable(Q_debug, A_debug) + + display_status(drone, déneigeuse, arrondissement, debug) + + # ---------------------- EXECUTION DE LA DEMONSTRATION --------------------------- + + demo_exec(arrondissements, drone, déneigeuse, debug) + + except KeyboardInterrupt: # Si l'utilisateur appuie sur Ctrl+C ou arrête le programme. + print_demo("Arrêt du programme", 1) \ No newline at end of file diff --git a/ero1/parameters.py b/ero1/parameters.py new file mode 100644 index 0000000..1c84720 --- /dev/null +++ b/ero1/parameters.py @@ -0,0 +1,47 @@ +# This file contains all parameters that will be used across ERO1 +# The goal of this file is to easily change the core parameters to make +# different observations + +# Costs (in euros); + +SUPER_DRONE_SPEED: float = 70 +SUPER_DRONE_COST_FIXED: float = 100 +SUPER_DRONE_COST_KILO: float = 0.01 + +TYPE_I_COST_FIXED: float = 500 +TYPE_I_COST_KILO: float = 1.1 +TYPE_I_COST_HOUR_UNDER_8: float = 1.1 +TYPE_I_COST_HOUR_ABOVE_8: float = 1.3 + +TYPE_II_COST_FIXED: float = 800 +TYPE_II_COST_KILO: float = 1.3 +TYPE_II_COST_HOUR_UNDER_8: float = 1.3 +TYPE_II_COST_HOUR_ABOVE_8: float = 1.5 + +# Speed (in km/h); + +TYPE_I_SPEED: int = 10 +TYPE_II_SPEED: int = 20 + +# Availability; + +SUPER_DRONE_AMOUNT: int = 1 +TYPE_I_AMOUNT: int = 5 +TYPE_II_AMOUNT: int = 0 + +# Snow; + +SNOW_MAX: float = 15 # (in cm) +SNOW_MIN: float = 0 # (in cm) +SNOW_THRESHOLD: float = 2.5 # (in cm) +# the quantity where whe should start to retrieve the snow + +HABITATION_PERCENTAGE = 0.02 # 10% of the roads will have habitation +SNOW_PERCENTAGE: float = 0.75 # 75% of the roads will have over 2.5 cm of snow +# peut etre faire un autre système ... +# à voir l'implé de la fonction qui dépose la neige + +# Graph; + +ALGORITHM_NAME: str = "NOM ALGORITHME ICI" +DEFAULT_PLACE_NAME: str = "Verdun" \ No newline at end of file diff --git a/ero1/rapport ERO1.pdf b/ero1/rapport ERO1.pdf new file mode 100644 index 0000000..35ab1b6 Binary files /dev/null and b/ero1/rapport ERO1.pdf differ diff --git a/ero1/requirements.txt b/ero1/requirements.txt new file mode 100644 index 0000000..1e51b91 --- /dev/null +++ b/ero1/requirements.txt @@ -0,0 +1,31 @@ +numpy==1.26.4 +networkx==3.4.2 +contourpy==1.3.2 +cycler==0.12.1 +fonttools==4.58.0 +kiwisolver==1.4.8 +matplotlib==3.10.3 +packaging==25.0 +pillow==11.2.1 +pyparsing==3.2.3 +python-dateutil==2.9.0.post0 +six==1.17.0 +certifi==2025.4.26 +charset-normalizer==3.4.2 +geopandas==1.0.1 +idna==3.10 +osmnx==2.0.3 +pandas==2.2.3 +pyogrio==0.11.0 +pyproj==3.7.1 +pytz==2025.2 +requests==2.32.3 +shapely==2.1.1 +tzdata==2025.2 +urllib3==2.4.0 +pyyaml==6.0.2 +simplekml==1.3.6 +joblib==1.5.1 +scikit-learn==1.6.1 +scipy==1.15.3 +threadpoolctl==3.6.0 diff --git a/ero1/run.sh b/ero1/run.sh new file mode 100755 index 0000000..600da31 --- /dev/null +++ b/ero1/run.sh @@ -0,0 +1,3 @@ +#!/bin/sh + +./venv/bin/python3 demo.py diff --git a/ero1/setup.sh b/ero1/setup.sh new file mode 100755 index 0000000..1a5a29e --- /dev/null +++ b/ero1/setup.sh @@ -0,0 +1,36 @@ +echo "Setting up venv" + +python3 -m venv venv # 1>/dev/null 2>/dev/null + +res_code=$? + +if [ $res_code -ne 0 ]; +then + echo "Please make sure python3 is installed on your machine and that you have the right to create a venv here" + return; +fi + +echo "activating the venv" + +. venv/bin/activate # 1>/dev/null 2>/dev/null + +res_code=$? + +if [ $res_code -ne 0 ]; +then + echo "could not activate the venv, please check that $PWD/venv/bin/activate exists and that you have the right to source it" + return; +fi + +echo "adding the necessary packages to the venv" + +pip install -r requirements.txt + +if [ $res_code -ne 0 ]; +then + echo "could not download all requirements in the file $PWD/requirements.txt" + return; +fi + +echo "venv correctly setup at $PWD" + diff --git a/ero1/src/README.md b/ero1/src/README.md new file mode 100644 index 0000000..7e34150 --- /dev/null +++ b/ero1/src/README.md @@ -0,0 +1,88 @@ +# Dossier Source + +Ce dossier contient plusieurs dossiers qui contiennent la logique du projet à travers +des fichiers python. +Afin d'éviter d'avoir un trop grand nombre de fichiers README.md, les détails des fichiers +seront, en plus des détails des dossier, donnés ci-dessous; + + +## Dossier `src/deneigeuses` + +Ce dossier contient l'ensemble des algorithmes clés pour l'étape des déneigeuses; + +### Descriptif des dossiers/fichiers de `deneigeuses` + +- `basic_euler.py` : Une des premières implémentations du parcours par la déneigeuse. Très mauvais car nécessite d'avoir un graph Eulériser par NetworkX ce qui le rends non orienté et non valide pour un parcours de déneigeuse + +- `directed_cpp.py` : Une version du problème du postier chinois sur un graphe orienté. ATTENTION, ne fonctionne que sur des graphes **fortement connexes**. Voici le document sur lequel est basé notre implémentation: https://www3.cs.stonybrook.edu/~algorith/implement/cpp/distrib/SPAEcpp.pdf + +- `drone_path.py` : Implémentation naïve qui extrapole le parcours de la déneigeuse à partir de celui du drone. + +- `hierolzer.py` : TODO + +- dossier `maps` : TODO + - `verdun.py` : TODO + + +## Dossier `src/drone` + +Ce dossier contient l'ensemble des algorithmes clés pour l'étape des déneigeuses; + +### Descriptif des dossiers/fichiers de `drone` + +- `couverture_sommets.py` : approche gloutonne du problème du drône + +- `postier_chinois_Martial.py` : première implémentation du postier chinois sur un seul quartier + +- `postier_chinoisV1.py` : parcours du drone sur tout montréal via une décomposition par arrondissement. Utilisation de l'algorithme du Postier chinois avec une eulerization du graphe fait à la main. + +- `postier_chinoisV2.py` : parcours du drone sur tout montréal via une décomposition par arrondissement. Utilisation de l'algorithme du Postier chinois avec l'eulerization de networkX. + +- `postier_chinoisV3.py` : parcours du drone sur tout montréal via une décomposition par arrondissement. Utilisation de l'algorithme du Postier chinois avec une eulerization issue de NetworkX mais légerement modifier pour etre plus rapide. + + +## Dossier `src/generation` + +Ce dossier contient diverses fonctions de génération en tout genre; + +### Descriptif des dossiers/fichiers de `generation` + +- `graph_generation.py` : génère un graph à partir d'un nom de lieu et de la lib osmnx + +- `snow_generation.py` : dépose de manière aléatoire de la neige sur une partie du graphe + +TODO : vérif si `suburb_snowplow_generation.py` existe sur la branche main +- `suburb_snowplow_generation.py` : créer un graphe à partir d'une liste de noms de lieux et + du résultat du parcours du drône + + +## Dossier `src/helper` + +Ce dossier des fonctions en tout genre qui sont utiles pour certains algorithmes; + +### Descriptif des dossiers/fichiers de `helper` + +- `check_eulerian.py` : vérifie si un graphe est eulerien (pour graphes orientés et non orientés) + +- `color_suburbs.py` : affiche chaque quartiers de Montréal, à partir du résulat du drone, chacun avec une couleur unique + +- `debug_printer.py` : affiche l'heure et le message donné seulement si le mode debug est activé + +- `display_graph.py` : fonctions pour un affichage légendé d'un graphe + +- `duplicate_removal.py` : supprime tous les doublons de la forme (u,v) pour les graphes générés pas osmnx + +- `export_cost.py` : créer le fichier `temp/export_cost.txt` à partir des différents parcours (drone/déneigeuse) + +- `export_import_yaml.py` : charge et sauvegarde le parcours du drone sous format yaml dans le dossier `paths` + +- `export_to_kml.py` : exporte le parcours des déneigeuses dans le fichier `temp/parcours_deneigeuse.kml` + +- `main_parcours.py` : la fonction qui appelle toutes les fontions de parcours et potentielles fonctions helpers au besoin + +- `output_debug.py` : utilisé pour faire des tests fonctionnels des fonctions nouvellement implémentées sans avoir a casser toute la logique de `main_parcours.py` + +- `partitions.py` : partitionne un graphe en K sous graphes, propose aussi une fonction d'affichage pour les partitions + +- `prune_maps.py` : enlève les arrêtes symptomatiques (les graphes de osmnx + n'étant pas fortement connexes, les déneigeuses peuvent rester bloquées) diff --git a/ero1/src/demo/ask_variable.py b/ero1/src/demo/ask_variable.py new file mode 100644 index 0000000..f2f9330 --- /dev/null +++ b/ero1/src/demo/ask_variable.py @@ -0,0 +1,26 @@ +from src.demo.print_demo import print_demo +import os + +def ask_variable(question, answers): + """ + Pose une question avec des réponses multiples et attend une réponse de l'utilisateur. + Parameters: + question : La question à afficher + answers : Liste de tuples contenant (réponse, valeur) + """ + print("") + print_demo(f"{question}") + for i, (answer_text, _) in enumerate(answers, 1): + print_demo(f"{i}. {answer_text}", 1) + + while True: + try: + choice = input("\n⟩ Entrez le numéro de votre choix ou 'stop' pour arrêter : ") + if choice == "stop": + raise KeyboardInterrupt + choice = int(choice) + if 1 <= choice <= len(answers): + return answers[choice - 1][1] + print_demo(f"Insérez un nombre entre 1 et {len(answers)}", 1) + except ValueError: + print_demo(f"Insérez un nombre entre 1 et {len(answers)}", 1) diff --git a/ero1/src/demo/demo_cost.py b/ero1/src/demo/demo_cost.py new file mode 100644 index 0000000..573e367 --- /dev/null +++ b/ero1/src/demo/demo_cost.py @@ -0,0 +1,41 @@ +import math + +def get_edge_length(graph, u, v): + try: + return graph[u][v][0]['length'] + except KeyError: + try: + return graph[v][u][0]['length'] + except KeyError: + return 0 + +def format_time(time_seconds): + seconds = math.ceil(time_seconds % 60) + minutes = math.floor(time_seconds / 60) + if minutes == 0: + return f"{seconds} secondes" + return f"{minutes} minute(s) et {seconds} secondes" + +def export_drone(graph, time_exec, parcours): + total_dist = 0 + time_exec = time_exec / 60 + total_dist += math.ceil(sum(get_edge_length(graph, u, v) for u, v in parcours)) + + return { + "dist":total_dist, + "time":{ + "format":format_time(time_exec), + "value":time_exec + } + } + +def export_deneigeuse(graph, time_exec, parcours): + total_dist = math.ceil(sum(get_edge_length(graph, u, v) for u, v in parcours)) + + return { + "dist":total_dist, + "time":{ + "format":format_time(time_exec), + "value":time_exec + } + } \ No newline at end of file diff --git a/ero1/src/demo/demo_exec.py b/ero1/src/demo/demo_exec.py new file mode 100644 index 0000000..1242ff5 --- /dev/null +++ b/ero1/src/demo/demo_exec.py @@ -0,0 +1,229 @@ +# DEMO IMPORT +from src.demo.print_demo import print_demo +from src.demo.ask_variable import ask_variable +from src.helper.color_suburbs import display_suburbs_with_colors +from src.demo.demo_cost import export_deneigeuse, export_drone, get_edge_length +from src.demo.demo_stats import stats_deneigeuses, stats_drone +from src.demo.demo_final_report import * # nsm, flemme de trier + +# IMPORT FOR GENERATION +from src.generation.graph_generation import generate_graph +from src.generation.suburb_snowplow_generation import generate_quartiers_from_path + +# IMPORT FOR DRONE: +from src.drone.postier_chinoisV2 import final_path, postier_chinois_process_v2, connect_circuits +from src.drone.postier_chinoisV1 import postier_chinois_process_v1 +from src.drone.postier_chinoisV3 import postier_chinois_process_v3 + +# IMPORT FOR DENEIGEUSE: +from src.deneigeuses.hierholzer_v1 import process_hierholzer_v1 +from src.deneigeuses.hierholzer_v2 import process_hierholzer_v2 +from src.deneigeuses.directed_cpp import oriented_cpt +from src.deneigeuses.drone_path import drone_path +from src.helper.partitions import partition +from src.deneigeuses.hangar_to_deneigeuse import path_hangar_to_deneigeuse, path_deneigeuse_to_hangar + +# IMPORT FOR YAML & KML +from src.helper.export_to_kml import export_to_kml +from src.helper.export_import_yaml import load_paths_from_yaml +import os +import time + + +def demo_exec(place, drone, deneigeuse, debug): + """ + Fonction principale pour le démarrage de la démo. + Parameters: + place : Liste des arrondissements à parcourir. + drone : Type de drone à utiliser. + deneigeuse : Type de déneigeuse à utiliser. + debug : Mode debug activé ou non. + """ + + # ---------------------- INITIALISATION --------------------------- + + os.system('cls' if os.name == 'nt' else 'clear') + print_demo("Démarrage du programme sur :", time=True) + for lieu in place: + print_demo(lieu, indent=1) + print("") + + # ---------------------- GENERATION DU GRAPHE --------------------------- + + print_demo("Génération du graph de Montréal en cours...", time=True) + graph = generate_graph("Montréal, Québec, Canada", debug_mode=debug) + print_demo("Graph généré avec succès.", indent=1) + + # ---------------------- PARCOURS - DRONE --------------------------- + + start_time_drone = time.time() + if drone == "postier_chinoisV1": + print_demo("Parcours du drone sur Montréal avec la version 1.", time=True) + parcours_drone, finalPath = postier_chinois_process_v1(graph, debug) + + elif drone == "postier_chinoisV2": + print_demo("Parcours du drone sur Montréal avec la version 2.", time=True) + parcours_drone, finalPath = postier_chinois_process_v2(graph, debug) + + elif drone == "postier_chinoisV3": + print_demo("Parcours du drone sur Montréal avec la version 3.", time=True) + parcours_drone, finalPath = postier_chinois_process_v3(graph, debug) + else: + print_demo(f"Récupération du parcours de Montréal sur le fichier : {drone}", time=True) + parcours_drone = load_paths_from_yaml(graph, drone) + finalPath = final_path(graph, parcours_drone) + + end_time_drone = time.time() + print_demo("Parcours du drone effectué avec succès.", indent=1) + + # ---------------------- AFFICHAGE DU GRAPHE --------------------------- + + Q_display = "Voulez-vous afficher le graph du parcours du drone ?" + A_display = [("Oui", True), ("Non", False)] + display = ask_variable(Q_display, A_display) + if display: + connections = connect_circuits(graph, parcours_drone) + display_suburbs_with_colors(graph, parcours_drone, connections) + + # ---------------------- RECUPERATION DU PARCOURS DU DRONE --------------------------- + + parcours_drone_arrondissements = [] + for elt in place: + if elt in parcours_drone: + parcours_drone_arrondissements.extend(parcours_drone[elt]) + else: + raise ValueError(f"{elt} introuvable dans le parcours du drone.") + + # ---------------------- CALCUL DES COUTS - DRONE --------------------------- + + cost_drone = export_drone( + graph, end_time_drone-start_time_drone, finalPath) + stat_drone = stats_drone(cost_drone) + + # ---------------------- CALCUL DU NOMBRE OPTIMAL DE DÉNEIGEUSES --------------------------- + + if deneigeuse == "naive": + print_demo("/!\\ L'algorithme de déneigeuse choisi ne dispose pas de la possibilité d'avoir plusieurs déneigeuses.", time=True) + number_of_deneigeuses = [1] + else: + optimal_number_deneigeuses = max(1, round((sum(get_edge_length( + graph, u, v) for u, v in parcours_drone_arrondissements)) / 200000)) + + Q_deneigeuse_number = "Avec quel nombre de déneigeuses voulez-vous comparer les coûts ?" + A_deneigeuse_number = [ + ("1 déneigeuse", 1), + (f"{optimal_number_deneigeuses} déneigeuses - Version Optimale", optimal_number_deneigeuses), + (f"{optimal_number_deneigeuses * 2} déneigeuses", optimal_number_deneigeuses * 2), (f"{optimal_number_deneigeuses * 3} déneigeuses", optimal_number_deneigeuses * 3), + ("Faire toutes les partitions et comparer les coûts", 0)] + number_reply = ask_variable(Q_deneigeuse_number, A_deneigeuse_number) + if number_reply == 0: + number_of_deneigeuses = [optimal_number_deneigeuses, 1, + optimal_number_deneigeuses * 2, optimal_number_deneigeuses * 3] + else: + number_of_deneigeuses = [number_reply] + print("") + + # ---------------------- GENERATION DU GRAPHE DE PARTITIONS --------------------------- + + G_partition = generate_quartiers_from_path( + parcours_drone, graph, suburb_list=place, debug_mode=debug) + + # ---------------------- PARCOURS - DÉNEIGEUSES --------------------------- + + if deneigeuse == "hierholzer_v1" or deneigeuse == "hierholzer_v2": + print_demo("Parcours de la déneigeuse à partir de l'algorithme de Hierholzer", time=True) + elif deneigeuse == "naive": + print_demo("Parcours de la déneigeuse à partir de l'implémentation naïve", time=True) + else: + print_demo("Parcours de la déneigeuse à partir de l'algorithme du Postier Chinois Orienté", time=True) + + cost_deneigeuses = {} + parcours_deneigeuses = {} + for i in number_of_deneigeuses: + cost_deneigeuses[i] = [] + parcours_deneigeuses[i] = [] + + if i == 1 and (deneigeuse == "naive" or "hierholzer" in deneigeuse): + temp = [] + for arrondissement in place: + temp.extend(parcours_drone[arrondissement]) + partitions = [temp] + else: + partitions = partition(G_partition, i, debug_mode=debug) + + for part in partitions: + start_time_deneigeuse = time.time() + drone_edges = [(u, v) for u, v in part.edges()] if i != 1 else part + + if "hierholzer" in deneigeuse: + if deneigeuse == "hierholzer_v2": + parcours_deneigeuse = process_hierholzer_v2( + graph, drone_edges, debug) + else: + parcours_deneigeuse = process_hierholzer_v1( + graph, drone_edges, debug) + + start_node = parcours_deneigeuse[0][0] + parcours_HangarDeneigeuse = path_hangar_to_deneigeuse( + graph, start_node) + end_node = parcours_deneigeuse[-1][1] + parcours_DeneigeuseHangar = path_deneigeuse_to_hangar( + graph, end_node) + + parcours_deneigeuse = parcours_HangarDeneigeuse + parcours_deneigeuse + parcours_DeneigeuseHangar + if deneigeuse == "oriented_cpt": + parcours_deneigeuse = oriented_cpt(part, graph, debug) + + start_node = parcours_deneigeuse[0][0] + parcours_HangarDeneigeuse = path_hangar_to_deneigeuse(graph, start_node) + end_node = parcours_deneigeuse[-1][1] + parcours_DeneigeuseHangar = path_deneigeuse_to_hangar(graph, end_node) + + parcours_deneigeuse = parcours_HangarDeneigeuse + parcours_deneigeuse + parcours_DeneigeuseHangar + if deneigeuse == "naive": + parcours_deneigeuse = drone_path(drone_edges, graph) + + start_node = parcours_deneigeuse[0][0] + parcours_HangarDeneigeuse = path_hangar_to_deneigeuse(graph, start_node) + end_node = parcours_deneigeuse[-1][1] + parcours_DeneigeuseHangar = path_deneigeuse_to_hangar(graph, end_node) + + parcours_deneigeuse = parcours_HangarDeneigeuse + parcours_deneigeuse + parcours_DeneigeuseHangar + + parcours_deneigeuses[i].append(parcours_deneigeuse) + end_time_deneigeuse = time.time() + + cost_deneigeuse = export_deneigeuse( + graph, end_time_deneigeuse-start_time_deneigeuse, parcours_deneigeuse) + cost_deneigeuses[i].append(cost_deneigeuse) + + stat_déneigeuses = {} + for i in number_of_deneigeuses: + stat_déneigeuses[i] = stats_deneigeuses(cost_deneigeuses[i]) + + print_demo("Parcours de la déneigeuse effectué avec succès.", indent=1) + + # ---------------------- CALCUL DES STATS - DÉNEIGEUSES --------------------------- + + os.system('cls' if os.name == 'nt' else 'clear') + + print_recap_stat_drone(stat_drone, 0) + + print("") + + print_all_stat(stat_déneigeuses, 0) + + print("") + print("--------------------") + print("") + + # ---------------------- EXPORTATION DU PARCOURS EN KML --------------------------- + + print_demo( + "Exportation des parcours des déneigeuses avec le parcours du drone au format KML.") + for i in parcours_deneigeuses: + print_demo( + f"{i} déneigeuses - Fichier KML : temp/parcours_{i}_deneigeuses.kml", indent=1) + export_to_kml(parcours_deneigeuses[i], finalPath, graph, debug, name=f"parcours_{i}_deneigeuses") + + return True diff --git a/ero1/src/demo/demo_final_report.py b/ero1/src/demo/demo_final_report.py new file mode 100644 index 0000000..59badda --- /dev/null +++ b/ero1/src/demo/demo_final_report.py @@ -0,0 +1,110 @@ +from src.demo.print_demo import print_demo +from src.demo.ask_variable import ask_variable +from src.helper.color_suburbs import display_suburbs_with_colors +from src.demo.demo_cost import export_deneigeuse, export_drone, get_edge_length +from src.demo.demo_stats import stats_deneigeuses, stats_drone + +# IMPORT FOR GENERATION +from src.generation.graph_generation import generate_graph +from src.generation.suburb_snowplow_generation import generate_quartiers_from_path + +# IMPORT FOR DRONE: +from src.drone.postier_chinoisV2 import final_path, postier_chinois_process_v2, connect_circuits +from src.drone.postier_chinoisV1 import postier_chinois_process_v1 +from src.drone.postier_chinoisV3 import postier_chinois_process_v3 + +# IMPORT FOR DENEIGEUSE: +from src.helper.partitions import partition +from src.deneigeuses.hangar_to_deneigeuse import path_hangar_to_deneigeuse, path_deneigeuse_to_hangar + +# IMPORT FOR YAML & KML +from src.helper.export_to_kml import export_to_kml +from src.helper.export_import_yaml import load_paths_from_yaml +import os +import time + + +def line(): + print("----------------------------------") + + +def print_cost_from_list(lst, base_indent=0): + """ + affiche la distance et le temps approximatif de chaque déneigeuses + """ + + # print_demo(f"Récap avec {len(lst)} déneigeuses:", base_indent) + print("") + print_demo("Récapitulatif des déneigeuses:", base_indent) + + for i, o in enumerate(lst): + print_demo(f"Déneigeuse numéro {i+1} :", base_indent + 1) + print_demo(f"Distance = {(o['dist']/1000):.2f} km", base_indent + 2) + print_demo(f"Durée approximative = {o['time']['format']}", base_indent + 2) + + +def print_recap_stat_target(stat_deneigeuses, nb_deneigeuse, most_opti=False, base_indent=0): + """ + Affiche dans le terminal sous un format organisé les statistiques + avec nb_deneigeuse déneigueses + """ + if (nb_deneigeuse not in stat_deneigeuses): + raise ValueError(f'Données pour {nb_deneigeuse} non calculées') + + data = stat_deneigeuses[nb_deneigeuse] + + if most_opti: + print_demo(f"Récapitulatif global (solution opti): {data['number']} déneigeuses", base_indent) + else: + print_demo(f"Récapitulatif global: {data['number']} déneigeuses", base_indent) + + # print_demo(f"nombre de déneigeuses = {data['number']}", base_indent + 1) + + print_demo("Distance parcourue par les déneigeuses :", base_indent + 1) + print_demo(f"Maximale = {data['dist']['max']:.2f} km", base_indent + 2) + print_demo(f"Minimale = {data['dist']['min']:.2f} km", base_indent + 2) + print_demo(f"Totale = {data['dist']['total']:.2f} km", base_indent + 2) + print_demo(f"Moyenne = {data['dist']['avg']:.2f} km", base_indent + 2) + + print_demo("Temps réel de parcours pour les déneigeuses:", base_indent + 1) + print_demo("Type 1 : ", base_indent+2) + print_demo(f"Maximale = {data['time']['real']['t1']['max']:.2f} heures", base_indent + 3) + print_demo(f"Moyenne = {data['time']['real']['t1']['avg']:.2f} heures", base_indent + 3) + print_demo("Type 2 : ", base_indent+2) + print_demo(f"Maximale = {data['time']['real']['t2']['max']:.2f} heures", base_indent + 3) + print_demo(f"Moyenne = {data['time']['real']['t2']['avg']:.2f} heures", base_indent + 3) + + print_demo("Coût total :", base_indent + 1) + print_demo(f"Type 1 = {data['cost']['t1']:.2f} euros", base_indent + 2) + print_demo(f"Type 2 = {data['cost']['t2']:.2f} euros", base_indent + 2) + + print_cost_from_list(data['list'], base_indent) + + +def print_recap_stat_drone(stat_drone, base_indent=0): + print("##################") + print("# Recap du drone #") + print("##################") + # dist en km plus bas print_demo(f"distance parcourue par le drone: {stat_drone["dist"]}", base_indent+1) + print_demo("Temps écoulé :", base_indent) + print_demo(f"Durée de l'exécution du programme : {stat_drone['time']['format']}", base_indent+1) + print_demo(f"Durée réelle du parcours :", base_indent+1) + print_demo(f"{stat_drone['time']['real']:.2f} minutes", base_indent+2) + print_demo(f"{(stat_drone['time']['real'] / 60):.2f} heures", base_indent+2) + print_demo(f"Distance parcourue : {stat_drone['distKM']:.2f} km", base_indent) + print_demo(f"Coût : {stat_drone['cost']:.2f} euros", base_indent) + + +def print_all_stat(stat_list, base_indent): + print("#########################") + print("# Recap des déneigeuses #") + print("#########################") + # line() + + best = True + for elem in stat_list: + print("") + line() + print("") + print_recap_stat_target(stat_list, elem, best, base_indent) + best = False diff --git a/ero1/src/demo/demo_stats.py b/ero1/src/demo/demo_stats.py new file mode 100644 index 0000000..d8dc78c --- /dev/null +++ b/ero1/src/demo/demo_stats.py @@ -0,0 +1,64 @@ +import math +import parameters + +def stats_deneigeuses(all_costs): + ''' + Calcule les statistiques des déneigeuses. + Parameters: + all_costs : Liste des coûts des déneigeuses. + Returns: + Un dictionnaire contenant les statistiques des déneigeuses. + ''' + result = { + "list":all_costs + } + result["number"] = len(all_costs) + result["dist"] = { + "max": max(d["dist"] for d in all_costs) / 1000, + "min": min(d["dist"] for d in all_costs) / 1000, + "total": sum(d["dist"] for d in all_costs) / 1000 + } + result["dist"]["avg"] = result["dist"]["total"] / result["number"] + result["time"] = {} + result["time"]["real"] = {"t1": {}, "t2": {}} + result["time"]["real"]["t1"]["avg"] = result["dist"]["avg"] / parameters.TYPE_I_SPEED + result["time"]["real"]["t2"]["avg"] = result["dist"]["avg"] / parameters.TYPE_II_SPEED + result["time"]["real"]["t1"]["max"] = result["dist"]["max"] / parameters.TYPE_I_SPEED + result["time"]["real"]["t2"]["max"] = result["dist"]["max"] / parameters.TYPE_II_SPEED + + + def coutHoraireTypeI(heures): + return heures * parameters.TYPE_I_COST_HOUR_UNDER_8 if heures <= 8 else 8 * parameters.TYPE_I_COST_HOUR_UNDER_8 + (heures - 8) * parameters.TYPE_I_COST_HOUR_ABOVE_8 + + def coutHoraireTypeII(heures): + return heures * parameters.TYPE_II_COST_HOUR_UNDER_8 if heures <= 8 else 8 * parameters.TYPE_II_COST_HOUR_UNDER_8 + (heures - 8) * parameters.TYPE_II_COST_HOUR_ABOVE_8 + + coutTotalTypeI = ( + parameters.TYPE_I_COST_FIXED * (result["number"]) + + parameters.TYPE_I_COST_KILO * result["dist"]["total"] + + coutHoraireTypeI(result["time"]["real"]["t1"]["avg"] * result["number"])) + + + coutTotalTypeII = ( + parameters.TYPE_II_COST_FIXED * result["number"] + + parameters.TYPE_II_COST_KILO * result["dist"]["total"] + + coutHoraireTypeII(result["time"]["real"]["t2"]["avg"] * result["number"]) + ) + result["cost"] = { + "t1":coutTotalTypeI, + "t2":coutTotalTypeII + } + return result + +def stats_drone(cost): + ''' + Calcule les statistiques du drone. + Parameters: + cost : Dictionnaire contenant les coûts du drone. + Returns: + Un dictionnaire contenant les statistiques du drone. + ''' + cost["distKM"] = cost["dist"] / 1000 + cost["time"]["real"] = (cost["distKM"] / parameters.SUPER_DRONE_SPEED) * 60 + cost["cost"] = parameters.SUPER_DRONE_COST_FIXED + parameters.SUPER_DRONE_COST_KILO * (cost["dist"] / 1000) + return cost \ No newline at end of file diff --git a/ero1/src/demo/print_demo.py b/ero1/src/demo/print_demo.py new file mode 100644 index 0000000..f44d98b --- /dev/null +++ b/ero1/src/demo/print_demo.py @@ -0,0 +1,20 @@ +from datetime import datetime + + +def print_demo(message, indent=0, time=False): + """ + Affiche dans la console un message de démo formaté. + Parameters: + message : Le message à afficher. + indent : Le nombre d'espaces à ajouter devant le message. + time : Si True, affiche le timestamp. + """ + # Récupérer le timestamp actuel en format string + str_time = datetime.now().strftime('%H:%M:%S.%f')[:-3] + time_in_str= f"[{str_time}] " if time else "" + space_in_str= " " * indent + + if indent == 0: + print(f"{time_in_str}» {message}") + else: + print(f"{space_in_str} {time_in_str}› {message}") diff --git a/ero1/src/deneigeuses/basic_euler.py b/ero1/src/deneigeuses/basic_euler.py new file mode 100644 index 0000000..117fed0 --- /dev/null +++ b/ero1/src/deneigeuses/basic_euler.py @@ -0,0 +1,48 @@ +from src.helper.debug_printer import debug_print +from src.helper.check_eulerian import check_directed_eulerian, check_non_directed_eulerian +import networkx as nx +import osmnx as ox + +def find_eulerian(G, debug_mode, path=False, start=None, directed=False): + """ + Trouve et renvoit un chemin ou un cycle eulérien du graph G. + Il est possible de spécifier le point de départ du cycle/chemin. + Renvoie le chemin/cycle crée ou None si la demande n'est pas possible + Parameters: + G: Graph duquel on souhaite obtenir le chemin/cycle eulérien + debug_mode: Indique si le debug est actif + path: [OPTIONNEL | DEFAUT = False] True si on souhaite avoir + un chemin eulérien. Faux pour avoir un cycle + start: [OPTIONNEL | DEFAUT = None] Noeud NetworkX de départ + du chemin/cycle. Un check est effectué si on souhaite un chemin + """ + if (G == None): + debug_print("[BASIC_EULER] Cannot procede: The graph is null") + + spots = None + + if (directed): + spots = check_directed_eulerian(G) + else: + spots = check_non_directed_eulerian(G) + + if (spots == None): + debug_print("[BASIC_EULER] This is not an Eulerian graph: Cannot create path or cycle", debug_mode) + return None + + if (path): + if (start != spots[0] and start != spots[1]): + # We just want to warn the user that the start position is invalid for this graph + debug_print("[BASIC_EULER] The starting position inputted is not a suitable start for an eulerian path", debug_mode) + start = spots[0] + + # We return a list and not an iterator + return [u for u, _ in nx.eulerian_path(G, source=start)] + else: + # This condition is a bit overkill but you never know + if (spots[0] != None or spots[1] != None): + debug_print("[BASIC_EULER] Cannot create cycle on this eulerian graph", debug_mode) + return None + + # We return a list and not an iterator + return [u for u, _ in nx.eulerian_circuit(G, source=start)] \ No newline at end of file diff --git a/ero1/src/deneigeuses/directed_cpp.py b/ero1/src/deneigeuses/directed_cpp.py new file mode 100644 index 0000000..552c4d9 --- /dev/null +++ b/ero1/src/deneigeuses/directed_cpp.py @@ -0,0 +1,294 @@ +from src.helper.debug_printer import debug_print +import networkx as nx +from copy import deepcopy +import heapq + +def split_into_strongly_connected(G): + """ + Renvoie la liste des composantes fortement connexes de G + + Params : + - G : Le graph à split + + Returns : + - composantes (list) : la liste des sous-graphes (composantes) fortement connexes de G + """ + return [G.subgraph(c) for c in nx.strongly_connected_components(G)] + +def chinese_postman_greedy(G, debug_mode=False): + if not nx.is_strongly_connected(G): + raise ValueError("Le graphe doit être fortement connexe") + + G = nx.DiGraph(G) + shortest_lengths = dict(nx.all_pairs_dijkstra_path_length(G, weight='length')) + shortest_paths = dict(nx.all_pairs_dijkstra_path(G, weight='length')) + + delta = {v: G.out_degree(v) - G.in_degree(v) for v in G.nodes()} + surplus = [v for v in G.nodes() if delta[v] > 0] + deficit = [v for v in G.nodes() if delta[v] < 0] + + debug_print(f"Déficitaires: {len(deficit)}, Excédentaires: {len(surplus)}", debug_mode) + + for u in deficit: + while delta[u] < 0: + heap = [] + for v in surplus: + if delta[v] <= 0: + continue + if v in shortest_lengths[u]: + heapq.heappush(heap, (shortest_lengths[u][v], v)) + if not heap: + raise RuntimeError("Aucun noeud excédentaire atteignable depuis", u) + _, v = heapq.heappop(heap) + + flow = min(-delta[u], delta[v]) + delta[u] += flow + delta[v] -= flow + + path = shortest_paths[u][v] + for i in range(len(path) - 1): + a, b = path[i], path[i + 1] + if not G.has_edge(a, b): + raise ValueError(f"Chemin invalide : arête manquante ({a} → {b})") + G[a][b]['duplicate'] = G[a][b].get('duplicate', 0) + flow + debug_print(f"Arête ({a} → {b}) dupliquée {flow} fois", debug_mode) + + MG = nx.MultiDiGraph() + for u, v, data in G.edges(data=True): + weight = data.get('length', 1) + MG.add_edge(u, v, length=weight) + for _ in range(data.get('duplicate', 0)): + MG.add_edge(u, v, length=weight) + + return list(nx.eulerian_circuit(MG)) + +def link_components(global_graph, path1, path2): + """ + Fusionne les 2 chemins en les reliant par leur plus court chemin + + Params : + - global_graph : Graphe de toute la ville pour avoir les données des arcs + - path1 : chemin de départ + - path2 : chemin d'arrivée + + Returns : + - fused_path : fusion des 2 chemins + """ + + fused_path = [] + if path1[0][0] != None: + fused_path = path1 + start = path1[-1][1] + end = path2[0][0] + invert = False + # print(start, end, nx.has_path(global_graph,start,end)) + if not nx.has_path(global_graph, start, end): + start,end = end, start + fused_path = path2 + invert = True + + shortest_path = [start,end] + if nx.has_path(global_graph, start, end): + shortest_path = nx.shortest_path(global_graph, source=start, target=end, weight='length') + for i in range(len(shortest_path) - 1): + fused_path.append((shortest_path[i], shortest_path[i + 1])) + if path2[0][1] != None: + if invert: + if path1[0][0] != None: + fused_path.extend(path1) + else: + fused_path.extend(path2) + return fused_path + +def oriented_cpt(local_graph, global_graph, debug_mode=False): + """ + Détermine le parcours de la déneigeuse sur local_graph en résolvant le problème du postier chinois orienté. + + Params : + - local_graph : le graph à parcourir + - global_graph : le graph global de référence + - debug_mode : active/désactive les logs de debug + + Returns : + - parcours : le parcours de la déneigeuse + """ + + components = split_into_strongly_connected(local_graph) + parcours = [] + if len(components[0].edges) > 0: + parcours = chinese_postman_greedy(components[0], debug_mode=debug_mode) + else: + parcours = [(None, list(components[0])[0])] + for component in components[1:]: + if len(component.edges) > 0: + cpp = chinese_postman_greedy(component, debug_mode=debug_mode) + parcours = link_components(global_graph, parcours, cpp) + else: + cpp = [(list(component)[0], None)] + parcours = link_components(global_graph, parcours, cpp) + return parcours + +# def oriented_cpt(G, debug_mode=False): +# """ +# Version orientée du Chinese Postman Problem. +# Le graph ne doit pas contenir de cycles de poids négatifs +# et le graph doit être fortement connexe pour que l'algo fonctionne +# Parameters: +# G: Graph à utiliser pour ce problème +# """ +# nb_nodes = len(G.nodes) +# class CPP: +# def __init__(self, graph): +# self.G = nx.DiGraph(graph) +# self.delta_tab = { elem: self.G.out_degree(elem) - self.G.in_degree(elem) for elem in self.G.nodes() } +# self.neg_degree = [] +# self.pos_degree = [] +# self.f = dict() +# self.c = dict() +# self.path = dict() +# # init the c and path dictionnary so it does not have to be in +# self.setup_fields() + +# def addEdge(self,l, u, v): +# if ((u, v) not in self.c or self.c[(u,v)] > l): +# self.c[(u,v)] = l +# self.path[(u,v)] = v +# if (not self.G.has_edge(u, v)): +# self.G.add_edge(u,v, length = l) +# else: +# nx.set_edge_attributes(self.G, {(u, v): {"length": l}}) + +# def setup_fields(self): +# for i, j in self.G.edges(): +# self.c[(i, j)] = self.G.get_edge_data(i,j)["length"] +# self.path[(i, j)] = j + +# def least_cost_paths(self): +# for edge in self.G.edges(): +# i = edge[0] +# k = edge[1] +# for j in self.G.nodes: +# if ((k, j) in self.c +# and ((i,j) not in self.c +# or self.c[(i, j)] > self.c[(i,k)] + self.c[(k,j)])): +# self.path[(i, j)] = self.path[(i, k)] +# self.c[(i, j)] = self.c[(i,k)] + self.c[(k,j)] +# if i == j and self.c[(i,j)] < 0: return # cycle négatif tu connais + +# def findUnbalanced(self): +# for (key, val) in self.delta_tab.items(): +# if (val < 0): +# self.neg_degree.append(key) +# elif (val > 0): +# self.pos_degree.append(key) + +# def findFeasible(self): +# for i in self.neg_degree: +# for j in self.pos_degree: +# self.f[(i, j)] = -self.delta_tab[i] if -self.delta_tab[i] < self.delta_tab[j] else self.delta_tab[j] +# self.delta_tab[i] += self.f[(i, j)] +# self.delta_tab[j] -= self.f[(i, j)] + +# # Improvements needed +# def improvements(self): +# residual = CPP(self.G) +# for i,j in zip(self.neg_degree, self.pos_degree): +# length = 0 +# if ((i,j) in self.c): +# length = self.c[(i, j)] +# residual.addEdge(length, i, j) +# if (i,j) not in self.f: +# self.f[(i,j)] = 0 +# elif (self.f[(i,j)] != 0): +# residual.addEdge(-length, j,i) +# residual.least_cost_paths() + +# for node in self.G.nodes: +# if (node,node) in residual.c and residual.c[(node,node)] < 0: +# k = 0 +# kunset = True +# u = node +# while True: +# v = residual.path[(u,node)] +# if residual.c[(u,v)] < 0 and (kunset or k > self.f[(v,u)]): +# k = self.f[(v,u)] +# kunset = False +# u = v +# if u == node: +# break +# u = node +# while True: +# v = residual.path[(u,node)] +# if ((u, v) not in residual.c): +# residual.c[(u,v)] = 0 +# if ((u, v) not in self.f): +# self.f[(u,v)] = 0 +# if ((v, u) not in self.f): +# self.f[(v,u)] = 0 +# if residual.c[(u,v)] < 0: +# self.f[(v,u)] -= k +# else: +# self.f[(u,v)] += k +# u = v +# if u == node: +# break +# return True +# return False + +# def solve(self): +# print(debug_mode) +# self.least_cost_paths() +# self.findUnbalanced() +# self.findFeasible() +# while self.improvements(): +# pass + +# def solution(self,start = None, debug_mode=False): +# if (start == None): +# start = list(self.G.nodes)[0] +# sol = [] +# arcs = dict() + +# def findPath(fromNode): +# for node in self.G.nodes: +# if ((fromNode,node) in self.f and self.f[(fromNode,node)] > 0): +# return node +# return None + +# v = start +# while True: +# u = v +# v = findPath(u) +# if v != None: +# self.f[(u,v)] -= 1 +# while u != v: +# if ((u, v) not in self.path): +# debug_print("We found a path with a 0 in it. This is probably a bad thig idk", debug_mode) +# return [] +# p = self.path[(u,v)] +# debug_print("Aller du noeud " + str(u) + " au noeud " + str(p), debug_mode) +# sol.append((u,p)) +# u = p +# else: +# if ((u, start) not in self.path): +# self.path[(u,start)] = 0 +# bridgeNode = self.path[(u,start)] +# if (u, bridgeNode) not in arcs: +# arcs[(u, bridgeNode)] = list(self.G.adj[u].keys()).count(bridgeNode) +# if arcs[(u,bridgeNode)] == 0: +# break +# v = bridgeNode +# for node in self.G.nodes: +# if (u, node) not in arcs: +# arcs[(u, node)] = list(self.G.adj[u].keys()).count(node) +# if node != bridgeNode and arcs[(u,node)] > 0: +# v = node +# break +# arcs[(u,v)] -= 1 +# debug_print("Aller du noeud " + str(u) + " au noeud " + str(v), debug_mode) +# sol.append((u,v)) +# return sol + +# res = CPP(G) +# res.solve() +# return res.solution(debug_mode=debug_mode) diff --git a/ero1/src/deneigeuses/drone_path.py b/ero1/src/deneigeuses/drone_path.py new file mode 100644 index 0000000..2f563b9 --- /dev/null +++ b/ero1/src/deneigeuses/drone_path.py @@ -0,0 +1,23 @@ +import networkx as nx + +def drone_path(parcours_drone, G): + """ + Utilise le parcours du drone comme base pour le parcours de la déneigeuse + Params: + parcours_drone: la liste des arêtes visitées par le drone + G: le graphe du quartier original + Return: + Le parcours de la déneigeuse + """ + parcours_deneigeuse = [] + for (u,v) in parcours_drone: + if G.has_edge(u,v): + parcours_deneigeuse.append((u,v)) + else: + pcc = nx.shortest_path(G, u, v, weight='length') + for i in range(len(pcc) - 1): + parcours_deneigeuse.append((pcc[i], pcc[i+1])) + parcours_deneigeuse.append((v,u)) + for i in range(len(pcc) - 1): + parcours_deneigeuse.append((pcc[i], pcc[i+1])) + return parcours_deneigeuse \ No newline at end of file diff --git a/ero1/src/deneigeuses/hangar_to_deneigeuse.py b/ero1/src/deneigeuses/hangar_to_deneigeuse.py new file mode 100644 index 0000000..1bd6ae0 --- /dev/null +++ b/ero1/src/deneigeuses/hangar_to_deneigeuse.py @@ -0,0 +1,35 @@ +import networkx as nx + +def path_hangar_to_deneigeuse(Graphe, start_point): + """ + Fait le lien entre le hangar "theorique" et le départ de la dénéigeuse + """ + hangar = 299783596 + res = [] + + try: + _, path_nodes = nx.single_source_dijkstra(Graphe, hangar, start_point, weight='length') + except nx.NetworkXNoPath: + return [] + + for i in range(len(path_nodes) - 1): + edge = (path_nodes[i], path_nodes[i+1]) + res.append(edge) + return res + +def path_deneigeuse_to_hangar(Graphe, start_point): + """ + Fait le lien entre l'emplacement de la deneigeuse et du hangar + """ + hangar = 299783596 + res = [] + + try: + _, path_nodes = nx.single_source_dijkstra(Graphe, start_point, hangar, weight='length') + except nx.NetworkXNoPath: + return [] + + for i in range(len(path_nodes) - 1): + edge = (path_nodes[i], path_nodes[i+1]) + res.append(edge) + return res diff --git a/ero1/src/deneigeuses/hierholzer_v1.py b/ero1/src/deneigeuses/hierholzer_v1.py new file mode 100644 index 0000000..e00e103 --- /dev/null +++ b/ero1/src/deneigeuses/hierholzer_v1.py @@ -0,0 +1,128 @@ +import networkx as nx +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph + +def parcours_eulerien(graph, drone_edges, debug_mode=False, start_node=None): + """ + Parcours de la déneigeuse à partir de l'algorithme de Hierholzer. + | PREMIERE VERSION - Celle-ci peut rester bloquée dans les impasses ou cycles présents dans le graphe. + Parameters: + graph : Le graphe orienté de Montréal + drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...] + debug_mode : Mode debug pour l'affichage des informations + start_node : Le noeud de départ [OPTIONNEL] + + Returns: + list : Liste des arêtes formant le chemin de la déneigeuse + """ + if not drone_edges: + debug_print("/!\\ Aucun parcours de drone effectué.", debug_mode) + return [] + + # Point de départ du parcours + if start_node is None: + start_node = drone_edges[0][0] + + debug_print(f"Start node: {start_node}", debug_mode) + + result = [] + stack = [start_node] + current_node = start_node + + # Récupération des arêtes du drone + drone_edges_dict = {} + for u, v in drone_edges: + if graph.has_edge(u, v) or graph.has_edge(v, u): + drone_edges_dict[(u, v)] = True + drone_edges_dict[(v, u)] = True + + # Arêtes du drone non visitées + unvisited_drone_edges = set(drone_edges_dict.keys()) + + def get_next_valid_edge(current, actual_edges): + ''' + Trouve la prochaine arête valide depuis le nœud courant. + ''' + for succ in graph.successors(current): + if (current, succ) in actual_edges: + return (current, succ) + return None + + def find_path_to_next_drone_edge(current, actual_edges): + ''' + Trouve un chemin valide vers la prochaine arête du drone non visitée. + ''' + for node in graph.nodes(): + for succ in graph.successors(node): + if (node, succ) in actual_edges: + try: + # Récupération du chemin le plus court entre noeud actuel => noeud suivant (avec poids = longueur) + path = nx.shortest_path(graph, current, node, weight='length') + if path: + return path + except nx.NetworkXNoPath: + continue + return None + + last_edges = [] + while unvisited_drone_edges: + # Récupération de la prochaine arête correcte + next_edge = get_next_valid_edge(current_node, unvisited_drone_edges) + + if next_edge: + stack.append(current_node) + + unvisited_drone_edges.discard(next_edge) + unvisited_drone_edges.discard((next_edge[1], next_edge[0])) # Autre sens (orienté) + + result.append(next_edge) + last_edges.append(next_edge) + + current_node = next_edge[1] + else: + # STUCK HERE => On trouve un chemin vers la prochaine arête + next_path = find_path_to_next_drone_edge(current_node, unvisited_drone_edges) + + if next_path: + # Ajout du parcours effectué pour atteindre la prochaine arête + for i in range(len(next_path) - 1): + u, v = next_path[i], next_path[i + 1] + result.append((u, v)) + last_edges.append((u, v)) + if (u, v) in drone_edges_dict: + unvisited_drone_edges.discard((u, v)) + unvisited_drone_edges.discard((v, u)) # Autre sens (orienté) + current_node = next_path[-1] + stack = [current_node] + + elif stack: # Si on est vraiment bien bloqué, on remonte + current_node = stack.pop() + else: + break + + debug_print(f"Longueur du chemin : {len(result)}", debug_mode) + debug_print(f"Nombre d'arêtes du drone : {len(drone_edges)}", debug_mode) + + if not result: + debug_print("/!\\ Aucun chemin possible avec cet algorithme", debug_mode) + return [] + + return result + +def process_hierholzer_v1(graph, drone_edges, debug_mode=False): + """ + Traite le graphe avec l'algorithme de Hierholzer en utilisant les arêtes du drone. + + Parameters: + graph : Le graphe orienté de Montréal + drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...] + debug_mode : Mode debug pour l'affichage d'informations supplémentaires + + Returns: + list : Liste des arêtes formant le chemin de la déneigeuse + """ + debug_print("Application de l'algorithme de Hierholzer avec les arêtes du drone...", debug_mode) + + path = parcours_eulerien(graph, drone_edges, debug_mode) + + return path \ No newline at end of file diff --git a/ero1/src/deneigeuses/hierholzer_v2.py b/ero1/src/deneigeuses/hierholzer_v2.py new file mode 100644 index 0000000..de73c4f --- /dev/null +++ b/ero1/src/deneigeuses/hierholzer_v2.py @@ -0,0 +1,168 @@ +import networkx as nx +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph + +def parcours_eulerien(graph, drone_edges, debug_mode=False, start_node=None): + """ + Parcours de la déneigeuse à partir de l'algorithme de Hierholzer. + | DEUXIEME VERSION - Celle-ci est plus robuste et peut gérer les impasses ou cycles présents dans le graphe. + Parameters: + graph : Le graphe orienté de Montréal + drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...] + debug_mode : Mode debug pour l'affichage des informations + start_node : Le noeud de départ [OPTIONNEL] + + Returns: + list : Liste des arêtes formant le chemin de la déneigeuse + """ + if not drone_edges: + debug_print("/!\\ Aucun parcours de drone effectué.", debug_mode) + return [] + + # Point de départ du parcours + if start_node is None: + start_node = drone_edges[0][0] + + debug_print(f"Start node: {start_node}", debug_mode) + + result = [] + stack = [start_node] + current_node = start_node + + # Récupération des arêtes du drone + drone_edges_dict = {} + for u, v in drone_edges: + if graph.has_edge(u, v) or graph.has_edge(v, u): + drone_edges_dict[(u, v)] = True + drone_edges_dict[(v, u)] = True + + # Arêtes du drone non visitées + unvisited_drone_edges = set(drone_edges_dict.keys()) + + def get_next_valid_edge(current, actual_edges): + ''' + Trouve la prochaine arête valide depuis le nœud courant. + ''' + for succ in graph.successors(current): + if (current, succ) in actual_edges: + return (current, succ) + return None + + def find_path_to_next_drone_edge(current, actual_edges): + ''' + Trouve un chemin valide vers la prochaine arête du drone non visitée. + ''' + for node in graph.nodes(): + for succ in graph.successors(node): + if (node, succ) in actual_edges: + try: + # Récupération du chemin le plus court entre noeud actuel => noeud suivant (avec poids = longueur) + path = nx.shortest_path(graph, current, node, weight='length') + if path: + return path + except nx.NetworkXNoPath: + continue + return None + + last_edges = [] + visited_nodes = set() + retry_count = 0 + max_retries = 100 # Cas d'arrêt si on est bloqué trop fortement + debug_print("Début du parcours eulerien...", debug_mode) + while unvisited_drone_edges and retry_count < max_retries*2: + # Récupération de la prochaine arête correcte + next_edge = get_next_valid_edge(current_node, unvisited_drone_edges) + + if next_edge: + stack.append(current_node) + visited_nodes.add(current_node) + retry_count = 0 + + unvisited_drone_edges.discard(next_edge) + unvisited_drone_edges.discard((next_edge[1], next_edge[0])) # Autre sens (orienté) + + result.append(next_edge) + last_edges.append(next_edge) + + current_node = next_edge[1] + else: + # STUCK HERE => On trouve un chemin vers la prochaine arête + next_path = find_path_to_next_drone_edge(current_node, unvisited_drone_edges) + + if next_path: + # Ajout du parcours effectué pour atteindre la prochaine arête + for i in range(len(next_path) - 1): + u, v = next_path[i], next_path[i + 1] + result.append((u, v)) + last_edges.append((u, v)) + visited_nodes.add(u) + if (u, v) in drone_edges_dict: + unvisited_drone_edges.discard((u, v)) + unvisited_drone_edges.discard((v, u)) # Autre sens (orienté) + current_node = next_path[-1] + stack = [current_node] + retry_count = 0 + + elif stack: # Si on est vraiment bien bloqué, on remonte + current_node = stack.pop() + retry_count += 1 + else: + # On fait demi-tour si vraiment sens unique + if result and retry_count < max_retries and len(last_edges) > 0: + last_edge = last_edges.pop() + current_node = last_edge[0] + result.append((last_edge[1], last_edge[0])) + retry_count += 1 + elif retry_count >= max_retries: + # On va essayer de trouver le chemin le plus court vers une arête non visitée + closest_edge = None + closest_edge_path = None + min_distance = float('inf') # max + for edge in unvisited_drone_edges: + path = find_path_to_next_drone_edge(current_node, {edge}) + if path and len(path) < min_distance: + closest_edge = edge + closest_edge_path = path + min_distance = len(path) + + if closest_edge: + result.extend(closest_edge_path) + current_node = closest_edge[0] + stack = [current_node] + retry_count = 0 + else: + break + else: + break + + debug_print("Fin du parcours eulerien...", debug_mode) + if retry_count >= max_retries * 2: + debug_print("/!\\ Problème rencontré : Déneigeuse bloquée dans un cycle.", debug_mode) + return result[:len(result)-retry_count] # suppression du cycle de la path + + debug_print(f"Longueur du chemin : {len(result)}", debug_mode) + debug_print(f"Nombre d'arêtes du drone : {len(drone_edges)}", debug_mode) + + if not result: + debug_print("/!\\ Aucun chemin possible avec cet algorithme", debug_mode) + return [] + + return result + +def process_hierholzer_v2(graph, drone_edges, debug_mode=False): + """ + Traite le graphe avec l'algorithme de Hierholzer en utilisant les arêtes du drone. + + Parameters: + graph : Le graphe orienté de Montréal + drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...] + debug_mode : Mode debug pour l'affichage d'informations supplémentaires + + Returns: + list : Liste des arêtes formant le chemin de la déneigeuse + """ + debug_print("Application de l'algorithme de Hierholzer avec les arêtes du drone...", debug_mode) + + path = parcours_eulerien(graph, drone_edges, debug_mode) + + return path \ No newline at end of file diff --git a/ero1/src/deneigeuses/maps/verdun.py b/ero1/src/deneigeuses/maps/verdun.py new file mode 100644 index 0000000..e949b42 --- /dev/null +++ b/ero1/src/deneigeuses/maps/verdun.py @@ -0,0 +1,37 @@ +# FICHIER DEPRECATED : Ce fichier n'est plus utilisé. + +import osmnx as ox +import networkx as nx +import matplotlib +matplotlib.use('TkAgg') + +def create_verdun(): + """ + Crée une version fortement connexe du graph représentant + le quartier de Verdun + Parameters: + None + """ + G = ox.graph_from_place("Verdun, Montréal, Québec, Canada", network_type='drive') + G.remove_edge(32764413, 248511841) + G.remove_edge(615028247, 615028248) + G.remove_edge(615028248, 4503982628) + G.remove_edge(615035051, 615028249) + G.remove_edge(4503982628, 615035051) + G.remove_edge(5342978418, 615028328) + + G.remove_node(32764413) + G.remove_node(248511841) + G.remove_node(615028247) + G.remove_node(615028248) + G.remove_node(4503982628) + G.remove_node(615035051) + G.remove_node(615028328) + + ox.plot_graph(G) + + fig, ax = ox.plot_graph(G, show=False, save=True, filepath='graph.png', dpi=300) + + return G + +create_verdun() \ No newline at end of file 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 diff --git a/ero1/src/drone/postier_chinoisV1.py b/ero1/src/drone/postier_chinoisV1.py new file mode 100644 index 0000000..6afe1a0 --- /dev/null +++ b/ero1/src/drone/postier_chinoisV1.py @@ -0,0 +1,209 @@ +import osmnx as ox +import networkx as nx +import parameters as params + +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph +from src.helper.duplicate_removal import remove_duplicates +from src.helper.export_import_yaml import save_paths_to_yaml + +arrondissements = [ + 'Ahuntsic-Cartierville', + 'Anjou', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Lachine', + 'LaSalle', + 'Le Plateau-Mont-Royal', + 'Le Sud-Ouest', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Mercier–Hochelaga-Maisonneuve', + 'Montréal-Nord', + 'Outremont', + 'Pierrefonds-Roxboro', + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Rosemont–La Petite-Patrie', + 'Saint-Laurent', + 'Saint-Léonard', + 'Verdun', + 'Ville-Marie', + 'Villeray–Saint-Michel–Parc-Extension' +] # first list, we changed its order manually to make a "smart path" for the drone + +connection_order = [ + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Montréal-Nord', + 'Saint-Léonard', + 'Anjou', + 'Mercier–Hochelaga-Maisonneuve', + 'Rosemont–La Petite-Patrie', + 'Villeray–Saint-Michel–Parc-Extension', + 'Outremont', + 'Le Sud-Ouest', + 'Ville-Marie', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Verdun', + 'LaSalle', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Le Plateau-Mont-Royal', + 'Saint-Laurent', + 'Ahuntsic-Cartierville', + 'Pierrefonds-Roxboro', + 'Lachine' +] + +def find_circuit(G_undirected, debug_mode): + if nx.is_eulerian(G_undirected): + G_eulerian = G_undirected + else: + G_eulerian = nx.eulerize(G_undirected) + return nx.eulerian_circuit(G_eulerian), G_eulerian + +def generate_graph(name, debug_mode=False): + """ + permet de charger un graphe + d'une localisation a partir du nom de cette derniere. + """ + G = ox.graph_from_place(name, network_type='drive') + G = remove_duplicates(G, False) + G = ox.project_graph(G) + return G + +def total_length_of_circuit(G, circuit): + return sum(G[u][v][0]['length'] for u, v in circuit) / 1000 + +def total_length_of_arrondissement(G): + distance = 0 + for u, v, data in G.edges(data=True): + distance += data["length"] + return distance / 1000 + +def process_graphs(name, debug_mode): + """ + Création des paths + """ + paths = {} + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + debug_print(f"Génération : {sub_name}", debug_mode) + sub_graph = generate_graph(sub_name, debug_mode) + G_undirected = sub_graph.to_undirected() + + circuit, _ = find_circuit(G_undirected, debug_mode) + c = [edge for edge in circuit] + # print(f"distance kilometre du quartier = {total_length_of_arrondissement(G_undirected):.2f}km") + # print(f"distance kilometre du drone = {total_length_of_circuit(G_eulerian, circuit):.2f}km") + # debug_print(f"Nombre de Route du Path : {len(c)}", debug_mode) + + paths[i] = c + + del sub_graph # to save as much memory as possible + del circuit + return paths + +def connect_circuits(G, path_dict, arrondissement_order=connection_order): + """ + La fonction trouve le chemin le plus cours entre 2 arrondissements + """ + connections = [] + for i in range(len(arrondissement_order) - 1): + from_name = arrondissement_order[i] + to_name = arrondissement_order[i + 1] + + from_path = path_dict[from_name] + to_path = path_dict[to_name] + + start_node = from_path[0][0] + end_node = from_path[-1][1] + + next_start_node = to_path[0][0] + + try: + path = nx.shortest_path(G, source=end_node, target=next_start_node, weight='length') + connections.append((from_name, to_name, path)) + except nx.NetworkXNoPath: + print(f"Aucun chemin trouvé entre {from_name} et {to_name}") + connections.append((from_name, to_name, None)) + return connections + +def final_path(graph, paths, connection_order=connection_order): + full_path = [] + + connections = connect_circuits(graph, paths) + + for i, arr_name in enumerate(connection_order): + full_path.extend(paths[arr_name]) + + if i < len(connection_order) - 1: + next_arr = connection_order[i+1] + + for conn in connections: + if conn[0] == arr_name and conn[1] == next_arr: + node_path = conn[2] + for j in range(len(node_path) - 1): + full_path.append((node_path[j], node_path[j+1])) + break + + return full_path + +def distance_total(G, paths, connections): + G_undir = G.to_undirected() + total_distance = 0.0 + used_edges = set() + + for arrondissement, edges in paths.items(): + for u, v in edges: + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + for from_arr, to_arr, node_path in connections: + for i in range(len(node_path) - 1): + u = node_path[i] + v = node_path[i+1] + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + unused_distance = 0.0 + for u, v, data in G_undir.edges(data=True): + key = (min(u, v), max(u, v)) + if key not in used_edges: + unused_distance += data['length'] + + total_distance /= 1000 + unused_distance /= 1000 + return total_distance, unused_distance + +def distance_optimal(G): + """ + Calcule la somme des longueurs de toutes les routes dans les arrondissements + """ + covered_edges = set() + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + sub_graph = generate_graph(sub_name) + for u, v, data in sub_graph.edges(data=True): + covered_edges.add((min(u, v), max(u, v))) + del sub_graph + + G_undir = G.to_undirected() + total = 0.0 + for u, v in covered_edges: + total += G_undir[u][v][0]['length'] + + + return total / 1000 + +def postier_chinois_process_v1(G, debug_mode): + name = "Montréal, Québec, Canada" + # initially, we ran find circuit on the whole graph + # => processes all suburbs instead of the whole graph + paths = process_graphs(name, debug_mode) + # it was our closest attempt to get an optimal answer but way to long (ran for more than 12h and did not finish) + + finalPath = final_path(G, paths) + + # Save Path with YML + save_paths_to_yaml(paths, "paths-PostierChinoisV1.yml") + + return paths, finalPath diff --git a/ero1/src/drone/postier_chinoisV2.py b/ero1/src/drone/postier_chinoisV2.py new file mode 100644 index 0000000..01f8643 --- /dev/null +++ b/ero1/src/drone/postier_chinoisV2.py @@ -0,0 +1,258 @@ +import osmnx as ox +import networkx as nx +import parameters as params + +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph +from src.helper.duplicate_removal import remove_duplicates +from src.helper.export_import_yaml import save_paths_to_yaml + +arrondissements = [ + 'Ahuntsic-Cartierville', + 'Anjou', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Lachine', + 'LaSalle', + 'Le Plateau-Mont-Royal', + 'Le Sud-Ouest', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Mercier–Hochelaga-Maisonneuve', + 'Montréal-Nord', + 'Outremont', + 'Pierrefonds-Roxboro', + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Rosemont–La Petite-Patrie', + 'Saint-Laurent', + 'Saint-Léonard', + 'Verdun', + 'Ville-Marie', + 'Villeray–Saint-Michel–Parc-Extension' +] # first list, we changed its order manually to make a "smart path" for the drone + +connection_order = [ + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Montréal-Nord', + 'Saint-Léonard', + 'Anjou', + 'Mercier–Hochelaga-Maisonneuve', + 'Rosemont–La Petite-Patrie', + 'Villeray–Saint-Michel–Parc-Extension', + 'Outremont', + 'Le Sud-Ouest', + 'Ville-Marie', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Verdun', + 'LaSalle', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Le Plateau-Mont-Royal', + 'Saint-Laurent', + 'Ahuntsic-Cartierville', + 'Pierrefonds-Roxboro', + 'Lachine' +] + +def find_pairs_odd(G, odd_nodes): + """ + L'objectif de cette fonction est de trouver des paires de nœuds de degré impair dans un graphe. + Cela, en les reliant via les plus courst chemins (avec "length" <=> distance réel). + """ + pairs = [] + used = set() + distances = {} + paths = {} + for u in odd_nodes: + dists, path = nx.single_source_dijkstra(G, u, weight='length') + distances[u] = dists + paths[u] = path + + for u in odd_nodes: + if u in used: + continue + min_dist = float('inf') + best_v = None + for v in odd_nodes: + if v == u or v in used: + continue + if distances[u][v] < min_dist: + min_dist = distances[u][v] + best_v = v + if best_v is not None: + used.add(u) + used.add(best_v) + pairs.append((u, best_v, paths[u][best_v])) + return pairs + +def eulerization_maison(G): + """ + L'objectif de cette fonction est de transformer un graphe non eulérien en un graphe eulérien. + La fonction rajoute des arretes dans le graphe. Les arretes sont ajouté entre les noeuds de degrée impaires. + Avec l'utilisation de find_pairs_odd, on trouve le chemin le plus cours (en distance réel) entre 2 sommets. + """ + G_update = G.copy() + odd_nodes = [v for (v, d) in G.degree() if d % 2 == 1] + pairs = find_pairs_odd(G, odd_nodes) + for u, v, path in pairs: + for i in range(len(path) - 1): + edge_data = G.get_edge_data(path[i], path[i+1]) + l = edge_data.get('length') + G_update.add_edge(path[i], path[i+1], length=l) + return G_update + +def find_circuit(G_undirected, debug_mode): + # debug_print(f"Avant eulérisation : {len(G_undirected.edges)} arêtes", debug_mode) + if nx.is_eulerian(G_undirected): + G_eulerian = G_undirected + else: + G_eulerian = eulerization_maison(G_undirected) + # debug_print(f"Apres eulérisation : {len(G_eulerian.edges)} arêtes", debug_mode) + return list(nx.eulerian_circuit(G_eulerian)), G_eulerian + +def generate_graph(name, debug_mode=False): + """ + permet de charger un graphe + d'une localisation a partir du nom de cette derniere. + """ + G = ox.graph_from_place(name, network_type='drive') + G = remove_duplicates(G, False) + G = ox.project_graph(G) + return G + +def total_length_of_circuit(G, circuit): + return sum(G[u][v][0]['length'] for u, v in circuit) / 1000 + +def total_length_of_arrondissement(G): + distance = 0 + for u, v, data in G.edges(data=True): + distance += data["length"] + return distance / 1000 + +def process_graphs(name, debug_mode): + """ + Création des paths + """ + paths = {} + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + debug_print(f"Génération : {sub_name}", debug_mode) + sub_graph = generate_graph(sub_name, debug_mode) + G_undirected = sub_graph.to_undirected() + + circuit, _ = find_circuit(G_undirected, debug_mode) + c = [edge for edge in circuit] + # print(f"distance kilometre du quartier = {total_length_of_arrondissement(G_undirected):.2f}km") + # print(f"distance kilometre du drone = {total_length_of_circuit(G_eulerian, circuit):.2f}km") + # debug_print(f"Nombre de Route du Path : {len(c)}", debug_mode) + + paths[i] = c + + del sub_graph # to save as much memory as possible + del circuit + return paths + +def connect_circuits(G, path_dict, arrondissement_order=connection_order): + """ + La fonction trouve le chemin le plus cours entre 2 arrondissements + """ + connections = [] + for i in range(len(arrondissement_order) - 1): + from_name = arrondissement_order[i] + to_name = arrondissement_order[i + 1] + + from_path = path_dict[from_name] + to_path = path_dict[to_name] + + start_node = from_path[0][0] + end_node = from_path[-1][1] + + next_start_node = to_path[0][0] + + try: + path = nx.shortest_path(G, source=end_node, target=next_start_node, weight='length') + connections.append((from_name, to_name, path)) + except nx.NetworkXNoPath: + print(f"Aucun chemin trouvé entre {from_name} et {to_name}") + connections.append((from_name, to_name, None)) + return connections + +def final_path(graph, paths, connection_order=connection_order): + full_path = [] + + connections = connect_circuits(graph, paths) + + for i, arr_name in enumerate(connection_order): + full_path.extend(paths[arr_name]) + + if i < len(connection_order) - 1: + next_arr = connection_order[i+1] + + for conn in connections: + if conn[0] == arr_name and conn[1] == next_arr: + node_path = conn[2] + for j in range(len(node_path) - 1): + full_path.append((node_path[j], node_path[j+1])) + break + + return full_path + +def distance_total(G, paths, connections): + G_undir = G.to_undirected() + total_distance = 0.0 + used_edges = set() + + for arrondissement, edges in paths.items(): + for u, v in edges: + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + for from_arr, to_arr, node_path in connections: + for i in range(len(node_path) - 1): + u = node_path[i] + v = node_path[i+1] + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + unused_distance = 0.0 + for u, v, data in G_undir.edges(data=True): + key = (min(u, v), max(u, v)) + if key not in used_edges: + unused_distance += data['length'] + + total_distance /= 1000 + unused_distance /= 1000 + return total_distance, unused_distance + +def distance_optimal(G): + """ + Calcule la somme des longueurs de toutes les routes dans les arrondissements + """ + covered_edges = set() + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + sub_graph = generate_graph(sub_name) + for u, v, data in sub_graph.edges(data=True): + covered_edges.add((min(u, v), max(u, v))) + del sub_graph + + G_undir = G.to_undirected() + total = 0.0 + for u, v in covered_edges: + total += G_undir[u][v][0]['length'] + + + return total / 1000 + +def postier_chinois_process_v2(G, debug_mode): + name = "Montréal, Québec, Canada" + # initially, we ran find circuit on the whole graph + # => processes all suburbs instead of the whole graph + paths = process_graphs(name, debug_mode) + # it was our closest attempt to get an optimal answer but way to long (ran for more than 12h and did not finish) + + finalPath = final_path(G, paths) + + # Save Path with YML + save_paths_to_yaml(paths, "paths-PostierChinoisV2.yml") + + return paths, finalPath diff --git a/ero1/src/drone/postier_chinoisV3.py b/ero1/src/drone/postier_chinoisV3.py new file mode 100644 index 0000000..fc74a26 --- /dev/null +++ b/ero1/src/drone/postier_chinoisV3.py @@ -0,0 +1,253 @@ +import osmnx as ox +import networkx as nx +import parameters as params +import yaml +import itertools + +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph +from src.helper.duplicate_removal import remove_duplicates +from src.helper.export_import_yaml import save_paths_to_yaml +from itertools import combinations + +arrondissements = [ + 'Ahuntsic-Cartierville', + 'Anjou', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Lachine', + 'LaSalle', + 'Le Plateau-Mont-Royal', + 'Le Sud-Ouest', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Mercier–Hochelaga-Maisonneuve', + 'Montréal-Nord', + 'Outremont', + 'Pierrefonds-Roxboro', + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Rosemont–La Petite-Patrie', + 'Saint-Laurent', + 'Saint-Léonard', + 'Verdun', + 'Ville-Marie', + 'Villeray–Saint-Michel–Parc-Extension' +] # first list, we changed its order manually to make a "smart path" for the drone + +connection_order = [ + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Montréal-Nord', + 'Saint-Léonard', + 'Anjou', + 'Mercier–Hochelaga-Maisonneuve', + 'Rosemont–La Petite-Patrie', + 'Villeray–Saint-Michel–Parc-Extension', + 'Outremont', + 'Le Sud-Ouest', + 'Ville-Marie', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Verdun', + 'LaSalle', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Le Plateau-Mont-Royal', + 'Saint-Laurent', + 'Ahuntsic-Cartierville', + 'Pierrefonds-Roxboro', + 'Lachine' +] + +def eulerization(G): + """ + Eulérise le graphe G (non orienté) en dupliquant des arêtes existantes. + Retourne un MultiGraph eulérien. + """ + + if not nx.is_connected(G): + return None + + odd_nodes = [v for v in G.nodes if G.degree(v) % 2 == 1] + + all_pairs = {} + for u in odd_nodes: + dist, path = nx.single_source_dijkstra(G, u, weight="length") + all_pairs[u] = (dist, path) + + H = nx.Graph() + for u, v in itertools.combinations(odd_nodes, 2): + if v in all_pairs[u][0]: + length = all_pairs[u][0][v] + H.add_edge(u, v, length=length) + else: + return None + + pairs = sorted(H.edges(data=True), key=lambda e: e[2]['length']) + matched = set() + min_matching = [] + for u, v, d in pairs: + if u not in matched and v not in matched: + matched.update([u, v]) + min_matching.append((u, v)) + + MG = nx.MultiGraph(G) + for u, v in min_matching: + path = all_pairs[u][1][v] + for i in range(len(path) - 1): + MG.add_edge(path[i], path[i+1]) + + return MG + +def find_circuit(G_undirected, debug_mode): + # debug_print(f"Avant eulérisation : {len(G_undirected.edges)} arêtes", debug_mode) + if nx.is_eulerian(G_undirected): + G_eulerian = G_undirected + else: + G_eulerian = eulerization(G_undirected) + # debug_print(f"Apres eulérisation : {len(G_eulerian.edges)} arêtes", debug_mode) + return list(nx.eulerian_circuit(G_eulerian)), G_eulerian + +def generate_graph(name, debug_mode=False): + """ + permet de charger un graphe + d'une localisation a partir du nom de cette derniere. + """ + G = ox.graph_from_place(name, network_type='drive') + G = remove_duplicates(G, False) + G = ox.project_graph(G) + return G + +def total_length_of_circuit(G, circuit): + return sum(G[u][v][0]['length'] for u, v in circuit) / 1000 + +def total_length_of_arrondissement(G): + distance = 0 + for u, v, data in G.edges(data=True): + distance += data["length"] + return distance / 1000 + +def process_graphs(name, debug_mode): + """ + Création des paths + """ + paths = {} + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + debug_print(f"Génération : {sub_name}", debug_mode) + sub_graph = generate_graph(sub_name, debug_mode) + G_undirected = sub_graph.to_undirected() + + circuit, G_eulerian = find_circuit(G_undirected, debug_mode) + c = [edge for edge in circuit] + + # print(f"distance kilometre du quartier = {total_length_of_arrondissement(G_undirected):.2f}km") + # print(f"distance kilometre du drone = {total_length_of_circuit(G_eulerian, circuit):.2f}km") + + paths[i] = c + + del sub_graph # to save as much memory as possible + del circuit + return paths + +def connect_circuits(G, path_dict, arrondissement_order=connection_order): + """ + La fonction trouve le chemin le plus cours entre 2 arrondissements + """ + connections = [] + for i in range(len(arrondissement_order) - 1): + from_name = arrondissement_order[i] + to_name = arrondissement_order[i + 1] + + from_path = path_dict[from_name] + to_path = path_dict[to_name] + + start_node = from_path[0][0] + end_node = from_path[-1][1] + + next_start_node = to_path[0][0] + + try: + path = nx.shortest_path(G, source=end_node, target=next_start_node, weight='length') + connections.append((from_name, to_name, path)) + except nx.NetworkXNoPath: + print(f"Aucun chemin trouvé entre {from_name} et {to_name}") + connections.append((from_name, to_name, None)) + return connections + +def final_path(graph, paths, connection_order=connection_order): + full_path = [] + + connections = connect_circuits(graph, paths) + + for i, arr_name in enumerate(connection_order): + full_path.extend(paths[arr_name]) + + if i < len(connection_order) - 1: + next_arr = connection_order[i+1] + + for conn in connections: + if conn[0] == arr_name and conn[1] == next_arr: + node_path = conn[2] + for j in range(len(node_path) - 1): + full_path.append((node_path[j], node_path[j+1])) + break + + return full_path + +def distance_total(G, paths, connections): + G_undir = G.to_undirected() + total_distance = 0.0 + used_edges = set() + + for arrondissement, edges in paths.items(): + for u, v in edges: + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + for from_arr, to_arr, node_path in connections: + for i in range(len(node_path) - 1): + u = node_path[i] + v = node_path[i+1] + key = (min(u, v), max(u, v)) + used_edges.add(key) + total_distance += G_undir[u][v][0]['length'] + + unused_distance = 0.0 + for u, v, data in G_undir.edges(data=True): + key = (min(u, v), max(u, v)) + if key not in used_edges: + unused_distance += data['length'] + + total_distance /= 1000 + unused_distance /= 1000 + return total_distance, unused_distance + +def distance_optimal(G): + """ + Calcule la somme des longueurs de toutes les routes dans les arrondissements + """ + covered_edges = set() + for i in arrondissements: + sub_name = i + ", Montréal, Québec, Canada" + sub_graph = generate_graph(sub_name) + for u, v, data in sub_graph.edges(data=True): + covered_edges.add((min(u, v), max(u, v))) + del sub_graph + + G_undir = G.to_undirected() + total = 0.0 + for u, v in covered_edges: + total += G_undir[u][v][0]['length'] + + + return total / 1000 + +def postier_chinois_process_v3(G, debug_mode): + name = "Montréal, Québec, Canada" + # initially, we ran find circuit on the whole graph + # => processes all suburbs instead of the whole graph + paths = process_graphs(name, debug_mode) + # it was our closest attempt to get an optimal answer but way to long (ran for more than 12h and did not finish) + finalPath = final_path(G, paths) + + # Save Path with YML + save_paths_to_yaml(paths, "paths-PostierChinoisV3.yml") + + return paths, finalPath diff --git a/ero1/src/drone/postier_chinois_Martial.py b/ero1/src/drone/postier_chinois_Martial.py new file mode 100644 index 0000000..a0afb14 --- /dev/null +++ b/ero1/src/drone/postier_chinois_Martial.py @@ -0,0 +1,122 @@ +import parameters as params +import itertools +from src.helper.debug_printer import debug_print +import networkx as nx +import pandas as pd + +def postier_chinois(G, debug_mode=False): + """ + Parcourt le graphe en résolvant le problème du postier chinois + Source: https://brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/#solving-the-chinese-postman-problem + Parameters: + G: Le graphe des routes + debug_mode: Logs de debug + Returns: + La liste des arêtes (routes) avec entre 2.5 et 15 cm de neige + """ + gu = nx.to_undirected(G) + nodes_odd_degree = [v for v, d in gu.degree() if d % 2 == 1] + debug_print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)), debug_mode) + debug_print('Number of total nodes: {}'.format(len(gu.nodes())), debug_mode) + + odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2)) + debug_print('Number of odd degree node pairs: {}'.format(len(odd_node_pairs)), debug_mode) + + def get_shortest_paths_distances(graph, pairs, edge_weight_name): + """ + Compute shortest distance between each pair of nodes in a graph. Return a dictionary keyed on node pairs (tuples). + """ + distances = {} + for pair in pairs: + distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name) + return distances + odd_node_pairs_shortest_paths = get_shortest_paths_distances(gu, odd_node_pairs, 'length') + + def create_complete_graph(pair_weights, flip_weights=True): + """ + Create a completely connected graph using a list of vertex pairs and the shortest path distances between them + Parameters: + pair_weights: list[tuple] from the output of get_shortest_paths_distances + flip_weights: Boolean. Should we negate the edge attribute in pair_weights? + """ + g = nx.Graph() + for k, v in pair_weights.items(): + wt_i = - v if flip_weights else v + # g.add_edge(k[0], k[1], {'distance': v, 'weight': wt_i}) # deprecated after NX 1.11 + g.add_edge(k[0], k[1], **{'distance': v, 'weight': wt_i}) + return g + g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True) + debug_print('Number of nodes in complete graph of odd nodes: {}'.format(len(g_odd_complete.nodes())), debug_mode) + debug_print('Number of edges in complete graph of odd nodes: {}'.format(len(g_odd_complete.edges())), debug_mode) + + odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True) + odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes])) + debug_print('Number of edges in max weight matching: {}'.format(len(odd_matching)), debug_mode) + + def add_augmenting_path_to_graph(graph, min_weight_pairs): + """ + Add the min weight matching edges to the original graph + Parameters: + graph: NetworkX graph (original graph from trailmap) + min_weight_pairs: list[tuples] of node pairs from min weight matching + Returns: + augmented NetworkX graph + """ + + # We need to make the augmented graph a MultiGraph so we can add parallel edges + graph_aug = nx.MultiGraph(graph.copy()) + for pair in min_weight_pairs: + graph_aug.add_edge(pair[0], + pair[1], + **{'length': nx.dijkstra_path_length(graph, pair[0], pair[1]), 'name': 'augmented'} + # attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]), + # 'trail': 'augmented'} # deprecated after 1.11 + ) + return graph_aug + g_aug = add_augmenting_path_to_graph(gu, odd_matching) + + # Counts + debug_print('Number of edges in original graph: {}'.format(len(gu.edges())), debug_mode) + debug_print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())), debug_mode) + + def create_eulerian_circuit(graph_augmented, graph_original): + """ + Create the eulerian path using only edges from the original graph. + """ + debug_print("Creating eulerian circuit", debug_mode) + euler_circuit = [] + naive_circuit = list(nx.eulerian_circuit(graph_augmented)) + dbg = False + + for edge in naive_circuit: + edge_data = graph_augmented.get_edge_data(edge[0], edge[1]) + + if len(edge_data) == 1 and 'name' in edge_data[0] and edge_data[0]['name'] != 'augmented': + # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit. + edge_att = graph_original[edge[0]][edge[1]] + euler_circuit.append((edge[0], edge[1], edge_att)) + else: + aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='length') + aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:])) + + debug_print('Filling in edges for augmented edge: {}'.format(edge), dbg) + debug_print('Augmenting path: {}'.format(' => '.join(str(aug_path))), dbg) + debug_print('Augmenting path pairs: {}\n'.format(aug_path_pairs), dbg) + + # If `edge` does not exist in original graph, find the shortest path between its nodes and + # add the edge attributes for each link in the shortest path. + for edge_aug in aug_path_pairs: + edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]] + euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att)) + + return euler_circuit + euler_circuit = create_eulerian_circuit(g_aug, gu) + debug_print('Length of Eulerian circuit: {}'.format(len(euler_circuit)), debug_mode) + + debug_print("Extraction des la météo des neiges depuis le parcours eulérien...", debug_mode) + + routes_enneigées = [] + for edge in euler_circuit: + if params.SNOW_THRESHOLD <= edge[2][0]['snow'] <= params.SNOW_MAX: + routes_enneigées.append(edge) + return routes_enneigées \ No newline at end of file diff --git a/ero1/src/drone/postier_chinois_montreal.py b/ero1/src/drone/postier_chinois_montreal.py new file mode 100644 index 0000000..04ade41 --- /dev/null +++ b/ero1/src/drone/postier_chinois_montreal.py @@ -0,0 +1,89 @@ +import osmnx as ox +import networkx as nx +import parameters as params + +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph +from src.helper.duplicate_removal import remove_duplicates +from src.helper.export_import_yaml import save_paths_to_yaml + +arrondissements = [ + 'Ahuntsic-Cartierville', + 'Anjou', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Lachine', + 'LaSalle', + 'Le Plateau-Mont-Royal', + 'Le Sud-Ouest', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Mercier–Hochelaga-Maisonneuve', + 'Montréal-Nord', + 'Outremont', + 'Pierrefonds-Roxboro', + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Rosemont–La Petite-Patrie', + 'Saint-Laurent', + 'Saint-Léonard', + 'Verdun', + 'Ville-Marie', + 'Villeray–Saint-Michel–Parc-Extension' +] # first list, we changed its order manually to make a "smart path" for the drone + +connection_order = [ + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Montréal-Nord', + 'Saint-Léonard', + 'Anjou', + 'Mercier–Hochelaga-Maisonneuve', + 'Rosemont–La Petite-Patrie', + 'Villeray–Saint-Michel–Parc-Extension', + 'Outremont', + 'Le Sud-Ouest', + 'Ville-Marie', + 'L\'Île-Bizard–Sainte-Geneviève', + 'Verdun', + 'LaSalle', + 'Côte-des-Neiges–Notre-Dame-de-Grâce', + 'Le Plateau-Mont-Royal', + 'Saint-Laurent', + 'Ahuntsic-Cartierville', + 'Pierrefonds-Roxboro', + 'Lachine' +] + +def find_circuit(G_undirected, debug_mode): + if nx.is_eulerian(G_undirected): + G_eulerian = G_undirected + else: + G_eulerian = nx.eulerize(G_undirected) + return nx.eulerian_circuit(G_eulerian), G_eulerian + +def generate_graph(name, debug_mode=False): + """ + permet de charger un graphe + d'une localisation a partir du nom de cette derniere. + """ + G = ox.graph_from_place(name, network_type='drive') + G = remove_duplicates(G, False) + G = ox.project_graph(G) + return G + +def process_graphs(Graphe_montreal, debug_mode): + """ + Création des paths + """ + paths = {} + debug_print(f"Génération : Montréal", debug_mode) + G_undirected = Graphe_montreal.to_undirected() + circuit, _ = find_circuit(G_undirected, debug_mode) + c = [edge for edge in circuit] + paths["Montréal"] = c + return paths + +def postier_chinois_process_montreal(Graphe_montreal, debug_mode): + paths = process_graphs(Graphe_montreal, debug_mode) + + # Save Path with YML + save_paths_to_yaml(paths, "paths-PostierChinoisMontreal.yml") + + return paths, finalPath diff --git a/ero1/src/generation/graph_generation.py b/ero1/src/generation/graph_generation.py new file mode 100644 index 0000000..641e761 --- /dev/null +++ b/ero1/src/generation/graph_generation.py @@ -0,0 +1,17 @@ +import osmnx as ox +from src.helper.duplicate_removal import remove_duplicates + +def generate_graph(city_name, debug_mode=False): + """ + Génère un graphe à partir du nom d'une ville en utilisant OSMnx. + + Parameters: + city_name : Le nom de la ville pour laquelle générer le graphe. + + Returns: + MultiDiGraph : Le graphe généré. + """ + # Generate the graph from the city name + GRAPH = ox.graph_from_place(city_name, network_type='drive') + GRAPH = remove_duplicates(GRAPH, debug_mode) + return GRAPH \ No newline at end of file diff --git a/ero1/src/generation/habitation_generation.py b/ero1/src/generation/habitation_generation.py new file mode 100644 index 0000000..35cddaa --- /dev/null +++ b/ero1/src/generation/habitation_generation.py @@ -0,0 +1,24 @@ +# FICHIER DEPRECATED : Ce fichier n'est plus utilisé. + +import random +import parameters as params + +def place_habitation(G): + """ + Place des zones d'habitation sur les arêtes du graphe. + Parameters: + G (voir quel type on veut utiliser): le graphe des routes + Returns: + None: le graphe est modifié en place + """ + edges = list(G.edges(keys=True, data=True)) + n = len(edges) + amount_to_place = int(params.HABITATION_PERCENTAGE * n) + + # Trie les arrêtes par leur longueur. (x[3] = data) + edges_sorted = sorted(edges, key=lambda x: x[3].get('length', 0), reverse=True) + + # Place les habitations sur les plus longues arêtes ? (tentative - juste pour tester les drones) + # WARNING : peut être remplacer la fonction plus tard. + for (u, v, k, data) in edges_sorted[:amount_to_place]: + data['habitation'] = True diff --git a/ero1/src/generation/snow_generation.py b/ero1/src/generation/snow_generation.py new file mode 100644 index 0000000..449a4ec --- /dev/null +++ b/ero1/src/generation/snow_generation.py @@ -0,0 +1,85 @@ +# FICHIER DEPRECATED : Ce fichier n'est plus utilisé. + +import random +import parameters as params + + +def place_snow(G): + """ + Place de la neige sur les egdes du graphe + Parameters: + G (voir quel type on veut utiliser): le graphe des routes + Returns: + None: le graphe est modifié en place + """ + # WARNING: je ne suis pas sûr de cette manière de faire qui me semble boffe, je pense qu'une manière plus random (mais plus sale/lente) serait de shuffle la liste d'edges. Le soucis avec la méthode actuelle c'est que si G.egdes(...) ordonne les arcs/arêtes d'une manière prédéfinie, alors le début/la fin de la liste sera composé de beacoup/peu de neige, ce qui n'est pas uniforme + edges = list(G.edges(keys=True, data=True)) + n = len(edges) + random.shuffle(edges) + amount_to_cover = int(params.SNOW_PERCENTAGE * n) + quantity: float = 0 + + for u, v, k, data in edges: + if (amount_to_cover == 0): # we should place > 2.5cm snow + quantity = random.uniform( + params.SNOW_THRESHOLD + 0.01, params.SNOW_MAX) + else: # we do not care + quantity = random.uniform(params.SNOW_MIN, params.SNOW_MAX) + + if (quantity >= params.SNOW_THRESHOLD): + amount_to_cover -= 1 + + data['snow'] = quantity + + +def place_snow_v2(G): + """ + Place de la neige sur les egdes du graphe, moins opti que la v1 mais gère les cas (u,v) et (v,u) (plus réaliste) + Parameters: + G (voir quel type on veut utiliser): le graphe des routes + Returns: + (int, int): (nb_edges_oriented, nb_edges_nonoriented), renvoie le nombre d'edges qui ont plus de 2.5 cm de neige (utile pour débug les drônes) + """ + edges = list(G.edges(keys=True, data=True)) + n = len(edges) + random.shuffle(edges) + amount_to_cover = int(params.SNOW_PERCENTAGE * n) + TO_DELETE = amount_to_cover # pls delete once testing is finished + quantity: float = 0 + + res_oriented = 0 + res_unoriented = 0 + visited = {} # (u,v) => quantity + + for u, v, k, data in edges: + if (v, u) in visited: + data['snow'] = visited[(v, u)] + amount_to_cover -= 1 + + res_unoriented += 1 + # we do not increment res_oriented since (u,v) and (v,u) are the same thing + # => check to_undirected but should be good + elif (u, v) in visited: + data['snow'] = visited[(u, v)] + # WARNING: this implementation might not be the most accurate/best + + amount_to_cover -= 1 + # TODO : wtf do I do with the counters ... technically nothing ? + else: + if (amount_to_cover <= 0): # we should place > 2.5cm snow + quantity = random.uniform( + params.SNOW_THRESHOLD + 0.01, params.SNOW_MAX) + else: # we do not care + quantity = random.uniform(params.SNOW_MIN, params.SNOW_MAX) + + if (quantity >= params.SNOW_THRESHOLD): + amount_to_cover -= 1 + + data['snow'] = quantity + visited[(u, v)] = quantity + + res_unoriented += 1 + res_oriented += 1 + + # assert (TO_DELETE == res_unoriented) => need to check how to handle duplicate of the form (u,v) + return res_oriented, res_unoriented diff --git a/ero1/src/generation/suburb_snowplow_generation.py b/ero1/src/generation/suburb_snowplow_generation.py new file mode 100644 index 0000000..156bdda --- /dev/null +++ b/ero1/src/generation/suburb_snowplow_generation.py @@ -0,0 +1,88 @@ +import networkx as nx +from src.generation.graph_generation import generate_graph +from src.helper.export_import_yaml import load_paths_from_yaml +import osmnx as ox + +arrondissements = [ + 'Anjou', + 'Le Plateau-Mont-Royal', + 'Outremont', + 'Rivière-des-Prairies–Pointe-aux-Trembles', + 'Verdun', +] + + +def logic_quartiers_(path_list, montreal_g, suburb_list, debug_mode=False): + """ + the main logic behind the generate_quartiers functions + """ + + if debug_mode: + tot_edges = 0 + tot_nodes = 0 + for arr in suburb_list: + g_temp = ox.graph_from_place( + arr + ", Montréal, Québec, Canada", network_type='drive') + removed = [(u, v, k) + for u, v, k in g_temp.edges(keys=True) if k > 0] + g_temp.remove_edges_from(removed) + tot_edges += len(g_temp.edges) + tot_nodes += len(g_temp.nodes) + + print("tot_edges = " + str(tot_edges)) + print("tot_nodes = " + str(tot_nodes)) + + # graph_mont = generate_graph("Montréal, Québec, Canada") + graph_mont = montreal_g + + res = nx.DiGraph() + + i = 0 + + for arr in suburb_list: + for u, v in path_list[arr]: + # print("u : " + str(u)) + # print("v : " + str(v)) + # print("noeud u: "+str(graph_mont.nodes[u])) + # print("noeud v: "+str(graph_mont.nodes[v])) + # print("(u,v) in graph : " + str((u, v) + # in graph_mont.edges(keys=False))) + # print("edge u,v: "+str(graph_mont.edges[(u, v, 0)])) + try: + res.add_node(u, **graph_mont.nodes[u]) + res.add_node(v, **graph_mont.nodes[v]) + if graph_mont.has_edge(u, v): + res.add_edge(u, v, **graph_mont.edges[(u, v, 0)]) + if graph_mont.has_edge(v, u): + res.add_edge(v, u, **graph_mont.edges[(v, u, 0)]) + except: + i += 1 + continue + + return res + + +def generate_quartiers_from_yaml(path_yaml_drone, montreal_g, suburb_list=arrondissements, debug_mode=False): + """ + Génère un graphe qui est l'union des edges/nodes des graphes de chaque + quartiers où path_yaml_drone est le chemin du fichier yaml qui + contient le resultat du drone + Parameters: + debug_mode (bool: default = False): le debug mode duh + Return: + nx.MultiDiGraph/nx.DiGraph : la fusion des quartiers + """ + path_res = load_paths_from_yaml(path_yaml_drone) + return logic_quartiers_(path_res, montreal_g, suburb_list, debug_mode) + + +def generate_quartiers_from_path(path_list, montreal_g, suburb_list=arrondissements, debug_mode=False): + """ + Génère un graphe qui est l'union des edges/nodes des graphes de chaque + quartiers où path_list est le resultat du drone + Parameters: + debug_mode (bool: default = False): le debug mode duh + Return: + nx.MultiDiGraph/nx.DiGraph : la fusion des quartiers + """ + return logic_quartiers_(path_list, montreal_g, suburb_list, debug_mode) diff --git a/ero1/src/helper/check_eulerian.py b/ero1/src/helper/check_eulerian.py new file mode 100644 index 0000000..31a5db4 --- /dev/null +++ b/ero1/src/helper/check_eulerian.py @@ -0,0 +1,77 @@ +import parameters as params +import networkx as nx +import osmnx as ox + +def check_directed_eulerian(G): + """ + Check si le graph ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est + renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none. + None = non eulérien + (None, None) = eulérien mais pas de sommets de degrée impair + (V1, V2) = eulérien et possède 2 sommets de degrée impaires + Parameters: + G: Graph à tester + """ + V = list(G.nodes) + odd_start = None + odd_end = None + for node in V: + # This is the implementation used when you want to play with a directed graph + # Sadly NetworkX cannor eulerize directed graph + # Eulerzing a directed graph is... NP-Hard + if (G.in_degree(node) + 1 == G.out_degree(node)): + # We have one more edge exitting than entering + # This is the potential start of an eulerian path + if (odd_start != None): + # We already found a node that could make a staring point ? + # We have too much odd degree vertices in this graph + return None + odd_start = node + elif (G.in_degree(node) == G.out_degree(node) + 1): + # We have one more edge entering than exitting + # This is the potential end of an eulerian path + if (odd_end != None): + # We already found a node that could make an ending point ? + # We have too much odd degree vertices in this graph + return None + odd_end = node + elif (G.in_degree(node) != G.out_degree(node)): + # Something's wrong, this is not at all an eulerian graph + return None + + # There is no clean XOR in python... + # Sad... + if (bool(odd_start) != bool(odd_end)): + # We only have one vertice with and odd degree + return None + return (odd_start, odd_end) + +def check_non_directed_eulerian(G): + """ + Check si le graph NON ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est + renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none. + None = non eulérien + (None, None) = eulérien mais pas de sommets de degrée impair + (V1, V2) = eulérien et possède 2 sommets de degrée impaires + Parameters: + G: Graph à tester + """ + V = list(G.nodes) + odd_start = None + odd_end = None + + for node in V: + if (G.degree(node) % 2 == 1): + if (odd_start == None): + odd_start = node + elif (odd_end == None): + odd_end = node + else: + return None + + # There is no clean XOR in python... + # Sad... + if (bool(odd_start) != bool(odd_end)): + # We only have one vertice with and odd degree + return None + return (odd_start, odd_end) \ No newline at end of file diff --git a/ero1/src/helper/color_suburbs.py b/ero1/src/helper/color_suburbs.py new file mode 100644 index 0000000..7668999 --- /dev/null +++ b/ero1/src/helper/color_suburbs.py @@ -0,0 +1,70 @@ +import osmnx as ox + +colors = [ + "#e6194b", # rouge vif 1 + "#3cb44b", # vert vif 2 + "#ffe119", # jaune 3 + "#4363d8", # bleu 4 + "#f58231", # orange 5 + "#911eb4", # violet 6 + "#46f0f0", # cyan clair 7 + "#f032e6", # rose 8 + "#bcf60c", # vert citron 9 + "#fabebe", # rose pâle 10 + "#008080", # turquoise foncé 11 + "#e6beff", # lavande 12 + "#9a6324", # brun 13 + "#fffac8", # crème 14 + "#800000", # bordeaux 15 + "#aaffc3", # vert menthe 16 + "#808000", # olive 17 + "#ffd8b1", # pêche 18 + "#000075", # bleu marine 19 +] + + +def display_suburbs_with_colors(G, path, connections=None): + """ + Colorie chaque quartier d'une couleur différente + Parameter: + path (map>: resultat du postier chinois, + G (DiGraph): graph de montreal + Result: + void + """ + + associated_color = {} + connection_color = "#FFFFFF" # noir + + i = 0 + for suburb in path: + for u, v in path[suburb]: + if (v,u) in G.edges(keys=False): + associated_color[(v, u)] = colors[i] + associated_color[(u, v)] = colors[i] + + i += 1 + + if connections: + for _, _, conn_path in connections: + if conn_path is None or len(conn_path) < 2: + continue + for i in range(len(conn_path) - 1): + u, v = conn_path[i], conn_path[i + 1] + if (v, u) in G.edges(keys=False): + associated_color[(v, u)] = connection_color + associated_color[(u, v)] = connection_color + + count = 0 + edge_colors = [] + for u, v in G.edges(keys=False): + if (u,v) in associated_color: + edge_colors.append(associated_color[(u, v)]) + count += 1 + else: + edge_colors.append("grey") + + # print(f"{count} arêtes colorées (quartiers + connexions)") + + fig, ax = ox.plot_graph(G, edge_color=edge_colors, + node_size=0, edge_linewidth=1) diff --git a/ero1/src/helper/debug_printer.py b/ero1/src/helper/debug_printer.py new file mode 100644 index 0000000..b276630 --- /dev/null +++ b/ero1/src/helper/debug_printer.py @@ -0,0 +1,13 @@ +from datetime import datetime + +def debug_print(message, started): + """ + Affiche dans la console un message de débug s'il est activé avec un timestamp. + Parameters: + message : Le message à afficher. + started : Indique si le debug est activé ou non. + """ + if started: + # Récupérer le timestamp actuel en format string + str_time = datetime.now().strftime('%H:%M:%S.%f')[:-3] + print(f"[{str_time}] [DEBUG] {message}") diff --git a/ero1/src/helper/display_graph.py b/ero1/src/helper/display_graph.py new file mode 100644 index 0000000..693d6e1 --- /dev/null +++ b/ero1/src/helper/display_graph.py @@ -0,0 +1,116 @@ +import matplotlib +matplotlib.use('TkAgg') # KEEP - Eviter erreur avc WSL +import osmnx as ox +import matplotlib.patches as mpatches +import matplotlib.pyplot as plt + +# Variables globales pour stocker la graphique et son état +fig = None +ax = None + +def init_display(): + global fig, ax + if fig is None and ax is None: + plt.ion() # Création du graphique par défaut s'il n'existe pas + fig = plt.figure(figsize=(12, 8)) + ax = fig.add_subplot(111) + plt.show(block=False) + +def edge_in_list(edge, edge_list): + if edge_list is None: + return False + for e in edge_list: + if (e[0] == edge[0] and e[1] == edge[1]) or \ + (e[0] == edge[1] and e[1] == edge[0]): + return True + return False + +def display_graph(G, place_name, reversed_legend, highlight_edges=None, current_edges=None, last_call=False, double_sens=False): + """ + Affiche le graphe G avec la quantité de neige sur chaque arête et les habitations. + Parameters: + G : Le graphe à afficher. + place_name : Nom du lieu + reversed_legend : Si True, la légende est à droite + highlight_edges : Liste des arêtes à mettre en surbrillance + current_edges : Liste des arêtes visitées + last_call : Si True, le graphique est affiché indéfiniment + """ + global fig, ax + + # Initialisation du graphique si premier appel + init_display() + + # Suppression du graphique actuel + ax.clear() + + # Récupérer les quantités de neige sur les arêtes + snow_quantities = [] + for u, v, k, data in G.edges(keys=True, data=True): + snow_quantities.append(data.get('snow', 0)) + + # Affecter une couleur à chaque arête en fonction de la quantité de neige et habitation + legend_labels = ['<2.5cm', '<5cm', '<10cm', '+10cm']#, 'Habitations'] + legend_colors = ['red', 'deepskyblue', 'dodgerblue', 'navy']#, 'green'] + if double_sens: + legend_labels= ["double sens", "une direction"] + legend_colors= ['green', 'black'] + snow_colors = [] + if snow_quantities: + for i, (u, v, k) in enumerate(G.edges(keys=True)): + snow = snow_quantities[i] + edge = (u, v, k) + if double_sens: + if any((v, u, k) == edge for edge in G.edges(keys=True)): + snow_colors.append('green') + else: + snow_colors.append('black') + continue + + # Déterminer la couleur de l'arête + elif current_edges and edge in current_edges: + # Si c'est la dernière arête visitée + snow_colors.append("purple") + elif last_call or (highlight_edges and edge_in_list(edge, highlight_edges)): + # Si c'est une arête enneigée + if snow < 2.5: + snow_colors.append('red') + elif snow < 5: + snow_colors.append('deepskyblue') + elif snow < 10: + snow_colors.append('dodgerblue') + else: + snow_colors.append('navy') + else: + # Couleur normale basée sur la neige + snow_colors.append("white") + else: + snow_colors = 'b' + + # Tracer toutes les arêtes sur le graphique + ox.plot_graph(G, edge_color=snow_colors, edge_linewidth=2, ax=ax, show=False, close=False) + + # Configurer le titre et la légende + ax.set_title('Graphe | ' + place_name) + + # Mise à jour de la légende & ajout des couleurs + for i in range(len(legend_colors)): + ax.plot([], [], color=legend_colors[i], linewidth=4, label=legend_labels[i]) + if highlight_edges: + if current_edges: + ax.plot([], [], color="purple", linewidth=4, label='Chemin actuel') + if double_sens: + ax.legend(title='Sens de circulation', loc='lower ' + ("right" if reversed_legend else "left")) + else: + ax.legend(title='Quantité de neige', loc='lower ' + ("right" if reversed_legend else "left")) + + # Sauvegarder l'image pour le debug + plt.savefig('temp/debug_graph.png', dpi=300) + + # Mettre à jour l'affichage + fig.canvas.draw() + fig.canvas.flush_events() + if not last_call: + plt.pause(0.01) # Délai pour pas tout exploser + else: + plt.pause(120) # Temporaire pour dernier affichage car destruction massive si pas de pause longue \ No newline at end of file diff --git a/ero1/src/helper/duplicate_removal.py b/ero1/src/helper/duplicate_removal.py new file mode 100644 index 0000000..4138bb8 --- /dev/null +++ b/ero1/src/helper/duplicate_removal.py @@ -0,0 +1,16 @@ +from src.helper.debug_printer import debug_print + +def remove_duplicates(graph, debug_mode=False): + """ + Supprime les noeuds dupliqués du graphe. + Parameters: + graph : Le graphe à nettoyer. + debug_mode : Indique si le mode debug est activé ou non. + """ + + removed = [(u, v, k) for u, v, k in graph.edges(keys=True) if k > 0] + graph.remove_edges_from(removed) + + debug_print(f"Nombre d'arêtes dupliquées supprimées : {len(removed)}", debug_mode) + + return graph diff --git a/ero1/src/helper/export_cost.py b/ero1/src/helper/export_cost.py new file mode 100644 index 0000000..d3d9ede --- /dev/null +++ b/ero1/src/helper/export_cost.py @@ -0,0 +1,60 @@ +# - Distance Parcourus +# - Nombre de déneigeuses +# - Coût en fonction de la déneigeuse choisie +# - Coût du drone +# - Distance parcourus par déneigeuse +# - Temps "réel" passé +# - Temps d'exécution (Indicatif uniquement) + +from src.helper.debug_printer import debug_print +import math +import parameters as params + +def export_cost(parcours_drone, parcours_deneigeuses, graph, debug_mode, temps_execution_deneigeuse, temps_execution_drone): + """ + Exporte le coût du parcours. + Parameters: + parcours_drone : Les routes à exporter. + parcours_deneigeuses : Les routes à exporter. + graph : Le graphe à exporter. + debug_mode : Indique si le mode debug est activé ou non. + temps_execution_deneigeuse : Le temps d'exécution des déneigeuses. + temps_execution_drone : Le temps d'exécution du drone. + """ + + debug_print(f"======== EXPORT COST ==========", debug_mode) + debug_print(f"Exportation du coût du parcours.", debug_mode) + + + def get_edge_length(u, v): + try: + return graph[u][v][0]['length'] + except KeyError: + try: + return graph[v][u][0]['length'] + except KeyError: + return 0 + + distance_parcourue_deneigeuses = math.ceil(sum(sum(get_edge_length(u, v) for u, v in parcours) for parcours in parcours_deneigeuses)) + distance_parcourue_drone = math.ceil(sum(get_edge_length(u, v) for u, v in parcours_drone)) + nombre_de_de_neigeuses = len(parcours_deneigeuses) + + debug_print(f"Distance parcourue - Drone : {distance_parcourue_drone}m", debug_mode) + debug_print(f"Distance parcourue - Déneigeuses : {distance_parcourue_deneigeuses}m", debug_mode) + debug_print(f"Nombre de déneigeuses : {nombre_de_de_neigeuses}", debug_mode) + debug_print(f"Temps d'exécution - Drone : {temps_execution_drone} secondes", debug_mode) + + i = 1 + for parcours in parcours_deneigeuses: + distance_parcourue_deneigeuse = math.ceil(sum(get_edge_length(u, v) for u, v in parcours)) + debug_print(f" Distance parcourue - Déneigeuse {i} : {distance_parcourue_deneigeuse}m", debug_mode) + i += 1 + + debug_print(f"======== EXPORT COST ==========", debug_mode) + + # Exportation du coût du parcours dans un fichier texte + with open("temp/export_cost.txt", "w") as f: + f.write(f"{params.ALGORITHM_NAME}|{distance_parcourue_drone}|{distance_parcourue_deneigeuses}|{nombre_de_de_neigeuses}|{temps_execution_deneigeuse}|{temps_execution_drone}\n") + for parcours in parcours_deneigeuses: + distance_parcourue_deneigeuse = math.ceil(sum(get_edge_length(u, v) for u, v in parcours)) + f.write(f"{distance_parcourue_deneigeuse}\n") diff --git a/ero1/src/helper/export_import_yaml.py b/ero1/src/helper/export_import_yaml.py new file mode 100644 index 0000000..1cafb8d --- /dev/null +++ b/ero1/src/helper/export_import_yaml.py @@ -0,0 +1,20 @@ +import yaml + +def save_paths_to_yaml(paths, filename="paths.yml"): + # to facilitate testing for snowplow (do not have to redo the drone part each time) + serializable_paths = { + k: [[u, v] for (u, v) in v] for k, v in paths.items() + } + with open(f"paths/{filename}", 'w') as f: + yaml.dump(serializable_paths, f) + +def load_paths_from_yaml(graph, filename="paths.yml"): + with open(filename, 'r') as f: + raw_paths = yaml.safe_load(f) + + # Reconstruit le format avec des tuples (u, v) + paths = { + k: [tuple(edge) for edge in v] for k, v in raw_paths.items() + } + + return paths diff --git a/ero1/src/helper/export_to_kml.py b/ero1/src/helper/export_to_kml.py new file mode 100644 index 0000000..37f123b --- /dev/null +++ b/ero1/src/helper/export_to_kml.py @@ -0,0 +1,95 @@ +from src.helper.debug_printer import debug_print +import simplekml +import random +import math + +def export_to_kml(parcours_deneigeuses, parcours_drone, graph, debug_mode, name="parcours_deneigeuses"): + """ + Exporte les parcours des déneigeuses dans un fichier KML. + Parameters: + parcours_deneigeuses : Les parcours des déneigeuses. + parcours_drone : Le parcours du drone. + graph : Le graphe à exporter. + debug_mode : Indique si le mode debug est activé ou non. + """ + + debug_print(f"Exportation des parcours des déneigeuses dans un fichier KML.", debug_mode) + + # Création d'un nouveau fichier KML + kml = simplekml.Kml() + + # Récupération d'une couleur aléatoire pour chaque déneigeuse + colors = [] + parcours_deneigeuses.insert(0, parcours_drone) + + for _ in range(len(parcours_deneigeuses)): + r = random.randint(0, 255) + g = random.randint(0, 255) + b = random.randint(0, 255) + colors.append(simplekml.Color.rgb(r, g, b)) + + # Traitement du parcours de chaque déneigeuse + for i, path in enumerate(parcours_deneigeuses): + # Création d'un itinéraire pour chaque déneigeuse + nom = f"Déneigeuse {i}" if i != 0 else "Drone" + folder = kml.newfolder(name=nom) + + coordonnées = [] + profondeurs_neige = [] + distance_parcourue = 0 + + # Ajout des coordonnées pour chaque arête du parcours + for u, v in path: + try: + c_u = (graph.nodes[u]['x'], graph.nodes[u]['y']) + c_v = (graph.nodes[v]['x'], graph.nodes[v]['y']) + + coordonnées.append(c_u) + coordonnées.append(c_v) + + # Récupération de la profondeur de neige et de la distance + try: + profondeur_neige = graph[u][v][0].get('snow', 0) + distance_parcourue += graph[u][v][0]["length"] + except KeyError: + try: + profondeur_neige = graph[v][u][0].get('snow', 0) + distance_parcourue += graph[v][u][0]["length"] + except KeyError: + profondeur_neige = 0 + + profondeurs_neige.append(profondeur_neige) + except KeyError: + continue + + moyenne_neige = sum(profondeurs_neige) / len(profondeurs_neige) if profondeurs_neige else 0 + + # Création du point de départ/arrivée + start_point = folder.newpoint(name=f"Départ {nom}") + start_point.coords = [coordonnées[0]] + start_point.style.iconstyle.icon.href = 'http://maps.google.com/mapfiles/kml/shapes/placemark_circle.png' + start_point.style.iconstyle.scale = 0.5 + start_point.style.iconstyle.color = simplekml.Color.red + + + start_point = folder.newpoint(name=f"Fin {nom}") + start_point.coords = [coordonnées[-1]] + start_point.style.iconstyle.icon.href = 'http://maps.google.com/mapfiles/kml/shapes/placemark_circle.png' + start_point.style.iconstyle.scale = 0.5 + start_point.style.iconstyle.color = simplekml.Color.red + + # Création de l'itinéraire + route = folder.newlinestring(name=f"Itinéraire {nom}") + route.coords = coordonnées + route.altitudemode = simplekml.AltitudeMode.clamptoground # Afficher correctement la route + + route.style.linestyle.color = colors[i] + route.style.linestyle.width = 5 + + route.description = f"Itinéraire {nom}\nDistance parcourue: {math.ceil(distance_parcourue/1000)} km" + + # Sauvegarde du fichier KML + kml.save(f"temp/{name}.kml") + debug_print(f"Fichier KML créé avec succès: temp/{name}.kml", debug_mode) + + return True \ No newline at end of file diff --git a/ero1/src/helper/main_parcours.py b/ero1/src/helper/main_parcours.py new file mode 100644 index 0000000..02b92de --- /dev/null +++ b/ero1/src/helper/main_parcours.py @@ -0,0 +1,137 @@ +import time +from src.helper.debug_printer import debug_print +from src.helper.export_cost import export_cost +from src.helper.export_to_kml import export_to_kml +from src.deneigeuses.hierholzer import process_hierholzer +from src.deneigeuses.directed_cpp import oriented_cpt +from src.helper.display_graph import display_graph +from src.helper.output_debug import output_debug +from src.generation.graph_generation import generate_graph +from src.helper.color_suburbs import display_suburbs_with_colors +from src.helper.prune_maps import prune_verdun +import networkx as nx + + +# IMPORT FOR YAML +from src.helper.export_import_yaml import load_paths_from_yaml +from src.helper.partitions import partition +from src.generation.suburb_snowplow_generation import generate_quartiers_from_path + +# IMPORT FOR DRONE +from src.drone.postier_chinoisV2 import final_path +# from src.drone.postier_chinoisV2 import postier_chinois_process + +def main_parcours(debug_mode=False, place_name=None, reversed_legend=None): + """ + Fonction principale pour le parcours du graphe. + Parameters: + debug_mode : Indique si le mode debug est activé ou non. + place_name : Le nom de la place à parcourir. + reversed_legend : Si la légende est inversée. + """ + + #output_debug(None, None, None, debug_mode) + + parcours_deneigeuses = [] + # ---------------------- GENERATION DU GRAPHE --------------------------- + + debug_print("Génération du graph de Montréal en cours...", debug_mode) + graph = generate_graph("Montréal, Québec, Canada", debug_mode) + debug_print("Graph généré avec succès.", debug_mode) + + # ---------------------- GENERATION DU GRAPHE --------------------------- + + # ---------------------- PARCOURS - DRONE --------------------------- + + start_time_drone = time.time() + + #debug_print("Parcours du drone dans chaque arrondissement", debug_mode) + # - Load from the saved file directly + parcours_drone = load_paths_from_yaml(graph, filename="paths/paths-PostierChinoisV1.yml") # Nom à rajouter du coup + finalPath = final_path(graph, parcours_drone) + + # - Postier Chinois V{?} + # parcours_drone, finalPath = postier_chinois_process(graph, debug_mode) + + end_time_drone = time.time() + + # ---------------------- PARCOURS - DRONE --------------------------- + + # display_suburbs_with_colors(graph, parcours_drone, connections) + + # ---------------------- RECUPERATION DU PARCOURS DU DRONE --------------------------- + temp = [] + # if place_name in parcours_drone: + # debug_print("Parcours du drone dans l'arrondissement de " + place_name, debug_mode) + # for elt in ["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"] : + # if elt in parcours_drone: + # print(elt, len(parcours_drone[elt])) + # temp.extend(parcours_drone[elt]) + # else: + # print("Arrondissement non trouvé:", elt) + # print("Total", len(temp)) + # parcours_drone = temp + # else: + # debug_print("Parcours du drone dans l'arrondissement de " + place_name + " non trouvé", debug_mode) + + # ---------------------- RECUPERATION DU PARCOURS DU DRONE --------------------------- + + #debug_print("Etablissement de connections entre arrondissement :", debug_mode) + #connections = connect_circuits(graph, parcours_drone) + + #output_debug(graph, parcours_drone, connections, debug_mode) + + # ---------------------- PARCOURS - DENEIGEUSE --------------------------- + + # G_partition = generate_quartiers_from_path(parcours_drone, graph, suburb_list=["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"], debug_mode=True) + # partitions = partition(G_partition, 5, debug_mode=True) + + # display_graph(graph, "Test 1", reversed_legend, parcours_drone, None, False) + + start_time_deneigeuse = time.time() + + # TEMP FIX + # parcours_deneigeuse = parcours_drone + + ## Postier chinois qui fonctionne que sur un graph fortement connexe + + verdun = generate_graph("Verdun, Montreal, Canada", debug_mode=debug_mode) + # verdun = prune_verdun(verdun) + parcours_deneigeuse = oriented_cpt(verdun, graph, debug_mode) + + # for elt in partitions: + # drone_edges = [(u, v) for u, v in elt.edges()] + # parcours_deneigeuses.append(process_hierholzer(graph, drone_edges, debug_mode)) + # parcours_deneigeuse = process_hierholzer(graph, parcours_drone, debug_mode) + end_time_deneigeuse = time.time() + + # ---------------------- PARCOURS - DENEIGEUSE --------------------------- + + #display_graph(graph, "Test 2", reversed_legend, parcours_deneigeuse, None, False) + + # ---------------------- EXPORT COST --------------------------- + + # parcours_deneigeuses.append(parcours_deneigeuse) + for elt in ["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"] : + if elt in parcours_drone: + print(elt, len(parcours_drone[elt])) + temp.extend(parcours_drone[elt]) + else: + print("Arrondissement non trouvé:", elt) + print("Total", len(temp)) + parcours_drone = temp + + if "verdun" in place_name.lower(): + export_cost(parcours_drone, parcours_deneigeuses, graph, debug_mode, end_time_deneigeuse - start_time_deneigeuse, end_time_drone - start_time_drone) + else: + print("/!\\ Exportation du coût du parcours désactivée : Seul Verdun est supporté") + + # ---------------------- EXPORT COST --------------------------- + + # ---------------------- EXPORT TO KML --------------------------- + + export_to_kml(parcours_deneigeuses, finalPath, graph, debug_mode) + + # ---------------------- EXPORT TO KML --------------------------- + + return True diff --git a/ero1/src/helper/output_debug.py b/ero1/src/helper/output_debug.py new file mode 100644 index 0000000..bcc521f --- /dev/null +++ b/ero1/src/helper/output_debug.py @@ -0,0 +1,36 @@ +import networkx as nx +import osmnx as ox +from src.generation.graph_generation import generate_graph +from src.helper.prune_maps import prune_verdun +from src.helper.display_graph import display_graph +from src.deneigeuses.directed_cpp import oriented_cpt, chinese_postman_greedy +from src.helper.export_to_kml import export_to_kml + +def output_debug(G, paths, connections, debug_mode): + # debug_print("Calcule de la distance total :", debug_mode) + # distance_drone, unused_distance = distance_total(G, paths, connections) + # debug_print(f"Distance total du drone en kilometre = {distance_drone}", debug_mode) + # debug_print(f"Distance Manqué (routes hors arrondissement) du drone en kilometre = {unused_distance}", debug_mode) + + # distance_opti = 4025.2333363147495 # distance_optimal(G) + # debug_print(f"Distance Optimal du drone en kilometre = {distance_opti}", debug_mode) + + # G_undirected = G.to_undirected() + # distance_ref = 0 + # for u, v, data in G_undirected.edges(data=True): + # distance_ref += data["length"] + # distance_ref /= 1000 + # debug_print(f"Distance total de Montréal en kilomètres = {distance_ref}", debug_mode) + tmp = generate_graph("Verdun, Montréal, Québec, Canada", debug_mode) + print("Graph généré") + tmp = prune_verdun(tmp, debug_mode) + print("Verdun pruné, nb_nodes : ", len(tmp.nodes), ", nb_edges : ", len(tmp.edges())) + print("cpt") + path = chinese_postman_greedy(tmp, debug=True) + print("cpt fini") + display_graph(tmp, "Verdun, Québec, Canada", False, last_call=True, double_sens=True) + export_to_kml(path, [], tmp, debug_mode) + #for edg in tmp.edges: + #print(edg, " ", tmp.get_edge_data(edg[0], edg[1])) + + return True \ No newline at end of file diff --git a/ero1/src/helper/partitions.py b/ero1/src/helper/partitions.py new file mode 100644 index 0000000..94e0739 --- /dev/null +++ b/ero1/src/helper/partitions.py @@ -0,0 +1,129 @@ +import networkx as nx +import osmnx as ox +from src.helper.debug_printer import debug_print +from sklearn.cluster import KMeans, BisectingKMeans + +# j'adore la duplication de code + +# TODO : à commenter et debug, pour l'instant go dodo + + +def display_partitions(G, partitions): + """ + Affiche sur les graphe 'G' (souvent Montreal), chaque partitions d'une couleur unique + Parameters: + G (nx.DiGraph ou MultiDiGraph) : le graphe qui contient les partitions + partitions (list[nx.DiGraph]) : des sous graphes incluent dans 'G' + Return: + void + """ + if len(partitions) > 50: + raise ValueError( + "src/helper/partitions; display_partition: ne peux pas afficher plus de 50 couleurs différentes, la partition est probablement valide mais inaffichable") + + colors = [ + "#e6194b", "#3cb44b", "#ffe119", "#0082c8", "#f58231", "#911eb4", "#46f0f0", "#f032e6", + "#d2f53c", "#fabebe", "#008080", "#e6beff", "#aa6e28", "#fffac8", "#800000", "#aaffc3", + "#808000", "#ffd8b1", "#000080", "#808080", "#FFFFFF", "#000000", "#e41a1c", "#377eb8", + "#4daf4a", "#984ea3", "#ff7f00", "#ffff33", "#a65628", "#f781bf", "#999999", "#66c2a5", + "#fc8d62", "#8da0cb", "#e78ac3", "#a6d854", "#ffd92f", "#e5c494", "#b3b3b3", "#1b9e77", + "#d95f02", "#7570b3", "#e7298a", "#66a61e", "#e6ab02", "#a6761d", "#666666", "#7fc97f", + "#beaed4", "#fdc086" + ] + + associated_color = {} + + i = 0 + for subg in partitions: + for u, v in subg.edges: + if (v, u) in G.edges(keys=False): + associated_color[(v, u)] = colors[i] + associated_color[(u, v)] = colors[i] + + i += 1 + + count = 0 + edge_colors = [] + for u, v in G.edges(keys=False): + if (u, v) in associated_color: + edge_colors.append(associated_color[(u, v)]) + count += 1 + else: + edge_colors.append("grey") + + print(f"{count} arêtes colorées (quartiers + connexions)") + + fig, ax = ox.plot_graph(G, edge_color=edge_colors, + node_size=0, edge_linewidth=1) + + +def partition(G, K, method="KMeans", debug_mode=True): + """ + Partitionne le graphe 'G', en 'K' partitions, selon la méthode 'method', par zone géographique, + G pour le cas des déneigeuses est l'union des graphes de chaque quartiers + Parameters: + G (nx.DiGraph ou MultiDiGraph) : le graphe qui contient les partitions + K (int) : le nombre de partitions voulues + method (string: default = "KMeans") : choix de méthode de partitions, soit "KMeans" soit "BisectingKMeans" + debug_mode (bool: default = True) : activation du mode debug ou pas + Return: + list(nx.DiGraph) : des sous graphes incluent dans 'G', + """ + + # WARNING : G à très certainement été créé à partir de generate_quartier, qui crée un graphe à partir de l'output du drone qui NE contient PAS la data initiale du graphe (length, gps et autre) + + debug_print("debut de l'étape de partitionnement", debug_mode) + + centroids = [] + edges = [] + for u, v, data in G.edges(data=True): + x1, y1 = G.nodes[u]["x"], G.nodes[u]["y"] + x2, y2 = G.nodes[v]["x"], G.nodes[v]["y"] + cx, cy = (x1 + x2)/2, (y1 + y2)/2 + centroids.append([cx, cy]) + edges.append((u, v, data)) + + part = None + if (method == "KMeans"): + part = KMeans(n_clusters=K, random_state=0).fit(centroids) + elif (method == "BisectingKMeans"): + part = BisectingKMeans(n_clusters=K, random_state=0).fit(centroids) + else: + raise ValueError( + "src/helper/partitions; partition: method invalide, choisir entre 'KMeans' et 'BisectingKMeans'") + + labels = part.labels_ + + partitioned_subgraphs = [nx.DiGraph() for _ in range(K)] + for (u, v, data), label in zip(edges, labels): + partitioned_subgraphs[label].add_edge(u, v, **data) + partitioned_subgraphs[label].add_node(u, **G.nodes[u]) + partitioned_subgraphs[label].add_node(v, **G.nodes[v]) + + debug_print("fin de l'étape de partitionnement", debug_mode) + + if (debug_mode): + tot_edges = 0 + tot_weight = 0 + lst_edges = [] + lst_weight = [] + + for partitioned in partitioned_subgraphs: + tot_edges += len(partitioned.edges) + lst_edges.append(len(partitioned.edges)) + tmp_w = 0 + for u, v, data in partitioned.edges(data=True): + tot_weight += data["length"] + tmp_w += data["length"] + lst_weight.append(tmp_w) + + debug_print("List du nb d'edges", debug_mode) + print(lst_edges) + debug_print("List des poids", debug_mode) + print(lst_weight) + debug_print("Nombre total d'edges", debug_mode) + print(tot_edges) + debug_print("Poids total", debug_mode) + print(tot_weight) + + return partitioned_subgraphs diff --git a/ero1/src/helper/prune_maps.py b/ero1/src/helper/prune_maps.py new file mode 100644 index 0000000..6559a77 --- /dev/null +++ b/ero1/src/helper/prune_maps.py @@ -0,0 +1,76 @@ +import networkx as nx +import osmnx as ox +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph + +def prune_verdun(G, debug_mode=False): + """ + Nettoie le graph en retirant les arrêtes problématiques + afin que le graph soit orienté et fortement connexe. + Les Retraits sont pour la plupart minimes et concernent + des routes à sens unique qui vont vers d'autre quartiers. + (Impossibles à parcourir dans le cadre d'un quartier à moins de sortir) + Retourne le graph nettoyé. + Parameters: + G: Graph du quartier de Verdun + debug_mode: [OPTIONEL | DEFAUT = False] + """ + debug_print("Nettoyage du graph Verdun", debug_mode) + + G.remove_edge(32764413, 248511841) + G.remove_edge(615028247, 615028248) + G.remove_edge(615028248, 4503982628) + G.remove_edge(615035051, 615028249) + G.remove_edge(4503982628, 615035051) + G.remove_edge(5342978418, 615028328) + + G.remove_node(8640521401) + G.remove_node(32764413) + G.remove_node(248511841) + G.remove_node(615028247) + G.remove_node(615028248) + G.remove_node(4503982628) + G.remove_node(615035051) + G.remove_node(615028328) + + debug_print("Verdun nettoyé! Supprimé 8 arcs et 8 noeuds", debug_mode) + + return G + +def prune_outremont(G, debug_mode=False): + """ + Nettoie le graph en retirant les arrêtes problématiques + afin que le graph soit orienté et fortement connexe. + Les Retraits sont pour la plupart minimes et concernent + des routes à sens unique qui vont vers d'autre quartiers. + (Impossibles à parcourir dans le cadre d'un quartier à moins de sortir) + Retourne le graph nettoyé. + Parameters: + G: Graph du quartier d'Outremont + debug_mode: [OPTIONEL | DEFAUT = False] + """ + debug_print("Nettoyage du graph Outremont...", debug_mode) + + # Avenue Willowdale + G.remove_node(209387127) + G.remove_node(3165394666) + G.remove_node(209387136) + G.remove_node(209387140) + G.remove_node(209387103) + G.remove_node(209387147) + + # Avenue Gare de Triage + G.remove_node(5412399376) + + # Avenue Durocher/Atlantic + G.remove_node(437865622) + G.remove_node(12844070435) + G.remove_node(5412399379) + + # Sortie autoroute Avenue Davaar et Rockland + G.remove_node(213955306) + G.remove_node(213955379) + + return G + +# TESTINGGGGGG diff --git a/ero1/src/tests/snow_testing.py b/ero1/src/tests/snow_testing.py new file mode 100644 index 0000000..d8e21d5 --- /dev/null +++ b/ero1/src/tests/snow_testing.py @@ -0,0 +1,17 @@ +import parameters as params + +def test_snow(G): + """ + Renvoie le pourcentage (nombre en 0 et 1) de route qui ont plus de neige que params.SNOW_TRESHOLD + Parameters: + G (voir quel type on veut utiliser): le graphe des routes + Returns: + float: le ratio (nb de route avec plus de neige que params.SNOW_THRESHOLD)/(nb de routes) + """ + qty = 0 + edges = list(G.edges(keys=True, data=True)) + for u, v, k, data in edges: + if (data['snow'] >= params.SNOW_THRESHOLD): + qty += 1 + + return qty/len(edges) \ No newline at end of file diff --git a/ero1/start_dev.py b/ero1/start_dev.py new file mode 100644 index 0000000..464766c --- /dev/null +++ b/ero1/start_dev.py @@ -0,0 +1,42 @@ +# This file contains the main logic and execution flow, the goal of this file +# is to create the graphs and call our functions on it +import parameters as params +import sys + +from src.helper.debug_printer import debug_print +from src.helper.main_parcours import main_parcours + + +# variables globales +debug_mode = False +reversed_legend = False +routes_mode = False + +# Démarrage du programme +# Si le mode debug est activé, on affiche les messages de debug +# on affiche à la fin le graphe généré +if __name__ == "__main__": + if "-d" in sys.argv: # mode debug + debug_mode = True + sys.argv.remove("-d") + if "-rl" in sys.argv: # legende inversée (gauche par défaut) + reversed_legend = True + sys.argv.remove("-rl") + if "-r" in sys.argv: # mode routes + routes_mode = True + sys.argv.remove("-r") + + debug_print("Debug mode : activé", debug_mode) + + if len(sys.argv) > 1: + PLACE_NAME = sys.argv[1] + else: + PLACE_NAME = params.DEFAULT_PLACE_NAME + + debug_print("Arrondissement selectionné : " + PLACE_NAME, debug_mode) + + debug_print("==============================================", debug_mode) + + main_parcours(debug_mode, PLACE_NAME, reversed_legend) + + debug_print("==============================================", debug_mode) \ No newline at end of file diff --git a/ero1/temp/README.md b/ero1/temp/README.md new file mode 100644 index 0000000..f729041 --- /dev/null +++ b/ero1/temp/README.md @@ -0,0 +1,18 @@ +# Dossier Temporaire + +Ce dossier contient les fichiers temporaires générés pendant l'exécution du programme. + +## Description de chaque fichier + +- `debug_graph.png` : (fichier non généré lors de la démo) + - Image générée à la fin du processus de la carte choisie. + +- `parcours_X_deneigeuses.kml` : + - Contient les itinéraires des déneigeuses et du drone + - Peut être ouvert dans Google My Maps (https://www.google.com/maps/d/u/0/) ou tout autre logiciel supportant le KML + - Affiche les distances et profondeurs de neige de chaque déneigeuse + +- `export_cost.txt` : (fichier non généré lors de la démo) + - Contient toutes les informations nécessaires au calcul des coûts + - Peut être importé directement sur Google Sheets + - https://docs.google.com/spreadsheets/d/1yXdxhq94XTg9V4pT8E_oUQVrLPnXS4NRDt-2gpsedeI/edit?usp=sharing -- cgit v1.2.3