xiiGraphAlgorithms Class Reference

#include <GraphAlgorithms.h>

Public Types
using	Visitor = xiiDelegate<bool(xiiGraphVertexHandle)>
	Return false from a visitor to stop successfully. Each reachable vertex is visited at most once.

Static Public Member Functions
static xiiResult	BreadthFirstTraversal (const xiiGraph &graph, xiiGraphVertexHandle hStart, Visitor visitor, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Copyright (c) Theophilus Eriata. All Rights Reserved.
static xiiResult	DepthFirstTraversal (const xiiGraph &graph, xiiGraphVertexHandle hStart, Visitor visitor, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
static bool	IsReachable (const xiiGraph &graph, xiiGraphVertexHandle hSource, xiiGraphVertexHandle hTarget, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Zero-length paths are reachable. Invalid/foreign endpoints are never reachable.
static xiiResult	TopologicalSort (const xiiGraph &graph, xiiDynamicArray< xiiGraphVertexHandle > &out_order, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Copyright (c) Theophilus Eriata. All Rights Reserved.
static bool	HasCycle (const xiiGraph &graph, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
static void	StronglyConnectedComponents (const xiiGraph &graph, xiiGraphComponents &out_components, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Iterative Kosaraju: vertices in a component are mutually reachable through directed edges.
static void	WeaklyConnectedComponents (const xiiGraph &graph, xiiGraphComponents &out_components, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Components when edge direction is ignored. An isolated vertex is a singleton component.
static xiiResult	FindShortestPath (const xiiGraph &graph, xiiGraphVertexHandle hSource, xiiGraphVertexHandle hTarget, xiiGraphPath &out_path, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	BFS shortest directed path, O(V + E), O(V) scratch. Failure clears output; source == target succeeds.
static xiiResult	FindLowestCostPath (const xiiGraph &graph, xiiGraphVertexHandle hSource, xiiGraphVertexHandle hTarget, xiiGraphEdgeWeight weight, xiiGraphPath &out_path, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Indexed-heap Dijkstra, O((V + E) log V), O(V) scratch. Examined weights must be finite and nonnegative.
static xiiResult	MaximumFlow (const xiiGraph &graph, xiiGraphVertexHandle hSource, xiiGraphVertexHandle hTarget, xiiGraphEdgeWeight capacity, xiiGraphFlow &out_flow, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Copyright (c) Theophilus Eriata. All Rights Reserved.
static xiiResult	MinimumSpanningForest (const xiiGraph &graph, xiiGraphSpanningForest &out_forest, xiiGraphEdgeWeight weight={}, xiiGraphAlgorithmWorkspace *pWorkspace=nullptr, xiiGraphEdgeFilter filter={})
	Copyright (c) Theophilus Eriata. All Rights Reserved.

Detailed Description

Iterative algorithms over xiiGraph's public connectivity interface. No recursion or permanent graph bookkeeping. Basic traversal/connectivity operations take O(V + E) time and O(V) auxiliary space; optimizations specify their bounds below. Outputs are replaced, retaining their allocations. Pass a workspace to reuse temporary allocations too. Without one, scratch uses the default allocator. The graph must remain unchanged throughout each call.

Member Function Documentation

BreadthFirstTraversal()

xiiResult xiiGraphAlgorithms::BreadthFirstTraversal ( const xiiGraph & graph, xiiGraphVertexHandle hStart, Visitor visitor, xiiGraphAlgorithmWorkspace * pWorkspace = nullptr, xiiGraphEdgeFilter filter = {} )

static

Copyright (c) Theophilus Eriata. All Rights Reserved.

Visit start and its reachable successors, following outgoing edges. Other components are not visited. Breadth first visits by nondecreasing distance; depth first visits in preorder. Adjacency is newest first. An invalid/foreign start or empty visitor returns XII_FAILURE without invoking the visitor.

MaximumFlow()

xiiResult xiiGraphAlgorithms::MaximumFlow ( const xiiGraph & graph, xiiGraphVertexHandle hSource, xiiGraphVertexHandle hTarget, xiiGraphEdgeWeight capacity, xiiGraphFlow & out_flow, xiiGraphAlgorithmWorkspace * pWorkspace = nullptr, xiiGraphEdgeFilter filter = {} )

static

Copyright (c) Theophilus Eriata. All Rights Reserved.

Edmonds-Karp, O(V + E + V E^2), O(V + E) scratch. Capacities must be finite/nonnegative; source and target must differ. Parallel and opposing edges have independent capacities; incoming edges provide residual reverse arcs.

MinimumSpanningForest()

xiiResult xiiGraphAlgorithms::MinimumSpanningForest ( const xiiGraph & graph, xiiGraphSpanningForest & out_forest, xiiGraphEdgeWeight weight = {}, xiiGraphAlgorithmWorkspace * pWorkspace = nullptr, xiiGraphEdgeFilter filter = {} )

static

Copyright (c) Theophilus Eriata. All Rights Reserved.

Kruskal, ignoring edge direction explicitly. O(E log E + V), O(V + E) scratch. Empty weight means unit weights. Disconnected/isolated vertices produce a forest; loops are ignored and parallel edges compete independently.

StronglyConnectedComponents()

void xiiGraphAlgorithms::StronglyConnectedComponents ( const xiiGraph & graph, xiiGraphComponents & out_components, xiiGraphAlgorithmWorkspace * pWorkspace = nullptr, xiiGraphEdgeFilter filter = {} )

static

Iterative Kosaraju: vertices in a component are mutually reachable through directed edges.

Copyright (c) Theophilus Eriata. All Rights Reserved.

TopologicalSort()

xiiResult xiiGraphAlgorithms::TopologicalSort ( const xiiGraph & graph, xiiDynamicArray< xiiGraphVertexHandle > & out_order, xiiGraphAlgorithmWorkspace * pWorkspace = nullptr, xiiGraphEdgeFilter filter = {} )

static

Copyright (c) Theophilus Eriata. All Rights Reserved.

Kahn's algorithm. Includes isolated vertices and disconnected components. Source precedes target for every edge. Returns XII_FAILURE and clears output on any cycle (including self-loops). Empty graphs succeed. Ready vertices use FIFO order seeded by GetVertices(); ties are otherwise unspecified.

---

The documentation for this class was generated from the following files:

• /home/runner/work/XII/XII/Source/Engine/Core/Graph/GraphAlgorithms.h
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphComponents.cpp
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphFlow.cpp
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphPaths.cpp
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphSpanningForest.cpp
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphTopology.cpp
• /home/runner/work/XII/XII/Source/Engine/Core/Graph/Implementation/GraphTraversal.cpp