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: Arguments: Returns the current range of chains of path. |
ChangedLoops | Return type: Returns the set of loops that were added by the change. |
ChangedPaths | Return type: Returns the set of paths that actually changed, i.e. that have more than one chain. |
ChangeLoops | Return type: Arguments: Describes the nodes that are newly loops in this change. |
ChangePath | Return type: Arguments: 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: Arguments: Same as above, but the initializer_list interface avoids the need to pass a vector. |
Commit | Return type: Set the current state G1 as committed. See class comment for details. |
CommittedIndex | Return type: Arguments: |
CommittedPathRange | Return type: Arguments: |
End | Return type: Arguments: Returns the end of a path. |
IsInvalid | Return type: |
Nodes | Return type: Arguments: Returns the current range of nodes of path. |
NumNodes | Return type: Returns the number of nodes in the underlying graph. |
NumPaths | Return type: Returns the number of paths (empty paths included). |
Path | Return type: Arguments: Returns the committed path of a given node, -1 if it is a loop. |
PathState | Arguments: Path constructor: path_start and path_end must be disjoint, their values in [0, num_nodes). |
Revert | Return type: Erase incremental changes. See class comment for details. |
SetInvalid | Return type: LNS Operators may not fix variables, in which case we mark the candidate invalid. |
Start | Return type: Arguments: Returns the start of a path. |