class RubyGraphWalker::Graph

Attributes

edges[RW]
edges_by_name[RW]
vertices[RW]

Public Class Methods

new(vertices) click to toggle source
# File lib/graph.rb, line 51
def initialize(vertices)
  @vertices = {}
  @edges_by_name = {}
  @edges = []
  vertices.each do |v_params|
    v = Vertex.new(v_params)
    @vertices[v_params[:name]] = v
    v.edges.each do |edge|
      puts "Warning: multiple edges named '#{edge.name}'" if @edges_by_name[edge.name]
      @edges_by_name[edge.name] = edge
      @edges << edge
    end
  end
end

Public Instance Methods

find_path(from, to, args = {}) click to toggle source
# File lib/graph.rb, line 97
def find_path(from, to, args = {})  
  vertex_path = []
  plan = []
  via_type = args.keys.join

  case via_type
  when "via"
    via = args[:via]
    vertex_path = Dijkstra.new(self, from).shortest_path_to(via) + Dijkstra.new(self, via).shortest_path_to(to).drop(1)
    vertex_path.each_cons(2) do |path|
      f, d = path
      vertex = @vertices[d]
      edge = vertex.edges.select { |e| e.to == d}.first
      plan << {v: vertex, e: edge}
    end
  when "via_edge"
    via_edge = args[:via_edge]
    plan = find_path_via_edge(from, to, via_edge)

  # when "via_edges"
  #   edges = args[:via_edges]
  #   if edges.size < 2
  #     raise "please specify multiple edges"
  #   end
  #   v = nil
  #   edges[0..-2].each do |edge|
  #     start = (plan.last[:v].name if plan.last) || from
  #     v = @edges_by_name[edge].to
  #     plan += find_path_via_edge(start, v, edge)
  #   end
  #   plan += find_path_via_edge(v, to, edges.last)
  when ""
    vertex_path = Dijkstra.new(self, from).shortest_path_to(to)
    
    vertex_path.each_cons(2) do |path|
      from, d = path
      vertex = @vertices[from]
      edge = vertex.edges.select { |e| e.to == d}.first
      plan << {v: vertex, e: edge}
    end
    if plan.empty? and from == to
      return  :on_the_spot
    end
  end

  if plan.any?
    puts plan.map {|p| "#{p[:v].name if p[:v]} (#{p[:e].name if p[:e]})" }.join(" -> ") + " >> #{@vertices[to].name}" 
  else
    raise "No path from #{from} to #{to}" 
  end
  plan
end
find_path_via_edge(from, to, edge_name) click to toggle source
# File lib/graph.rb, line 66
def find_path_via_edge(from, to, edge_name)
  log_info "#{from} -> #{to} via: (#{edge_name}): "
  matched_edges = @edges.select { |edge| edge.name == edge_name }
  log_error "no edge found for '#{edge_name}'" if matched_edges.size == 0
  log_error "multiple edges matched for '#{edge_name}'" if matched_edges.size > 1
  via_edge = matched_edges.first
  plan = []

  first_path = Dijkstra.new(self, from).shortest_path_to(via_edge.from)

  first_path.each_cons(2) do |path|
    start, dest = path
    vertex = @vertices[start]
    edge = vertex.edges.select { |e| e.to == dest}.first
    plan << {v: vertex, e: edge}
  end

  via_v = @vertices[via_edge.from]
  plan << {v: via_v, e: via_edge}

  second_path = Dijkstra.new(self, via_edge.to).shortest_path_to(to)

  second_path.each_cons(2) do |path|
    start, dest = path
    vertex = @vertices[start]
    edge = vertex.edges.select { |e| e.to == dest }.first
    plan << {v: vertex, e: edge}
  end
  plan 
end