Class: Quicopt::Permutation

Inherits:
Object
  • Object
show all
Defined in:
lib/quicopt/structured.rb

Overview

A permutation declared by Model#permutation: n_items items placed in as many slots, one item per slot, both numbered from 0. Read it with item_at and slot_of; constrain it with precede.

route = m.permutation("route", 5)
route.item_at(0)     # the first stop visited
route.slot_of(3)     # when stop 3 is visited
route.precede(3, 0)  # stop 3 is visited before stop 0

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(model, name, n_items, start) ⇒ Permutation

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Declared with Model#permutation, not built directly.



69
70
71
72
73
74
75
76
 
# File 'lib/quicopt/structured.rb', line 69

def initialize(model, name, n_items, start)
  @model = model
  @name = name
  @n_items = n_items
  @start = start&.freeze
  @precedences = []
  @reads = {}
end

Instance Attribute Details

#model ⇒ Model (readonly)

Returns the model that declared this permutation.

Returns:

  • (Model) —

    the model that declared this permutation



57
58
59
 
# File 'lib/quicopt/structured.rb', line 57

def model
  @model
end

#n_items ⇒ Integer (readonly)

Returns the number of items, which is also the number of slots.

Returns:

  • (Integer) —

    the number of items, which is also the number of slots



61
62
63
 
# File 'lib/quicopt/structured.rb', line 61

def n_items
  @n_items
end

#name ⇒ String (readonly)

Returns the permutation's name; its arrangement comes back keyed by it.

Returns:

  • (String) —

    the permutation's name; its arrangement comes back keyed by it



59
60
61
 
# File 'lib/quicopt/structured.rb', line 59

def name
  @name
end

#start ⇒ Array<Integer>? (readonly)

Returns the slot each item starts in, or nil for the default (item i in slot i).

Returns:

  • (Array<Integer>, nil) —

    the slot each item starts in, or nil for the default (item i in slot i)



64
65
66
 
# File 'lib/quicopt/structured.rb', line 64

def start
  @start
end

Class Method Details

.cycle?(edges, n_items) ⇒ Boolean

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Whether the [before, after] requirements over items 0...n_items contradict each other: Kahn's algorithm leaves an item unplaced exactly when they contain a cycle.

Returns:

  • (Boolean) 


142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/quicopt/structured.rb', line 142

def self.cycle?(edges, n_items)
  indegree = Array.new(n_items, 0)
  edges.each { |_, b| indegree[b] += 1 }
  ready = (0...n_items).select { |i| indegree[i].zero? }
  placed = 0
  until ready.empty?
    x = ready.pop
    placed += 1
    edges.each do |a, b|
      next unless a == x

      indegree[b] -= 1
      ready << b if indegree[b].zero?
    end
  end
  placed < n_items
end

Instance Method Details

#inspect ⇒ String

Returns name and number of items.

Returns:

  • (String) —

    name and number of items



133
134
135
 
# File 'lib/quicopt/structured.rb', line 133

def inspect
  "#<Quicopt::Permutation #{@name} (#{@n_items} items in #{@n_items} slots)>"
end

#item_at(slot) ⇒ Expression

The item in slot slot, an expression whose value the service chooses. For a route whose items are stops, route.item_at(0) is the first stop visited. Index a LookupTable with it to read data about that item.

Parameters:

  • slot (Integer) —

    from 0 to n_items - 1

Returns:

Raises:

  • (TypeError, ArgumentError) —

    if slot is not one of the slots



85
86
87
 
# File 'lib/quicopt/structured.rb', line 85

def item_at(slot)
  read(:item_at, Positions.check(slot, @n_items, "slot", owner))
end

#precede(before, after) ⇒ Permutation

Require item before to be in an earlier slot than item after: a pickup before its delivery, or a job before the job that needs its output. The service only considers arrangements that meet every such requirement, so every solution meets it.

Parameters:

  • before (Integer) —

    an item

  • after (Integer) —

    another item

Returns:

  • (Permutation) —

    self, so requirements can be chained

Raises:

  • (ArgumentError) —

    if the two items are the same, if the requirement contradicts those already given (1 before 2 and 2 before 1), or if the start places before after after



111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/quicopt/structured.rb', line 111

def precede(before, after)
  a = Positions.check(before, @n_items, "item", owner)
  b = Positions.check(after, @n_items, "item", owner)
  raise ArgumentError, "an item cannot precede itself" if a == b
  if @start && @start[a] > @start[b]
    raise ArgumentError, "#{owner}: the start places item #{a} after item #{b}, which it must precede"
  end
  if Permutation.cycle?(@precedences + [[a, b]], @n_items)
    raise ArgumentError, "requiring #{a} before #{b} contradicts the requirements already given for #{owner}"
  end

  @precedences << [a, b].freeze
  self
end

#precedences ⇒ Array<Array(Integer, Integer)>

Returns the [before, after] requirements, in the order given.

Returns:

  • (Array<Array(Integer, Integer)>) —

    the [before, after] requirements, in the order given



128
129
130
 
# File 'lib/quicopt/structured.rb', line 128

def precedences
  @precedences.dup.freeze
end

#slot_of(item) ⇒ Expression

The slot item item is placed in, an expression whose value the service chooses. For a route whose items are stops, route.slot_of(3) is when stop 3 is visited.

Parameters:

  • item (Integer) —

    from 0 to n_items - 1

Returns:

Raises:

  • (TypeError, ArgumentError) —

    if item is not one of the items



96
97
98
 
# File 'lib/quicopt/structured.rb', line 96

def slot_of(item)
  read(:slot_of, Positions.check(item, @n_items, "item", owner))
end