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