FeatureWalker - algorithm to walk through bikeway data. Replaced by single PostGIS query.

bikeway_segment.rb

require 'gis_tools'
# == Schema Information
#
# Table name: bikeway_segments
#
#  id                          :integer          not null, primary key
#  city_rid                    :integer
#  city_geo_id                 :integer
#  city_linear_feature_name_id :integer
#  city_object_id              :integer
#  full_street_name            :string(255)
#  address_left                :string(255)
#  address_right               :string(255)
#  odd_even_flag_left          :string(255)
#  odd_even_flag_right         :string(255)
#  lowest_address_left         :integer
#  lowest_address_right        :integer
#  highest_address_left        :integer
#  highest_address_right       :integer
#  from_intersection_id        :integer
#  to_intersection_id          :integer
#  street_classification       :string(255)
#  bikeway_type                :string(255)
#  created_at                  :datetime
#  updated_at                  :datetime
#  geom                        :spatial          geometry, 4326
#  bikeway_id                  :integer
#  length_m                    :float
#

class BikewaySegment < ActiveRecord::Base
  def self.all_feature_ids
    BikewaySegment.pluck(:city_linear_feature_name_id).uniq.sort
  end

  def self.full_street_name(feature_id)
    BikewaySegment.where(:city_linear_feature_name_id => feature_id).first!.full_street_name
  end

  def kml
    result = BikewaySegment.select('*, st_askml(st_transform(geom, 4326)) as _kml').where(:id => self.id).first
    result._kml
  end

  def next
    # NOTE: strong assumption that this will return exactly 1 or 0 records
    # undefined behaviour if it returns >1 record, should detect this
    BikewaySegment.where(
      from_intersection_id: self.to_intersection_id,
      city_linear_feature_name_id: self.city_linear_feature_name_id
    ).first
  end

  def prev
    BikewaySegment.where(
      to_intersection_id: self.from_intersection_id,
      city_linear_feature_name_id: self.city_linear_feature_name_id
    ).first
  end

end

bikeway_segment_spec.rb

describe BikewaySegment do

  # XXX HACK FIXME:
  # This is a pretty brittle test.
  # Excuse: I wanted to get *something* done in a TDD fashion to whet my appetite.
  #
  # Problems with this test:
  # 1) It has hardcoded expected and actuals that are opaque and based on the result
  #    of running it by hand in postgresql.
  #
  # 2) It is tightly coupled to the SRID of the database (though perhaps this could be
  #    argued to be a poor-mans-smoke-test, if the SRID ever changes this will fail)
  #
  # 3) It actually hits the DB, which is bad form, but so is the .kml method itself.
  #
  # 4) The rounding/floating point semantics may change between platforms/implementations.

  # It does function as a fine smoke test to ensure the SRID is correct.

  it "should be able to render itself as KML" do
    segment = FactoryGirl.create(:bikeway_segment,
      :geom => "MULTILINESTRING ((-79.521209665 43.590895067, -79.522533939 43.590800049))")

    actual = segment.kml
    expected = "<MultiGeometry><LineString><coordinates>-79.521209665000001,43.590895066999998 -79.522533938999999,43.590800049000002</coordinates></LineString></MultiGeometry>"

    expect(actual).to eq(expected)
  end

  describe 'neighbour functions'

    # A little fuzzy on let vs let!
    let!(:different_before_first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 300, :from_intersection_id => 500, :to_intersection_id => 1) }
    let!(:first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 1, :from_intersection_id => 1, :to_intersection_id => 2) }
    let!(:second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 1, :from_intersection_id => 2, :to_intersection_id => 1000) }
    let!(:different_after_second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 50, :from_intersection_id => 1000, :to_intersection_id => 1001) }


    it "should be able to find it's next neighbour" do
      actual = first.next
      expected = second

      expect(actual).to eq(expected)
    end

    it "should be able to find it's previous neighbour" do
      actual = second.prev
      expected = first

      expect(actual).to eq(expected)
    end

    it "should return nil when it's next neighbor is another feature" do
      actual = second.next
      expect(actual).to be_nil
    end

    it "should return nil when it's previous neighbor is another feature" do
      actual = first.prev
      expect(actual).to be_nil
    end

end

feature_walker.rb

require 'logging_helpers'
require 'segment_walker'

class FeatureWalker
  # n.b. "Feature" is a GIS term:
  # "a collection of geographic features with the same geometry type (such as point, line, or polygon)"
  #
  # The city data is provided as an ESRI shapefile which is essentially a list of features
  # (specifically, lines), with attached metadata. One useful piece of metadata is the
  # `city_linear_feature_name_id`, which essentially groups together all entries with the
  # same "street name".
  #
  # This class is a super-set of SegmentWalker. It will provide a list of all contiguous paths
  # sharing the same `city_linear_feature_name_id`.
  #
  # usage:
  #   walker = FeatureWalker.new(feature_id: 10900)
  #   paths = walker.paths
  #   path_ids = paths.map { |list| list.map { |path| path.id } }
  #   # => [[4766, 1314, 1318, 4141, 1125],
  #         [1797, 1795, 4192, 4183, 1335, 4141, 1125],
  #         [1797, 1796, 1406, 3515],
  #         [3396, 4897, 3516],
  #         [3782]]

  def initialize(opts)
    @feature_id = nil
    if opts.key?(:feature_id)
      @feature_id = opts[:feature_id]
    end
  end

  # Analyzes the feature pointed to by @feature_id, and returns an array containing all contiguous paths.
  # Each entry in the returned array is itself an array of BikewaySegment records, in the correct sequence*.
  # For example:
  #    [[a,b,c], [d,e]]
  #    where all letters are BikewaySegments;
  #    a,b,c are one contiguous part of the feature;
  #    d,e are another contiguous part of the feature.
  def paths
    paths = []

    all_segments = find_segments_by_feature_id(@feature_id)
    unwalked_segments = all_segments
    i=1
    until unwalked_segments.empty? do
      walked_segments = build_path(unwalked_segments)
      paths << walked_segments

      unwalked_segments = all_segments - paths.flatten
      if unwalked_segments.count > 0
        debug " [#{@feature_id}] iteration #{i+=1}: #{unwalked_segments.count} unwalked segments remaining"
      end
    end

    paths
  end

  private
  def find_segments_by_feature_id(id)
    BikewaySegment.where(:city_linear_feature_name_id => id)
  end

  # Builds a single path from the list of segments passed in.
  # The entire `segments` array is passed in for better logging,
  # though technically, only the first element is considered.
  # The selection of the first element is arbitrary.
  #
  # The caller of this method is responsible for keeping track
  # of which segments have been visited and which have not.
  def build_path(segments)
    segment = segments.first

    debug \
      "#{segment.full_street_name} " \
      "(lfn_id=#{segment.city_linear_feature_name_id}); " \
      "id=#{segment.id}; " \
      "geoid=#{segment.city_geo_id}; " \
      "#{segments.count} segments in db; \n"

    walker = SegmentWalker.new(segment: segment)
    walked_segments = walker.ordered_segments

    debug "#{walked_segments.count} segments found by walking; "

    walked_segments
  end

end

feature_walker_spec.rb

require 'feature_walker'

describe FeatureWalker do
  describe "straight continuous line" do
    let!(:first)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) }
    let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) }
    let!(:third)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 4) }
    let!(:fourth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4, :to_intersection_id => 5) }
    let!(:fifth)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 5, :to_intersection_id => 1000) }

    it "should walk a simple straight-line feature successfully" do

      feature_walker = FeatureWalker.new(feature_id: 1)
      actual = feature_walker.paths
      expected = [[first, second, third, fourth, fifth]]

      expect(actual).to eq(expected)
    end
  end


  describe "discontiguous lines" do
    let!(:first)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) }
    let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) }
    let!(:third)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 1000) }
    let!(:other_part_first) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4000, :to_intersection_id => 4001) }
    let!(:other_part_second)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4001, :to_intersection_id => 9999) }

    it "should walk all discontiguous paths with the same feature id" do

      feature_walker = FeatureWalker.new(feature_id: 1)
      actual = feature_walker.paths

      # how will we know what order the paths will come in?
      expected = [[first, second, third], [other_part_first, other_part_second]]

      expect(actual).to eq(expected)
    end
  end

end

open_data_stats.rb

# n.b. for this purpose, "feature" means "LINEAR FEATURE" a.k.a. a road or route.

class OpenDataStats
  def display_all_routes
    for id in BikewaySegment.all_feature_ids
      walker = FeatureWalker.new(feature_id: id)
      paths = walker.paths

      path_ids = paths.map { |list| list.map { |path| path.id } }

      if path_ids.length > 1
        puts "lfn_id=#{id} full_street_name=#{BikewaySegment.full_street_name(id)} num_paths=#{paths.length} paths:"
        puts "  --> #{path_ids}"
      end
    end
  end
end

segment_walker.rb

class SegmentWalker
  # SegmentWalker takes an arbitrary BikewaySegment and "walks" through in both
  # directions using the city-provided "from intersection" and "to intersection"
  # metadata.
  #
  # usage:
  #
  #  walker = SegmentWalker.new(segment: BikewaySegment.first)
  #  walker = SegmentWalker.new(segment_id: 1)
  #
  #  segments = walker.ordered_segments
  #  segments.map { |s| s.id }
  #  # => [5191, 1, 2, 5192, 90, 3833, 3006, 4815, 86, 3619, 3620]

  def initialize(opts)
    @segment = nil
    if opts.key?(:segment)
      @segment = opts[:segment]
    elsif opts.key?(:segment_id)
      @segment = BikewaySegment.find(opts[:segment_id])
    end
  end

  def ordered_segments
    @segments = []
    @cycle = false

    # don't clobber the instance variable...
    segment = @segment

    # current segment is the "middle" or the pivot
    pivot = segment
    @segments.push(pivot)

    # first walk forwards...
    until segment.nil?
      segment = segment.next
      break unless process_segment(segment) do |segment|
        @segments.push(segment)
      end
    end

    # go back to the pivot, then walk backwards
    segment = pivot
    until segment.nil?
      segment = segment.prev
      break unless process_segment(segment) do |segment|
        @segments.unshift(segment)
      end
    end

    @segments
  end

  def process_segment(segment, &block)
    if segment.nil?
      return false
    elsif @segments.include?(segment)
      # cycle detected! segment already seen! breaking out!"
      @cycle = true
      return false
    else
      yield segment
    end
  end
end

segment_walker_spec.rb

require 'spec_helper'
require 'segment_walker'

describe SegmentWalker do

  describe "#ordered_segments" do

    let!(:different_before_first) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 300, :from_intersection_id => 500, :to_intersection_id => 1) }
    let!(:first)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 1, :to_intersection_id => 2) }
    let!(:second) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 2, :to_intersection_id => 3) }
    let!(:third)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 3, :to_intersection_id => 4) }
    let!(:fourth) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 4, :to_intersection_id => 5) }
    let!(:fifth)  { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 5, :to_intersection_id => 1000) }
    let!(:different_after_second) { FactoryGirl.create(:bikeway_segment, :city_linear_feature_name_id => 50, :from_intersection_id => 1000, :to_intersection_id => 1001) }

    def test_ordered_segments(walker)
      actual = walker.ordered_segments
      expected = [first, second, third, fourth, fifth]
      expect(actual).to eq(expected)
    end

    it "should work from the middle" do
      test_ordered_segments(SegmentWalker.new(segment_id: third.id))
    end

    it "should work from the left" do
      test_ordered_segments(SegmentWalker.new(segment_id: first.id))
    end

    it "should work from the right" do
      test_ordered_segments(SegmentWalker.new(segment_id: fifth.id))
    end

    it "can accept a segment object directly" do
      test_ordered_segments(SegmentWalker.new(segment: fifth))
    end

  end

  describe "cyclic data" do
    let!(:one)   { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 11, :to_intersection_id => 22) }
    let!(:two)   { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 22, :to_intersection_id => 33) }
    let!(:three) { FactoryGirl.create(:bikeway_segment, :from_intersection_id => 33, :to_intersection_id => 11) }

    it "can handle cycles without going into infinite loop" do
      walker = SegmentWalker.new(segment: one)
      actual = walker.ordered_segments
      expected = [one, two, three]

      expect(actual).to eq(expected)

    end
  end

end

This code took me a long time to write and I was really proud of it. Well tested and powerful, if a little hard to follow.

It feels good to delete code (especially knowing it's still there under source control), but jeez, this code was the bulk of the application. It was literally replaced with a single SQL query. I only have 1 test now.