Ruby Snippet: DFS

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!

This entry was posted in News. Bookmark the permalink.

Comments are closed.