#include <DirectedGraphAlgo.h>

Static Public Member Functions
static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API void	BuildDirectedTree (TArrayView< const FDirectedEdge > InEdges, FDirectedTree &OutTree)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API void	BuildTransposeDirectedTree (TArrayView< const FDirectedEdge > InEdges, FDirectedTree &OutTree)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API void	DepthFirstTraversal (int32 InInitialVertex, const FDirectedTree &InTree, TFunctionRef< bool(int32)> InVisitFunc)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API void	BreadthFirstTraversal (int32 InInitialVertex, const FDirectedTree &InTree, TFunctionRef< bool(int32)> InVisitFunc)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API bool	DepthFirstTopologicalSort (TArrayView< const int32 > InUniqueVertices, TArrayView< const FDirectedEdge > InUniqueEdges, TArray< int32 > &OutVertexOrder)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API bool	KahnTopologicalSort (TArrayView< const int32 > InUniqueVertices, TArrayView< const FDirectedEdge > InUniqueEdges, TArray< int32 > &OutVertexOrder)

PRAGMA_ENABLE_DEPRECATION_WARNINGS static PRAGMA_DISABLE_DEPRECATION_WARNINGS SIGNALPROCESSING_API bool	TarjanStronglyConnectedComponents (const TSet< FDirectedEdge > &InEdges, TArray< FStronglyConnectedComponent > &OutComponents, bool bExcludeSingleVertex=true)

Member Function Documentation

◆ BreadthFirstTraversal()

void Audio::FDirectedGraphAlgo::BreadthFirstTraversal	(	int32	InInitialVertex,
		const FDirectedTree &	InTree,
		TFunctionRef< bool(int32)>	InVisitFunc
	)

static

Traverse a tree in a breadth first ordering.

Parameters

InInitialVertex	- The starting vertex for traversal.
InTree	- The tree structure to traverse.
InVisitFunc	- A function that is called for each vertex that is visited. If this function returns true, the children of this vertex will be visited in the future. If this function returns false, then the children of the current vertex will not be visited.

◆ BuildDirectedTree()

void Audio::FDirectedGraphAlgo::BuildDirectedTree	(	TArrayView< const FDirectedEdge >	InEdges,
		FDirectedTree &	OutTree
	)

static

Build a directed tree from an array of edges.

@parma InEdges - An array of directed eges.

Parameters

OutTree - A tree structure built from the edges.

◆ BuildTransposeDirectedTree()

void Audio::FDirectedGraphAlgo::BuildTransposeDirectedTree	(	TArrayView< const FDirectedEdge >	InEdges,
		FDirectedTree &	OutTree
	)

static

Build a transpose directed tree from an array of edges.

The transpose of a directed graph is created by reversing each edge.

@parma InEdges - An array of directed eges.

Parameters

OutTree - A tree structure built from the reversed edges.

◆ DepthFirstTopologicalSort()

bool Audio::FDirectedGraphAlgo::DepthFirstTopologicalSort	(	TArrayView< const int32 >	InUniqueVertices,
		TArrayView< const FDirectedEdge >	InUniqueEdges,
		TArray< int32 > &	OutVertexOrder
	)

static

Sort vertices topologically using a depth first sorting algorithm.

Parameters

InUniqueVertices	- An array of vertices to sort.
InUniqueEdges	- An array of edges describing dependencies.
OutVertexOrder	- An array where ordered vertices are placed.

Returns: True if sorting was successful. False otherwise.

◆ DepthFirstTraversal()

void Audio::FDirectedGraphAlgo::DepthFirstTraversal	(	int32	InInitialVertex,
		const FDirectedTree &	InTree,
		TFunctionRef< bool(int32)>	InVisitFunc
	)

static

Traverse a tree in a depth first ordering.

Parameters

InInitialVertex	- The starting vertex for traversal.
InTree	- The tree structure to traverse.
InVisitFunc	- A function that is called for each vertex that is visited. If this function returns true, traversal is continued in a depth first manner. If this function returns false, the children of the current vertex are not visited.

◆ KahnTopologicalSort()

bool Audio::FDirectedGraphAlgo::KahnTopologicalSort	(	TArrayView< const int32 >	InUniqueVertices,
		TArrayView< const FDirectedEdge >	InUniqueEdges,
		TArray< int32 > &	OutVertexOrder
	)

static

Sort vertices topologically using a Kahn's sorting algorithm.

Parameters

InUniqueVertices	- An array of vertices to sort.
InUniqueEdges	- An array of edges describing dependencies.
OutVertexOrder	- An array where ordered vertices are placed.

Returns: True if sorting was successful. False otherwise.

◆ TarjanStronglyConnectedComponents()

bool Audio::FDirectedGraphAlgo::TarjanStronglyConnectedComponents	(	const TSet< FDirectedEdge > &	InEdges,
		TArray< FStronglyConnectedComponent > &	OutComponents,
		bool	bExcludeSingleVertex = `true`
	)

static

Find strongly connected components given a set of edges using Tarjan algorithm.

Parameters

InEdges	- Edges in the directed graph.
OutComponents	- Strongly connected components found in the graph are be added to this array.
bExcludeSingleVertex	- If true, single vertices are not be returned as strongly connected components. If false, single vertices may be returned as strongly connected components.

Returns: True if one or more strongly connected components are added to OutComponents. False otherwise.

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

Engine/Source/Runtime/SignalProcessing/Public/DSP/DirectedGraphAlgo.h
Engine/Source/Runtime/SignalProcessing/Private/DirectedGraphAlgo.cpp

Static Public Member Functions

Member Function Documentation

◆ BreadthFirstTraversal()

◆ BuildDirectedTree()

◆ BuildTransposeDirectedTree()

◆ DepthFirstTopologicalSort()

◆ DepthFirstTraversal()

◆ KahnTopologicalSort()

◆ TarjanStronglyConnectedComponents()