Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::DimensionValues Class Reference

#include <routing_filter_committables.h>

Classes

struct  Interval
struct  VehicleBreak

Public Member Functions

 DimensionValues (int num_paths, int num_nodes)
void PushNode (int node)
 Adds a node to new nodes.
void MakePathFromNewNodes (int path)
 Turns new nodes into a new path, allocating dimension values for it.
void Reset ()
 Resets all path to empty, in both committed and current state.
void Revert ()
 Clears the changed state, make it point to the committed state.
void Commit ()
absl::Span< const int > CommittedNodes (int path) const
 Returns a const view of the nodes of the path, in the committed state.
absl::Span< const int > Nodes (int path) const
 Returns a const view of the nodes of the path, in the current state.
absl::Span< const IntervalTransits (int path) const
 Returns a const view of the transits of the path, in the current state.
absl::Span< IntervalMutableTransits (int path)
 Returns a mutable view of the transits of the path, in the current state.
absl::Span< const int64_t > CommittedTravels (int path) const
 Returns a const view of the travels of the path, in the committed state.
absl::Span< const int64_t > Travels (int path) const
 Returns a const view of the travels of the path, in the current state.
absl::Span< int64_t > MutableTravels (int path)
 Returns a mutable view of the travels of the path, in the current state.
absl::Span< const int64_t > TravelSums (int path) const
 Returns a const view of the travel sums of the path, in the current state.
absl::Span< int64_t > MutableTravelSums (int path)
 Returns a mutable view of the travel sums of the path in the current state.
absl::Span< const IntervalCumuls (int path) const
 Returns a const view of the cumul mins of the path, in the current state.
absl::Span< IntervalMutableCumuls (int path)
 Returns a mutable view of the cumul mins of the path, in the current state.
Interval Span (int path) const
 Returns the span interval of the path, in the current state.
IntervalMutableSpan (int path)
absl::Span< const VehicleBreakVehicleBreaks (int path) const
std::vector< VehicleBreak > & MutableVehicleBreaks (int path)
int NumNodes (int path) const
 Returns the number of nodes of the path, in the current state.
absl::Span< const size_t > ChangedPaths () const
 Returns a const view of the set of paths changed, in the current state.
bool PathHasChanged (int path) const
 Returns whether the given path was changed, in the current state.

Detailed Description

This class allows to represent a state of dimension values for all paths of a vehicle routing problem. Values of interest for each path are:

  • nodes,
  • cumuls (min/max),
  • transit times,
  • sum of transit times since the beginning of the path,
  • span (min/max).

This class can maintain two states at once: a committed state and a current state. The current state can be modified by first describing a path p to be modified with PushNode() and MakePathFromNewNodes(). Then the dimension values of this path can be modified with views returned by MutableXXX() methods.

When a set of paths has been modified, the caller can decide to definitely change the committed state to the new state, or to revert to the committed state.

Operations are meant to be efficient:

  • all path modifications, i.e. PushNode(), MakePathFromNewNodes(), MutableXXX(), MutableSpan() operations are O(1).
  • Revert() is O(num changed paths).
  • Commit() has two behaviors:
    • if there are less than max_num_committed_elements_ elements in the committed state, then Commit() is O(num changed paths).
    • otherwise, Commit() does a compaction of the committed state, in O(num_nodes + num_paths). The amortized cost of Commit(), when taking modifications into account, is O(size of changed paths), because all modifications pay at worst O(1) for its own compaction.
Note
this class does not support the semantics associated with its fields names, for instance it does not make sure that cumul_min <= cumul_max. The field names are meant for readability for the user. However, path sizes are enforced: if a path has n nodes, then it has n fields for cumul min/max, n for transit_sums, and max(0, n-1) for transits.

Definition at line 209 of file routing_filter_committables.h.

Constructor & Destructor Documentation

◆ DimensionValues()

operations_research::DimensionValues::DimensionValues ( int num_paths,
int num_nodes )
inline

Definition at line 211 of file routing_filter_committables.h.

Member Function Documentation

◆ ChangedPaths()

absl::Span< const size_t > operations_research::DimensionValues::ChangedPaths ( ) const
inline

Returns a const view of the set of paths changed, in the current state.

Definition at line 460 of file routing_filter_committables.h.

◆ Commit()

void operations_research::DimensionValues::Commit ( )
inline

Makes the committed state point to the current state. If the state representation is too large, reclaims memory by compacting the committed state.

If the committed data would take too much space, defragment it.

Definition at line 338 of file routing_filter_committables.h.

◆ CommittedNodes()

absl::Span< const int > operations_research::DimensionValues::CommittedNodes ( int path) const
inline

Returns a const view of the nodes of the path, in the committed state.

Definition at line 357 of file routing_filter_committables.h.

◆ CommittedTravels()

absl::Span< const int64_t > operations_research::DimensionValues::CommittedTravels ( int path) const
inline

Returns a const view of the travels of the path, in the committed state.

Definition at line 387 of file routing_filter_committables.h.

◆ Cumuls()

absl::Span< const Interval > operations_research::DimensionValues::Cumuls ( int path) const
inline

Returns a const view of the cumul mins of the path, in the current state.

Definition at line 421 of file routing_filter_committables.h.

◆ MakePathFromNewNodes()

void operations_research::DimensionValues::MakePathFromNewNodes ( int path)
inline

Turns new nodes into a new path, allocating dimension values for it.

Allocate dimension values. We allocate n cells for all dimension values, even transits, so they can all be indexed by the same range_of_path.

Definition at line 295 of file routing_filter_committables.h.

◆ MutableCumuls()

absl::Span< Interval > operations_research::DimensionValues::MutableCumuls ( int path)
inline

Returns a mutable view of the cumul mins of the path, in the current state.

Definition at line 427 of file routing_filter_committables.h.

◆ MutableSpan()

Interval & operations_research::DimensionValues::MutableSpan ( int path)
inline

Returns a mutable view of the span of the path, in the current state. The path must have been changed since the last commit.

Definition at line 437 of file routing_filter_committables.h.

◆ MutableTransits()

absl::Span< Interval > operations_research::DimensionValues::MutableTransits ( int path)
inline

Returns a mutable view of the transits of the path, in the current state.

When the path is not empty, #transits = #nodes - 1. When the path is empty, begin = end, return empty span.

Definition at line 378 of file routing_filter_committables.h.

◆ MutableTravels()

absl::Span< int64_t > operations_research::DimensionValues::MutableTravels ( int path)
inline

Returns a mutable view of the travels of the path, in the current state.

Definition at line 401 of file routing_filter_committables.h.

◆ MutableTravelSums()

absl::Span< int64_t > operations_research::DimensionValues::MutableTravelSums ( int path)
inline

Returns a mutable view of the travel sums of the path in the current state.

Definition at line 415 of file routing_filter_committables.h.

◆ MutableVehicleBreaks()

std::vector< VehicleBreak > & operations_research::DimensionValues::MutableVehicleBreaks ( int path)
inline

Returns a mutable vector of the vehicle breaks of the path, in the current state. The path must have been changed since the last commit.

Definition at line 452 of file routing_filter_committables.h.

◆ Nodes()

absl::Span< const int > operations_research::DimensionValues::Nodes ( int path) const
inline

Returns a const view of the nodes of the path, in the current state.

Definition at line 363 of file routing_filter_committables.h.

◆ NumNodes()

int operations_research::DimensionValues::NumNodes ( int path) const
inline

Returns the number of nodes of the path, in the current state.

Definition at line 458 of file routing_filter_committables.h.

◆ PathHasChanged()

bool operations_research::DimensionValues::PathHasChanged ( int path) const
inline

Returns whether the given path was changed, in the current state.

Definition at line 464 of file routing_filter_committables.h.

◆ PushNode()

void operations_research::DimensionValues::PushNode ( int node)
inline

Adds a node to new nodes.

Definition at line 292 of file routing_filter_committables.h.

◆ Reset()

void operations_research::DimensionValues::Reset ( )
inline

Resets all path to empty, in both committed and current state.

Definition at line 312 of file routing_filter_committables.h.

◆ Revert()

void operations_research::DimensionValues::Revert ( )
inline

Clears the changed state, make it point to the committed state.

Definition at line 324 of file routing_filter_committables.h.

◆ Span()

Interval operations_research::DimensionValues::Span ( int path) const
inline

Returns the span interval of the path, in the current state.

Definition at line 433 of file routing_filter_committables.h.

◆ Transits()

absl::Span< const Interval > operations_research::DimensionValues::Transits ( int path) const
inline

Returns a const view of the transits of the path, in the current state.

When the path is not empty, #transits = #nodes - 1. When the path is empty, begin = end, return empty span.

Definition at line 369 of file routing_filter_committables.h.

◆ Travels()

absl::Span< const int64_t > operations_research::DimensionValues::Travels ( int path) const
inline

Returns a const view of the travels of the path, in the current state.

Definition at line 394 of file routing_filter_committables.h.

◆ TravelSums()

absl::Span< const int64_t > operations_research::DimensionValues::TravelSums ( int path) const
inline

Returns a const view of the travel sums of the path, in the current state.

Definition at line 408 of file routing_filter_committables.h.

◆ VehicleBreaks()

absl::Span< const VehicleBreak > operations_research::DimensionValues::VehicleBreaks ( int path) const
inline

Returns a const view of the vehicle breaks of the path, in the current state.

Definition at line 444 of file routing_filter_committables.h.


The documentation for this class was generated from the following file: