-
Notifications
You must be signed in to change notification settings - Fork 0
/
distance_matrix.py
179 lines (131 loc) · 4.94 KB
/
distance_matrix.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 os
from dotenv import load_dotenv
from data import create_data
from google_places import GooglePlaces
load_dotenv()
API_KEY = os.getenv('API_KEY')
def build_distance_matrix(response):
"""
Gets the distance value from the response to create the row list.
:param response: The concatenated response for max_rows origins.
:type response: dict
:return: The distance matrix for max_rows origins.
:rtype: list
"""
distance_matrix = []
for row in response['rows']:
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
distance_matrix.append(row_list)
return distance_matrix
def merge_responses(responses, length):
"""
Concatenate the responses for a place.
:param responses: The responses received for max_rows origin for all destinations.
:type responses: list[dict]
:param length: The number of origins in each request.
:type length: int
:return: The concatenated response for max_rows origins.
:rtype: dict
"""
rows = []
for row in range(length):
elements = []
for response in responses:
elements.extend(response['rows'][row]['elements'])
res = {'elements': elements}
rows.append(res)
response = {
'rows': rows
}
return response
def send_request(origin, destination):
"""
Build and send request for the given origin and destination addresses.
:param origin: The list of place_ids to be treated as origins in one request.
:type origin: list
:param destination: The list of place_ids to be treated as destinations in one request.
:type destination: list
:return: The response from the distance matrix api.
:rtype: dict
"""
def build_str(places):
return '|place_id:'.join(places) # Build a pipe-separated string of addresses
api = GooglePlaces(API_KEY)
origin_str = build_str(origin)
destination_str = build_str(destination)
response = api.distance_matrix(origin_str, destination_str)
return response
def col_itr(place_ids, q_col, r_col, max_rows, max_cols, origin, distance_matrix):
"""
Send requests returning max_cols columns per request.
:param place_ids: A list of place_ids.
:type place_ids: list
:param q_col: The number of requests to be send, obtaining max_cols columns per request.
:type q_col: int
:param r_col: The remaining columns after q_col x max_cols columns.
:type r_col: int
:param max_rows: The maximum number of rows obtained per request.
:type max_rows: int
:param max_cols: The maximum number of columns obtained per request.
:type max_cols: int
:param origin: The list of place_ids to be treated as origins in one request.
:type origin: list
:param distance_matrix: The list of distances between nodes returned after previous request.
:type distance_matrix: list
:return: Distance matrix
:rtype: list
"""
responses = []
for j in range(q_col):
destination = place_ids[j * max_cols: (j + 1) * max_cols]
response = send_request(origin, destination)
responses.append(response)
if r_col > 0:
destination = place_ids[q_col * max_cols: q_col * max_cols + r_col]
response = send_request(origin, destination)
responses.append(response)
res = merge_responses(responses, max_rows)
distance_matrix += build_distance_matrix(res)
return distance_matrix
def create_distance_matrix(place_ids):
"""
Create the distance matrix.
Method to overcome the usage limits of Distance Matrix Api.
:param place_ids: A list of place_ids.
:type place_ids: list
:return: A list of distances between the nodes.
:rtype: list
"""
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.
max_elements = 100
num_places = len(place_ids)
if num_places > 25:
max_rows = max_elements // 25
max_cols = 25
else:
max_rows = max_elements // num_places
max_cols = num_places
q_row, r_row = divmod(num_places, max_rows)
q_col, r_col = divmod(num_places, max_cols)
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q_row):
origin = place_ids[i * max_rows: (i + 1) * max_rows]
distance_matrix = col_itr(place_ids, q_col, r_col, max_rows, max_cols, origin, distance_matrix)
# Get the remaining remaining r rows, if necessary.
if r_row > 0:
origin = place_ids[q_row * max_rows: q_row * max_rows + r_row]
distance_matrix = col_itr(place_ids, q_col, r_col, max_rows, max_cols, origin, distance_matrix)
return distance_matrix
########
# Main #
########
def distance():
"""
Entry point of the program
"""
place_ids = create_data() # Create the data.
distance_matrix = create_distance_matrix(place_ids)
return distance_matrix
if __name__ == '__main__':
distance()