## Using the Google Maps Distance Matrix API and Directions Service (Post 2 of 4)

01/09/2017

This post is part 2 of 4 in a Series

#### Getting Started

This post covers the technical details of building the graph(s) used in the application and the integration of the Google Maps API. This application is written in Ruby/Rails with JavaScript for client side map display.

After discussing the high level applications of graphs, we start here by implementing our graph. The first three components of the graph are modeled in the Graph, Node, and Edge classes seen below.

The Graph class initializes the graph with empty hashes – one for the edges and one for the nodes. All edges and nodes will be stored in their hashes for constant lookup. As a result of Hash storage, duplicate nodes are not permitted in the Graph.

```# graph.rb

class Graph

attr_accessor :node_list
attr_accessor :edges

# Graph is a hash of nodes and hash of edges
def initialize(node_list = Hash.new, edges = Hash.new)
@node_list = node_list
@edges = edges
end

@node_list[node.node_data] = node
end

def find_node_by_element(element)
return @node_list[element]
end

edge1 = Edge.new(node_from, node_to, weight)
edge2 = Edge.new(node_to, node_from, weight)

# edge1 and edge2 used as checks to prevent duplicate edges between two nodes
# since this is an undirected graph, only add edge1 (edge2 is just for a check)
if !@edges.has_key?(edge1.hash_key) && !@edges.has_key?(edge2.hash_key)

@edges[edge1.hash_key] = weight
end

end

edge = Edge.new(node_from, node_to, weight)
@edges[edge.hash_key] = weight

end

def update_all_nodes_to_distance(distance)
@node_list.values.each do |node|
node.key = distance
end
end

def print_graph
puts 'printing graph'
@node_list.values.each do |node|
puts 'Node (' + node.node_data.to_s + ')'
puts 'nodes neighbors: '
node.neighbors.each_with_index do |neighbor, index|
puts neighbor.node_data.to_s + ' edge ' + index.to_s + ' ' + neighbor.edges[index].to_s
end
end
end

def minimum_spanning_tree
mst = PrimMinimumSpanningTree.new(self)
return mst.minimum_spanning_tree
end

def minimum_spanning_tree_edges(edges)
mst_edges = []
edges.each do |edge|
mst_edge = MstEdge.new(edge.node1.node_data.name.to_s, edge.node2.node_data.name.to_s, edge.weight)
mst_edges << mst_edge
end
return mst_edges
end

end
```

The Node class defines the individual nodes used in a graph. Each Node has node data, a list of Neighbor nodes, a list of edges, a reference (if any) to its parent, and a key (initially set to ‘Infinite’). The key is used in the MST algorithm.

The Node data attribute allows for generic data to be assigned to the Node. In our example application, the node data will be the location (modeled as a ‘Place’ object). Node data could be an integer, string, or any object. Neighbors is the list of the the other Node objects connected to this node through the Edge objects. The Edges are also modeled in the Edge class and stored in each Node’s edges list.

```# node.rb

class Node

INT_MAX = Float::INFINITY

include Comparable

attr_accessor :node_data, :neighbors, :edges, :key, :parent

def initialize(params = {})
@node_data = params.fetch(:node_data, nil) # object, name, or identifier of node (a place object)
@neighbors = params.fetch(:neighbors, []) # this node's neighbor nodes - other place objects
@edges = params.fetch(:edges, []) # this node neighbor edges - edge objects connecting place object to place object
@key = params.fetch(:key, INT_MAX)
@parent = params.fetch(:parent, nil)
end

@neighbors << node # add the actual node to the neighbor list
end

@edges << edge # add the edge (all edges will be from this node to another node)
end

def <=>(other)
@key <=> other.key
end

end
```

The Edge class takes two nodes (the ‘from’ and ‘to’ node references) and an edge weight as its parameters.

```# edge.rb

class Edge

include Comparable

attr_accessor :node1, :node2, :weight

def initialize(node1, node2, weight)
@node1 = node1
@node2 = node2
@weight = weight
end

def hash_key
return @node1.node_data.to_s + "->" + @node2.node_data.to_s
end

def <=>(other)
@weight <=> other.weight
end

end
```

With these three classes, the GraphBuilder class is used to facilitate the buildout of a graph from a list of objects.

```# graph_builder.rb

class GraphBuilder

def build_graph(object_list)
graph = Graph.new
object_list.each do |object|
node = Node.new(node_data: object)
end
return graph
end

end
```

#### Integrating the Google Maps API

With all of these classes together, it is now time to build a graph and integrate the Google Maps API.

The documentation for the Google Maps Distance Matrix API can be seen HERE

In our application, locations entered in the UI are saved as ‘Places’ (models/place.rb). The lists of places are saved under the parent resource ‘MinimumSpanningTree’ (models/minimum_spanning_tree.rb). The MiniumSpanningTree controller coordinates the CRUD methods associated with building the resources from the user input. When it comes time to calculate and render the MST, the Google Maps API is used to determine the distances between all of the locations entered. The locations are passed in as parameters to form an API call, and the results of the json response are parsed in the GoogleMatrixApiClient class.

An example json post would look like the below:

The corresponding API response (to be parsed) looks like:

```{
"destination_addresses" : [ "Saint Louis, MO, USA" ],
"origin_addresses" : [ "Seattle, WA, USA" ],
"rows" : [
{
"elements" : [
{
"distance" : {
"text" : "2,077 mi",
"value" : 3342228
},
"duration" : {
"text" : "1 day 6 hours",
"value" : 107485
},
"status" : "OK"
}
]
}
],
"status" : "OK"
}
```

So to create the API call and parse the corresponding results, the GoogleMatrixApiClient has methods to build and receive the responses. The ‘rest-client’ gem is used for parsing the json response, and the ‘figaro’ gem is used to store the Google Maps API key(s) within the correct environment variables.

```# google_matrix_api_client.rb

require 'rest-client'
require 'json'

def initialize
@graph_builder = GraphBuilder.new
end

def build_graph(locations)

graph = @graph_builder.build_graph(locations)

begin
rest_client_response = RestClient.get(api_call(locations))
api_response = JSON.parse(rest_client_response)

locations.each_with_index do |location, index|
node_from = graph.find_node_by_element(location)
api_response['rows'][index]['elements'].each_with_index do |element, i|
status = element['status']
if status == 'OK'
node_to = graph.find_node_by_element(locations[i])
distance = element['distance']['value'].to_i
if distance > 1 # don't add self to self
end
else
raise RestClient::Exception # example would be invalid city to city direction
end

end
end

rescue SocketError => socketerror
puts socketerror
return socketerror
rescue RestClient::Exception => restexception
puts restexception
return restexception
rescue Exception => generalexception
puts generalexception
return generalexception
end

return graph

end

private

def formatted_locations(locations)
formatted_locations = ""
locations.each_with_index do |location, index|
formatted_location = location.name.gsub(/[\,]/ ,"").gsub(/\s/,'+')
if index != locations.size - 1
formatted_locations += formatted_location + '|'
else
formatted_locations += formatted_location
end
end
return formatted_locations
end

def api_call(locations)
formatted_location_list = formatted_locations(locations)
api_call = url + 'origins=' + formatted_location_list + '&destinations=' + formatted_location_list + '&mode=driving&units=imperial&language=en-US' + '&key=' + key
return api_call
end

end
```

#### Exceptions

One important point of consideration is the treatment of this application as an undirected graph (outlined in the first post). As the name indicates, the Google Maps Matrix API returns an n x n matrix of distances (much like the manual map distance tables in a printed Rand-McNally map). Therefore, it is important to not have an edge from the node to itself, and to avoid any duplicated edges. The GoogleMatrixAPIClient therefore has a check to ensure the distance is > 1 meter, and the graph’s add_undirected_edge method ensures that no more than one edge connects two nodes within the graph.

The GoogleMatrixAPIClient handles any errors in a generic sense – there is no specific behavior for each error. Errors could come in the form of two locations not having valid directions between them (ie there is no way to drive between Paris and New York), or if the API response is invalid (ie the rate limit has been reached). Errors are returned generically to the controller which renders a json error message to the view.

#### Rendering the Final Result

Once the graph is constructed and the MST is calculated, MST edges are returned as json to the ‘show’ controller method and set in instance variables. Each edge is rendered using the Google Directions service like the below:

```// minimum_spanning_trees.js
var markers = [];
// foreach edge
// initialize directionService and directionDisplay
// pass the nodes of the edge to the service
for (var i = 0; i < \$mst_edges.length; i++) {

var node1 = \$mst_edges[i].name1;
var node2 = \$mst_edges[i].name2;

var directionsDisplay = new google.maps.DirectionsRenderer({suppressMarkers: true});
directionsDisplay.setMap(map);
directionsDisplay.setOptions({
polylineOptions: {
strokeWeight: 4,
strokeOpacity: 1,
strokeColor: 'red'
}
});

calculateAndDisplayRoute(directionsService, directionsDisplay, node1, node2, map, markers);

}
```

#### Recap

To recap the workflow, locations are entered by the user in the UI. These locations are modeled into MinimumSpanningTree resources, and then the sent to the Google Maps Matrix API where the distances are parsed and a graph is constructed and the MST is calculated. This is all in turn sent back to the user and rendered again using the Google Maps API and direction service on the front end.

To see this all in action, be sure to try out the application HERE

Visit the Previous Post 1 of 4 in this Series

Visit the Next Post 3 of 4 in this Series