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.

source on GitHub

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 j \rightarrow k est …
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.

source on GitHub

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

source on GitHub

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

source on GitHub

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

source on GitHub

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 }

source on GitHub

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

source on GitHub

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

source on GitHub

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)

source on GitHub

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

source on GitHub

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 j \rightarrow k est présent, j \rightarrow k 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

source on GitHub

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

source on GitHub

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

source on GitHub

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)

source on GitHub