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)[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]

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