GraphConvert.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "Algo/Sort.h"
#include "Algo/Unique.h"
#include "Containers/Array.h"
#include "Containers/ArrayView.h"
#include "Containers/Map.h"
#include "HAL/Platform.h"
#include "Misc/AssertionMacros.h"
#include "Misc/EnumClassFlags.h"
#include "Templates/IdentityFunctor.h"
#include "Templates/Invoke.h"
#include "Traits/ElementType.h"
 
#include <utility>
 
namespace UE::Graph
{
 
typedef int32 FVertex;
// Valid vertices are in the range 0 <= vertex < MAX_int32.
// This ensures that a edge list that contains an edge to every vertex from 0 to MaxVertex inclusive in a graph can be stored in
// a TArray or TArrayView.
inline constexpr FVertex MaxVertex = static_cast<FVertex>(MAX_int32-1);
inline constexpr FVertex InvalidVertex = static_cast<FVertex>(INDEX_NONE);
 
struct FGraph
{
    // Singular buffer which each element of EdgeLists is a view into.
    TArray64<FVertex> Buffer;
    // Each member of EdgeLists is a slice of Buffer.
    TArray<TConstArrayView<FVertex>> EdgeLists;
 
    FGraph() = default;
    // Copy construction not implemented as buffers may be very large and expensive to copy
    FGraph(const FGraph&) = delete;
    FGraph& operator=(const FGraph&) = delete;
    FGraph(FGraph&&) = default;
    FGraph& operator=(FGraph&&) = default;
 
    SIZE_T GetAllocatedSize() const 
    {
        return Buffer.GetAllocatedSize() + EdgeLists.GetAllocatedSize();
    }
};
 
struct FMappingOneToMany 
{
    TArray64<FVertex> Buffer;
    TArray<TConstArrayView<FVertex>> Mapping;
 
    FMappingOneToMany() = default;
    // Copy construction not implemented as buffers may be very large and expensive to copy
    FMappingOneToMany(const FMappingOneToMany&) = delete;
    FMappingOneToMany& operator=(const FMappingOneToMany&) = delete;
    FMappingOneToMany(FMappingOneToMany&&) = default;
    FMappingOneToMany& operator=(FMappingOneToMany&&) = default;
    
    SIZE_T GetAllocatedSize() const 
    {
        return Buffer.GetAllocatedSize() + Mapping.GetAllocatedSize();
    }
};
 
struct FMappingManyToOne
{
    TArray<FVertex> Mapping;
 
    FMappingManyToOne() = default;
    FMappingManyToOne(const FMappingManyToOne&) = default;
    FMappingManyToOne& operator=(const FMappingManyToOne&) = default;
    FMappingManyToOne(FMappingManyToOne&&) = default;
    FMappingManyToOne& operator=(FMappingManyToOne&&) = default;
 
    SIZE_T GetAllocatedSize() const 
    {
        return Mapping.GetAllocatedSize();
    }
};
 
enum class EConvertToGraphOptions
{
    None = 0,
    Shrink = 1 << 0,
};
ENUM_CLASS_FLAGS(EConvertToGraphOptions);
 
template <typename RangeType, typename GetKeyEdgesType>
inline FGraph ConvertToGraph(
    const RangeType& UniqueKeys,
    GetKeyEdgesType GetKeyEdges,
    EConvertToGraphOptions Options = EConvertToGraphOptions::None)
{
    using KeyType = TElementType_T<RangeType>;
 
    // Map Elements to vertices in VertexOfKey
    int32 NumVertices = GetNum(UniqueKeys);
    TMap<KeyType, FVertex> VertexOfKey;
    VertexOfKey.Reserve(NumVertices);
    FVertex Vertex = 0;
    for (const KeyType& Key : UniqueKeys)
    {
        FVertex& ExistingHandle = VertexOfKey.FindOrAdd(Key, InvalidVertex);
        check(ExistingHandle == InvalidVertex);
        if (ExistingHandle == InvalidVertex)
        {
            ExistingHandle = Vertex++;
        }
    }
 
    FGraph OutGraph;
    OutGraph.Buffer.Reset();
    if (EnumHasAnyFlags(Options, EConvertToGraphOptions::Shrink))
    {
        OutGraph.EdgeLists.Empty(NumVertices);
    }
    else
    {
        OutGraph.EdgeLists.Reset(NumVertices);
    }
 
    // Temporary base pointer for edge lists until the data pointer of OutGraph.Buffer is fixed. 
    FVertex* EdgeListBase = nullptr;
    // Call GetKeyEdges on each Element, map its returnvalue to Vertices, normalize them, and store them in EdgeOffsets
    Vertex = 0;
    for (const KeyType& Element : UniqueKeys)
    {
        int64 InitialOffset = OutGraph.Buffer.Num();
        for (const KeyType& Dependency : Invoke(GetKeyEdges, Element))
        {
            FVertex* TargetVertex = VertexOfKey.Find(Dependency);
            if (!TargetVertex)
            {
                continue;
            }
 
            // Normalize Step 1: remove edges to self
            if (*TargetVertex == Vertex)
            {
                continue;
            }
            OutGraph.Buffer.Add(*TargetVertex);
        }
 
        // Normalize Step 2: Sort
        TArrayView64<FVertex> VertexEdges = TArrayView64<FVertex>(OutGraph.Buffer).Mid(InitialOffset);
        Algo::Sort(VertexEdges);
 
        // Normalize Step 3: Remove duplicates
        VertexEdges = VertexEdges.Left(Algo::Unique(VertexEdges));
        OutGraph.Buffer.SetNum(InitialOffset + VertexEdges.Num(), EAllowShrinking::No);
 
        // Store the vertex's offset into GraphBuffer, for later fixup
        // Edge list is guaranteed to fit within 32 bits after removal of duplicates
        OutGraph.EdgeLists.Emplace(EdgeListBase + InitialOffset, static_cast<int32>(VertexEdges.Num())); //-V769
 
        ++Vertex;
    }
    if (EnumHasAnyFlags(Options, EConvertToGraphOptions::Shrink))
    {
        OutGraph.Buffer.Shrink();
    }
 
    // Correct data pointers in edge lists 
    FVertex* NewBase = OutGraph.Buffer.GetData();
    for (TConstArrayView<FVertex>& EdgeList : OutGraph.EdgeLists)
    {
        EdgeList = TConstArrayView<FVertex>(NewBase + (EdgeList.GetData() - EdgeListBase), EdgeList.Num());
    }
    return OutGraph;
}
 
template <typename RangeType, typename ProjectionType>
inline FGraph ConvertToSingleBufferGraph(
    RangeType&& Graph,
    ProjectionType Proj,
    EConvertToGraphOptions Options = EConvertToGraphOptions::None)
{
    typedef TElementType_T<RangeType> InEdgeRangeType;
    typedef decltype(Proj(std::declval<const InEdgeRangeType&>())) ProjectedEdgeRangeType;
 
    int32 NumVertices = Graph.Num();
    int64 NumEdges = 0;
    for (const InEdgeRangeType& VertexEdges : Graph)
    {
        NumEdges += GetNum(Proj(VertexEdges));
    }
 
    FGraph OutGraph;
    if (EnumHasAnyFlags(Options, EConvertToGraphOptions::Shrink))
    {
        OutGraph.Buffer.Empty(NumEdges);
        OutGraph.EdgeLists.Empty(NumVertices);
    }
    else
    {
        OutGraph.Buffer.Reset(NumEdges);
        OutGraph.EdgeLists.Reset(NumVertices);
    }
 
    FVertex* OutBufferData = OutGraph.Buffer.GetData();
    for (const InEdgeRangeType& InVertexEdges : Graph)
    {
        ProjectedEdgeRangeType VertexEdges = Proj(InVertexEdges);
        int32 NumVertexEdges = GetNum(VertexEdges);
        OutGraph.EdgeLists.Emplace(OutBufferData + OutGraph.Buffer.Num(), NumVertexEdges);
        OutGraph.Buffer.Append(GetData(VertexEdges), NumVertexEdges);
    }
    check(OutGraph.Buffer.GetData() == OutBufferData); // We have arrayviews into OutBufferData
    return OutGraph;    
}
 
template <typename RangeType>
inline FGraph ConvertToSingleBufferGraph(RangeType Graph, 
    EConvertToGraphOptions Options = EConvertToGraphOptions::None)
{
    return ConvertToSingleBufferGraph(Graph, FIdentityFunctor(), Options);
}
 
CORE_API FGraph ConstructTransposeGraph(
    TConstArrayView<TConstArrayView<FVertex>> Graph,
    EConvertToGraphOptions Options = EConvertToGraphOptions::None);
 
 
CORE_API bool TryConstructCondensationGraph(
    TConstArrayView<TConstArrayView<FVertex>> Graph,
    FGraph& OutGraph,
    FMappingOneToMany* OutCondensationVertexToInputVertex,
    FMappingManyToOne* OutInputVertexToCondensationVertex,
    EConvertToGraphOptions Options = EConvertToGraphOptions::None);
 
CORE_API FGraph ConstructPartialTransposeGraph(
    TConstArrayView<TConstArrayView<FVertex>> Graph,
    TArrayView<FVertex> InVertices,
    int64 MaxOutGraphEdges,
    TArray<FVertex>& OutInputVerticesPresentInOutputGraph);
}