metro.py

#!/usr/bin/env python2.6
#coding=utf8

import re

COLOR_MAPPING = {
	1: 'gold',
	2: 'blue',
	3: 'gold4',
	30: 'deepskyblue', # Ligne 3b
	4: 'hotpink3',
	5: 'orange',
	6: 'springgreen2',
	7: 'pink1',
	8: 'darkorchid2',
	9: 'yellow3',
	11: 'tan4',
	12: 'springgreen4',
	13: 'skyblue',
	14: 'indigo',
}

def slugify(name):
	chars = u'abcdefghijklmnopqrstuvwxyz'
	special_chars = {
		u'é': u'e', u'è': u'e', u'â': u'a',
		u'ê': u'e', u'î': u'i', u'ô': u'o',
		u'ç': u'c', u'ü': u'u', u'—': u' '
	}
	sluged_string = ''
	for char in name.lower():
		if char in chars:
			sluged_string += char
		elif char in special_chars:
			sluged_string += special_chars[char]
	return sluged_string


class Node(object):
	def __init__(self, name):
		self.name = name
		self.reset()

	def reset(self):
		self.previous = None
		self.traveled = float('inf')
		self.line_nb = None
	
	def __repr__(self):
		return '<Node: %s (%s)>' % (self.name.encode('utf8'), self.traveled)
	
class Edge(object):
	def __init__(self, node1, node2, weight, line_nb):
		self.node1 = node1
		self.node2 = node2
		self.weight = weight
		self.line_nb = line_nb
	
	def give_other_node(self, node):
		'''Return the other node'''
		if node is self.node1:
			return self.node2
		elif node is self.node2:
			return self.node1
	
	def __repr__(self):
		return '<Edge: %s -%s- %s>' % (self.node1.name, self.weight, self.node2.name)

class Graph(object):

	regex_import = re.compile(r'(?P<line_nb>\d+): "(?P<station1>.+?)" -(?P<weight>\d+)- "(?P<station2>.+?)"')
	
	def __init__(self):
		self.nodes = []
		self.edges = []
		self.edge_start = None
	
	def add_node(self, node):
		if not node in self.nodes:
			self.nodes.append(node)
	
	def add_edge(self, edge):
		if not edge in self.edges:
			self.edges.append(edge)

	def search_station(self, name):
		selection = [n for n in self.nodes if slugify(name.decode('utf8')) in slugify(n.name)]
		if len(selection) == 1:
			return [selection[0]]
		elif not selection:
			return []
		for node in selection:
			if slugify(name.decode('utf8')) == slugify(node.name):
				return [node]
		else:
			return selection

	def import_from_file(self, filename):
		
		stations = {}
		edges = []
		
		for line in open(filename, 'r'):
			m = self.regex_import.match(line)
			if m:
				line_nb = int(m.group('line_nb'))
				station1 = m.group('station1').decode('utf8')
				weight = int(m.group('weight'))
				station2 = m.group('station2').decode('utf8')
				
				if not station1 in stations:
					stations[station1] = Node(station1)
				if not station2 in stations:
					stations[station2] = Node(station2)
				
				edges.append(Edge(stations[station1], stations[station2], weight, line_nb))
		
		self.edges = edges
		self.nodes = stations.values()

	def give_connected_edges(self, node):
		edges = []
		for edge in self.edges:
			if node is edge.node1 or node is edge.node2:
				edges.append(edge)
		
		return edges

	def init_dijkstra(self, node_start):
		for node in self.nodes:
			node.reset()
		
		self.node_start = node_start
		
		self.node_start.traveled = 0
		nodes_not_traveled = list(self.nodes)
		
		while nodes_not_traveled:
			n1 = min(nodes_not_traveled, key=lambda x: x.traveled)
			nodes_not_traveled.remove(n1)
						
			for edge in self.give_connected_edges(n1):
				if n1.line_nb and n1.line_nb != edge.line_nb:
					changing_malus = 300
				else:
					changing_malus = 0
				n2 = edge.give_other_node(n1)
				if n2.traveled > n1.traveled + edge.weight + changing_malus:
					n2.traveled = n1.traveled + edge.weight + changing_malus
					n2.previous = n1
					n2.line_nb = edge.line_nb
	
	def best_path_dijkstra(self, node_end):
		if self.node_start not in self.nodes:
			raise ValueError('Dijkstra not initialized')
		path = []
		current_node = node_end
		while current_node is not self.edge_start:
			path.insert(0, current_node)
			current_node = current_node.previous
		
		return path
	
	def export_graphviz(self):
		lines = ['graph {']
		for node in self.nodes:
			lines.append('	"%s";' % node.name)
		for edge in self.edges:
			lines.append('	"%s" -- "%s" [label="%s", color="%s"];' % (edge.node1.name, edge.node2.name, edge.weight, COLOR_MAPPING[edge.line_nb]))
		lines.append('}')
		
		return '\n'.join(lines)
		
			
if __name__ == '__main__':
	
	g = Graph()
	g.import_from_file('paris.gph')
	
	print 'Bienvenue dans le programme de calcul d\'itinéraires'
	print
	print 'Entrez une station de départ'
	while True:
		station_start = raw_input('>')
		stations_found = g.search_station(station_start)
		if not len(stations_found):
			print 'Aucune station trouvée, recommencez.'
			continue
		elif len(stations_found) == 1:
			station_start = stations_found[0]
			break
		else:
			print 'Plusieurs stations trouvées :'
			for i, st in enumerate(stations_found):
				print '  - %s : %s' % (i+1, st.name.encode('utf8'))
			print
			print 'Entrez le numéro de la station voulue :'
			while True:
				nb_station = input('>')-1
				if 0 < nb_station <= len(stations_found):
					break
				else:
					print 'Mauvais numéro, recommencez.'
			station_start = stations_found[nb_station]
			break
	
	print 'Station %s selectionnée pour le départ.' % station_start.name.encode('utf8')
	print
	print 'Entrez une station d\'arrivée'
	while True:
		station_end = raw_input('>')
		stations_found = g.search_station(station_end)
		if not len(stations_found):
			print 'Aucune station trouvée, recommencez.'
			continue
		elif len(stations_found) == 1:
			station_end = stations_found[0]
			break
		else:
			print 'Plusieurs stations trouvées :'
			for i, st in enumerate(stations_found):
				print '  - %s : %s' % (i+1, st.name.encode('utf8'))
			print
			print 'Entrez le numéro de la station voulue :'
			while True:
				nb_station = input('>')-1
				if 0 <= nb_station <= len(stations_found):
					break
				else:
					print 'Mauvais numéro, recommencez.'
			station_end = stations_found[nb_station]
			break

	print 'Station %s selectionnée pour l\'arrivée.' % station_end.name.encode('utf8')

	print
	print 'Itinéraire :'
	print '============'
	print
	g.init_dijkstra(station_start)
	
	path = g.best_path_dijkstra(station_end)
	
	last_line = 0
	last_sta = None
	
	for n in path:
		if not n.line_nb:
			print ' - Entrez dans la station %s et prenez le métro (sans blague)' % n.name.encode('utf8')
		elif last_line and n.line_nb != last_line:
			print ' - Changez à %s et prendre la ligne %s' % (last_sta.name.encode('utf8'), n.line_nb)
		last_line = n.line_nb
		last_sta = n
	print ' - Arrivée à %s (trop bien \o)' % n.name.encode('utf8')

paris.gph

1: "Château de Vincennes" -100- "Bérault"
1: "Saint-Mandé-Tourelle" -100- "Bérault"
1: "Saint-Mandé-Tourelle" -100- "Porte de Vincennes"
1: "Porte de Vincennes" -100- "Nation"
1: "Reuilly — Diderot" -100- "Nation"
1: "Reuilly — Diderot" -100- "Gare de Lyon"
1: "Gare de Lyon" -100- "Bastille"
1: "Bastille" -100- "Saint-Paul"
1: "Saint-Paul" -100- "Hôtel de Ville"
1: "Hôtel de Ville" -100- "Châtelet"
1: "Châtelet" -100- "Louvre-Rivoli"
1: "Louvre-Rivoli" -100- "Palais Royal-Musée du Louvre"
1: "Palais Royal-Musée du Louvre" -100- "Tuileries"
1: "Tuileries" -100- "Concorde"
1: "Concorde" -100- "Champs-Élysées-Clémenceau"
1: "Champs-Élysées-Clémenceau" -100- "Franklin D.Roosevelt"
1: "Franklin D.Roosevelt" -100- "Georges V"
1: "Georges V" -100- "Charles de Gaulle — Étoile"
1: "Charles de Gaulle — Étoile" -100- "Argentine"
1: "Argentine" -100- "Porte Maillot"
1: "Porte Maillot" -100- "Les Sablons"
1: "Les Sablons" -100- "Pont de Neuilly"
1: "Pont de Neuilly" -100- "Esplanade de la Défense"
1: "Esplanade de la Défense" -100- "La Défense"
2: "Porte Dauphine" -100- "Victor Hugo"
2: "Victor Hugo" -100- "Charles de Gaulle — Étoile"
2: "Charles de Gaulle — Étoile" -100- "Ternes"
2: "Ternes" -100- "Courcelles"
2: "Courcelles" -100- "Monceau"
2: "Monceau" -100- "Villiers"
2: "Villiers" -100- "Rome"
2: "Rome" -100- "Place de Clichy"
2: "Place de Clichy" -100- "Blanche"
2: "Blanche" -100- "Pigalle"
2: "Pigalle" -100- "Anvers"
2: "Anvers" -100- "Barbès — Rochechouart"
2: "Barbès — Rochechouart" -100- "La Chapelle"
2: "La Chapelle" -100- "Stalingrad"
2: "Stalingrad" -100- "Jaurès"
2: "Jaurès" -100- "Colonel Fabien"
2: "Colonel Fabien" -100- "Belleville"
2: "Belleville" -100- "Couronnes"
2: "Couronnes" -100- "Ménilmontant"
2: "Ménilmontant" -100- "Père Lachaise"
2: "Père Lachaise" -100- "Philippe Auguste"
2: "Philippe Auguste" -100- "Alexandre Dumas"
2: "Alexandre Dumas" -100- "Avron"
2: "Avron" -100- "Nation"
3: "Pont de Levallois — Bécon" -100- "Anatole France"
3: "Anatole France" -100- "Louise Michel"
3: "Louise Michel" -100- "Porte de Champerret"
3: "Porte de Champerret" -100- "Pereire"
3: "Pereire" -100- "Wagram"
3: "Wagram" -100- "Malesherbes"
3: "Malesherbes" -100- "Villiers"
3: "Villiers" -100- "Europe"
3: "Europe" -100- "Saint-Lazare"
3: "Saint-Lazare" -100- "Havre — Caumartin"
3: "Havre — Caumartin" -100- "Opéra"
3: "Opéra" -100- "Quatre-Septembre"
3: "Quatre-Septembre" -100- "Bourse"
3: "Bourse" -100- "Sentier"
3: "Sentier" -100- "Réaumur — Sébastopol"
3: "Réaumur — Sébastopol" -100- "Arts et Métiers"
3: "Arts et Métiers" -100- "Temple"
3: "Temple" -100- "République"
3: "République" -100- "Parmentier"
3: "Parmentier" -100- "Rue Saint-Maur"
3: "Rue Saint-Maur" -100- "Père Lachaise"
3: "Père Lachaise" -100- "Gambetta"
3: "Gambetta" -100- "Porte de Bagnolet"
3: "Porte de Bagnolet" -100- "Gallieni"
30: "Gambetta" -100- "Pelleport"
30: "Pelleport" -100- "Saint-Fargeau"
30: "Saint-Fargeau" -100- "Porte des Lilas"



8: "Balard" -100- "Lourmel"
8: "Lourmel" -100- "Boucicaut"
8: "Boucicaut" -100- "Félix Faure"
8: "Félix Faure" -100- "Commerce"
8: "Commerce" -100- "La Motte-Picquet — Grenelle"
8: "La Motte-Picquet — Grenelle" -100- "École Militaire"
8: "École Militaire" -100- "La Tour-Maubourg"
8: "La Tour-Maubourg" -100- "Invalides"
8: "Invalides" -100- "Concorde"
8: "Concorde" -100- "Madeleine"
8: "Madeleine" -100- "Opéra"
8: "Opéra" -100- "Richelieu — Drouot"
8: "Richelieu — Drouot" -100- "Grands Boulevards"
8: "Grands Boulevards" -100- "Bonne Nouvelle"
8: "Bonne Nouvelle" -100- "Strasbourg — Saint-Denis"
8: "Strasbourg — Saint-Denis" -100- "République"
8: "République" -100- "Filles du Calvaire"
8: "Filles du Calvaire" -100- "Saint-Sébastien — Froissart"
8: "Saint-Sébastien — Froissart" -100- "Chemin Vert"
8: "Chemin Vert" -100- "Bastille"
8: "Bastille" -100- "Ledru-Rollin"
8: "Ledru-Rollin" -100- "Faidherbe — Chaligny"
8: "Faidherbe — Chaligny" -100- "Reuilly — Diderot"
8: "Reuilly — Diderot" -100- "Montgallet"
8: "Montgallet" -100- "Daumesnil"
8: "Daumesnil" -100- "Michel Bizot"
8: "Michel Bizot" -100- "Porte Dorée"
8: "Porte Dorée" -100- "Porte de Charenton"
8: "Porte de Charenton" -100- "Liberté"
8: "Liberté" -100- "Charenton — Écoles"
8: "Charenton — Écoles" -100- "École Vétérinaire de Maisons-Alfort"
8: "École Vétérinaire de Maisons-Alfort" -100- "Maisons-Alfort — Stade"
8: "Maisons-Alfort — Stade" -100- "Maisons-Alfort — Les Juilliottes"
8: "Maisons-Alfort — Les Juilliottes" -100- "Créteil — L'Échat"
8: "Créteil — L'Échat" -100- "Créteil — Université"
8: "Créteil — Université" -100- "Créteil — Préfecture"



4: "Porte de Clignancourt" -100- "Simplon"
4: "Simplon" -100- "Marcadet — Poissonniers"
4: "Marcadet — Poissonniers" -100- "Château Rouge"
4: "Château Rouge" -100- "Barbès — Rochechouart"
4: "Barbès — Rochechouart" -100- "Gare du Nord"
4: "Gare du Nord" -100- "Gare de l'Est"
4: "Gare de l'Est" -100- "Château d'Eau"
4: "Château d'Eau" -100- "Strasbourg — Saint-Denis"
4: "Strasbourg — Saint-Denis" -100- "Réaumur — Sébastopol"
4: "Réaumur — Sébastopol" -100- "Étienne Marcel"
4: "Étienne Marcel" -100- "Les Halles"
4: "Les Halles" -100- "Châtelet"
4: "Châtelet" -100- "Cité"
4: "Cité" -100- "Saint-Michel"
4: "Saint-Michel" -100- "Odéon"
4: "Odéon" -100- "Saint-Germain-des-Prés"
4: "Saint-Germain-des-Prés" -100- "Saint-Sulpice"
4: "Saint-Sulpice" -100- "Saint-Placide"
4: "Saint-Placide" -100- "Montparnasse — Bienvenüe"
4: "Montparnasse — Bienvenüe" -100- "Vavin"
4: "Vavin" -100- "Raspail"
4: "Raspail" -100- "Denfert-Rochereau"
4: "Denfert-Rochereau" -100- "Mouton-Duvernet"
4: "Mouton-Duvernet" -100- "Alésia"
4: "Alésia" -100- "Porte d'Orléans"
5: "Bobigny — Pablo Picasso" -100- "Bobigny — Pantin — Raymond Queneau"
5: "Bobigny — Pantin — Raymond Queneau" -100- "Église de Pantin"
5: "Église de Pantin" -100- "Hoche"
5: "Hoche" -100- "Porte de Pantin"
5: "Porte de Pantin" -100- "Ourcq"
5: "Ourcq" -100- "Laumière"
5: "Laumière" -100- "Jaurès"
5: "Jaurès" -100- "Stalingrad"
5: "Stalingrad" -100- "Gare du Nord"
5: "Gare du Nord" -100- "Gare de l'Est"
5: "Gare de l'Est" -100- "Jacques Bonsergent"
5: "Jacques Bonsergent" -100- "République"
5: "République" -100- "Oberkampf"
5: "Oberkampf" -100- "Richard-Lenoir"
5: "Richard-Lenoir" -100- "Bréguet — Sabin"
5: "Bréguet — Sabin" -100- "Bastille"
5: "Bastille" -100- "Quai de la Rapée"
5: "Quai de la Rapée" -100- "Gare d'Austerlitz"
5: "Gare d'Austerlitz" -100- "Saint-Marcel"
5: "Saint-Marcel" -100- "Campo-Formio"
5: "Campo-Formio" -100- "Place d'Italie"
6: "Charles de Gaulle — Étoile" -100- "Kléber"
6: "Kléber" -100- "Boissière"
6: "Boissière" -100- "Trocadéro"
6: "Trocadéro" -100- "Passy"
6: "Passy" -100- "Bir-Hakeim"
6: "Bir-Hakeim" -100- "Dupleix"
6: "Dupleix" -100- "La Motte-Picquet — Grenelle"
6: "La Motte-Picquet — Grenelle" -100- "Cambronne"
6: "Cambronne" -100- "Sèvres — Lecourbe"
6: "Sèvres — Lecourbe" -100- "Pasteur"
6: "Pasteur" -100- "Montparnasse — Bienvenüe"
6: "Montparnasse — Bienvenüe" -100- "Edgar Quinet"
6: "Edgar Quinet" -100- "Raspail"
6: "Raspail" -100- "Denfert-Rochereau"
6: "Denfert-Rochereau" -100- "Saint-Jacques"
6: "Saint-Jacques" -100- "Glacière"
6: "Glacière" -100- "Corvisart"
6: "Corvisart" -100- "Place d'Italie"
6: "Place d'Italie" -100- "Nationale"
6: "Nationale" -100- "Chevaleret"
6: "Chevaleret" -100- "Quai de la Gare"
6: "Quai de la Gare" -100- "Bercy"
6: "Bercy" -100- "Dugommier"
6: "Dugommier" -100- "Daumesnil"
6: "Daumesnil" -100- "Bel-Air"
6: "Bel-Air" -100- "Picpus"
6: "Picpus" -100- "Nation"
7: "La Courneuve — 8 Mai 1945" -100- "Fort d'Aubervilliers"
7: "Fort d'Aubervilliers" -100- "Aubervilliers — Pantin — Quatre Chemins"
7: "Aubervilliers — Pantin — Quatre Chemins" -100- "Porte de la Villette"
7: "Porte de la Villette" -100- "Corentin Cariou"
7: "Corentin Cariou" -100- "Crimée"
7: "Crimée" -100- "Riquet"
7: "Riquet" -100- "Stalingrad"
7: "Stalingrad" -100- "Louis Blanc"
7: "Louis Blanc" -100- "Château-Landon"
7: "Château-Landon" -100- "Gare de l'Est"
7: "Gare de l'Est" -100- "Poissonnière"
7: "Poissonnière" -100- "Cadet"
7: "Cadet" -100- "Le Peletier"
7: "Le Peletier" -100- "Chaussée d'Antin — La Fayette"
7: "Chaussée d'Antin — La Fayette" -100- "Opéra"
7: "Opéra" -100- "Pyramides"
7: "Pyramides" -100- "Palais Royal — Musée du Louvre"
7: "Palais Royal — Musée du Louvre" -100- "Pont Neuf"
7: "Pont Neuf" -100- "Châtelet"
7: "Châtelet" -100- "Pont Marie"
7: "Pont Marie" -100- "Sully — Morland"
7: "Sully — Morland" -100- "Jussieu"
7: "Jussieu" -100- "Place Monge"
7: "Place Monge" -100- "Censier — Daubenton"
7: "Censier — Daubenton" -100- "Les Gobelins"
7: "Les Gobelins" -100- "Place d'Italie"
7: "Place d'Italie" -100- "Tolbiac"
7: "Tolbiac" -100- "Maison Blanche"
7: "Maison Blanche" -100- "Le Kremlin-Bicêtre"
7: "Le Kremlin-Bicêtre" -100- "Villejuif — Léo Lagrange"
7: "Villejuif — Léo Lagrange" -100- "Villejuif — Paul Vaillant-Couturier"
7: "Villejuif — Paul Vaillant-Couturier" -100- "Villejuif — Louis Aragon"
7: "Maison Blanche" -100- "Porte d'Italie"
7: "Porte d'Italie" -100- "Porte de Choisy"
7: "Porte de Choisy" -100- "Porte d'Ivry"
7: "Porte d'Ivry" -100- "Pierre et Marie Curie"
7: "Pierre et Marie Curie" -100- "Mairie d'Ivry"
9: "Pont de Sèvres" -100- "Billancourt"
9: "Billancourt" -100- "Marcel Sembat"
9: "Marcel Sembat" -100- "Porte de Saint-Cloud"
9: "Porte de Saint-Cloud" -100- "Exelmans"
9: "Exelmans" -100- "Michel-Ange — Molitor"
9: "Michel-Ange — Molitor" -100- "Michel-Ange — Auteuil"
9: "Michel-Ange — Auteuil" -100- "Jasmin"
9: "Jasmin" -100- "Ranelagh"
9: "Ranelagh" -100- "La Muette"
9: "La Muette" -100- "Rue de la Pompe"
9: "Rue de la Pompe" -100- "Trocadéro"
9: "Trocadéro" -100- "Iéna"
9: "Iéna" -100- "Alma — Marceau"
9: "Alma — Marceau" -100- "Franklin D. Roosevelt"
9: "Franklin D. Roosevelt" -100- "Saint-Philippe du Roule"
9: "Saint-Philippe du Roule" -100- "Miromesnil"
9: "Miromesnil" -100- "Saint-Augustin"
9: "Saint-Augustin" -100- "Havre — Caumartin"
9: "Havre — Caumartin" -100- "Chaussée d'Antin — La Fayette"
9: "Chaussée d'Antin — La Fayette" -100- "Richelieu — Drouot"
9: "Richelieu — Drouot" -100- "Grands Boulevards"
9: "Grands Boulevards" -100- "Bonne Nouvelle"
9: "Bonne Nouvelle" -100- "Strasbourg — Saint-Denis"
9: "Strasbourg — Saint-Denis" -100- "République"
9: "République" -100- "Oberkampf"
9: "Oberkampf" -100- "Saint-Ambroise"
9: "Saint-Ambroise" -100- "Voltaire"
9: "Voltaire" -100- "Charonne"
9: "Charonne" -100- "Rue des Boulets"
9: "Rue des Boulets" -100- "Nation"
9: "Nation" -100- "Buzenval"
9: "Buzenval" -100- "Maraîchers"
9: "Maraîchers" -100- "Porte de Montreuil"
9: "Porte de Montreuil" -100- "Robespierre"
9: "Robespierre" -100- "Croix de Chavaux"
9: "Croix de Chavaux" -100- "Mairie de Montreuil"
14: "Saint-Lazare" -100- "Madeleine"
14: "Madeleine" -100- "Pyramides"
14: "Pyramides" -100- "Châtelet"
14: "Châtelet" -100- "Gare de Lyon"
14: "Gare de Lyon" -100- "Bercy"
14: "Bercy" -100- "Cour Saint-Émilion"
14: "Cour Saint-Émilion" -100- "Bibliothèque François Mitterrand"
14: "Bibliothèque François Mitterrand" -100- "Olympiades"
11: "Châtelet" -100- "Hôtel de Ville"
11: "Hôtel de Ville" -100- "Rambuteau"
11: "Rambuteau" -100- "Arts et Métiers"
11: "Arts et Métiers" -100- "République"
11: "République" -100- "Goncourt"
11: "Goncourt" -100- "Belleville"
11: "Belleville" -100- "Pyrénées"
11: "Pyrénées" -100- "Jourdain"
11: "Jourdain" -100- "Place des Fêtes"
11: "Place des Fêtes" -100- "Télégraphe"
11: "Télégraphe" -100- "Porte des Lilas"
11: "Porte des Lilas" -100- "Mairie des Lilas"
12: "Porte de la Chapelle" -100- "Marx Dormoy"
12: "Marx Dormoy" -100- "Marcadet — Poissonniers"
12: "Marcadet — Poissonniers" -100- "Jules Joffrin"
12: "Jules Joffrin" -100- "Lamarck — Caulaincourt"
12: "Lamarck — Caulaincourt" -100- "Abbesses"
12: "Abbesses" -100- "Pigalle"
12: "Pigalle" -100- "Saint-Georges"
12: "Saint-Georges" -100- "Notre-Dame-de-Lorette"
12: "Notre-Dame-de-Lorette" -100- "Trinité — d'Estienne d'Orves"
12: "Trinité — d'Estienne d'Orves" -100- "Saint-Lazare"
12: "Saint-Lazare" -100- "Madeleine"
12: "Madeleine" -100- "Concorde"
12: "Concorde" -100- "Assemblée nationale"
12: "Assemblée nationale" -100- "Solférino"
12: "Solférino" -100- "Rue du Bac"
12: "Rue du Bac" -100- "Sèvres — Babylone"
12: "Sèvres — Babylone" -100- "Rennes"
12: "Rennes" -100- "Notre-Dame-des-Champs"
12: "Notre-Dame-des-Champs" -100- "Montparnasse — Bienvenüe"
12: "Montparnasse — Bienvenüe" -100- "Falguière"
12: "Falguière" -100- "Pasteur"
12: "Pasteur" -100- "Volontaires"
12: "Volontaires" -100- "Vaugirard"
12: "Vaugirard" -100- "Convention"
12: "Convention" -100- "Porte de Versailles"
12: "Porte de Versailles" -100- "Corentin Celton"
12: "Corentin Celton" -100- "Mairie d'Issy"

13: "Asnières — Gennevilliers" -100- "Les Agnettes"
13: "Les Agnettes" -100- "Gabriel Péri"
13: "Gabriel Péri" -100- "Mairie de Clichy"
13: "Mairie de Clichy" -100- "Porte de Clichy"
13: "Porte de Clichy" -100- "Brochant"
13: "Brochant" -100- "La Fourche"
13: "Saint-Denis — Université" -100- "Basilique de Saint-Denis"
13: "Basilique de Saint-Denis" -100- "Saint-Denis — Porte de Paris"
13: "Saint-Denis — Porte de Paris" -100- "Carrefour Pleyel"
13: "Carrefour Pleyel" -100- "Mairie de Saint-Ouen"
13: "Mairie de Saint-Ouen" -100- "Garibaldi"
13: "Garibaldi" -100- "Porte de Saint-Ouen"
13: "Porte de Saint-Ouen" -100- "Guy Môquet"
13: "Guy Môquet" -100- "La Fourche"
13: "La Fourche" -100- "Place de Clichy"
13: "Place de Clichy" -100- "Liège"
13: "Liège" -100- "Saint-Lazare"
13: "Saint-Lazare" -100- "Miromesnil"
13: "Miromesnil" -100- "Champs-Élysées — Clemenceau"
13: "Champs-Élysées — Clemenceau" -100- "Invalides"
13: "Invalides" -100- "Varenne"
13: "Varenne" -100- "Saint-François-Xavier"
13: "Saint-François-Xavier" -100- "Duroc"
13: "Duroc" -100- "Montparnasse — Bienvenüe"
13: "Montparnasse — Bienvenüe" -100- "Gaîté"
13: "Gaîté" -100- "Pernety"
13: "Pernety" -100- "Plaisance"
13: "Plaisance" -100- "Porte de Vanves"
13: "Porte de Vanves" -100- "Malakoff — Plateau de Vanves"
13: "Malakoff — Plateau de Vanves" -100- "Malakoff — Rue Etienne Dolet"
13: "Malakoff — Rue Etienne Dolet" -100- "Châtillon — Montrouge"