source: subversion/applications/routing/pyroute/route.py @ 5392

Last change on this file since 5392 was 5392, checked in by ojw, 12 years ago

Weightings are now added to the routing table, which (a) means its
structure has changed and route.py need to be modified, and (b) means
route.py can use this info when deciding where to go

File size: 4.3 KB
Line 
1#!/usr/bin/python
2#----------------------------------------------------------------
3# Routing for OSM data
4#
5#------------------------------------------------------
6# Usage as library:
7#   router = Router(LoadOsmObject)
8#   result, route = router.doRoute(node1, node2, transport)
9#
10# Usage from command-line:
11#   route.py filename.osm node1 node2 transport
12#
13# (where transport is cycle, foot, car, etc...)
14#------------------------------------------------------
15# Copyright 2007, Oliver White
16#
17# This program is free software: you can redistribute it and/or modify
18# it under the terms of the GNU General Public License as published by
19# the Free Software Foundation, either version 3 of the License, or
20# (at your option) any later version.
21#
22# This program is distributed in the hope that it will be useful,
23# but WITHOUT ANY WARRANTY; without even the implied warranty of
24# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
25# GNU General Public License for more details.
26#
27# You should have received a copy of the GNU General Public License
28# along with this program.  If not, see <http://www.gnu.org/licenses/>.
29#------------------------------------------------------
30# Changelog:
31#  2007-11-04  OJW  Modified from pyroute.py
32#  2007-11-05  OJW  Multiple forms of transport
33#------------------------------------------------------
34import sys
35import math 
36from loadOsm import *
37
38class Router:
39  def __init__(self, data):
40    self.data = data
41  def distance(self,n1,n2):
42    """Calculate distance between two nodes"""
43    lat1 = self.data.nodes[n1][0]
44    lon1 = self.data.nodes[n1][1]
45    lat2 = self.data.nodes[n2][0]
46    lon2 = self.data.nodes[n2][1]
47    # TODO: projection issues
48    dlat = lat2 - lat1
49    dlon = lon2 - lon1
50    dist2 = dlat * dlat + dlon * dlon
51    return(math.sqrt(dist2))
52 
53  def doRoute(self,start,end,transport):
54    """Do the routing"""
55    self.searchEnd = end
56    closed = [start]
57    self.queue = []
58   
59    # Start by queueing all outbound links from the start node
60    blankQueueItem = {'end':-1,'distance':0,'nodes':str(start)}
61    try:
62      for i, weight in self.data.routing[transport][start].items():
63        self.addToQueue(start,i, blankQueueItem, weight)
64    except KeyError:
65      return('no_such_node',[])
66   
67    # Limit for how long it will search
68    count = 0
69    while count < 10000:
70      count = count + 1
71      try:
72        nextItem = self.queue.pop(0)
73      except IndexError:
74        # Queue is empty: failed
75        return('no_route',[])
76      x = nextItem['end']
77      if x in closed:
78        continue
79      if x == end:
80        # Found the end node - success
81        routeNodes = [int(i) for i in nextItem['nodes'].split(",")]
82        return('success', routeNodes)
83      closed.append(x)
84      try:
85        for i, weight in self.data.routing[transport][x].items():
86          if not i in closed:
87            self.addToQueue(x,i,nextItem, weight)
88      except KeyError:
89        pass
90    else:
91      return('gave_up',[])
92 
93  def addToQueue(self,start,end, queueSoFar, weight = 1):
94    """Add another potential route to the queue"""
95   
96    # If already in queue
97    for test in self.queue:
98      if test['end'] == end:
99        return
100    distance = self.distance(start, end)
101    if(weight == 0):
102      return
103    distance = distance / weight
104   
105    # Create a hash for all the route's attributes
106    distanceSoFar = queueSoFar['distance']
107    queueItem = { \
108      'distance': distanceSoFar + distance,
109      'maxdistance': distanceSoFar + self.distance(end, self.searchEnd),
110      'nodes': queueSoFar['nodes'] + "," + str(end),
111      'end': end}
112   
113    # Try to insert, keeping the queue ordered by decreasing worst-case distance
114    count = 0
115    for test in self.queue:
116      if test['maxdistance'] > queueItem['maxdistance']:
117        self.queue.insert(count,queueItem)
118        break
119      count = count + 1
120    else:
121      self.queue.append(queueItem)
122
123if __name__ == "__main__":
124  data = LoadOsm(sys.argv[1])
125 
126  try:
127    transport = sys.argv[4]
128  except IndexError:
129    transport = 'cycle'
130    print "WARNING: No transport type specified, assuming \"%s\"" % transport
131 
132  router = Router(data)
133  result, route = router.doRoute(int(sys.argv[2]), int(sys.argv[3]), transport)
134 
135  if result == 'success':
136    print "Route: %s" % ",".join("%d" % i for i in route)
137  else:
138    print "Failed (%s)" % result
139
Note: See TracBrowser for help on using the repository browser.