Skip to content

Game.Simulation.Flow.MaxFlowSolver

Assembly:
Assembly-CSharp

Namespace:
Game.Simulation.Flow

Type:
struct MaxFlowSolver

Base:
System.ValueType

Summary:
MaxFlowSolver is a native-memory based, layered max-flow solver used by the simulation to compute augmenting flows between a source and a sink in a directed flow network. It operates on arrays of Node, Edge and Connection structures using Unity.Collections primitives (NativeArray, NativeList, NativeQueue, UnsafeList). The solver organizes the graph into layers of cut elements and alternates between a labeling/preflow phase and active/retreat phases to advance flow from sink towards source. It is built for high performance inside the simulation and assumes the Node/Edge/Connection arrays are prepared externally. There is an absolute node limit defined by kMaxNodes.

Fields

  • public const int kMaxNodes
    Maximum supported number of nodes (16777216). Used as an upper bound / sentinel for some node height initialization.

  • public int m_LayerHeight
    Number of heights per layer. Used to map node heights into layer indices and determine layer ranges.

  • public int m_SourceNode
    Index of the source node in m_Nodes.

  • public int m_SinkNode
    Index of the sink node in m_Nodes.

  • public NativeArray<Node> m_Nodes
    NativeArray containing graph nodes. Nodes store height, excess, versioning and pointers to their connections.

  • public NativeArray<Edge> m_Edges
    NativeArray containing graph edges. Edges hold flow, capacity and a cut-element identifier for bookkeeping.

  • public NativeArray<Connection> m_Connections
    NativeArray of connection entries (adjacency entries). Connections reference start & end node indices and an edge index and direction.

  • public NativeList<Layer> m_Layers
    List of Layer objects used to store cut elements grouped by layer. Layers are created/cleared as the solver progresses.

  • public NativeQueue<int> m_LabelQueue
    Queue used during the labeling/preflow phase to propagate labels (heights) from newly discovered nodes.

  • public NativeArray<UnsafeList<int>> m_ActiveQueue
    Per-height active node queues used during the active advancing/retreat phases. Indexing is relative to m_LayerHeight.

  • public bool m_Complete
    Flag indicating if the solver has completed (no more layers to process).

  • public int m_CurrentLayerIndex
    Index of the currently processed layer.

  • public int m_NextLayerIndex
    Index of the next layer to be processed (may be updated dynamically while advancing).

  • public int m_CurrentLabelVersion
    Version counter for label/cut-element identifiers. Bumped to avoid stale identifiers across iterations.

  • public int m_CurrentActiveVersion
    Version counter for active node visitation to avoid revisiting nodes within the same pass.

  • public int m_StepCounter
    Instrumentation/counter tracking internal steps (useful for profiling or asserts).

Properties

  • (none)

Constructors

  • public MaxFlowSolver()
    Default struct constructor. The solver is a value type — fields must be initialized before use. Native containers referenced by fields must be allocated externally and assigned to the solver prior to calling API methods.

Methods

  • public void InitializeState()
    Builds the initial layer (layer 0) from the source node's outgoing connections. For each outgoing connection with residual capacity, a CutElement is created and registered, edge cut-element identifiers are set and the first layer is added to m_Layers. Resets solver flags and version counters used for labeling/active processing.

  • public void LoadState(NativeReference<MaxFlowSolverState> solverState, NativeList<LayerState> layerStates, NativeList<CutElement> layerElements, NativeList<CutElementRef> layerElementRefs)
    Loads a previously saved solver state (useful for pausing/resuming). Restores simple solver flags and then reconstructs layers by loading LayerState entries and associated cut element lists.

  • public void SaveState(NativeReference<MaxFlowSolverState> solverState, NativeList<LayerState> layerStates, NativeList<CutElement> layerElements, NativeList<CutElementRef> layerElementRefs)
    Saves the minimal solver state and serializes the current layers and their cut elements (unless the solver is complete). Clears and populates provided lists for persistence.

  • public void ResetNetwork()
    Resets nodes and edges in the assigned m_Nodes and m_Edges arrays and sets the source node height to 0. Clears excesses, cut-element ids and temporary flows. This is a convenience which delegates to the static ResetNetwork overload.

  • public static void ResetNetwork(NativeArray<Node> nodes, NativeArray<Edge> edges, int sourceNode)
    Static helper that iterates all nodes and edges to reset their persistent state (heights to sentinel, excess zero, versions zero, no cut element) and finalizes any temp flows on edges. The source node height is set to 0.

  • public void Solve()
    Runs the solver to completion by repeatedly calling SolveNextLayer while m_Complete is false.

  • public void SolveNextLayer()
    Process a single layer: gets the next layer, grows the layer list as needed, increments active-version counter and performs the label/preflow phase (LabelPreflow). If LabelPreflow indicates augmentations reached the source, AdvanceToSource is invoked, and if appropriate retreat processing (RetreatFromLayer) is done.

  • private bool LabelPreflow()
    Performs the labeling/preflow pass on the current layer. It processes changed/created cut elements, enqueues newly labeled nodes, propagates labels and creates/bumps cut elements in higher layers, and handles direct augmentations to the source (sending flow to active queue). Returns true if active augmentations were produced for the next active phase.

  • private void DeleteLinkedElements(int lowerLayerIndex, int index)
    Helper that deletes linked cut-element references from a given lower-layer cut element. Walks and marks referenced cut-elements in higher layers as deleted and frees their reference entries.

  • private int GetNodeValidLayerIndex(Node node)
    Checks whether a node's current height and cut-element id correspond to a valid cut element in the appropriate layer. Returns the layer index if valid; otherwise -1.

  • private void AddAdmissibleLayerCutElement(int lowerLayerIndex, int higherLayerIndex, in Connection lhConnection)
    Adds a newly discovered admissible cut element to a higher layer and creates a link from the lower layer element to it. Sets edge cut-element id and initial flags.

  • private void BumpAdmissibleLayerCutElement(int lowerLayerIndex, int higherLayerIndex, in Connection lhConnection)
    Re-activates (un-deletes) an existing admissible element in the higher layer and links it from the lower layer.

  • private void AddInadmissibleLayerCutElement(int lowerLayerIndex, int higherLayerIndex, in Connection lhConnection)
    Adds an inadmissible cut element to the higher layer that shares the same group as an existing end-node cut element. Links it from the lower layer.

  • private void BumpInadmissibleLayerCutElement(int lowerLayerIndex, int higherLayerIndex, in Connection lhConnection)
    Un-deletes and marks an inadmissible cut element in the higher layer; if it was previously admissible, flags it as changed and no longer admissible.

  • private void CreateElementLink(int lowerLayerIndex, int lowerElementIndex, int higherLayerIndex, int higherElementIndex)
    Creates a CutElementRef in the lower layer that points to a cut element in a higher layer and attaches it to the lower element's linked list.

  • private int AdvanceToSource()
    After LabelPreflow produced active augmentations, this walks layers from current down to source height, advances flow along active queues, performs consistency asserts, and returns a retreatLayerIndex used to decide retreat processing or label-version incrementing.

  • private void AdvanceActiveLayer(int activeLayerIndex, ref int retreatLayerIndex)
    Advances the active nodes for a single layer index: iterates per-height active queues from highest height down, attempts to push excess along incoming residual edges to nodes of height-1 (including the sink), finalizes temp flows and organizes next-layer active queues. Updates retreatLayerIndex if nodes remain with excess and need retreating later.

  • private void RetreatFromLayer(int retreatLayerIndex)
    When advancing cannot fully push, this method increments active-version and collects retreating nodes from the given layer that need to be processed, then calls RetreatActiveLayer across affected layers.

  • private void RetreatActiveLayer(int activeLayerIndex)
    Processes retreating nodes for a layer: distributes excess to branch and sink connections proportionally using temporary flow accounting, moves nodes to appropriate active queues, and marks cut elements as changed or deleted as necessary.

  • private void GetTotalAdvancedFlow(Node currentNode, int heightPlusOne, out int branchFlow, out int sinkFlow, out Connection sinkConnection)
    Sums the temporary flows for outgoing connections from currentNode that go to the next height (branch flow) and to the sink (sink flow). Used by retreat logic to allocate flows correctly.

  • private int GetLayerIndexForHeight(int height)
    Converts a node height to a layer index using m_LayerHeight. Height-to-layer mapping helper.

  • private int GetLowerCutHeight(int layerIndex)
    Returns the lowest node height covered by the given layer index.

  • private int GetUpperCutHeight(int layerIndex)
    Returns the highest node height covered by the given layer index.

  • private void FinalizeTempFlow(in Connection connection)
    Calls FinalizeTempFlow on the referenced edge to push temporary flow into the edge's persistent flow state.

  • private void AugmentOutgoingTempFlow(in Connection connection, int flow)
    Applies an outgoing augmentation along a connection by adjusting node excesses and edge temporary flow in the direction of the connection. Performs assertions to keep invariants (non-negative excess except at sink and valid edge flow bounds).

  • private void AugmentIncomingTempFlow(in Connection connection, int flow)
    Applies an incoming augmentation (pulling flow into end node) by adjusting node excesses and edge temp flow accordingly. Also asserts invariants.

  • private int GetOutgoingTempFlow(in Connection connection)
    Returns the signed temporary flow of the edge as viewed from the connection's direction (taking connection.m_Backwards into account).

  • private ref Node GetNode(int index)
    Small helper to get a reference to node at index from m_Nodes via ElementAt (fast, bounds-aware in NativeArray).

  • private ref Edge GetEdge(int index)
    Helper to get a reference to edge at index from m_Edges.

  • private Connection GetConnection(int index)
    Helper to get a Connection value from m_Connections.

  • private ref Layer GetLayer(int index)
    Helper to get a reference to Layer from m_Layers.

Usage Example

// Example usage sketch (pseudocode must be adapted to actual Node/Edge/Connection allocation)
MaxFlowSolver solver = new MaxFlowSolver();

// The caller is responsible for allocating and filling these Native containers:
solver.m_Nodes = /* NativeArray<Node> allocated & populated */;
solver.m_Edges = /* NativeArray<Edge> allocated & populated */;
solver.m_Connections = /* NativeArray<Connection> allocated & populated */;
solver.m_Layers = new NativeList<Layer>(Allocator.Temp);
solver.m_LabelQueue = new NativeQueue<int>(Allocator.Temp);
solver.m_ActiveQueue = new NativeArray<UnsafeList<int>>(solver.m_LayerHeight, Allocator.Temp);

// Set special nodes and layer height:
solver.m_SourceNode = sourceIndex;
solver.m_SinkNode = sinkIndex;
solver.m_LayerHeight = 16; // example choice

// Prepare network and solver state:
MaxFlowSolver.ResetNetwork(solver.m_Nodes, solver.m_Edges, solver.m_SourceNode);
solver.InitializeState();

// Run until complete:
solver.Solve();

// After completion, edge.flow (or Edge.flow property) contains the computed max flow values.
// Remember to dispose any Native containers allocated by the caller when done.

Notes: - The solver assumes the Node, Edge, Connection, Layer, CutElement and related structs/types match the data layout used by the simulation and that their methods (e.g., GetOutgoingResidualCapacity, FinalizeTempFlow, GetCapacity) are available. - Native containers must be allocated and disposed by the caller; many Layer instances are created with Allocator.Temp internally. - The solver uses version counters and strict assertions to enforce invariants — builds in defensive checks for correctness during development (UNITY_ASSERTIONS). - This implementation is specific to the simulation's multi-layer cut-element approach and is not a general-purpose, single-shot max-flow library; it is optimized for the simulation's incremental & layered flow progression.