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

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)