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


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 =, edges =
    @node_list = node_list
    @edges = edges

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

  def find_node_by_element(element)
    return @node_list[element]

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


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


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

  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

  def minimum_spanning_tree
    mst =
    return mst.minimum_spanning_tree

  def minimum_spanning_tree_edges(edges)
    mst_edges = []
    edges.each do |edge|
      mst_edge =,, edge.weight)
      mst_edges << mst_edge
    return mst_edges


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


  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)

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

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

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


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

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

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


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 =
    object_list.each do |object|
      node = object)
    return graph


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:,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 =

  def build_graph(locations)

    graph = @graph_builder.build_graph(locations)

      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)
            raise RestClient::Exception # example would be invalid city to city direction


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

    return graph



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

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



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});
            polylineOptions: {
                strokeWeight: 4,
                strokeOpacity: 1,
                strokeColor: 'red'

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



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