-
Notifications
You must be signed in to change notification settings - Fork 0
/
best_points.py
180 lines (149 loc) · 6.31 KB
/
best_points.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
import time, signal, json, random, sys
from multiprocessing import Pool
import urllib2 #for OSRM queries
import psycopg2 #for postgres DB access
import util, config #local modules
def init():
global conn, cur
conn = util.db_connect()
cur = conn.cursor()
def fetch_parts(sql):
"""Extract unique parts from the database using the given sql query and returns them via a generator.
Returns:
A generator object yielding cellpath parts.
"""
global mconn, mcur
mcur.execute(sql)
for segment, in mcur.fetchall():
yield tuple(segment)
def best_point(part):
"""Finds the best start or endpoint for the list of two cells (first two cells in celpath for startpoint, last two for endpoint)
When the gloabl variable direction = 1 startpoints are calculated, when direction = -1 endpoints are calculated.
Args:
part: a 2-tuple of cell ids in the order of travel"""
global direction, conn, cur
a,b = part
y = None #when no start or endpoint, no border points or no routes were found, null value will be added to the database
assert direction == 1 or direction == -1
#find start/end nodes
data = (a,b) if direction == 1 else (b,a)
sql = " SELECT xid, ST_Y(x.geom) AS xlat, ST_X(x.geom) AS xlon\
FROM closest_junction(%s, %s) AS xid, hh_2po_4pgr_vertices AS x\
WHERE x.id = xid"
cur.execute(sql, data)
if cur.rowcount > 0: #start and end point found
x, xlat, xlon = cur.fetchone()
#fetch waypoint candidates
data = (a,) if direction == 1 else (b,)
sql = " SELECT * FROM get_candidate_junctions(%s)"
cur.execute(sql, data)
y_candidates = cur.fetchall()
#calculate route cost for all waypoints
costs = []
for y, ylat, ylon in y_candidates:
if direction == 1:
costs.append(route_cost(ylat, ylon, xlat, xlon))
elif direction == -1:
costs.append(route_cost(xlat, xlon, ylat, ylon))
#select cheapest waypoint
if len(costs) > 0 and min(costs) < float("inf"): #at least one feasible route found
y = y_candidates[costs.index(min(costs))][0]
data = ([a,b], y)
if y == None:
print("WARNING: no start/endpoint found for " + str([a,b]))
if direction == 1:
cur.execute("INSERT INTO best_startpoint VALUES (%s,%s);", data)
elif direction == -1:
cur.execute("INSERT INTO best_endpoint VALUES (%s,%s);", data)
conn.commit()
def route_cost(xlat, xlon, ylat, ylon, attempts = 3):
"""Calculates the cost from x via y to z; OSRM backend needs to listen at port 5000
Args:
xlat: latitude of the start point
xlon: longitude of the start point
ylat: latitude of the via point
ylon: longitude of the via point
Returns:
The cost of the calculated route (travel time in seconds) or inf if no route found"""
data = {}
if hasattr(config, "PYOSRM") and config.PYOSRM == True:
data = engine.route([(xlat, xlon), (ylat,ylon)])
else:
try:
data = json.load(urllib2.urlopen('http://www.server.com:5000/viaroute?loc=' + str(xlat) + ',' + str(xlon) + '&loc=' + str(ylat) + ',' + str(ylon)))
except Exception, e:
print("WARNING: " + str(e))
if attempts > 0:
time.sleep(5)
return route_cost(xlat, xlon, ylat, ylon, attempts = attempts - 1)
else:
raise e
if "route_summary" in data:
return data["route_summary"]["total_time"]
else: #no feasible route found, return infinite cost
return float("inf")
def signal_handler(signal, frame):
global mapper, request_stop
request_stop = True
if mapper:
mapper.stop()
print("Aborting (can take a minute)...")
sys.exit(1)
mapper = None
request_stop = False
cur = None
conn = None
engine = None
if hasattr(config, "PYOSRM") and config.PYOSRM == True:
import pyosrm
engine = pyosrm.Engine(config.PYOSRM_FILE)
if __name__ == '__main__':
signal.signal(signal.SIGINT, signal_handler) #abort on CTRL-C
#connect to db
mconn = util.db_connect()
mcur = mconn.cursor()
print("Creating best point tables...")
mcur.execute(open("SQL/04_Routing_Network_Loading/create_best_points.sql", 'r').read())
mconn.commit()
print("Creating closest_junction() function...")
mcur.execute(open("SQL/04_Routing_Network_Loading/create_closest_junction_func.sql", 'r').read())
mconn.commit()
#get number of remaining segments to calculate
sql_remaining = """
SELECT COUNT(DISTINCT cellpath[1:2])
FROM ((SELECT cellpath FROM cellpath_dist) UNION (SELECT ARRAY[orig_cell, dest_cell] AS cellpath FROM od)) AS cellpaths --include direct cellpaths for shortest algorithm
WHERE array_length(cellpath, 1) >= 2 AND
NOT EXISTS(SELECT * FROM best_startpoint WHERE best_startpoint.part = cellpath[1:2])
"""
mcur.execute(sql_remaining)
remaining = mcur.fetchone()[0]
print(str(remaining) + " startpoints to be calculated" )
startparts = fetch_parts("""
SELECT DISTINCT cellpath[1:2]
FROM ((SELECT cellpath FROM cellpath_dist) UNION (SELECT ARRAY[orig_cell, dest_cell] AS cellpath FROM od)) AS cellpaths --include direct cellpaths for shortest algorithm
WHERE array_length(cellpath, 1) >= 2 AND
NOT EXISTS(SELECT * FROM best_startpoint WHERE best_startpoint.part = cellpath[1:2])""")
print("Calculating startpoints...")
direction = 1 #startpoints
mapper = util.ParMap(best_point, initializer = init)
mapper(startparts, length = remaining)
mapper.stop()
#get number of remaining segments to calculate
sql_remaining = """
SELECT COUNT(DISTINCT cellpath[array_upper(cellpath,1)-1:array_upper(cellpath,1)])
FROM ((SELECT cellpath FROM cellpath_dist) UNION (SELECT ARRAY[orig_cell, dest_cell] AS cellpath FROM od)) AS cellpaths --include direct cellpaths for shortest algorithm
WHERE array_length(cellpath, 1) >= 2 AND
NOT EXISTS(SELECT * FROM best_endpoint WHERE best_endpoint.part = cellpath[array_upper(cellpath,1)-1:array_upper(cellpath,1)])"""
mcur.execute(sql_remaining)
remaining = mcur.fetchone()[0]
print(str(remaining) + " endpoints to be calculated" )
endparts = fetch_parts("""
SELECT DISTINCT cellpath[array_upper(cellpath,1)-1:array_upper(cellpath,1)]
FROM ((SELECT cellpath FROM cellpath_dist) UNION (SELECT ARRAY[orig_cell, dest_cell] AS cellpath FROM od)) AS cellpaths --include direct cellpaths for shortest algorithm
WHERE array_length(cellpath, 1) >= 2 AND
NOT EXISTS(SELECT * FROM best_endpoint WHERE best_endpoint.part = cellpath[array_upper(cellpath,1)-1:array_upper(cellpath,1)])""")
print("Calculating endpoints...")
direction = -1 #endpoints
mapper = util.ParMap(best_point, initializer = init)
mapper(endparts, length = remaining)
mapper.stop()