Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/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')
Add Comment
Please, Sign In to add comment