teachpyx.practice.rues_paris#

teachpyx.practice.rues_paris.bellman(edges: List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]], max_iter: int = 20, allow: Callable | None = None, init: Dict[Tuple[int, int], float] | None = None, verbose: bool = False) Dict[Tuple[int, int], float][source][source]#

Implémente l’algorithme de Bellman-Ford.

Paramètres:
  • edges – liste de tuples (noeud 1, noeud 2, ?, ?, ?, poids)

  • max_iter – nombre d’itérations maximal

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

  • verbose – afficher le progrès

Renvoie:

listes des arcs et des distances calculées

teachpyx.practice.rues_paris.connected_components(edges: List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]]) Dict[int, int][source][source]#

Computes the connected components.

Paramètres:

edges – edges

Renvoie:

dictionary { vertex : id of connected components }

teachpyx.practice.rues_paris.distance_haversine(lat1: float, lng1: float, lat2: float, lng2: float) float[source][source]#

Calcule la distance de Haversine Haversine formula

teachpyx.practice.rues_paris.distance_paris(lat1: float, lng1: float, lat2: float, lng2: float) float[source][source]#

Distance euclidienne approchant la distance de Haversine (uniquement pour Paris).

teachpyx.practice.rues_paris.euler_path(edges: List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]], added_edges)[source][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)

teachpyx.practice.rues_paris.eulerien_extension(edges: ~typing.List[~typing.Tuple[int, int, int, ~typing.Tuple[float, float], ~typing.Tuple[float, float], float]], max_iter: int = 20, alpha: float = 0.5, distance: ~typing.Callable = <function distance_haversine>, verbose: bool = False) List[Tuple[int, int]][source][source]#

Construit une extension eulérienne d’un graphe.

Paramètres:
  • edges – liste des arcs

  • max_iter – nombre d’itérations pour la fonction @see fn bellman

  • alpha – coefficient multiplicatif de max_segment

  • distance – la distance de Haversine est beaucoup trop longue sur de grands graphes, on peut la changer

  • verbose – afficher l’avancement

Renvoie:

added edges

teachpyx.practice.rues_paris.get_data(url: str = 'https://github.com/sdpython/teachpyx/raw/main/_data/paris_54000.zip', dest: str = '.', timeout: int = 10, verbose: bool = False, keep: int = -1) List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]][source][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:
  • url – location of the data

  • dest – répertoire dans lequel télécharger les données

  • timeout – timeout (seconds) when estabishing the connection

  • verbose – affiche le progrès

  • keep – garde tout si la valeur est -1, sinon garde les 1000 premières rues, ces rues sont choisies de façon à construire un ensemble connexe

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

teachpyx.practice.rues_paris.graph_degree(edges: List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]]) Dict[Tuple[int, int], int][source][source]#

Calcul le degré de chaque noeud.

Paramètres:

edges – list des arcs

Renvoie:

degrés

teachpyx.practice.rues_paris.kruskal(edges: List[Tuple[int, int, int, Tuple[float, float], Tuple[float, float], float]], extension: Dict[Tuple[int, int], float]) List[Tuple[int, int]][source][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

Renvoie:

added_edges

teachpyx.practice.rues_paris.possible_edges(edges: ~typing.List[~typing.Tuple[int, int, int, ~typing.Tuple[float, float], ~typing.Tuple[float, float], float]], threshold: float, distance: ~typing.Callable = <function distance_haversine>)[source][source]#

Construit la liste de tous les arcs possibles en filtrant sur la distance à vol d’oiseau.

Paramètres:
  • edges – list des arcs

  • threshold – seuil au-delà duquel deux noeuds ne seront pas connectés

  • distance – la distance de Haversine est beaucoup trop longue sur de grands graphes, on peut la changer

Renvoie:

arcs possibles (symétrique –> incluant edges)