#include <routing_filters.h>

Classes
class	Chain
	A Chain is a range of committed nodes. More...

struct	ChainBounds

class	ChainRange
	A ChainRange is a range of Chains, committed or not. More...

class	NodeRange

Public Member Functions
int	CommittedIndex (int node) const

ChainBounds	CommittedPathRange (int path) const

	PathState (int num_nodes, std::vector< int > path_start, std::vector< int > path_end)

int	NumNodes () const
	Instance-constant accessors.

int	NumPaths () const
	Returns the number of paths (empty paths included).

int	Start (int path) const
	Returns the start of a path.

int	End (int path) const
	Returns the end of a path.

int	Path (int node) const

const std::vector< int > &	ChangedPaths () const

const std::vector< int > &	ChangedLoops () const
	Returns the set of loops that were added by the change.

ChainRange	Chains (int path) const
	Returns the current range of chains of path.

NodeRange	Nodes (int path) const
	Returns the current range of nodes of path.

void	ChangePath (int path, absl::Span< const ChainBounds > chains)
	State modifiers.

void	ChangePath (int path, const std::initializer_list< ChainBounds > &chains)

void	ChangeLoops (absl::Span< const int > new_loops)
	Describes the nodes that are newly loops in this change.

void	Commit ()
	Set the current state G1 as committed. See class comment for details.

void	Revert ()
	Erase incremental changes. See class comment for details.

void	Reset ()
	Sets all paths to start->end, all other nodes to kUnassigned.

void	SetInvalid ()

bool	IsInvalid () const

Static Public Attributes
static constexpr int	kUnassigned = -2
	State-dependent accessors.

static constexpr int	kLoop = -1

Detailed Description

A PathState represents a set of paths and changes made on it.

More accurately, let us define P_{num_nodes, starts, ends}-graphs the set of directed graphs with nodes [0, num_nodes) whose connected components are paths from starts[i] to ends[i] (for the same i) and loops. Let us fix num_nodes, starts and ends, so we call these P-graphs.

A P-graph can be described by the sequence of nodes of each of its paths, and its set of loops. To describe a change made on a given P-graph G0 that yields another P-graph G1, we choose to describe G1 in terms of G0. When the difference between G0 and G1 is small, as is almost always the case in a local search setting, the description is compact, allowing for incremental filters to be efficient.

In order to describe G1 in terms of G0 succintly, we describe each path of G1 as a sequence of chains of G0. A chain of G0 is either a nonempty sequence of consecutive nodes of a path of G0, or a node that was a loop in G0. For instance, a path that was not modified from G0 to G1 has one chain, the sequence of all nodes in the path. Typically, local search operators modify one or two paths, and the resulting paths can described as sequences of two to four chains of G0. Paths that were modified are listed explicitly, allowing to iterate only on changed paths. The loops of G1 are described more implicitly: the loops of G1 not in G0 are listed explicitly, but those in both G1 and G0 are not listed.

A PathState object can be in two states: committed or changed. At construction, the object is committed, G0. To enter a changed state G1, one can pass modifications with ChangePath() and ChangeLoops(). For reasons of efficiency, a chain is described as a range of node indices in the representation of the committed graph G0. To that effect, the nodes of a path of G0 are guaranteed to have consecutive indices.

Filters can then browse the change efficiently using ChangedPaths(), Chains(), Nodes() and ChangedLoops().

Then Commit() or Revert() can be called: Commit() sets the changed state G1 as the new committed state, Revert() erases all changes.

Definition at line 136 of file routing_filters.h.

Constructor & Destructor Documentation

◆ PathState()

operations_research::PathState::PathState	(	int	num_nodes,
		std::vector< int >	path_start,
		std::vector< int >	path_end )

Path constructor: path_start and path_end must be disjoint, their values in [0, num_nodes).

Definition at line 3408 of file routing_filters.cc.

Member Function Documentation

◆ Chains()

PathState::ChainRange operations_research::PathState::Chains ( int path ) const

Returns the current range of chains of path.

Definition at line 3455 of file routing_filters.cc.

◆ ChangedLoops()

const std::vector< int > & operations_research::PathState::ChangedLoops ( ) const

inline

Returns the set of loops that were added by the change.

Definition at line 187 of file routing_filters.h.

◆ ChangedPaths()

const std::vector< int > & operations_research::PathState::ChangedPaths ( ) const

inline

Returns the set of paths that actually changed, i.e. that have more than one chain.

Definition at line 185 of file routing_filters.h.

◆ ChangeLoops()

void operations_research::PathState::ChangeLoops ( absl::Span< const int > new_loops )

Describes the nodes that are newly loops in this change.

If the node was already a loop, do not add it. If it was not assigned, it becomes a loop.

Definition at line 3478 of file routing_filters.cc.

◆ ChangePath() [1/2]

void operations_research::PathState::ChangePath	(	int	path,
		absl::Span< const ChainBounds >	chains )

State modifiers.

Changes the path to the given sequence of chains of the committed state. Chains are described by semi-open intervals. No optimization is made in case two consecutive chains are actually already consecutive in the committed state: they are not merged into one chain, and Chains(path) will report the two chains.

Definition at line 3469 of file routing_filters.cc.

◆ ChangePath() [2/2]

void operations_research::PathState::ChangePath	(	int	path,
		const std::initializer_list< ChainBounds > &	chains )

inline

Same as above, but the initializer_list interface avoids the need to pass a vector.

Always add sentinel, in case this is the last path change.

Definition at line 203 of file routing_filters.h.

◆ Commit()

void operations_research::PathState::Commit ( )

Set the current state G1 as committed. See class comment for details.

Definition at line 3487 of file routing_filters.cc.

◆ CommittedIndex()

int operations_research::PathState::CommittedIndex ( int node ) const

inline

Definition at line 157 of file routing_filters.h.

◆ CommittedPathRange()

ChainBounds operations_research::PathState::CommittedPathRange ( int path ) const

inline

Definition at line 158 of file routing_filters.h.

◆ End()

int operations_research::PathState::End ( int path ) const

inline

Returns the end of a path.

Definition at line 174 of file routing_filters.h.

◆ IsInvalid()

bool operations_research::PathState::IsInvalid ( ) const

inline

Definition at line 226 of file routing_filters.h.

◆ Nodes()

PathState::NodeRange operations_research::PathState::Nodes ( int path ) const

Returns the current range of nodes of path.

Definition at line 3462 of file routing_filters.cc.

◆ NumNodes()

int operations_research::PathState::NumNodes ( ) const

inline

Instance-constant accessors.

Returns the number of nodes in the underlying graph.

Definition at line 168 of file routing_filters.h.

◆ NumPaths()

int operations_research::PathState::NumPaths ( ) const

inline

Returns the number of paths (empty paths included).

Definition at line 170 of file routing_filters.h.

◆ Path()

int operations_research::PathState::Path ( int node ) const

inline

Returns the committed path of a given node, kLoop if it is a loop, kUnassigned if it is not assigned,

Definition at line 182 of file routing_filters.h.

◆ Reset()

void operations_research::PathState::Reset ( )

Sets all paths to start->end, all other nodes to kUnassigned.

Initial state is all unperformed: paths go from start to end directly.

Nodes that are not starts or ends are not in any path, but they still need to be represented in the committed state.

Definition at line 3422 of file routing_filters.cc.

◆ Revert()

void operations_research::PathState::Revert ( )

Erase incremental changes. See class comment for details.

Definition at line 3496 of file routing_filters.cc.

◆ SetInvalid()

void operations_research::PathState::SetInvalid ( )

inline

LNS Operators may not fix variables, in which case we mark the candidate invalid.

Definition at line 225 of file routing_filters.h.

◆ Start()

int operations_research::PathState::Start ( int path ) const

inline

Returns the start of a path.

Definition at line 172 of file routing_filters.h.

Member Data Documentation

◆ kLoop

int operations_research::PathState::kLoop = -1

staticconstexpr

Definition at line 179 of file routing_filters.h.

◆ kUnassigned

int operations_research::PathState::kUnassigned = -2

staticconstexpr

State-dependent accessors.

Definition at line 178 of file routing_filters.h.

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

ortools/constraint_solver/routing_filters.h
ortools/constraint_solver/routing_filters.cc

Classes

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PathState()

Member Function Documentation

◆ Chains()

◆ ChangedLoops()

◆ ChangedPaths()

◆ ChangeLoops()

◆ ChangePath() [1/2]

◆ ChangePath() [2/2]

◆ Commit()

◆ CommittedIndex()

◆ CommittedPathRange()

◆ End()

◆ IsInvalid()

◆ Nodes()

◆ NumNodes()

◆ NumPaths()

◆ Path()

◆ Reset()

◆ Revert()

◆ SetInvalid()

◆ Start()

Member Data Documentation

◆ kLoop

◆ kUnassigned