d4/d82/test__kosaraju_8cc_source.html

/*

                          Aleph_w


  Data structures & Algorithms

  version 2.0.0b

  https://github.com/lrleon/Aleph-w


  This file is part of Aleph-w library


  Copyright (c) 2002-2026 Leandro Rabindranath Leon


  Permission is hereby granted, free of charge, to any person obtaining a copy

  of this software and associated documentation files (the "Software"), to deal

  in the Software without restriction, including without limitation the rights

  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

  copies of the Software, and to permit persons to whom the Software is

  furnished to do so, subject to the following conditions:


  The above copyright notice and this permission notice shall be included in all

  copies or substantial portions of the Software.


  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  SOFTWARE.

*/


#include <gtest/gtest.h>


#include <kosaraju.H>

#include <tpl_graph.H>

#include <Tarjan.H>


using namespace Aleph;


// Graph types for tests

using GT = List_Digraph<Graph_Node<int>, Graph_Arc<int>>;

using Node = GT::Node;

using Arc = GT::Arc;


// ========== Helper Functions ==========


// Create a simple chain: 0 -> 1 -> 2 -> ... -> (n-1)


GT create_chain(size_t n) {

  GT g;

  std::vector<Node*> nodes;

  for (size_t i = 0; i < n; ++i)

    nodes.push_back(g.insert_node(static_cast<int>(i)));

  for (size_t i = 0; i < n - 1; ++i)

    g.insert_arc(nodes[i], nodes[i + 1], static_cast<int>(i));

  return g;

}


// Create a cycle: 0 -> 1 -> 2 -> ... -> (n-1) -> 0


GT create_cycle(size_t n) {

  GT g;

  std::vector<Node*> nodes;

  for (size_t i = 0; i < n; ++i)

    nodes.push_back(g.insert_node(static_cast<int>(i)));

  for (size_t i = 0; i < n; ++i)

    g.insert_arc(nodes[i], nodes[(i + 1) % n], static_cast<int>(i));

  return g;

}


// Count total nodes across all SCCs


size_t count_total_nodes(const DynList<DynList<Node*>>& sccs) {

  size_t count = 0;

  for (const auto& scc : sccs)

    count += scc.size();

  return count;

}


// ========== TEST 1: Empty Graph ==========


TEST(KosarajuTest, EmptyGraph) {

  GT g;


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 0u);

}


// ========== TEST 2: Single Node ==========


TEST(KosarajuTest, SingleNode) {

  GT g;

  g.insert_node(0);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 1u);

}


// ========== TEST 3: Single Node with Self-Loop ==========


TEST(KosarajuTest, SingleNodeWithSelfLoop) {

  GT g;

  Node* n = g.insert_node(0);

  g.insert_arc(n, n, 0);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 1u);

}


// ========== TEST 4: Two Disconnected Nodes ==========


TEST(KosarajuTest, TwoDisconnectedNodes) {

  GT g;

  g.insert_node(0);

  g.insert_node(1);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 2u);

  size_t total = count_total_nodes(sccs);

  ASSERT_EQ(total, 2u);

}


// ========== TEST 5: Simple Chain (No SCC) ==========


TEST(KosarajuTest, SimpleChain) {

  GT g = create_chain(5);


  auto sccs = kosaraju_connected_components(g);


  // Each node is its own SCC (no cycles)

  ASSERT_EQ(sccs.size(), 5u);

}


// ========== TEST 6: Simple Cycle (Single SCC) ==========


TEST(KosarajuTest, SimpleCycle) {

  GT g = create_cycle(5);


  auto sccs = kosaraju_connected_components(g);


  // All nodes form one SCC

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 5u);

}


// ========== TEST 7: Two Separate Cycles ==========


TEST(KosarajuTest, TwoSeparateCycles) {

  GT g;


  // Cycle 1: 0 -> 1 -> 2 -> 0

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n2, 1);

  g.insert_arc(n2, n0, 2);


  // Cycle 2: 3 -> 4 -> 3

  Node* n3 = g.insert_node(3);

  Node* n4 = g.insert_node(4);

  g.insert_arc(n3, n4, 3);

  g.insert_arc(n4, n3, 4);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 2u);

  size_t total = count_total_nodes(sccs);

  ASSERT_EQ(total, 5u);

}


// ========== TEST 8: Two Cycles Connected by One Arc ==========


TEST(KosarajuTest, TwoCyclesConnectedByOneArc) {

  GT g;


  // Cycle 1: 0 -> 1 -> 0

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n0, 1);


  // Cycle 2: 2 -> 3 -> 2

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);

  g.insert_arc(n2, n3, 2);

  g.insert_arc(n3, n2, 3);


  // Cross arc: 1 -> 2 (makes two SCCs)

  g.insert_arc(n1, n2, 4);


  auto sccs = kosaraju_connected_components(g);


  // Still 2 SCCs because there's no path from cycle 2 back to cycle 1

  ASSERT_EQ(sccs.size(), 2u);

}


// ========== TEST 9: Two Cycles Connected Bidirectionally ==========


TEST(KosarajuTest, TwoCyclesConnectedBidirectionally) {

  GT g;


  // Cycle 1: 0 -> 1 -> 0

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n0, 1);


  // Cycle 2: 2 -> 3 -> 2

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);

  g.insert_arc(n2, n3, 2);

  g.insert_arc(n3, n2, 3);


  // Cross arcs in both directions

  g.insert_arc(n1, n2, 4);

  g.insert_arc(n3, n0, 5);


  auto sccs = kosaraju_connected_components(g);


  // Now all 4 nodes are in one SCC

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 4u);

}


// ========== TEST 10: Classic Example from CLRS ==========


TEST(KosarajuTest, ClassicCLRSExample) {

  // This is the classic example from CLRS (Cormen et al.)

  // Graph with 8 nodes and specific SCCs

  GT g;


  Node* a = g.insert_node(0); // a

  Node* b = g.insert_node(1); // b

  Node* c = g.insert_node(2); // c

  Node* d = g.insert_node(3); // d

  Node* e = g.insert_node(4); // e

  Node* f = g.insert_node(5); // f

  Node* h = g.insert_node(6); // h (renamed from g to avoid conflict)

  Node* i = g.insert_node(7); // i (renamed from h)


  // Arcs

  g.insert_arc(a, b, 0);

  g.insert_arc(b, c, 1);

  g.insert_arc(c, a, 2); // SCC 1: {a, b, c}


  g.insert_arc(b, e, 3);

  g.insert_arc(c, d, 4);


  g.insert_arc(d, e, 5);

  g.insert_arc(e, f, 6);

  g.insert_arc(f, d, 7); // SCC 2: {d, e, f}


  g.insert_arc(f, h, 8);

  g.insert_arc(h, i, 9);

  g.insert_arc(i, h, 10); // SCC 3: {h, i}


  auto sccs = kosaraju_connected_components(g);


  // Should have 3 SCCs

  ASSERT_EQ(sccs.size(), 3u);

  ASSERT_EQ(count_total_nodes(sccs), 8u);

}


// ========== TEST 11: Subgraph Version ==========


TEST(KosarajuTest, SubgraphVersion) {

  GT g;


  // Create two SCCs

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);


  // SCC 1: 0 <-> 1

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n0, 1);


  // SCC 2: 2 <-> 3

  g.insert_arc(n2, n3, 2);

  g.insert_arc(n3, n2, 3);


  // Cross arc: 1 -> 2

  Arc* cross = g.insert_arc(n1, n2, 4);


  DynList<GT> blk_list;

  DynList<Arc*> arc_list;

  kosaraju_connected_components(g, blk_list, arc_list);


  ASSERT_EQ(blk_list.size(), 2u);

  ASSERT_EQ(arc_list.size(), 1u);

  ASSERT_EQ(arc_list.get_first(), cross);


  // Verify each subgraph

  for (auto& blk : blk_list)

    {

      ASSERT_EQ(blk.get_num_nodes(), 2u);

      ASSERT_EQ(blk.get_num_arcs(), 2u);

    }

}


// ========== TEST 12: Cross Arc List Correctness ==========


TEST(KosarajuTest, CrossArcListCorrectness) {

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);


  // SCC 1: {0}

  // SCC 2: {1}

  // SCC 3: {2}


  Arc* a01 = g.insert_arc(n0, n1, 0);

  Arc* a12 = g.insert_arc(n1, n2, 1);

  Arc* a02 = g.insert_arc(n0, n2, 2);


  DynList<GT> blk_list;

  DynList<Arc*> arc_list;

  kosaraju_connected_components(g, blk_list, arc_list);


  ASSERT_EQ(blk_list.size(), 3u);

  ASSERT_EQ(arc_list.size(), 3u);


  // All arcs should be cross arcs

  bool found_a01 = false, found_a12 = false, found_a02 = false;

  for (auto a : arc_list) {

    if (a == a01) found_a01 = true;

    if (a == a12) found_a12 = true;

    if (a == a02) found_a02 = true;

  }


  ASSERT_TRUE(found_a01);

  ASSERT_TRUE(found_a12);

  ASSERT_TRUE(found_a02);

}


// ========== TEST 13: is_strongly_connected True Case ==========


TEST(KosarajuTest, IsStronglyConnectedTrue) {

  GT g = create_cycle(5);


  ASSERT_TRUE(is_strongly_connected(g));

}


// ========== TEST 14: is_strongly_connected False Case ==========


TEST(KosarajuTest, IsStronglyConnectedFalse) {

  GT g = create_chain(5);


  ASSERT_FALSE(is_strongly_connected(g));

}


// ========== TEST 15: is_strongly_connected Empty Graph ==========


TEST(KosarajuTest, IsStronglyConnectedEmpty) {

  GT g;


  ASSERT_TRUE(is_strongly_connected(g));

}


// ========== TEST 16: is_strongly_connected Single Node ==========


TEST(KosarajuTest, IsStronglyConnectedSingleNode) {

  GT g;

  g.insert_node(0);


  ASSERT_TRUE(is_strongly_connected(g));

}


// ========== TEST 17: kosaraju_scc_count ==========


TEST(KosarajuTest, SccCount) {

  GT g;


  // Create 4 separate SCCs

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);


  g.insert_arc(n0, n1, 0);

  g.insert_arc(n2, n3, 1);


  ASSERT_EQ(kosaraju_scc_count(g), 4u);

}


// ========== TEST 18: Functor Interface ==========


TEST(KosarajuTest, FunctorInterface) {

  GT g = create_cycle(3);


  Kosaraju_Connected_Components<GT> functor;


  // Test list version

  auto sccs = functor(g);

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 3u);


  // Test subgraph version

  DynList<GT> blk_list;

  DynList<Arc*> arc_list;

  functor(g, blk_list, arc_list);

  ASSERT_EQ(blk_list.size(), 1u);

  ASSERT_EQ(arc_list.size(), 0u);

}


// ========== TEST 19: Large Chain ==========


TEST(KosarajuTest, LargeChain) {

  GT g = create_chain(100);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 100u);

}


// ========== TEST 20: Large Cycle ==========


TEST(KosarajuTest, LargeCycle) {

  GT g = create_cycle(100);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 100u);

}


// ========== TEST 21: Node Mapping Correctness ==========


TEST(KosarajuTest, NodeMappingCorrectness) {

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n0, 1);


  DynList<GT> blk_list;

  DynList<Arc*> arc_list;

  kosaraju_connected_components(g, blk_list, arc_list);


  ASSERT_EQ(blk_list.size(), 1u);


  // Verify mapping

  GT& blk = blk_list.get_first();

  for (typename GT::Node_Iterator it(blk); it.has_curr(); it.next())

    {

      auto blk_node = it.get_curr();

      auto orig_node = mapped_node<GT>(blk_node);

      ASSERT_NE(orig_node, nullptr);

      ASSERT_EQ(blk_node->get_info(), orig_node->get_info());

    }

}


// ========== TEST 22: Arc Mapping Correctness ==========


TEST(KosarajuTest, ArcMappingCorrectness) {

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Arc* a01 = g.insert_arc(n0, n1, 10);

  Arc* a10 = g.insert_arc(n1, n0, 20);


  DynList<GT> blk_list;

  DynList<Arc*> arc_list;

  kosaraju_connected_components(g, blk_list, arc_list);


  GT& blk = blk_list.get_first();


  // Verify arc count matches

  ASSERT_EQ(blk.get_num_arcs(), 2u);


  // Verify original arcs are mapped to block arcs

  auto blk_a01 = mapped_arc<GT>(a01);

  auto blk_a10 = mapped_arc<GT>(a10);

  ASSERT_NE(blk_a01, nullptr);

  ASSERT_NE(blk_a10, nullptr);


  // Verify the block arcs are different

  ASSERT_NE(blk_a01, blk_a10);

}


// ========== TEST 23: Diamond Graph ==========


TEST(KosarajuTest, DiamondGraph) {

  /*

   *     0

   *    / \

   *   1   2

   *    \ /

   *     3

   */

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);


  g.insert_arc(n0, n1, 0);

  g.insert_arc(n0, n2, 1);

  g.insert_arc(n1, n3, 2);

  g.insert_arc(n2, n3, 3);


  auto sccs = kosaraju_connected_components(g);


  // No cycles, each node is its own SCC

  ASSERT_EQ(sccs.size(), 4u);

}


// ========== TEST 24: Complete Digraph (K4) ==========


TEST(KosarajuTest, CompleteDigraph) {

  GT g;


  std::vector<Node*> nodes;

  for (int i = 0; i < 4; ++i)

    nodes.push_back(g.insert_node(i));


  // Add all directed edges

  for (int i = 0; i < 4; ++i)

    for (int j = 0; j < 4; ++j)

      if (i != j)

        g.insert_arc(nodes[i], nodes[j], i * 10 + j);


  auto sccs = kosaraju_connected_components(g);


  // Complete digraph is strongly connected

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 4u);

}


// ========== TEST 25: Multiple Self-Loops ==========


TEST(KosarajuTest, MultipleSelfLoops) {

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);


  g.insert_arc(n0, n0, 0);

  g.insert_arc(n1, n1, 1);

  g.insert_arc(n2, n2, 2);


  auto sccs = kosaraju_connected_components(g);


  // Each node is its own SCC (self-loops don't connect nodes)

  ASSERT_EQ(sccs.size(), 3u);

}


// ========== TEST 26: Tree Structure ==========


TEST(KosarajuTest, TreeStructure) {

  /*

   *      0

   *     / \

   *    1   2

   *   / \

   *  3   4

   */

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);

  Node* n4 = g.insert_node(4);


  g.insert_arc(n0, n1, 0);

  g.insert_arc(n0, n2, 1);

  g.insert_arc(n1, n3, 2);

  g.insert_arc(n1, n4, 3);


  auto sccs = kosaraju_connected_components(g);


  // Tree has no cycles, each node is its own SCC

  ASSERT_EQ(sccs.size(), 5u);

}


// ========== TEST 27: Comparison with Tarjan ==========


TEST(KosarajuTest, CompareWithTarjan) {

  GT g;


  // Create a moderately complex graph

  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);

  Node* n4 = g.insert_node(4);


  g.insert_arc(n0, n1, 0);

  g.insert_arc(n1, n2, 1);

  g.insert_arc(n2, n0, 2);

  g.insert_arc(n2, n3, 3);

  g.insert_arc(n3, n4, 4);

  g.insert_arc(n4, n3, 5);


  auto kosaraju_sccs = kosaraju_connected_components(g);


  // Use Tarjan for comparison

  DynList<DynList<Node*>> tarjan_sccs;

  Tarjan_Connected_Components<GT>().connected_components(g, tarjan_sccs);


  // Both should find the same number of SCCs

  ASSERT_EQ(kosaraju_sccs.size(), tarjan_sccs.size());

}


// ========== TEST 28: Stress Test ==========


TEST(KosarajuTest, StressTest) {

  GT g;

  const size_t N = 500;


  std::vector<Node*> nodes;

  for (size_t i = 0; i < N; ++i)

    nodes.push_back(g.insert_node(static_cast<int>(i)));


  // Create a large cycle

  for (size_t i = 0; i < N; ++i)

    g.insert_arc(nodes[i], nodes[(i + 1) % N], static_cast<int>(i));


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), N);

}


// ========== TEST 29: Graph with Isolated Nodes and SCCs ==========


TEST(KosarajuTest, IsolatedNodesAndSCCs) {

  GT g;


  // Isolated nodes

  g.insert_node(0);

  g.insert_node(1);


  // SCC: 2 <-> 3

  Node* n2 = g.insert_node(2);

  Node* n3 = g.insert_node(3);

  g.insert_arc(n2, n3, 0);

  g.insert_arc(n3, n2, 1);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 3u);

}


// ========== TEST 30: Parallel Arcs ==========


TEST(KosarajuTest, ParallelArcs) {

  GT g;


  Node* n0 = g.insert_node(0);

  Node* n1 = g.insert_node(1);


  // Multiple arcs in same direction

  g.insert_arc(n0, n1, 0);

  g.insert_arc(n0, n1, 1);

  g.insert_arc(n1, n0, 2);


  auto sccs = kosaraju_connected_components(g);


  // Both nodes in same SCC (there's a cycle)

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 2u);

}


// ========== TEST 31: Dense Graph Performance ==========


TEST(KosarajuTest, DenseGraphPerformance) {

  GT g;

  const size_t N = 100;

  std::vector<Node*> nodes;


  for (size_t i = 0; i < N; ++i)

    nodes.push_back(g.insert_node(static_cast<int>(i)));


  // Create complete digraph (every node connects to every other node)

  for (size_t i = 0; i < N; ++i)

    for (size_t j = 0; j < N; ++j)

      if (i != j)

        g.insert_arc(nodes[i], nodes[j], static_cast<int>(i * N + j));


  auto sccs = kosaraju_connected_components(g);


  // Complete digraph is strongly connected (one SCC)

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), N);

}


// ========== TEST 32: Multiple Self-Loops on Same Node ==========


TEST(KosarajuTest, MultipleLoopsOnSameNode) {

  GT g;

  Node* n = g.insert_node(0);


  // Add multiple self-loops on the same node

  g.insert_arc(n, n, 0);

  g.insert_arc(n, n, 1);

  g.insert_arc(n, n, 2);


  auto sccs = kosaraju_connected_components(g);


  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 1u);

}


// ========== TEST 33: Nodes Without Any Arcs ==========


TEST(KosarajuTest, NodesWithoutArcs) {

  GT g;

  const size_t N = 10;


  // Insert nodes without any arcs

  for (size_t i = 0; i < N; ++i)

    g.insert_node(static_cast<int>(i));


  auto sccs = kosaraju_connected_components(g);


  // Each node is its own SCC

  ASSERT_EQ(sccs.size(), N);

  for (auto& scc : sccs)

    ASSERT_EQ(scc.size(), 1u);

}


// ========== TEST 34: Fully Bidirectional Graph ==========


TEST(KosarajuTest, FullyBidirectionalGraph) {

  GT g;


  std::vector<Node*> nodes;

  for (int i = 0; i < 5; ++i)

    nodes.push_back(g.insert_node(i));


  // Create a path with bidirectional edges (every edge has its reverse)

  for (size_t i = 0; i < 4; ++i) {

    g.insert_arc(nodes[i], nodes[i+1], static_cast<int>(i));

    g.insert_arc(nodes[i+1], nodes[i], static_cast<int>(i+10));

  }


  auto sccs = kosaraju_connected_components(g);


  // All nodes should be in one SCC (can reach each other)

  ASSERT_EQ(sccs.size(), 1u);

  ASSERT_EQ(sccs.get_first().size(), 5u);

}


// ========== TEST 35: Transposed Cycle Correctness ==========


TEST(KosarajuTest, TransposedCycleCorrectness) {

  // Verify that transposition doesn't create spurious cycles

  // Graph: 0 → 1 → 2 → 3 (no cycles in original)

  // Transposed: 0 ← 1 ← 2 ← 3 (still no cycles)

  GT g = create_chain(4);


  auto sccs = kosaraju_connected_components(g);


  // Should still be 4 SCCs (each node is its own SCC)

  ASSERT_EQ(sccs.size(), 4u);


  // Verify each SCC has exactly one node

  for (auto& scc : sccs)

    ASSERT_EQ(scc.size(), 1u);

}


// ========== GoogleTest main ==========


int main(int argc, char **argv)

{

  ::testing::InitGoogleTest(&argc, argv);

  return RUN_ALL_TESTS();

}


Tarjan.H
Tarjan's algorithm for strongly connected components.

main
int main()
Definition ah_parallel_example.cc:690

Node
WeightedDigraph::Node Node
Definition bellman_ford_example.cc:140

Arc
WeightedDigraph::Arc Arc
Definition bellman_ford_example.cc:141

h
long double h
Definition btreepic.C:154

Aleph::Digraph
Generic directed graph (digraph) wrapper template.
Definition graph-dry.H:3848

Aleph::Digraph::Arc
typename BaseGraph::Arc Arc
Definition graph-dry.H:3852

Aleph::Digraph::Node
typename BaseGraph::Node Node
Definition graph-dry.H:3851

Aleph::DynList
Dynamic singly linked list with functional programming support.
Definition htlist.H:1423

Aleph::DynList::get_first
T & get_first() const
Return the first item of the list.
Definition htlist.H:1675

Aleph::HTList::size
size_t size() const noexcept
Count the number of elements of the list.
Definition htlist.H:1319

Aleph::List_Graph< Graph_Node< int >, Graph_Arc< int > >

Aleph::List_Graph::insert_node
virtual Node * insert_node(Node *node) noexcept
Insertion of a node already allocated.
Definition tpl_graph.H:524

Aleph::List_Graph::insert_arc
Arc * insert_arc(Node *src_node, Node *tgt_node, void *a)
Definition tpl_graph.H:604

TEST
#define TEST(name)
Definition disjoint_sparse_table_test.cc:95

N
#define N
Definition fib.C:294

nodes
DynArray< Graph::Node * > nodes
Definition graphpic.C:406

Aleph::kosaraju_connected_components
void kosaraju_connected_components(const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list)
Compute strongly connected components using Kosaraju's algorithm.
Definition kosaraju.H:210

Aleph::kosaraju_scc_count
size_t kosaraju_scc_count(const GT &g)
Count the number of strongly connected components.
Definition kosaraju.H:381

Aleph::is_strongly_connected
bool is_strongly_connected(const GT &g)
Check if a directed graph is strongly connected.
Definition kosaraju.H:402

kosaraju.H
Kosaraju's algorithm for finding strongly connected components.

Aleph
Main namespace for Aleph-w library functions.
Definition ah-arena.H:89

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

Aleph::count
Itor::difference_type count(const Itor &beg, const Itor &end, const T &value)
Count elements equal to a value.
Definition ahAlgo.H:127

Aleph::Graph_Arc
Arc of graph implemented with double-linked adjacency lists.
Definition tpl_graph.H:222

Aleph::Kosaraju_Connected_Components
Functor wrapper for Kosaraju's algorithm.
Definition kosaraju.H:343

count_total_nodes
size_t count_total_nodes(const DynList< DynList< Node * > > &sccs)
Definition test_kosaraju.cc:83

create_cycle
GT create_cycle(size_t n)
Definition test_kosaraju.cc:72

create_chain
GT create_chain(size_t n)
Definition test_kosaraju.cc:61

tpl_graph.H
Generic graph and digraph implementations.