class Connected::Path
Represents an indirect connection (combined edges) between two Vertices on a graph
Public Class Methods
all(from:, to:, include_closed: false, debug: false, suboptimal: false)
click to toggle source
rubocop:disable Metrics/AbcSize rubocop:disable Metrics/CyclomaticComplexity rubocop:disable Metrics/PerceivedComplexity
# File lib/connected/path.rb, line 56 def self.all(from:, to:, include_closed: false, debug: false, suboptimal: false) paths = [] path_queue = from.neighbors.map { |n| new([from, n]) } until path_queue.empty? this_path = path_queue.pop next unless this_path.open? || include_closed puts "Walking from #{this_path.nodes.map(&:name).join(' to ')}" if debug if this_path.to == to puts "Found destination with #{this_path.nodes.map(&:name).join(' to ')}" if debug paths << this_path else highmetric = paths.max_by(&:cost)&.cost highops = paths.max_by(&:hops)&.hops this_path.to.neighbors.each do |n| new_path = this_path.branch(n) next unless new_path if paths.empty? || new_path.cost <= highmetric || new_path.hops <= highops || suboptimal path_queue.unshift(new_path) elsif debug puts "Skipping #{new_path.nodes.map(&:name).join(' to ')}" end end end end # Return the list of paths, sorted first by cost then by hops paths.sort_by { |p| [p.cost, p.hops] } end
find(from:, to:, include_closed: false)
click to toggle source
rubocop:enable Metrics/AbcSize rubocop:enable Metrics/CyclomaticComplexity rubocop:enable Metrics/PerceivedComplexity
# File lib/connected/path.rb, line 94 def self.find(from:, to:, include_closed: false) all(from: from, to: to, include_closed: include_closed).first end
new(nodes, validate: true)
click to toggle source
# File lib/connected/path.rb, line 6 def initialize(nodes, validate: true) validate_nodes(nodes) if validate @nodes = nodes end
Public Instance Methods
branch(node)
click to toggle source
# File lib/connected/path.rb, line 27 def branch(node) return unless nodes.last.neighbors.include?(node) && !nodes.include?(node) self.class.new(nodes + [node], validate: false) end
connections()
click to toggle source
# File lib/connected/path.rb, line 12 def connections links = nodes.dup links.size.downto(2).map do |i| links[-1 * i].connection_to(links[-1 * (i - 1)]) end end
cost()
click to toggle source
# File lib/connected/path.rb, line 19 def cost connections.map(&:metric).reduce(&:+) end
from()
click to toggle source
# File lib/connected/path.rb, line 41 def from nodes.first end
hops()
click to toggle source
# File lib/connected/path.rb, line 23 def hops nodes.size - 1 end
nodes()
click to toggle source
# File lib/connected/path.rb, line 33 def nodes @nodes.dup end
open?()
click to toggle source
# File lib/connected/path.rb, line 37 def open? connections.select(&:closed?).empty? end
to()
click to toggle source
# File lib/connected/path.rb, line 45 def to nodes.last end
to_s(separator = ' -> ')
click to toggle source
# File lib/connected/path.rb, line 49 def to_s(separator = ' -> ') nodes.map(&:name).join(separator) end
Private Instance Methods
validate_nodes(list)
click to toggle source
# File lib/connected/path.rb, line 100 def validate_nodes(list) # Want to throw an exception if there are loops raise 'Invalid Nodes list, duplicates found' unless list.size == list.uniq.size list.each_with_index do |item, index| break if index == list.size - 1 # Each node should connect to the next (no leaves except the end of the list) raise 'Invalid Nodes list, broken chain' unless item.neighbors.include?(list[index + 1]) end true end