Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class PathState

Note: This documentation is automatically generated.

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.
Method
ChainBounds

Chains

Return type: ChainRange

Arguments: int path

Returns the current range of chains of path.

ChangedLoops

Return type: const std::vector<int>&

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

ChangedPaths

Return type: const std::vector<int>&

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

ChangeLoops

Return type: void

Arguments: const std::vector<int>& new_loops

Describes the nodes that are newly loops in this change.

ChangePath

Return type: void

Arguments: int path, const std::vector<ChainBounds>& chains

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.

ChangePath

Return type: void

Arguments: int path, const std::initializer_list<ChainBounds>& chains

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

Commit

Return type: void

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

CommittedIndex

Return type: int

Arguments: int node

CommittedPathRange

Return type: ChainBounds

Arguments: int path

End

Return type: int

Arguments: int path

Returns the end of a path.

IsInvalid

Return type: bool

Nodes

Return type: NodeRange

Arguments: int path

Returns the current range of nodes of path.

NumNodes

Return type: int

Returns the number of nodes in the underlying graph.

NumPaths

Return type: int

Returns the number of paths (empty paths included).

Path

Return type: int

Arguments: int node

Returns the committed path of a given node, -1 if it is a loop.

PathState

Arguments: 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).

Revert

Return type: void

Erase incremental changes. See class comment for details.

SetInvalid

Return type: void

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

Start

Return type: int

Arguments: int path

Returns the start of a path.