TarjanSccTests.cpp File Reference

#include <gtest/gtest.h>
#include <jlm/util/HashSet.hpp>
#include <jlm/util/TarjanScc.hpp>
#include <iostream>
#include <optional>
#include <tuple>
#include <vector>

Include dependency graph for TarjanSccTests.cpp:

Go to the source code of this file.

Functions
static size_t	Identity (size_t i)
template<typename UnificationRootFunctor , typename SuccessorFunctor >
static void	ValidateTopologicalOrderAndSccIndices (size_t numNodes, UnificationRootFunctor &unificationRoot, SuccessorFunctor &successors, size_t numSccs, const std::vector< size_t > &sccIndex, const std::vector< size_t > &reverseTopologicalOrder)
	TEST (TarjanSccTests, TestDag)
	TEST (TarjanSccTests, TestCycles)
static std::tuple< size_t, size_t, std::vector< size_t > >	CreateDiamondChain (size_t knots, std::optional< std::pair< size_t, size_t >> extraEdge)
	TEST (TarjanSccTests, TestSimpleDiamondChain)
	TEST (TarjanSccTests, TestDiamondChainWithForwardEdge)
	TEST (TarjanSccTests, TestDiamondChainWithBackEdge)
	TEST (TarjanSccTests, TestVisitEachNodeTwice)
	TEST (TarjanSccTests, TestUnifiedNodes)

Function Documentation

CreateDiamondChain()

static std::tuple<size_t, size_t, std::vector<size_t> > CreateDiamondChain ( size_t  knots, std::optional< std::pair< size_t, size_t >>  extraEdge  )

static

Creates a chain of diamonds, possibly with an extra edge. Performs SCC on the graph. The node indices are shuffled before being sent to the SCC algorithm.

Parameters

knots	The knots are the bottlenecks in the diamonds. All edges go that way ==> 1 4 etc. / \ / \ / 0 3 6 <- these are the knots \ / \ / \ 2 5 etc.
extraEdge	an optional extra edge going from first to second. If the extra edge is a forward edge (first < second), no cycles exist. If the extra edge is a back edge, there should be a single SCC with order > 1.

Returns

a pair: the number of nodes, the number of SCCs, and the sccIndex of each node, after un-shuffling

Definition at line 195 of file TarjanSccTests.cpp.

Identity()

static size_t Identity ( size_t  i )

static

Definition at line 18 of file TarjanSccTests.cpp.

TEST() [1/7]

TEST	(	TarjanSccTests	,
		TestCycles
	)

Definition at line 129 of file TarjanSccTests.cpp.

TEST() [2/7]

TEST	(	TarjanSccTests	,
		TestDag
	)

Definition at line 90 of file TarjanSccTests.cpp.

TEST() [3/7]

TEST	(	TarjanSccTests	,
		TestDiamondChainWithBackEdge
	)

Definition at line 268 of file TarjanSccTests.cpp.

TEST() [4/7]

TEST	(	TarjanSccTests	,
		TestDiamondChainWithForwardEdge
	)

Definition at line 260 of file TarjanSccTests.cpp.

TEST() [5/7]

TEST	(	TarjanSccTests	,
		TestSimpleDiamondChain
	)

Definition at line 254 of file TarjanSccTests.cpp.

TEST() [6/7]

TEST	(	TarjanSccTests	,
		TestUnifiedNodes
	)

Definition at line 336 of file TarjanSccTests.cpp.

TEST() [7/7]

TEST	(	TarjanSccTests	,
		TestVisitEachNodeTwice
	)

Definition at line 294 of file TarjanSccTests.cpp.

ValidateTopologicalOrderAndSccIndices()

template<typename UnificationRootFunctor , typename SuccessorFunctor >

static void ValidateTopologicalOrderAndSccIndices ( size_t  numNodes, UnificationRootFunctor &  unificationRoot, SuccessorFunctor &  successors, size_t  numSccs, const std::vector< size_t > &  sccIndex, const std::vector< size_t > &  reverseTopologicalOrder  )

static

Validation function checking that the found SCCs correspond to the successors:

• All sccIndex are between 0 and numSccs-1
• All SCCs contain at least one node
• All edges in the graph point to an sccIndex which is equal or lower
• The reverseTopologicalOrder contains all nodes, sorted by descending sccIndex

Definition at line 32 of file TarjanSccTests.cpp.