Philip Cunningham music, code and stuff.

Ruby Snippet: DFS 27 October 2012

So, this semester, I'm taking a class called Intelligent Systems Techniques. It started off by exploring search as a means of finding routes between two locations and we're now in the territory of game-playing and problem solving.

Unfortunately, we have to write our final assignment in Java. So, I decided to plod along and implement some bits and pieces in Ruby as a bit of respite.

class DepthFirstSearch

  attr_reader :graph

  def initialize(graph)
    @graph = graph
  end

  def shortest_path_between(start, goal)
    all_paths_between(start, goal).first
  end

  def all_paths_between(start, goal)
    paths = search(start, goal)
    order_by_length(paths)
  end

  private

  def successors(start)
    graph.get_successors(start)
  end

  def order_by_length(search)
    search.sort_by { |array| array.size }
  end

  def search(start, goal, path=[])
    path  = path + [start]
    paths = []

    successors(start).each do |node|
      unless path.include? node
        new_paths = search(node, goal, path)
        new_paths.each { |new_path| paths << new_path }
      end
    end
    start == goal ? [path] : paths
  end

end

class CampusRouteMap

  attr_reader :graph

  def initialize(graph)
    @graph = graph
  end

  def get_successors(point)
    graph.inject [] do |locations, connection|
      locations << connection[0] if connection[1] == point
      locations << connection[1] if connection[0] == point
      locations
    end
  end

end

# Campus map route search

connections = [["office", "debuggingRoom"],
               ["office", "CHI343"],
               ["CHI343", "informaticsSchoolOffice"],
               ["informaticsSchoolOffice", "ITS"],
               ["ITS", "PEV11A6"],
               ["PEV11A6", "PEV12A11"],
               ["PEV11A6", "library"],
               ["CHI343", "PEV11A6"],
               ["PEV12A11", "library"],
               ["library", "bridgeTeaBar"],
               ["library", "meetingHouse"],
               ["meetingHouse", "bridgeTeaBar"],
               ["bridgeTeaBar", "debuggingRoom"]]

campus_map = CampusRouteMap.new(connections)
search     = DepthFirstSearch.new(campus_map)
puts search.shortest_path_between("office", "meetingHouse").join(", ") # => office, debuggingRoom, bridgeTeaBar, meetingHouse

Depth first search is a maverick search strategy. It's cheap on memory but can fall into a pit when it has to search an infinite space with no solutions.

If you're interested, my notes for this class are available here on Github. I've been using a combination of git, emacs and tmux for my note taking this year and it's working out really well for me!