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]

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]

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

Calcule la distance de Haversine Haversine formula

teachpyx.practice.rues_paris.distance_paris(lat1: float, lng1: float, lat2: float, lng2: float) → float

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)

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

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

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:

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

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

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

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)