scc_test.cc

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// -*- mode: C++ -*-
//
// Copyright 2020-2022 Google LLC
//
// Licensed under the Apache License v2.0 with LLVM Exceptions (the
// "License"); you may not use this file except in compliance with the
// License.  You may obtain a copy of the License at
//
//     https://llvm.org/LICENSE.txt
//
// 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.
//
// Author: Giuliano Procida

#include "scc.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <map>
#include <optional>
#include <random>
#include <set>
#include <sstream>
#include <utility>
#include <vector>

#include <catch2/catch.hpp>

namespace Test {

using stg::SCC;

// Nodes are [0, N), the sets are the out-edges.
typedef std::vector<std::set<size_t>> Graph;

template <typename G>
Graph invent(size_t n, G& gen) {
  Graph graph(n);
  std::uniform_int_distribution<int> toss(0, 1);
  for (auto& node : graph) {
    for (size_t o = 0; o < n; ++o) {
      if (toss(gen)) {
        node.insert(o);
      }
    }
  }
  return graph;
}

// Generate a graph g' where i -> j iff i and j are strongly connected in g.
Graph symmetric_subset_of_reflexive_transitive_closure(Graph g) {
  const size_t n = g.size();
  // compute reflexive, transitive closure using a modified Floyd-Warshall
  for (size_t o = 0; o < n; ++o) {
    // 1. add edge o -> o, for each node o
    g[o].insert(o);
  }
  for (size_t k = 0; k < n; ++k) {
    // 2. for each node k check for paths of the form: i -> ... -> k -> ... -> j
    // where no node after k appears in the ...
    for (size_t i = 0; i < n; ++i) {
      // since we scan the nodes k in order, it suffices to consider just paths:
      // i -> k -> j
      if (g[i].count(k)) {
        // we have i -> k
        for (size_t j = 0; j < n; ++j) {
          if (g[k].count(j)) {
            // and k -> j
            g[i].insert(j);
          }
        }
      }
    }
  }
  // now have edge i -> j iff there is a path from i to j
  for (size_t i = 0; i < n; ++i) {
    for (size_t j = i + 1; j < n; ++j) {
      // discard i -> j if not j -> i and vice versa
      auto ij = g[i].count(j);
      auto ji = g[j].count(i);
      if (ij < ji) {
        g[j].erase(i);
      }
      if (ji < ij) {
        g[i].erase(j);
      }
    }
  }
  // now have edge i -> j iff there is a path from i to j and a path from j to i
  return g;
}

// Generate a graph where i -> j iff i and j are in the same SCC.
Graph scc_strong_connectivity(const std::vector<std::set<size_t>>& sccs) {
  size_t n = 0;
  std::map<size_t, const std::set<size_t>*> edges;
  for (const auto& scc : sccs) {
    for (auto o : scc) {
      if (o >= n) {
        n = o + 1;
      }
      edges[o] = &scc;
    }
  }
  Graph g(n);
  for (size_t o = 0; o < n; ++o) {
    g[o] = *edges[o];
  }
  return g;
}

void dfs(std::set<size_t>& visited, SCC<size_t>& scc, const Graph& g,
         size_t node, std::vector<std::set<size_t>>& sccs) {
  if (visited.count(node)) {
    return;
  }
  auto handle = scc.Open(node);
  if (!handle) {
    return;
  }
  for (auto o : g[node]) {
    dfs(visited, scc, g, o, sccs);
  }
  auto nodes = scc.Close(*handle);
  if (!nodes.empty()) {
    std::set<size_t> scc_set;
    for (auto o : nodes) {
      CHECK(visited.insert(o).second);
      CHECK(scc_set.insert(o).second);
    }
    sccs.push_back(scc_set);
  }
}

void process(const Graph& g) {
  const size_t n = g.size();

  // find SCCs
  std::set<size_t> visited;
  std::vector<std::set<size_t>> sccs;
  for (size_t o = 0; o < n; ++o) {
    // could reuse a single SCC finder but assert stronger invariants this way
    SCC<size_t> scc;
    dfs(visited, scc, g, o, sccs);
    CHECK(scc.Empty());
  }

  // check partition and topological order properties
  std::set<size_t> seen;
  for (const auto& nodes : sccs) {
    CHECK(!nodes.empty());
    for (auto node : nodes) {
      // value in range [0, n)
      CHECK(node < n);
      // value seen at most once
      CHECK(seen.insert(node).second);
    }
    for (auto node : nodes) {
      for (auto o : g[node]) {
        // edges point to nodes in this or earlier SCCs
        CHECK(seen.count(o));
      }
    }
  }
  // exactly n values seen
  CHECK(seen.size() == n);

  // check strong connectivity
  auto g_scc_closure = scc_strong_connectivity(sccs);
  auto g_closure = symmetric_subset_of_reflexive_transitive_closure(g);
  CHECK(g_scc_closure == g_closure);
}

TEST_CASE("randomly-generated graphs") {
  std::ranlux48 gen;
  auto seed = gen();
  // NOTES:
  //   Graphs of size 6 are plenty big enough to shake out bugs.
  //   There are O(2^k^2) possible directed graphs of size k.
  //   Testing costs are O(k^3) so we restrict accordingly.
  uint64_t budget = 10000;
  for (size_t k = 0; k < 7; ++k) {
    uint64_t count = std::min(static_cast<uint64_t>(1) << (k * k),
                              budget / (k ? k * k * k : 1));
    INFO("testing with " << count << " graphs of size " << k);
    for (uint64_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      Graph g = invent(k, gen);
      std::ostringstream os;
      os << "a graph of " << k << " nodes generated using seed " << seed;
      GIVEN(os.str()) {
        process(g);
      }
    }
  }
}

}  // namespace Test