C++ Reference: class PathState
This documentation is automatically generated.
A PathState represents a set of paths and changed 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.
Let us define some notions on graphs with the same set of nodes: tails(D) is the set of nodes that are the tail of some arc of D. P0 inter P1 is the graph of all arcs both in P0 and P1. P0 union P1 is the graph of all arcs either in P0 or P1. P1 - P0 is the graph with arcs in P1 and not in P0. P0 |> D is the graph with arcs of P0 whose tail is not in tails(D). P0 + D is (P0 |> D) union D.
Now suppose P0 and P1 are P-graphs. P0 + (P1 - P0) is exactly P1. Moreover, note that P0 |> D is not a union of paths from some starts[i] to ends[i] and loops like P0, because the operation removes arcs from P0. P0 |> D is a union of generic paths, loops, and isolated nodes. Let us call the generic paths and isolated nodes "chains". Then the paths of P0 + D are chains linked by arcs of D. Those chains are particularly interesting when examining a P-graph change.
A PathState represents a P-graph for a fixed {num_nodes, starts, ends}. The value of a PathState can be changed incrementally from P0 to P1 by passing the arcs of P1 - P0 to ChangeNext() and marking the end of the change with a call to CutChains(). If P0 + D is not a P-graph, the behaviour is undefined. TODO(user): check whether we want to have a DCHECK that P0 + D is a P-graph or if CutChains() should return false.
After CutChains(), tails(D) can be traversed using an iterator, and the chains of P0 |> D can be browsed by chain-based iterators. An iterator allows to browse the set of paths that have changed. Then Commit() or Revert() can be called: Commit() changes the PathState to represent P1 = P0 + D, all further changes are made from P1; Revert() changes the PathState to forget D completely and return the state to P0.
After a Commit(), Revert() or at initial state, the same iterators are available and represent the change by an empty D: the set of changed paths and the set of changed nodes is empty. Still, the chain-based iterator allows to browse paths: each path has exactly one chain.
| Method | |
|---|---|
Chains | Return type: Arguments: Returns the current range of chains of path. |
ChangedPaths | Return type: Returns the set of paths that actually changed, i.e. that have an arc in ChangedArcs(). |
ChangeNext | Return type: Arguments: Adds arc (node, new_next) to the changed state, more formally, changes the state from (P0, D) to (P0, D + (node, new_next)). |
Commit | Return type: Makes the current temporary state permanent, more formally, changes the state from (P0 |> D, D) to (P0 + D, \emptyset), |
CutChains | Return type: Marks the end of ChangeNext() sequence, more formally, changes the state from (P0, D) to (P0 |> D, D). |
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 made by ChangeNext() and CutChains(), more formally, changes the state from (P0 |> D, D) to (P0, \emptyset). |
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. |