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