Class: Connected::Path

Inherits:
Object
  • Object
show all
Defined in:
lib/connected/path.rb

Overview

Represents an indirect connection (combined edges) between two Vertices on a graph

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes, validate: true) ⇒ Path

Returns a new instance of Path.



6
7
8
9
10
 
# File 'lib/connected/path.rb', line 6

def initialize(nodes, validate: true)
  validate_nodes(nodes) if validate

  @nodes = nodes
end

Class Method Details

.all(from:, to:, include_closed: false, debug: false, suboptimal: false) ⇒ Object

rubocop:disable Metrics/AbcSize rubocop:disable Metrics/CyclomaticComplexity rubocop:disable Metrics/PerceivedComplexity



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# 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) ⇒ Object

rubocop:enable Metrics/AbcSize rubocop:enable Metrics/CyclomaticComplexity rubocop:enable Metrics/PerceivedComplexity



94
95
96
 
# 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

Instance Method Details

#branch(node) ⇒ Object 



27
28
29
30
31
 
# 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 ⇒ Object 



12
13
14
15
16
17
 
# 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 ⇒ Object 



19
20
21
 
# File 'lib/connected/path.rb', line 19

def cost
  connections.map(&:metric).reduce(&:+)
end

#from ⇒ Object 



41
42
43
 
# File 'lib/connected/path.rb', line 41

def from
  nodes.first
end

#hops ⇒ Object 



23
24
25
 
# File 'lib/connected/path.rb', line 23

def hops
  nodes.size - 1
end

#nodes ⇒ Object 



33
34
35
 
# File 'lib/connected/path.rb', line 33

def nodes
  @nodes.dup
end

#open? ⇒ Boolean

Returns:

  • (Boolean) 


37
38
39
 
# File 'lib/connected/path.rb', line 37

def open?
  connections.select(&:closed?).empty?
end

#to ⇒ Object 



45
46
47
 
# File 'lib/connected/path.rb', line 45

def to
  nodes.last
end

#to_s(separator = ' -> ') ⇒ Object 



49
50
51
 
# File 'lib/connected/path.rb', line 49

def to_s(separator = ' -> ')
  nodes.map(&:name).join(separator)
end