test_triangle_count.cpp

/**
 * @file test_triangle_count.cpp
 * @brief Tests for triangle counting algorithm
 */

#include <catch2/catch_test_macros.hpp>
#include <catch2/catch_template_test_macros.hpp>
#include <graph/algorithm/tc.hpp>
#include <graph/container/undirected_adjacency_list.hpp>
#include <graph/container/traits/vos_graph_traits.hpp>
#include <graph/container/traits/uos_graph_traits.hpp>
#include <graph/container/traits/dos_graph_traits.hpp>
#include "../common/graph_fixtures.hpp"
#include "../common/algorithm_test_types.hpp"

using namespace graph;
using namespace graph::container;

// Graph type with sorted edges (required for triangle_count)
using vos_void = vos_graph<>;

// Undirected adjacency list (automatically handles bidirectional edges)
using ual_int = undirected_adjacency_list<int, int>;

//=============================================================================
// Basic Triangle Tests
//=============================================================================

TEST_CASE("triangle_count - empty graph", "[algorithm][triangle_count]") {
  vos_void g;
  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - single vertex", "[algorithm][triangle_count]") {
  vos_void g;
  g.resize_vertices(1);
  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - two vertices no edge", "[algorithm][triangle_count]") {
  vos_void g;
  g.resize_vertices(2);
  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - two vertices with edge", "[algorithm][triangle_count]") {
  // Each undirected edge needs both directions
  vos_void g({{0, 1}, {1, 0}});
  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - single triangle", "[algorithm][triangle_count]") {
  // Triangle: 0-1-2-0 (each undirected edge stored as two directed edges)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}});
  REQUIRE(triangle_count(g) == 1);
}

//=============================================================================
// Multiple Triangles
//=============================================================================

TEST_CASE("triangle_count - complete graph K4", "[algorithm][triangle_count]") {
  // Complete graph on 4 vertices: all pairs connected bidirectionally
  // Has C(4,3) = 4 triangles
  vos_void g({{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}});

  REQUIRE(triangle_count(g) == 4);
}

TEST_CASE("triangle_count - two separate triangles", "[algorithm][triangle_count]") {
  // Triangle 1: 0-1-2, Triangle 2: 3-4-5
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}, {3, 4}, {4, 3}, {4, 5}, {5, 4}, {3, 5}, {5, 3}});

  REQUIRE(triangle_count(g) == 2);
}

TEST_CASE("triangle_count - two triangles sharing edge", "[algorithm][triangle_count]") {
  // Triangle 1: 0-1-2, Triangle 2: 0-1-3 (share edge 0-1)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}, {1, 3}, {3, 1}, {0, 3}, {3, 0}});

  REQUIRE(triangle_count(g) == 2);
}

TEST_CASE("triangle_count - two triangles sharing vertex", "[algorithm][triangle_count]") {
  // Triangle 1: 0-1-2, Triangle 2: 0-3-4 (share vertex 0)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {3, 4}, {4, 3}, {0, 4}, {4, 0}});

  REQUIRE(triangle_count(g) == 2);
}

//=============================================================================
// Graphs with No Triangles
//=============================================================================

TEST_CASE("triangle_count - path graph (no triangles)", "[algorithm][triangle_count]") {
  // Path: 0-1-2-3-4
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - cycle graph (no triangles)", "[algorithm][triangle_count]") {
  // Cycle: 0-1-2-3-4-0
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 0}, {0, 4}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - star graph (no triangles)", "[algorithm][triangle_count]") {
  // Star: center vertex 0 connected to all others (no triangles)
  vos_void g({{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {0, 4}, {4, 0}, {0, 5}, {5, 0}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - bipartite graph (no triangles)", "[algorithm][triangle_count]") {
  // Complete bipartite K(3,3): {0,1,2} to {3,4,5} (no triangles)
  vos_void g({{0, 3},
              {3, 0},
              {0, 4},
              {4, 0},
              {0, 5},
              {5, 0},
              {1, 3},
              {3, 1},
              {1, 4},
              {4, 1},
              {1, 5},
              {5, 1},
              {2, 3},
              {3, 2},
              {2, 4},
              {4, 2},
              {2, 5},
              {5, 2}});

  REQUIRE(triangle_count(g) == 0);
}

//=============================================================================
// Complex Structures
//=============================================================================

TEST_CASE("triangle_count - diamond graph", "[algorithm][triangle_count]") {
  // Diamond: 0 at top, 1,2 in middle (connected), 3 at bottom
  vos_void g({{0, 1}, {1, 0}, {0, 2}, {2, 0}, {1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}});

  REQUIRE(triangle_count(g) == 2); // {0,1,2} and {1,2,3}
}

TEST_CASE("triangle_count - wheel graph", "[algorithm][triangle_count]") {
  // Wheel: center vertex 0, rim vertices 1-5 forming cycle
  vos_void g({{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {0, 4}, {4, 0}, {0, 5}, {5, 0},
              {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 5}, {5, 4}, {5, 1}, {1, 5}});

  REQUIRE(triangle_count(g) == 5); // One triangle for each rim edge with center
}

TEST_CASE("triangle_count - house graph", "[algorithm][triangle_count]") {
  // House: square base (0-1-2-3) + triangular roof (0-4-1)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 0}, {0, 3}, {0, 4}, {4, 0}, {4, 1}, {1, 4}});

  REQUIRE(triangle_count(g) == 1); // Only {0,1,4}
}

//=============================================================================
// Graph Type Variations
//=============================================================================

TEST_CASE("triangle_count - single triangle vos", "[algorithm][triangle_count]") {
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}});

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - K4 vos", "[algorithm][triangle_count]") {
  vos_void g({{0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0}, {1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}});

  REQUIRE(triangle_count(g) == 4);
}

//=============================================================================
// Edge Cases
//=============================================================================

TEST_CASE("triangle_count - graph with isolated vertices", "[algorithm][triangle_count]") {
  // Triangle 0-1-2 plus isolated vertices 3,4,5,6
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}});
  g.resize_vertices(7); // Add isolated vertices

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - graph with self-loops ignored", "[algorithm][triangle_count]") {
  // Triangle with self-loops (self-loops don't contribute to triangles)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}, {0, 0}, {1, 1}}); // Self-loops

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - chordal cycle", "[algorithm][triangle_count]") {
  // 5-cycle with chord 0-2: creates one triangle {0,1,2}
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 0}, {0, 4}, {0, 2}, {2, 0}});

  REQUIRE(triangle_count(g) == 1); // Only {0,1,2}
}

//=============================================================================
// undirected_adjacency_list Tests (no manual bidirectional edges needed)
//=============================================================================

TEST_CASE("triangle_count - UAL single triangle", "[algorithm][triangle_count][ual]") {
  // Triangle: 0-1-2-0 (only specify once, automatic bidirectional)
  // Using initializer list constructor like dynamic_graph
  ual_int g({{0, 1, 0}, {1, 2, 0}, {0, 2, 0}});

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - UAL complete graph K4", "[algorithm][triangle_count][ual]") {
  // Complete graph on 4 vertices has C(4,3) = 4 triangles
  // Only need to specify each edge once (automatic bidirectional)
  ual_int g({{0, 1, 0}, {0, 2, 0}, {0, 3, 0}, {1, 2, 0}, {1, 3, 0}, {2, 3, 0}});

  REQUIRE(triangle_count(g) == 4);
}

TEST_CASE("triangle_count - UAL two separate triangles", "[algorithm][triangle_count][ual]") {
  // Triangle 1: 0-1-2, Triangle 2: 3-4-5
  ual_int g({{0, 1, 0}, {1, 2, 0}, {0, 2, 0}, {3, 4, 0}, {4, 5, 0}, {3, 5, 0}});

  REQUIRE(triangle_count(g) == 2);
}

TEST_CASE("triangle_count - UAL path graph (no triangles)", "[algorithm][triangle_count][ual]") {
  // Path: 0-1-2-3-4
  ual_int g({{0, 1, 0}, {1, 2, 0}, {2, 3, 0}, {3, 4, 0}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - UAL star graph (no triangles)", "[algorithm][triangle_count][ual]") {
  // Star: center vertex 0 connected to all others
  ual_int g({{0, 1, 0}, {0, 2, 0}, {0, 3, 0}, {0, 4, 0}, {0, 5, 0}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - UAL diamond graph", "[algorithm][triangle_count][ual]") {
  // Diamond: 0 at top, 1,2 in middle (connected), 3 at bottom
  ual_int g({{0, 1, 0}, {0, 2, 0}, {1, 2, 0}, {1, 3, 0}, {2, 3, 0}});

  REQUIRE(triangle_count(g) == 2); // {0,1,2} and {1,2,3}
}

TEST_CASE("triangle_count - UAL wheel graph", "[algorithm][triangle_count][ual]") {
  // Wheel: center vertex 0, rim vertices 1-5 forming cycle
  ual_int g(
        {{0, 1, 0}, {0, 2, 0}, {0, 3, 0}, {0, 4, 0}, {0, 5, 0}, {1, 2, 0}, {2, 3, 0}, {3, 4, 0}, {4, 5, 0}, {5, 1, 0}});

  REQUIRE(triangle_count(g) == 5); // One triangle for each rim edge with center
}

TEST_CASE("triangle_count - UAL graph with isolated vertices", "[algorithm][triangle_count][ual]") {
  // Triangle: 0-1-2, vertices 3-6 isolated
  ual_int g({{0, 1, 0}, {1, 2, 0}, {0, 2, 0}});
  // Note: Isolated vertices 3-6 don't need to be created explicitly
  // The initializer list constructor only creates vertices up to max edge vertex id

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - UAL bipartite graph (no triangles)", "[algorithm][triangle_count][ual]") {
  // Complete bipartite K(3,3): {0,1,2} to {3,4,5}
  ual_int g({{0, 3, 0}, {0, 4, 0}, {0, 5, 0}, {1, 3, 0}, {1, 4, 0}, {1, 5, 0}, {2, 3, 0}, {2, 4, 0}, {2, 5, 0}});

  REQUIRE(triangle_count(g) == 0);
}

// =============================================================================
// Sparse (mapped) graph tests — mos_weighted (map + ordered set edges)
// =============================================================================

using namespace graph::test::algorithm;

TEST_CASE("triangle_count - sparse single triangle", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Triangle: 10-20-30 (bidirectional, sorted edges via set)
  Graph g({{10, 20, 1}, {20, 10, 1}, {20, 30, 1}, {30, 20, 1}, {10, 30, 1}, {30, 10, 1}});

  REQUIRE(triangle_count(g) == 1);
}

TEST_CASE("triangle_count - sparse K4", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Complete graph K4 with sparse IDs: 10,20,30,40
  Graph g({
    {10, 20, 1}, {20, 10, 1}, {10, 30, 1}, {30, 10, 1}, {10, 40, 1}, {40, 10, 1},
    {20, 30, 1}, {30, 20, 1}, {20, 40, 1}, {40, 20, 1}, {30, 40, 1}, {40, 30, 1}
  });

  REQUIRE(triangle_count(g) == 4);
}

TEST_CASE("triangle_count - sparse path (no triangles)", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Path: 10-20-30-40-50 (bidirectional)
  Graph g({{10, 20, 1}, {20, 10, 1}, {20, 30, 1}, {30, 20, 1},
           {30, 40, 1}, {40, 30, 1}, {40, 50, 1}, {50, 40, 1}});

  REQUIRE(triangle_count(g) == 0);
}

TEST_CASE("triangle_count - sparse diamond", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Diamond: 10 top, {20,30} middle connected, 40 bottom
  Graph g({{10, 20, 1}, {20, 10, 1}, {10, 30, 1}, {30, 10, 1},
           {20, 30, 1}, {30, 20, 1}, {20, 40, 1}, {40, 20, 1}, {30, 40, 1}, {40, 30, 1}});

  REQUIRE(triangle_count(g) == 2); // {10,20,30} and {20,30,40}
}

TEST_CASE("triangle_count - sparse two separate triangles", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Triangle 1: 10-20-30, Triangle 2: 100-200-300
  Graph g({{10, 20, 1}, {20, 10, 1}, {20, 30, 1}, {30, 20, 1}, {10, 30, 1}, {30, 10, 1},
           {100, 200, 1}, {200, 100, 1}, {200, 300, 1}, {300, 200, 1}, {100, 300, 1}, {300, 100, 1}});

  REQUIRE(triangle_count(g) == 2);
}

TEST_CASE("triangle_count - sparse star (no triangles)", "[algorithm][triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Star: center=10, leaves=20,30,40,50,60
  Graph g({{10, 20, 1}, {20, 10, 1}, {10, 30, 1}, {30, 10, 1},
           {10, 40, 1}, {40, 10, 1}, {10, 50, 1}, {50, 10, 1}, {10, 60, 1}, {60, 10, 1}});

  REQUIRE(triangle_count(g) == 0);
}

// =============================================================================
// Directed Triangle Count Tests
// =============================================================================

TEST_CASE("directed_triangle_count - empty graph", "[algorithm][directed_triangle_count]") {
  vos_void g;
  REQUIRE(directed_triangle_count(g) == 0);
}

TEST_CASE("directed_triangle_count - single directed 3-cycle", "[algorithm][directed_triangle_count]") {
  // Directed cycle: 0->1, 1->2, 0->2 (one directed 3-cycle)
  vos_void g({{0, 1}, {1, 2}, {0, 2}});
  REQUIRE(directed_triangle_count(g) == 1);
}

TEST_CASE("directed_triangle_count - missing one edge (no 3-cycle)", "[algorithm][directed_triangle_count]") {
  // Only 0->1, 1->2 — no edge from 0 to 2, so no 3-cycle
  vos_void g({{0, 1}, {1, 2}});
  REQUIRE(directed_triangle_count(g) == 0);
}

TEST_CASE("directed_triangle_count - two directed 3-cycles from same vertices", "[algorithm][directed_triangle_count]") {
  // All 6 directed edges between {0,1,2}: each permutation of the triangle
  // forms a directed 3-cycle. With edges in both directions:
  // 0->1, 1->2, 0->2 (one 3-cycle starting from 0 via 1)
  // 0->2, 2->1, 0->1 (one 3-cycle starting from 0 via 2)
  // 1->0, 0->2, 1->2 (one starting from 1 via 0)
  // 1->2, 2->0, 1->0 (one starting from 1 via 2)
  // 2->0, 0->1, 2->1 (one starting from 2 via 0)
  // 2->1, 1->0, 2->0 (one starting from 2 via 1)
  // = 6 directed 3-cycles total
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}});
  REQUIRE(directed_triangle_count(g) == 6);
}

TEST_CASE("directed_triangle_count - undirected triangle gives 6x", "[algorithm][directed_triangle_count]") {
  // An undirected triangle stored bidirectionally gives 6 directed 3-cycles
  // (one per permutation of the 3 vertices)
  vos_void g({{0, 1}, {1, 0}, {1, 2}, {2, 1}, {0, 2}, {2, 0}});
  // Compare: undirected triangle_count gives 1
  REQUIRE(triangle_count(g) == 1);
  REQUIRE(directed_triangle_count(g) == 6);
}

TEST_CASE("directed_triangle_count - directed acyclic (no 3-cycles)", "[algorithm][directed_triangle_count]") {
  // DAG: 0->1, 0->2, 1->2 — this IS a 3-cycle (0->1, 1->2, and 0->2)
  // But 2->0, 2->1 are missing, so only 1 directed 3-cycle
  vos_void g({{0, 1}, {0, 2}, {1, 2}});
  REQUIRE(directed_triangle_count(g) == 1);
}

TEST_CASE("directed_triangle_count - complete directed K4", "[algorithm][directed_triangle_count]") {
  // All 12 directed edges between 4 vertices
  // Number of directed 3-cycles = 4 * 6 = 24
  // (4 triangles as vertex sets, each with 6 directed permutations via 3! / 3 = 2... wait)
  // Actually: for each triple of vertices, there are 2 cyclic orderings that 
  // produce directed 3-cycles where all 3 edges go the same circular direction.
  // But our algorithm counts (u, v, w) where u->v, v->w, u->w exist.
  // For each 3-vertex subset, with all 6 edges present, each of the 6 ordered 
  // triples (u,v,w) with u,v,w distinct satisfies: u->v exists, v->w exists, u->w exists.
  // C(4,3) = 4 subsets, 6 permutations each = 24
  vos_void g({
    {0, 1}, {1, 0}, {0, 2}, {2, 0}, {0, 3}, {3, 0},
    {1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}
  });
  REQUIRE(directed_triangle_count(g) == 24);
}

TEST_CASE("directed_triangle_count - self-loops ignored", "[algorithm][directed_triangle_count]") {
  // 3-cycle with self-loops: self-loops should not be counted
  vos_void g({{0, 1}, {1, 2}, {0, 2}, {0, 0}, {1, 1}, {2, 2}});
  REQUIRE(directed_triangle_count(g) == 1);
}

TEST_CASE("directed_triangle_count - path (no 3-cycles)", "[algorithm][directed_triangle_count]") {
  // Directed path: 0->1->2->3->4 (no triangles possible)
  vos_void g({{0, 1}, {1, 2}, {2, 3}, {3, 4}});
  REQUIRE(directed_triangle_count(g) == 0);
}

TEST_CASE("directed_triangle_count - sparse directed triangle", "[algorithm][directed_triangle_count][sparse]") {
  using Graph = mos_weighted;

  // Directed 3-cycle: 10->20, 20->30, 10->30
  Graph g({{10, 20, 1}, {20, 30, 1}, {10, 30, 1}});
  REQUIRE(directed_triangle_count(g) == 1);
}

TEST_CASE("directed_triangle_count - sparse bidirectional triangle", "[algorithm][directed_triangle_count][sparse]") {
  using Graph = mos_weighted;

  // All 6 directed edges between {10,20,30}
  Graph g({{10, 20, 1}, {20, 10, 1}, {20, 30, 1}, {30, 20, 1}, {10, 30, 1}, {30, 10, 1}});
  REQUIRE(directed_triangle_count(g) == 6);
}