module special.rues_paris
¶
Short summary¶
module ensae_teaching_cs.special.rues_paris
Code implémentant la première solution proposée à Parcourir les rues de Paris.
Functions¶
function | truncated documentation |
---|---|
_delete_edge |
Removes an edge from the graph. |
_explore_path |
Explores an eulerian path, remove used edges from edges_from. |
bellman |
Implémente l’algorithme de Bellman-Ford. |
connected_components |
Computes the connected components. |
distance_haversine |
Calcule la distance de Haversine Haversine formula |
distance_paris |
Distance euclidienne approchant la distance de Haversine (uniquement pour Paris). |
euler_path |
Computes an eulerian path. We assume every vertex has an even degree. |
eulerien_extension |
Contruit une extension eulérienne d’un graphe. |
get_data |
Retourne les données des rues de Paris. On suppose que les arcs sont uniques et qu’il si |
graph_degree |
calcul le degré de chaque noeud |
kruskal |
Applique l’algorithme de Kruskal (ou ressemblant) pour choisir les arcs à ajouter. |
possible_edges |
Construit la liste de tous les arcs possibles en filtrant sur la distance à vol d’oiseau. |
Documentation¶
Code implémentant la première solution proposée à Parcourir les rues de Paris.
-
ensae_teaching_cs.special.rues_paris.
_delete_edge
(edges_from, n, to)[source]¶ Removes an edge from the graph.
Paramètres: - edges_from – structure which contains the edges (will be modified)
- n – first vertex
- to – second vertex
Renvoie: the edge
-
ensae_teaching_cs.special.rues_paris.
_explore_path
(edges_from, begin)[source]¶ Explores an eulerian path, remove used edges from edges_from.
Paramètres: - edges_from – structure which contains the edges (will be modified)
- begin – first vertex to use
Renvoie: path
-
ensae_teaching_cs.special.rues_paris.
bellman
(edges, iter=20, fLOG=<function noLOG>, allow=None, init=None)[source]¶ Implémente l’algorithme de Bellman-Ford.
Paramètres: - edges – liste de tuples (noeud 1, noeud 2, ?, ?, ?, poids)
- iter – nombre d’itérations maximal
- fLOG – logging function
- allow – fonction déterminant si l’algorithme doit envisager cette liaison ou pas
- init – initialisation (pour pouvoir continuer après une première exécution)
Renvoie: listes des arcs et des distances calculées
-
ensae_teaching_cs.special.rues_paris.
connected_components
(edges)[source]¶ Computes the connected components.
Paramètres: edges – edges Renvoie: dictionary { vertex : id of connected components }
-
ensae_teaching_cs.special.rues_paris.
distance_haversine
(lat1, lng1, lat2, lng2)[source]¶ Calcule la distance de Haversine Haversine formula
Paramètres: - lat1 – lattitude
- lng1 – longitude
- lat2 – lattitude
- lng2 – longitude
Renvoie: distance
-
ensae_teaching_cs.special.rues_paris.
distance_paris
(lat1, lng1, lat2, lng2)[source]¶ Distance euclidienne approchant la distance de Haversine (uniquement pour Paris).
Paramètres: - lat1 – lattitude
- lng1 – longitude
- lat2 – lattitude
- lng2 – longitude
Renvoie: distance
-
ensae_teaching_cs.special.rues_paris.
euler_path
(edges, added_edges)[source]¶ Computes an eulerian path. We assume every vertex has an even degree.
Paramètres: - edges – initial edges
- added_edges – added edges
Renvoie: path, list of (vertex,edge)
-
ensae_teaching_cs.special.rues_paris.
eulerien_extension
(edges, iter=20, fLOG=<function noLOG>, alpha=0.5, distance=<function distance_haversine>)[source]¶ Contruit une extension eulérienne d’un graphe.
Paramètres: - edges – liste des arcs
- iter – nombre d’itérations pour la fonction
bellman
- fLOG – logging function
- alpha – coefficient multiplicatif de
max_segment
- distance – la distance de Haversine est beaucoup trop longue sur de grands graphes, on peut la changer
Renvoie: added edges
-
ensae_teaching_cs.special.rues_paris.
get_data
(whereTo='.', timeout=None, fLOG=<function noLOG>)[source]¶ Retourne les données des rues de Paris. On suppose que les arcs sont uniques et qu’il si
est présent,
ne l’est pas. Ceci est vérifié par un test.
Paramètres: - whereTo – répertoire dans lequel télécharger les données
- timeout – timeout (seconds) when estabishing the connection
- fLOG – fonction de logging
Renvoie: liste d’arcs
Un arc est défini par un 6-uple contenant les informations suivantes :
- v1: indice du premier noeud
- v2: indice du second noeud
- ways: sens unique ou deux sens
- p1: coordonnées du noeud 1
- p2: coordonnées du noeud 2
- d: distance
-
ensae_teaching_cs.special.rues_paris.
graph_degree
(edges)[source]¶ calcul le degré de chaque noeud
Paramètres: edges – list des arcs (voir ci-dessus) Renvoie: degrés
-
ensae_teaching_cs.special.rues_paris.
kruskal
(edges, extension, fLOG=None)[source]¶ Applique l’algorithme de Kruskal (ou ressemblant) pour choisir les arcs à ajouter.
Paramètres: - edges – listes des arcs
- extension – résultat de l’algorithme de Bellman
- fLOG – logging function
Renvoie: added_edges
-
ensae_teaching_cs.special.rues_paris.
possible_edges
(edges, threshold, fLOG=None, distance=<function distance_haversine>)[source]¶ Construit la liste de tous les arcs possibles en filtrant sur la distance à vol d’oiseau.
Paramètres: - edges – liste des arcs
- threshold – seuil au-delà duquel deux noeuds ne seront pas connectés
- fLOG – logging function
- distance – la distance de Haversine est beaucoup trop longue sur de grands graphes, on peut la changer
Renvoie: arcs possibles (symétrique –> incluant edges)