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: ChainRange

Arguments: int path

Returns the current range of chains of path.

ChangedPaths

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

Returns the set of paths that actually changed, i.e. that have an arc in ChangedArcs().

ChangeNext

Return type: void

Arguments: int node, int new_next

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: void

Makes the current temporary state permanent, more formally, changes the state from (P0 |> D, D) to (P0 + D, \emptyset),

CutChains

Return type: void

Marks the end of ChangeNext() sequence, more formally, changes the state from (P0, D) to (P0 |> D, D).

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 made by ChangeNext() and CutChains(), more formally, changes the state from (P0 |> D, D) to (P0, \emptyset).

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.