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