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.

#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 Interval >	Transits (int path) const
	Returns a const view of the transits of the path, in the current state.
absl::Span< Interval >	MutableTransits (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 Interval >	Cumuls (int path) const
	Returns a const view of the cumul mins of the path, in the current state.
absl::Span< Interval >	MutableCumuls (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.
Interval &	MutableSpan (int path)
absl::Span< const VehicleBreak >	VehicleBreaks (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.

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:

ortools/constraint_solver/routing_filter_committables.h

Detailed Description

Classes

Public Member Functions

Constructor & Destructor Documentation

◆ DimensionValues()

Member Function Documentation

◆ ChangedPaths()

◆ Commit()

◆ CommittedNodes()

◆ CommittedTravels()

◆ Cumuls()

◆ MakePathFromNewNodes()

◆ MutableCumuls()

◆ MutableSpan()

◆ MutableTransits()

◆ MutableTravels()

◆ MutableTravelSums()

◆ MutableVehicleBreaks()

◆ Nodes()

◆ NumNodes()

◆ PathHasChanged()

◆ PushNode()

◆ Reset()

◆ Revert()

◆ Span()

◆ Transits()

◆ Travels()

◆ TravelSums()

◆ VehicleBreaks()