Module omnitigs::hydrostructure::incremental_hydrostructure

An incremental implementation of the hydrostructure. Computes and stores the hydrostructure in linear time for a macrotig and all of its subwalks of length at least two.

Modules

• conjunctive_safety_tracker
  A type that combines two safety trackers under conjunction.
• node_centric_component_tracker
  A type that keeps counts of the nodes in the different hydrostructure components to dynamically determine if they contain nodes.
• river_is_non_empty_tracker
  A type that keeps counts about nodes and edges in the vapor to dynamically determine if the vapor is empty.
• size_one_scc_tracker
  A type that tracks if the river, sea or cloud contain an SCC of size one.
• vapor_is_path_tracker
  A type that keeps counts about nodes and edges in a subgraph to dynamically determine if the subgraph is a path.

Structs

• IncrementalHydrostructure
  The hydrostructure for a walk W. This hydrostructure implementation is incremental, meaning that it is valid for any subwalk of W. The subwalk can be adjusted using the left and right finger.

Traits

• IncrementalSafetyTracker
  An incremental safety tracker for the incremental hydrostructure.

Type Definitions

• BridgeLikeIncrementalHydrostructure
  An incremental hydrostructure that checks if a subwalk is bridge-like.
• MultiSafeIncrementalHydrostructure
  An incremental hydrostructure that checks if the node sequence (including the tail of the last arc and the head of the first arc) of a subwalk is safe in the node-visible node-covering multi-closed walk model.
• NodeBridgeLikeIncrementalHydrostructure
  An incremental hydrostructure that checks if the node sequence (including the tail of the last arc and the head of the first arc) of a subwalk is safe in the node-visible node-covering 1-closed walk model.