module OverpassGraph

Constants

MAXSIZE
TIMEOUT

Public Class Methods

create_adjacency_hash(roads, vertices, directed, metric) click to toggle source
# File lib/overpass_graph/create_adjacency_hash.rb, line 5
def self.create_adjacency_hash(roads, vertices, directed, metric)
  """
  Creates an adjacency hash from a list of roads and set of vertices. 
  
  The graph is represented as a hash of hashes, where the keys are coordinate pairs [lat, lon] (as a list), 
  and the values are hashes that contain neighbor coordinate pairs as keys and edge lengths as values.
  If an edge exists from a coordinate pair, x, to coordinate pair, y, of length z, then adj[x][y] will equal z.
  
  Here's an example: { [lat1, lon1] => { [lat2, lon2] => distance1, [lat3, lon3] => distance2 } }
  In this example, there is an edge from [lat1, lon1] to [lat2, lon2] of length distance1 and an edge from [lat1, lon1] to [lat3, lon3] of length distance2.

  :return: adjacency hash representation of a graph
  """
  adj = {}

  roads.each do |road|

    road_nodes = road[:geometry]

    start_vertex = [road_nodes[0][:lat], road_nodes[0][:lon]]
    if !adj.has_key?(start_vertex)
      adj[start_vertex] = {}
    end

    # Need to keep track of the distance travelled along road, the previous node (to increment distance)
    # and the previous vertex. Upon discovering a new vertex in the iteration, an edge is created from
    # the previous vertex to the discovered vertex (and if the road is two-way, from the discovered
    # vertex back to the previous vertex)
    distance = 0
    prev_node = { coords: start_vertex, distance: distance }
    prev_vertex = { coords: start_vertex, distance: distance }

    (1..road_nodes.length - 1).each do |i|

      current = [road_nodes[i][:lat], road_nodes[i][:lon]]
      
      # updating distance with previous node and current node
      if !metric
        distance += Haversine.distance(prev_node[:coords][0], prev_node[:coords][1], current[0], current[1]).to_miles
      else
        distance += Haversine.distance(prev_node[:coords][0], prev_node[:coords][1], current[0], current[1]).to_km
      end
      
      # if the current node is in the set of vertices, calculate the distance between it and the previous vertex.
      # Then add an edge of that length from the previous vertex to the current node. If the road is two-way, also add an edge
      # from the current node back to the previous vertex.
      if vertices === current

        distance_between = distance - prev_vertex[:distance]

        if road[:tags][:oneway] != 'yes' || !directed
          if adj.has_key?(current)
            adj[current][prev_vertex[:coords]] = distance_between
          else
            adj[current] = { prev_vertex[:coords] => distance_between }
          end
        end

        if adj.has_key?(prev_vertex[:coords])
          adj[prev_vertex[:coords]][current] = distance_between
        else
          adj[prev_vertex[:coords]] = { current => distance_between }
        end

        prev_vertex = {coords: current, distance: distance}
      end

      # previous node kept track of to calculate distance along the road
      prev_node = {coords: current, distance: distance}
    end

  end

  return adj

end
create_vertex_set(roads) click to toggle source
# File lib/overpass_graph/create_vertex_set.rb, line 5
def self.create_vertex_set(roads)
  '''
  Function to process a list of road hashes and return the set of vertex coordinates from that list.
  Vertices are any coordinates that either: a) begin or end a road or b) are found within at least two roads (i.e. intersections)
  :return: a set of vertices
  '''

  # frequency map of times a given node appears in all roads
  node_count = {}

  roads.each do |road|

    road_nodes = road[:geometry]
    start_vertex = [road_nodes[0][:lat], road_nodes[0][:lon]]
    end_vertex = [road_nodes[-1][:lat], road_nodes[-1][:lon]]

    # this ensures that each start and end vertex will be included in the set of returned
    # vertices, because post iteration they'll both have at least 2 in node_count
    if !node_count.has_key?(start_vertex)
      node_count[start_vertex] = 1
    end
    if !node_count.has_key?(end_vertex)
      node_count[end_vertex] = 1
    end
    
    # this will pick up any nodes that form intersections (i.e. are nodes in multiple roads),
    # but aren't the starting or ending nodes of any road
    road_nodes.each do |node|
      current = [node[:lat], node[:lon]]
      if !node_count.has_key?(current)
        node_count[current] = 1
      else
        node_count[current] += 1
      end
    end
  end

  return Set.new( node_count.filter{ |node, num| num > 1 }.keys )

end
get_roads(north, east, south, west, allowed_values, disallowed_values) click to toggle source
# File lib/overpass_graph/get_roads.rb, line 8
def self.get_roads(north, east, south, west, allowed_values, disallowed_values)
  '''
  Gets roads by querying the Overpass API.
  :return: a list of hashes with information about all the roads in the bounding box
  '''

  if 90 < north || 90 < south || north < -90 || south < -90
    raise "Latitudes in bounding boxes must be between -90.0 and 90.0"
  end

  if 180 < east || 180 < west || east < -180 || west < -180
    raise "Longitudes in bounding boxes must be between -180.0 and 180.0"
  end

  if north < south
    raise "Northern latitude is less than southern latitude.\nDid you mean 'overpass_graph(#{south}, #{east}, #{north}, #{west}...)"
  end

  if east < west
    puts "OVERPASS_GRAPH WARNING: Eastern longitude is less than western longitude.\n"\
         "In most cases this is not intended by the developer.\n"\
         "Perhaps you meant 'overpass_graph(#{north}, #{west}, #{south}, #{east}...)'?\n"\
         "Find out more here: https://dev.overpass-api.de/overpass-doc/en/full_data/bbox.html"
  end

  options = {
    bbox: {
      s: south,
      n: north,
      w: west,
      e: east
    },
    timeout: TIMEOUT,
    maxsize: MAXSIZE
  }

  allowed_string = allowed_values.map{|allowed_value| "[highway=#{allowed_value}]" }.join()
  disallowed_string = disallowed_values.map{|disallowed_value| "[highway!=#{disallowed_value}]" }.join()

  # query for all highways within the bounding box
  overpass = OverpassAPI::QL.new(options)
  query = "way[highway]#{allowed_string}#{disallowed_string};(._;>;);out geom;"
  
  begin
    response = overpass.query(query)
  rescue
    
    # try again if first request is denied, if second request is denied, throw the exception
    response = overpass.query(query)

  end

  # filter out all partial roads and return the filtered hash
  elements = response[:elements]
  return elements.filter { |element| element[:type] == "way" }

end
graph(north, east, south, west, directed: true, filter_by_allowing: true, filtered_values:[], metric: false) click to toggle source
# File lib/overpass_graph.rb, line 7
def self.graph(north, east, south, west, directed: true, filter_by_allowing: true, filtered_values:[], metric: false)
  '''
  Primary function for the library. The user may specify whether to filter by allowing or not, in addition to  a few other options.
  If they choose to filter by allowing certain road types, the get roads function will be passed an empty array for disallowed values.
  If they choose to filter by disallowing certain road types, the get roads function will be passed an empty array for allowed values.
  :return: adjacency map representation of a graph
  '''
  allowed_values = []
  disallowed_values = []

  filter_by_allowing ? allowed_values = filtered_values : disallowed_values = filtered_values

  roads = get_roads(north, east, south, west, allowed_values, disallowed_values)

  vertices = create_vertex_set(roads)

  return create_adjacency_hash(roads, vertices, directed, metric)

end