DirectedGraphUtils.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreMinimal.h"
 
namespace UE::MathCore::Graph
{
    using FDirectedEdge = TTuple<int32, int32>;
 
    struct FStronglyConnectedComponent
    {
        TArray<int32> Vertices;
 
        TArray<FDirectedEdge> Edges;
    };
 
    struct FDirectedTreeElement
    {
        TArray<int32> Children;
    };
 
    using FDirectedTree = TMap<int32, FDirectedTreeElement>;
 
 
    MATHCORE_API void BuildDirectedTree(TArrayView<const FDirectedEdge> InEdges, FDirectedTree& OutTree);
 
    MATHCORE_API void BuildTransposeDirectedTree(TArrayView<const FDirectedEdge> InEdges, FDirectedTree& OutTree);
 
    MATHCORE_API void DepthFirstNodeTraversal(int32 InInitialVertex, const FDirectedTree& InTree, TFunctionRef<bool(int32)> InVisitFunc);
 
    MATHCORE_API void DepthFirstEdgeTraversal(int32 InInitialVertex, const FDirectedTree& InTree, TFunctionRef<bool(int32, int32)> InVisitFunc);
 
    MATHCORE_API void BreadthFirstNodeTraversal(int32 InInitialVertex, const FDirectedTree& InTree, TFunctionRef<bool(int32)> InVisitFunc);
 
    MATHCORE_API void BreadthFirstEdgeTraversal(int32 InInitialVertex, const FDirectedTree& InTree, TFunctionRef<bool(int32, int32)> InVisitFunc);
 
    MATHCORE_API void FindLeaves(int32 InInitialVertex, const FDirectedTree& InTree, TArray<int32>& OutLeafVertices);
 
    MATHCORE_API bool DepthFirstTopologicalSort(TArrayView<const int32> InUniqueVertices, TArrayView<const FDirectedEdge> InUniqueEdges, TArray<int32>& OutVertexOrder);
 
    MATHCORE_API bool KahnTopologicalSort(TArrayView<const int32> InUniqueVertices, TArrayView<const FDirectedEdge> InUniqueEdges, TArray<int32>& OutVertexOrder);
 
 
    MATHCORE_API bool TarjanStronglyConnectedComponents(const TSet<FDirectedEdge>& InEdges, TArray<FStronglyConnectedComponent>& OutComponents, bool bExcludeSingleVertex = true);
} // namespace UE::MathCore::Graph