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