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

  def add_node(node)
    @node_list[node.node_data] = node
  end

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

  def add_undirected_edge(node_from, node_to, weight)
    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)

      @node_list[node_from.node_data].add_neighbor(node_to)
      @node_list[node_from.node_data].add_edge(edge1)

      @node_list[node_to.node_data].add_neighbor(node_from)
      @node_list[node_to.node_data].add_edge(edge1)

      @edges[edge1.hash_key] = weight
    end

  end

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

    @node_list[node_from.node_data].add_neighbor(node_to)
    @node_list[node_from.node_data].add_edge(edge)
  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

  def add_neighbor(node)
    @neighbors << node # add the actual node to the neighbor list
  end

  def add_edge(edge)
    @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)
      graph.add_node(node)
    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:
https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial&mode=driving&origins=Seattle,WA&destinations=St+Louis,MO&key=KEY

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

class GoogleMatrixApiClient

  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
              graph.add_undirected_edge(node_from, node_to, distance)
            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)
      key = ENV['GOOGLE_MAPS']
      url = 'https://maps.googleapis.com/maps/api/distancematrix/json?'
      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 directionsService = new google.maps.DirectionsService;
        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