graphcycles_test.cc | Explore in Territory

// Copyright 2017 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "absl/synchronization/internal/graphcycles.h"

#include <climits>
#include <map>
#include <random>
#include <unordered_set>
#include <utility>
#include <vector>

#include "gtest/gtest.h"
#include "absl/base/macros.h"
#include "absl/log/check.h"
#include "absl/log/log.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace synchronization_internal {

// We emulate a GraphCycles object with a node vector and an edge vector.
// We then compare the two implementations.

Nodes;
struct Edge { … };
Edges;
RandomEngine;

// Mapping from integer index to GraphId.
IdMap;
static GraphId Get(const IdMap& id, int num) { … }

// Return whether "to" is reachable from "from".
static bool IsReachable(Edges *edges, int from, int to,
                        std::unordered_set<int> *seen) { … }

static void PrintEdges(Edges *edges) { … }

static void PrintGCEdges(Nodes *nodes, const IdMap &id, GraphCycles *gc) { … }

static void PrintTransitiveClosure(Nodes *nodes, Edges *edges) { … }

static void PrintGCTransitiveClosure(Nodes *nodes, const IdMap &id,
                                     GraphCycles *gc) { … }

static void CheckTransitiveClosure(Nodes *nodes, Edges *edges, const IdMap &id,
                                   GraphCycles *gc) { … }

static void CheckEdges(Nodes *nodes, Edges *edges, const IdMap &id,
                       GraphCycles *gc) { … }

static void CheckInvariants(const GraphCycles &gc) { … }

// Returns the index of a randomly chosen node in *nodes.
// Requires *nodes be non-empty.
static int RandomNode(RandomEngine* rng, Nodes *nodes) { … }

// Returns the index of a randomly chosen edge in *edges.
// Requires *edges be non-empty.
static int RandomEdge(RandomEngine* rng, Edges *edges) { … }

// Returns the index of edge (from, to) in *edges or -1 if it is not in *edges.
static int EdgeIndex(Edges *edges, int from, int to) { … }

TEST(GraphCycles, RandomizedTest) { … }

class GraphCyclesTest : public ::testing::Test { … };

TEST_F(GraphCyclesTest, NoCycle) { … }

TEST_F(GraphCyclesTest, SimpleCycle) { … }

TEST_F(GraphCyclesTest, IndirectCycle) { … }

TEST_F(GraphCyclesTest, LongPath) { … }

TEST_F(GraphCyclesTest, RemoveNode) { … }

TEST_F(GraphCyclesTest, ManyEdges) { … }

TEST(GraphCycles, IntegerOverflow) { … }

}  // namespace synchronization_internal
ABSL_NAMESPACE_END
}  // namespace absl
chromium/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc
