bipartite_test.cc

Go to the documentation of this file.

 
/*
                          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 <tpl_bipartite.H>
#include <tpl_graph.H>
 
using namespace std;
using namespace Aleph;
 
// Graph type for testing - using Empty_Class for arc info as required by bipartite algorithms
using Graph = List_Graph<Graph_Node<int>, Graph_Arc<Empty_Class>>;
 
// ============================================================================
// Helper Functions
// ============================================================================
 
Graph create_complete_bipartite(size_t m, size_t n)
{
  Graph g;
 
  // Create left partition nodes
  vector<Graph::Node *> left(m);
  for (size_t i = 0; i < m; ++i)
    left[i] = g.insert_node(static_cast<int>(i));
 
  // Create right partition nodes
  vector<Graph::Node *> right(n);
  for (size_t j = 0; j < n; ++j)
    right[j] = g.insert_node(static_cast<int>(m + j));
 
  // Connect every node in left to every node in right
  for (size_t i = 0; i < m; ++i)
    for (size_t j = 0; j < n; ++j)
      g.insert_arc(left[i], right[j]);
 
  return g;
}
 
Graph create_path_graph(size_t n)
{
  Graph g;
 
  if (n == 0)
    return g;
 
  vector<Graph::Node *> nodes(n);
  for (size_t i = 0; i < n; ++i)
    nodes[i] = g.insert_node(static_cast<int>(i));
 
  for (size_t i = 0; i + 1 < n; ++i)
    g.insert_arc(nodes[i], nodes[i + 1]);
 
  return g;
}
 
Graph create_cycle_graph(size_t n)
{
  Graph g;
 
  if (n < 3)
    return g;
 
  vector<Graph::Node *> nodes(n);
  for (size_t i = 0; i < n; ++i)
    nodes[i] = g.insert_node(static_cast<int>(i));
 
  for (size_t i = 0; i < n; ++i)
    g.insert_arc(nodes[i], nodes[(i + 1) % n]);
 
  return g;
}
 
Graph create_star_graph(size_t n)
{
  Graph g;
 
  auto * center = g.insert_node(0);
 
  for (size_t i = 0; i < n; ++i)
    {
      auto * leaf = g.insert_node(static_cast<int>(i + 1));
      g.insert_arc(center, leaf);
    }
 
  return g;
}
 
Graph create_triangle()
{
  Graph g;
 
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  auto * c = g.insert_node(2);
 
  g.insert_arc(a, b);
  g.insert_arc(b, c);
  g.insert_arc(c, a);
 
  return g;
}
 
Graph create_disconnected_bipartite()
{
  Graph g;
 
  // Component 1: path 0--1
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  g.insert_arc(a, b);
 
  // Component 2: path 2--3
  auto * c = g.insert_node(2);
  auto * d = g.insert_node(3);
  g.insert_arc(c, d);
 
  return g;
}
 
bool verify_bipartition(const Graph & g,
                        const DynDlist<Graph::Node *> & l,
                        const DynDlist<Graph::Node *> & r)
{
  // Create sets for fast lookup
  DynSetAvlTree<Graph::Node *> left_set, right_set;
 
  for (auto it = l.get_it(); it.has_curr(); it.next_ne())
    left_set.insert(it.get_curr());
 
  for (auto it = r.get_it(); it.has_curr(); it.next_ne())
    right_set.insert(it.get_curr());
 
  // Check that partitions don't overlap
  for (auto it = l.get_it(); it.has_curr(); it.next_ne())
    if (right_set.contains(it.get_curr()))
      return false;
 
  // Check that every edge between partitioned nodes connects different partitions
  for (Arc_Iterator<Graph> it(g); it.has_curr(); it.next_ne())
    {
      auto * arc = it.get_curr();
      auto * src = g.get_src_node(arc);
      auto * tgt = g.get_tgt_node(arc);
 
      bool src_in_left = left_set.contains(src);
      bool src_in_right = right_set.contains(src);
      bool tgt_in_left = left_set.contains(tgt);
      bool tgt_in_right = right_set.contains(tgt);
 
      // Skip edges involving nodes that weren't partitioned
      if (!(src_in_left || src_in_right) || !(tgt_in_left || tgt_in_right))
        continue;
 
      // Both in same partition = invalid
      if (src_in_left == tgt_in_left)
        return false;
    }
 
  return true;
}
 
bool verify_matching(const Graph & g,
                     const DynDlist<Graph::Arc *> & matching)
{
  DynSetAvlTree<Graph::Node *> matched_nodes;
 
  for (auto it = matching.get_it(); it.has_curr(); it.next_ne())
    {
      auto * arc = it.get_curr();
      auto * src = g.get_src_node(arc);
      auto * tgt = g.get_tgt_node(arc);
 
      // Check if either node is already matched
      if (matched_nodes.contains(src) || matched_nodes.contains(tgt))
        return false;
 
      matched_nodes.insert(src);
      matched_nodes.insert(tgt);
    }
 
  return true;
}
 
// ============================================================================
// Basic Bipartite Detection Tests
// ============================================================================
 
// KNOWN BUG: Empty graph is not handled - throws range_error
// TODO: Fix tpl_bipartite.H to handle empty graphs gracefully
TEST(Bipartite, DISABLED_EmptyGraph)
{
  Graph g;
  DynDlist<Graph::Node *> l, r;
 
  // Empty graph should be trivially bipartite
  // Note: Current implementation throws on empty graph - this tests the fix
  EXPECT_NO_THROW(compute_bipartite<Graph>(g, l, r));
  EXPECT_TRUE(l.is_empty());
  EXPECT_TRUE(r.is_empty());
}
 
// This test documents the current (buggy) behavior
TEST(Bipartite, EmptyGraphThrowsRangeError)
{
  Graph g;
  DynDlist<Graph::Node *> l, r;
 
  // BUG: Empty graph throws range_error instead of succeeding with empty partitions
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), std::range_error);
}
 
TEST(Bipartite, SingleNode)
{
  Graph g;
  g.insert_node(1);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  // Single node goes into one partition
  EXPECT_EQ(l.size() + r.size(), 1u);
}
 
TEST(Bipartite, TwoConnectedNodes)
{
  Graph g;
  auto * a = g.insert_node(1);
  auto * b = g.insert_node(2);
  g.insert_arc(a, b);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 1u);
  EXPECT_EQ(r.size(), 1u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, PathGraphEven)
{
  auto g = create_path_graph(4);  // 0--1--2--3
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 4u);
  EXPECT_EQ(l.size(), 2u);
  EXPECT_EQ(r.size(), 2u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, PathGraphOdd)
{
  auto g = create_path_graph(5);  // 0--1--2--3--4
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 5u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, StarGraph)
{
  auto g = create_star_graph(5);  // Center with 5 leaves
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 6u);
  // One partition has the center, other has all leaves
  EXPECT_TRUE((l.size() == 1 && r.size() == 5) ||
              (l.size() == 5 && r.size() == 1));
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, CompleteBipartiteK22)
{
  auto g = create_complete_bipartite(2, 2);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 2u);
  EXPECT_EQ(r.size(), 2u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, CompleteBipartiteK33)
{
  auto g = create_complete_bipartite(3, 3);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 3u);
  EXPECT_EQ(r.size(), 3u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, CompleteBipartiteK25)
{
  auto g = create_complete_bipartite(2, 5);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 7u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(Bipartite, EvenCycle)
{
  auto g = create_cycle_graph(6);  // 6-cycle is bipartite
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 3u);
  EXPECT_EQ(r.size(), 3u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
// ============================================================================
// Non-Bipartite Graph Detection Tests
// ============================================================================
 
TEST(Bipartite, TriangleThrows)
{
  auto g = create_triangle();
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), domain_error);
}
 
TEST(Bipartite, OddCycleThrows)
{
  auto g = create_cycle_graph(5);  // 5-cycle is NOT bipartite
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), domain_error);
}
 
TEST(Bipartite, LargeOddCycleThrows)
{
  auto g = create_cycle_graph(11);  // 11-cycle is NOT bipartite
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), domain_error);
}
 
TEST(Bipartite, CompleteGraphK3Throws)
{
  // K_3 is a triangle
  auto g = create_triangle();
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), domain_error);
}
 
TEST(Bipartite, GraphWithOddCycleAttached)
{
  Graph g;
 
  // Create a bipartite part
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  g.insert_arc(a, b);
 
  // Attach an odd cycle (3 nodes = triangle) to node b
  auto * c = g.insert_node(2);
  auto * d = g.insert_node(3);
  g.insert_arc(b, c);
  g.insert_arc(c, d);
  g.insert_arc(d, b);  // Creates odd cycle b-c-d-b (3 nodes)
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(compute_bipartite<Graph>(g, l, r), domain_error);
}
 
// ============================================================================
// Disconnected Graph Tests
// ============================================================================
 
// Note: These tests document the expected behavior.
// The current implementation may not handle disconnected graphs correctly.
 
TEST(Bipartite, TwoDisconnectedNodes)
{
  Graph g;
  g.insert_node(1);
  g.insert_node(2);
  // No edges - two isolated nodes
 
  DynDlist<Graph::Node *> l, r;
 
  // Two isolated nodes should be bipartite
  // Current implementation only processes first node's component
  compute_bipartite<Graph>(g, l, r);
 
  // At minimum, should process one node without crashing
  EXPECT_GE(l.size() + r.size(), 1u);
}
 
TEST(Bipartite, DisconnectedBipartiteComponents)
{
  auto g = create_disconnected_bipartite();
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  // Should process at least the first component
  EXPECT_GE(l.size() + r.size(), 2u);
 
  // Verify what was partitioned is correct
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
// ============================================================================
// Class Wrapper Tests
// ============================================================================
 
TEST(ComputeBipartiteClass, BasicUsage)
{
  auto g = create_complete_bipartite(3, 4);
 
  DynDlist<Graph::Node *> l, r;
 
  Compute_Bipartite<Graph>()(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 7u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(ComputeBipartiteClass, ThrowsOnNonBipartite)
{
  auto g = create_triangle();
 
  DynDlist<Graph::Node *> l, r;
 
  EXPECT_THROW(Compute_Bipartite<Graph>()(g, l, r), domain_error);
}
 
// ============================================================================
// Maximum Matching Tests
// ============================================================================
// KNOWN BUG: The maximum matching algorithm is not returning correct results.
// The flow network-based algorithm returns 0 matches for all cases.
// Empty graph throws range_error (consistent with compute_bipartite behavior)
TEST(MaximumMatching, EmptyGraphThrowsRangeError)
{
  Graph g;
 
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_THROW(
    compute_maximum_cardinality_bipartite_matching<Graph>(g, matching),
    std::range_error);
}
 
TEST(MaximumMatching, SingleEdge)
{
  Graph g;
  auto * a = g.insert_node(1);
  auto * b = g.insert_node(2);
  g.insert_arc(a, b);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 1u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, PathGraph4)
{
  auto g = create_path_graph(4);  // 0--1--2--3
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Maximum matching in path of 4 nodes is 2 edges
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, PathGraph5)
{
  auto g = create_path_graph(5);  // 0--1--2--3--4
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Maximum matching in path of 5 nodes is 2 edges
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, CompleteBipartiteK22)
{
  auto g = create_complete_bipartite(2, 2);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Perfect matching: 2 edges
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, CompleteBipartiteK33)
{
  auto g = create_complete_bipartite(3, 3);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Perfect matching: 3 edges
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, CompleteBipartiteK55)
{
  auto g = create_complete_bipartite(5, 5);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Perfect matching: 5 edges
  EXPECT_EQ(matching.size(), 5u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, UnbalancedK25)
{
  auto g = create_complete_bipartite(2, 5);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Maximum matching limited by smaller partition: 2 edges
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, UnbalancedK52)
{
  auto g = create_complete_bipartite(5, 2);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Maximum matching limited by smaller partition: 2 edges
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, StarGraph)
{
  auto g = create_star_graph(5);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // Star can only have 1 edge in matching (center is shared)
  EXPECT_EQ(matching.size(), 1u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, EvenCycle)
{
  auto g = create_cycle_graph(6);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  // 6-cycle has perfect matching: 3 edges
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatching, ThrowsOnNonBipartite)
{
  auto g = create_triangle();
 
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_THROW(
    compute_maximum_cardinality_bipartite_matching<Graph>(g, matching),
    domain_error);
}
 
// ============================================================================
// Matching Class Wrapper Tests
// ============================================================================
 
TEST(MaximumMatchingClass, BasicUsage)
{
  auto g = create_complete_bipartite(4, 4);
 
  DynDlist<Graph::Arc *> matching;
 
  Compute_Maximum_Cardinality_Bipartite_Matching<Graph>()(g, matching);
 
  EXPECT_EQ(matching.size(), 4u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(MaximumMatchingClass, ThrowsOnNonBipartite)
{
  auto g = create_cycle_graph(5);  // Odd cycle
 
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_THROW(
    Compute_Maximum_Cardinality_Bipartite_Matching<Graph>()(g, matching),
    domain_error);
}
 
// ============================================================================
// Stress Tests
// ============================================================================
 
TEST(BipartiteStress, LargeBipartiteGraph)
{
  auto g = create_complete_bipartite(50, 50);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size() + r.size(), 100u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(BipartiteStress, LargePathGraph)
{
  auto g = create_path_graph(100);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 50u);
  EXPECT_EQ(r.size(), 50u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
TEST(MaximumMatchingStress, LargeMatching)
{
  auto g = create_complete_bipartite(20, 20);
 
  DynDlist<Graph::Arc *> matching;
 
  compute_maximum_cardinality_bipartite_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 20u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(BipartiteStress, LargeEvenCycle)
{
  auto g = create_cycle_graph(100);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 50u);
  EXPECT_EQ(r.size(), 50u);
  EXPECT_TRUE(verify_bipartition(g, l, r));
}
 
// ============================================================================
// Edge Cases
// ============================================================================
 
TEST(Bipartite, MultipleEdgesBetweenSameNodes)
{
  Graph g;
  auto * a = g.insert_node(1);
  auto * b = g.insert_node(2);
 
  // Multiple edges between same nodes (multigraph)
  g.insert_arc(a, b);
  g.insert_arc(a, b);
  g.insert_arc(a, b);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  EXPECT_EQ(l.size(), 1u);
  EXPECT_EQ(r.size(), 1u);
}
 
TEST(Bipartite, IsolatedNodeWithBipartiteComponent)
{
  Graph g;
 
  // Bipartite component
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  g.insert_arc(a, b);
 
  // Isolated node
  g.insert_node(2);
 
  DynDlist<Graph::Node *> l, r;
 
  compute_bipartite<Graph>(g, l, r);
 
  // At least the connected component should be processed
  EXPECT_GE(l.size() + r.size(), 2u);
}
 
// ============================================================================
// Color Enum Tests
// ============================================================================
 
TEST(BipartiteColor, EnumValues)
{
  // Verify the color enum values
  EXPECT_EQ(Bp_White, 0);
  EXPECT_EQ(Bp_Red, 1);
  EXPECT_EQ(Bp_Blue, 2);
}
 
// ============================================================================
// Hopcroft-Karp Matching Tests
// ============================================================================
 
// --- Base cases ---
 
TEST(HopcroftKarp, EmptyGraph)
{
  Graph g;
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_NO_THROW(hopcroft_karp_matching<Graph>(g, matching));
  EXPECT_TRUE(matching.is_empty());
}
 
TEST(HopcroftKarp, SingleIsolatedNode)
{
  Graph g;
  g.insert_node(0);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_TRUE(matching.is_empty());
}
 
TEST(HopcroftKarp, SingleEdge)
{
  Graph g;
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  g.insert_arc(a, b);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 1u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
// --- Standard bipartite graphs ---
 
TEST(HopcroftKarp, PathGraph4)
{
  auto g = create_path_graph(4);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, PathGraph5)
{
  auto g = create_path_graph(5);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, CompleteBipartiteK22)
{
  auto g = create_complete_bipartite(2, 2);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, CompleteBipartiteK33)
{
  auto g = create_complete_bipartite(3, 3);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, CompleteBipartiteK55)
{
  auto g = create_complete_bipartite(5, 5);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 5u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, UnbalancedK25)
{
  auto g = create_complete_bipartite(2, 5);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, StarGraph)
{
  auto g = create_star_graph(5);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 1u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, EvenCycle6)
{
  auto g = create_cycle_graph(6);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
// --- Non-bipartite detection ---
 
TEST(HopcroftKarp, TriangleThrows)
{
  auto g = create_triangle();
 
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_THROW(hopcroft_karp_matching<Graph>(g, matching), domain_error);
}
 
TEST(HopcroftKarp, OddCycleThrows)
{
  auto g = create_cycle_graph(5);
 
  DynDlist<Graph::Arc *> matching;
 
  EXPECT_THROW(hopcroft_karp_matching<Graph>(g, matching), domain_error);
}
 
// --- Disconnected graphs ---
 
TEST(HopcroftKarp, TwoDisconnectedEdges)
{
  auto g = create_disconnected_bipartite();
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 2u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, DisconnectedWithIsolatedNodes)
{
  Graph g;
 
  // Component 1: single edge
  auto * a = g.insert_node(0);
  auto * b = g.insert_node(1);
  g.insert_arc(a, b);
 
  // Isolated nodes
  g.insert_node(2);
  g.insert_node(3);
 
  // Component 2: K_{2,2}
  auto * c = g.insert_node(10);
  auto * d = g.insert_node(11);
  auto * e = g.insert_node(12);
  auto * f = g.insert_node(13);
  g.insert_arc(c, e);
  g.insert_arc(c, f);
  g.insert_arc(d, e);
  g.insert_arc(d, f);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  // 1 from edge + 2 from K_{2,2} = 3
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, TwoDisconnectedCompleteBipartite)
{
  Graph g;
 
  // Component 1: K_{3,3}
  vector<Graph::Node *> l1(3), r1(3);
  for (int i = 0; i < 3; ++i)
    l1[i] = g.insert_node(i);
  for (int i = 0; i < 3; ++i)
    r1[i] = g.insert_node(10 + i);
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      g.insert_arc(l1[i], r1[j]);
 
  // Component 2: K_{2,2}
  vector<Graph::Node *> l2(2), r2(2);
  for (int i = 0; i < 2; ++i)
    l2[i] = g.insert_node(20 + i);
  for (int i = 0; i < 2; ++i)
    r2[i] = g.insert_node(30 + i);
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      g.insert_arc(l2[i], r2[j]);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  // 3 + 2 = 5
  EXPECT_EQ(matching.size(), 5u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
// --- Cross-validation with max-flow ---
 
TEST(HopcroftKarp, CrossValidateK44)
{
  auto g = create_complete_bipartite(4, 4);
 
  DynDlist<Graph::Arc *> hk_matching;
  hopcroft_karp_matching<Graph>(g, hk_matching);
 
  DynDlist<Graph::Arc *> ff_matching;
  compute_maximum_cardinality_bipartite_matching<Graph>(g, ff_matching);
 
  EXPECT_EQ(hk_matching.size(), ff_matching.size());
  EXPECT_EQ(hk_matching.size(), 4u);
}
 
TEST(HopcroftKarp, CrossValidatePath6)
{
  auto g = create_path_graph(6);
 
  DynDlist<Graph::Arc *> hk_matching;
  hopcroft_karp_matching<Graph>(g, hk_matching);
 
  DynDlist<Graph::Arc *> ff_matching;
  compute_maximum_cardinality_bipartite_matching<Graph>(g, ff_matching);
 
  EXPECT_EQ(hk_matching.size(), ff_matching.size());
  EXPECT_EQ(hk_matching.size(), 3u);
}
 
TEST(HopcroftKarp, CrossValidateEvenCycle8)
{
  auto g = create_cycle_graph(8);
 
  DynDlist<Graph::Arc *> hk_matching;
  hopcroft_karp_matching<Graph>(g, hk_matching);
 
  DynDlist<Graph::Arc *> ff_matching;
  compute_maximum_cardinality_bipartite_matching<Graph>(g, ff_matching);
 
  EXPECT_EQ(hk_matching.size(), ff_matching.size());
  EXPECT_EQ(hk_matching.size(), 4u);
}
 
// --- Functor wrapper ---
 
TEST(HopcroftKarp, FunctorWrapper)
{
  auto g = create_complete_bipartite(3, 3);
 
  DynDlist<Graph::Arc *> matching;
  Hopcroft_Karp_Matching<Graph>()(g, matching);
 
  EXPECT_EQ(matching.size(), 3u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, FunctorMatchesFreeFunction)
{
  auto g = create_complete_bipartite(4, 4);
 
  DynDlist<Graph::Arc *> fn_matching, op_matching;
  hopcroft_karp_matching<Graph>(g, fn_matching);
  Hopcroft_Karp_Matching<Graph>()(g, op_matching);
 
  EXPECT_EQ(fn_matching.size(), op_matching.size());
}
 
// --- Stress tests ---
 
TEST(HopcroftKarp, StressK50_50)
{
  auto g = create_complete_bipartite(50, 50);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 50u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, StressK100_100)
{
  auto g = create_complete_bipartite(100, 100);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 100u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
TEST(HopcroftKarp, StressPath200)
{
  auto g = create_path_graph(200);
 
  DynDlist<Graph::Arc *> matching;
  hopcroft_karp_matching<Graph>(g, matching);
 
  EXPECT_EQ(matching.size(), 100u);
  EXPECT_TRUE(verify_matching(g, matching));
}
 
int main(int argc, char **argv)
{
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}