UE::Graph Namespace Reference

Classes
struct	FGraph
struct	FMappingManyToOne
struct	FMappingOneToMany

Typedefs
typedef int32	FVertex

Enumerations
enum class	EConvertToGraphOptions { None = 0 , Shrink = 1 << 0 }

Functions
FGraph	ConstructTransposeGraph (TConstArrayView< TConstArrayView< FVertex > > Graph, EConvertToGraphOptions Options)
bool	TryConstructCondensationGraph (TConstArrayView< TConstArrayView< FVertex > > Graph, FGraph &OutGraph, FMappingOneToMany *OutCondensationVertexToInputVertex, FMappingManyToOne *OutInputVertexToCondensedVertex, EConvertToGraphOptions Options)
FGraph	ConstructPartialTransposeGraph (TConstArrayView< TConstArrayView< FVertex > > Graph, TArrayView< FVertex > InVertices, int64 MaxOutGraphEdges, TArray< FVertex > &OutInputVerticesPresentInOutputGraph)
	ENUM_CLASS_FLAGS (EConvertToGraphOptions)
template<typename RangeType , typename GetKeyEdgesType >
FGraph	ConvertToGraph (const RangeType &UniqueKeys, GetKeyEdgesType GetKeyEdges, EConvertToGraphOptions Options=EConvertToGraphOptions::None)
template<typename RangeType , typename ProjectionType >
FGraph	ConvertToSingleBufferGraph (RangeType &&Graph, ProjectionType Proj, EConvertToGraphOptions Options=EConvertToGraphOptions::None)
template<typename RangeType >
FGraph	ConvertToSingleBufferGraph (RangeType Graph, EConvertToGraphOptions Options=EConvertToGraphOptions::None)

Variables
constexpr FVertex	MaxVertex = static_cast<FVertex>(MAX_int32-1)
constexpr FVertex	InvalidVertex = static_cast<FVertex>(INDEX_NONE)

Typedef Documentation

FVertex

typedef int32 UE::Graph::FVertex

Enumeration Type Documentation

EConvertToGraphOptions

enum class UE::Graph::EConvertToGraphOptions

strong

Enumerator
None
Shrink	The output buffer will be shrunk to reduce memory to minimum required.

Function Documentation

ConstructPartialTransposeGraph()

CORE_API FGraph UE::Graph::ConstructPartialTransposeGraph	(	TConstArrayView< TConstArrayView< FVertex > >	Graph,
		TArrayView< FVertex >	InVertices,
		int64	MaxOutGraphEdges,
		TArray< FVertex > &	OutInputVerticesPresentInOutputGraph
	)

Construct the TransposeGraph (see @ConstructTransposeGraph), but only include edges in the original graph from the given vertices (in the transpose graph, edges will be present to the given vertices). Additionally, limit the number of edges in the returned graph, and report which InVertices were added. This is used to create a partial ReachedBy graph from a large Reachability graph.

Parameters

InVertices	Vertices in the input graph, edges from which will be included in the output. This list will be modified: vertices will be sorted from largest number of edges to smallest.
OutInputVerticesPresentInOutputGraph	Output value. Populated with a list of which vertices from InVertices were used when constructing the output graph.

ConstructTransposeGraph()

CORE_API FGraph UE::Graph::ConstructTransposeGraph	(	TConstArrayView< TConstArrayView< FVertex > >	Graph,
		EConvertToGraphOptions	Options = EConvertToGraphOptions::None
	)

Return a new buffer and graph with the same vertices but with each edge reversed. If and only if (i,j) is an edge in the input Graph, (j,i) is an edge in the output TransposeGraph.

Parameters

Graph

A standard GraphConvert-format Graph.

See also

ConvertToGraph for a description of the format. Entries in these edges lists must themselves be valid indices into Graph.

Parameters

Options

for the conversion,

See also

EConvertToGraphOptions.

ConvertToGraph()

template<typename RangeType , typename GetKeyEdgesType >

FGraph UE::Graph::ConvertToGraph ( const RangeType &  UniqueKeys, GetKeyEdgesType  GetKeyEdges, EConvertToGraphOptions  Options = EConvertToGraphOptions::None  )

inline

Convert an array of Keys and a function that returns the directed edges from each Key into the Normalized Graph Form. Normalized Graph Form is an implicit set of vertices identified as integers from 0 to N - 1, and an array of arrayviews of edges from each vertex. The Normalized Graph form has two structures: The buffer which contains the memory storage for the graph and the graph itself which is the array of arrayviews of edges. The length of the array in the graph defines the number of vertices.

Parameters

UniqueKeys	A range with element type KeyType. KeyType must support GetTypeHash and copy+move constructors. KeyType being pointertype is recommended. Keys in the range must be unique. The ith element of the range will correspond to a vertex i in the OutGraph. UniqueKeys must have length < MAX_int32.
GetKeyEdges	A callable with prototype that is one of RangeType<KeyType> GetKeyEdges(const KeyType& Key); const RangeType<KeyType>& GetKeyEdges(const KeyType& Key); It must return the TargetKeys that are pointed to from the directed edges from Key. TargetKeys that are not elements of UniqueKeys will be discarded. TargetKeys equal to Key will also be discarded. RangeType must support ranged-for (begin() and end()).
Options	for the conversion,

See also

EConvertToGraphOptions.

Returns

Output value that holds the graph. See @FGraph for a description of the format. Vertex i in the graph corresponds to UniqueKeys[i].

ConvertToSingleBufferGraph() [1/2]

template<typename RangeType , typename ProjectionType >

FGraph UE::Graph::ConvertToSingleBufferGraph ( RangeType &&  Graph, ProjectionType  Proj, EConvertToGraphOptions  Options = EConvertToGraphOptions::None  )

inline

Convert an array of separately allocated edge ranges into a single buffer shared by all vertices and an edge graph of arrayviews into that buffer. No overlapping is done; every input edge range is reproduced in the output buffer. No validation or normalization is performed; the final edge lists may contain integers which are not valid indices into the graph, duplicates, etc.

Parameters

Graph	ArrayView of N vertices; each element is interpreted by the ProjectionType to return a range of edges for that vertex.
Proj	Returns the edges for Graph[n]. The prototype is // Input is either const& or by value. Output can be const&, &&, or by value. EdgeRangeType Proj(MultiBufferRangeType VertexEdges) EdgeRangeType must support GetData and GetNum.
Options	for the conversion,

See also

EConvertToGraphOptions.

ConvertToSingleBufferGraph() [2/2]

template<typename RangeType >

FGraph UE::Graph::ConvertToSingleBufferGraph ( RangeType  Graph, EConvertToGraphOptions  Options = EConvertToGraphOptions::None  )

inline

Convert an array of separately allocated edge ranges into a single buffer shared by all vertices and an edge graph of arrayviews into that buffer. No overlapping is done; every input edge range is reproduced in the output buffer. This version requires MultiBufferRange type to be a range type; see other prototype to provide a Projection.

Parameters

Graph	ArrayView of N vertices; each element is interpreted by the ProjectionType to return a range of edges for that vertex.
Options	for the conversion,

See also

EConvertToGraphOptions.

ENUM_CLASS_FLAGS()

UE::Graph::ENUM_CLASS_FLAGS

(

EConvertToGraphOptions

)

TryConstructCondensationGraph()

CORE_API bool UE::Graph::TryConstructCondensationGraph	(	TConstArrayView< TConstArrayView< FVertex > >	Graph,
		FGraph &	OutGraph,
		FMappingOneToMany *	OutCondensationVertexToInputVertex,
		FMappingManyToOne *	OutInputVertexToCondensationVertex,
		EConvertToGraphOptions	Options = EConvertToGraphOptions::None
	)

Return a new graph where cycles in the input graph have been replaced by a single vertex. The new graph is topologically sorted from root to leaf. If the input graph has no cycles, the function returns false and the OutGraph is reset to empty.

After conversion you can iterate over the OutCondensationVertexToInputVertex mapping to go through the map topologically.

Parameters

Graph

The input graph, may contain cycles.

See also

ConvertToGraph for a description of the format.

Parameters

OutGraph	Output value that holds the graph. It has no cycles and the vertices are topologically sorted from root to leaf.
OutCondensationVertexToInputVertex	Output value, optional, can be null. If non-null, it is populated with a mapping between the vertices in the condensation and the vertices in the input graph. See @FMappingOneToMany for a description of the format. Vertices in the condensation which correspond to input vertices which were not in a cycle map to single element. This value is populated even if the function returns false.
OutInputVertexToCondensationVertex	Output value, optional, can be null. If non-null, it is populated with a mapping from vertices in the input graph to vertices in the condensation. See @FMappingManyToOne for a description of the format.
Options	for the conversion,

See also

EConvertToGraphOptions.

Returns

True if the input graph had any cycles, false otherwise. If false is returned, OutGraph is reset to empty, but the other output variables are still populated if present.

Variable Documentation

InvalidVertex

constexpr FVertex UE::Graph::InvalidVertex = static_cast<FVertex>(INDEX_NONE)

inlineconstexpr

MaxVertex

constexpr FVertex UE::Graph::MaxVertex = static_cast<FVertex>(MAX_int32-1)

inlineconstexpr