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

Construit 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)#

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)#

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)#

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)#

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)#

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)#

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)#

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>)#

Construit 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>)#

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)#

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)#

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>)#

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