random_network_generator_test.cc

Go to the documentation of this file.

/* Tests for random network generator
 *
 * Demonstrates the use of random network generators for comprehensive testing
 */
 
#include <gtest/gtest.h>
#include "random_network_generator.H"
#include <tpl_net.H>
#include <tpl_netcost.H>
#include <tpl_maxflow.H>
#include <tpl_mincost.H>
 
using namespace Aleph;
using namespace Aleph::Testing;
 
namespace
{
  using TestNet = Net_Graph<Net_Node<int>, Net_Arc<int, double>>;
  using CostNet = Net_Cost_Graph<Net_Cost_Node<int>, Net_Cost_Arc<int, double>>;
}
 
 
//==============================================================================
// Erdős–Rényi Generator Tests
//==============================================================================
 
TEST(ErdosRenyiGeneratorTest, BasicGeneration)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 10;
  config.density = 0.3;
  config.seed = 42;
  
  ErdosRenyiGenerator<TestNet> gen(config);
  TestNet net;
  gen.generate(net);
  
  EXPECT_EQ(net.vsize(), 10);
  EXPECT_GT(net.esize(), 0);
}
 
TEST(ErdosRenyiGeneratorTest, ConnectivityGuarantee)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 20;
  config.density = 0.2;
  config.ensure_connected = true;
  config.seed = 123;
  
  ErdosRenyiGenerator<TestNet> gen(config);
  TestNet net;
  gen.generate(net);
  
  // Try to compute max flow - should succeed if connected
  auto flow = dinic_maximum_flow(net);
  
  EXPECT_GT(flow, 0.0);  // Should find some flow
}
 
TEST(ErdosRenyiGeneratorTest, DifferentDensities)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 15;
  config.seed = 456;
  
  // Low density
  config.density = 0.1;
  ErdosRenyiGenerator<TestNet> gen_low(config);
  TestNet net_low;
  gen_low.generate(net_low);
  size_t arcs_low = net_low.esize();
  
  // High density
  config.density = 0.8;
  ErdosRenyiGenerator<TestNet> gen_high(config);
  TestNet net_high;
  gen_high.generate(net_high);
  size_t arcs_high = net_high.esize();
  
  // Higher density should produce more arcs
  EXPECT_LT(arcs_low, arcs_high);
}
 
 
//==============================================================================
// Layered Generator Tests
//==============================================================================
 
TEST(LayeredGeneratorTest, BasicGeneration)
{
  NetworkGeneratorConfig config;
  config.density = 0.5;
  config.seed = 789;
  
  LayeredNetworkGenerator<TestNet> gen(config, 4, 5);
  TestNet net;
  gen.generate(net);
  
  // Should have source + 2*5 intermediate + sink = 12 nodes
  EXPECT_EQ(net.vsize(), 12);
  EXPECT_GT(net.esize(), 0);
}
 
TEST(LayeredGeneratorTest, FlowsCorrectly)
{
  NetworkGeneratorConfig config;
  config.density = 0.6;
  config.ensure_connected = true;
  config.seed = 111;
  
  LayeredNetworkGenerator<TestNet> gen(config, 5, 3);
  TestNet net;
  gen.generate(net);
  
  // Consolidate multiple sources/sinks into single super-source/sink if needed
  if (!net.is_single_source())
    net.make_super_source();
  if (!net.is_single_sink())
    net.make_super_sink();
  
  auto flow = edmonds_karp_maximum_flow(net);
  
  EXPECT_GT(flow, 0.0);
}
 
 
//==============================================================================
// Grid Generator Tests
//==============================================================================
 
TEST(GridGeneratorTest, BasicGeneration)
{
  NetworkGeneratorConfig config;
  config.seed = 222;
  
  GridNetworkGenerator<TestNet> gen(config, 5, 5);
  TestNet net;
  gen.generate(net);
  
  EXPECT_EQ(net.vsize(), 25);  // 5x5 grid
  
  // Grid should have (rows * (cols-1)) + ((rows-1) * cols) arcs
  // = 5*4 + 4*5 = 20 + 20 = 40
  EXPECT_EQ(net.esize(), 40);
}
 
TEST(GridGeneratorTest, FlowFromCornerToCorner)
{
  NetworkGeneratorConfig config;
  config.min_capacity = 10.0;
  config.max_capacity = 20.0;
  config.seed = 333;
  
  GridNetworkGenerator<TestNet> gen(config, 4, 4);
  TestNet net;
  gen.generate(net);
  
  auto flow = dinic_maximum_flow(net);
  
  EXPECT_GT(flow, 0.0);
}
 
TEST(GridGeneratorTest, DifferentSizes)
{
  NetworkGeneratorConfig config;
  config.seed = 444;
  
  // Small grid
  GridNetworkGenerator<TestNet> gen_small(config, 3, 3);
  TestNet net_small;
  gen_small.generate(net_small);
  
  // Larger grid
  GridNetworkGenerator<TestNet> gen_large(config, 10, 10);
  TestNet net_large;
  gen_large.generate(net_large);
  
  EXPECT_EQ(net_small.vsize(), 9);
  EXPECT_EQ(net_large.vsize(), 100);
}
 
 
//==============================================================================
// Bipartite Generator Tests
//==============================================================================
 
TEST(BipartiteGeneratorTest, BasicGeneration)
{
  NetworkGeneratorConfig config;
  config.seed = 555;
  
  BipartiteNetworkGenerator<TestNet> gen(config, 5, 5);
  TestNet net;
  gen.generate(net);
  
  // source + sink + left + right = 2 + 5 + 5 = 12
  EXPECT_EQ(net.vsize(), 12);
}
 
TEST(BipartiteGeneratorTest, MatchingProblem)
{
  NetworkGeneratorConfig config;
  config.min_capacity = 1.0;
  config.max_capacity = 1.0;  // Unit capacity for matching
  config.seed = 666;
  
  BipartiteNetworkGenerator<TestNet> gen(config, 6, 6);
  TestNet net;
  gen.generate(net);
  
  auto flow = hlpp_maximum_flow(net);
  
  // Maximum matching should be at most min(6, 6) = 6
  EXPECT_LE(flow, 6.0);
  EXPECT_GT(flow, 0.0);
}
 
 
//==============================================================================
// Cost Network Generator Tests
//==============================================================================
 
TEST(CostNetworkGeneratorTest, ErdosRenyiWithCosts)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 15;
  config.density = 0.3;
  config.min_cost = 1.0;
  config.max_cost = 50.0;
  config.ensure_connected = true;
  config.seed = 777;
  
  ErdosRenyiGenerator<CostNet> gen(config);
  CostNet net;
  gen.generate(net);
  
  // Consolidate sources/sinks if needed
  if (!net.is_single_source())
    net.make_super_source();
  if (!net.is_single_sink())
    net.make_super_sink();
  
  // Compute min-cost flow
  auto [flow, cost] = successive_shortest_paths(net);
  
  EXPECT_GT(flow, 0.0);
  EXPECT_GT(cost, 0.0);
}
 
TEST(CostNetworkGeneratorTest, LayeredWithCosts)
{
  NetworkGeneratorConfig config;
  config.density = 0.5;
  config.min_cost = 1.0;
  config.max_cost = 10.0;
  // Use small network and unit capacities to keep SSP iterations reasonable
  // SSP has O(V * U * ...) complexity where U is max flow value
  // In Debug mode with Clang, even small networks can be slow
  config.min_capacity = 1.0;
  config.max_capacity = 1.0;  // Unit capacity for minimal iterations
  config.ensure_connected = true;
  config.seed = 888;
  
  // Small network: 3 layers with 2 nodes per intermediate layer
  // Total: 1 (source) + 2 (intermediate) + 1 (sink) = 4 nodes
  LayeredNetworkGenerator<CostNet> gen(config, 3, 2);
  CostNet net;
  gen.generate(net);
  
  // Consolidate sources/sinks if needed
  if (!net.is_single_source())
    net.make_super_source();
  if (!net.is_single_sink())
    net.make_super_sink();
  
  auto [flow, cost] = successive_shortest_paths(net);
  
  EXPECT_GT(flow, 0.0);
  EXPECT_GT(cost, 0.0);
}
 
 
//==============================================================================
// Stress Tests with Random Networks
//==============================================================================
 
TEST(StressTest, MultipleRandomNetworks)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 20;
  config.density = 0.3;
  config.ensure_connected = true;
  
  // Generate and test 10 different random networks
  for (int i = 0; i < 10; ++i)
  {
    config.seed = 1000 + i;
    
    ErdosRenyiGenerator<TestNet> gen(config);
    
    // Test Edmonds-Karp
    gen.reseed();  // Reset RNG to get reproducible network
    TestNet net1;
    gen.generate(net1);
    auto flow_ek = edmonds_karp_maximum_flow(net1);
    
    // Test Dinic on identical network
    gen.reseed();  // Reset RNG to generate identical network
    TestNet net2;
    gen.generate(net2);
    auto flow_dinic = dinic_maximum_flow(net2);
    
    // Both should give same result (within floating-point tolerance)
    EXPECT_NEAR(flow_ek, flow_dinic, 1e-6);
    
    // Both should find positive flow
    EXPECT_GT(flow_ek, 0.0);
    EXPECT_GT(flow_dinic, 0.0);
    
    // Networks should be valid after max flow
    EXPECT_TRUE(net1.check_network());
    EXPECT_TRUE(net2.check_network());
  }
}
 
TEST(StressTest, LargeGridNetworks)
{
  NetworkGeneratorConfig config;
  config.min_capacity = 5.0;
  config.max_capacity = 50.0;
  config.seed = 999;
  
  for (int size = 5; size <= 15; size += 5)
  {
    GridNetworkGenerator<TestNet> gen(config, size, size);
    TestNet net;
    gen.generate(net);
    
    EXPECT_EQ(net.vsize(), size_t(size * size));
    
    // Grid networks are inherently single-source, single-sink
    EXPECT_TRUE(net.is_single_source());
    EXPECT_TRUE(net.is_single_sink());
    
    auto flow = capacity_scaling_maximum_flow(net);
    
    EXPECT_GT(flow, 0.0);
  }
}
 
TEST(StressTest, VaryingDensities)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 25;
  config.ensure_connected = true;
  config.seed = 1111;
  
  for (double density = 0.1; density <= 0.9; density += 0.2)
  {
    config.density = density;
    
    LayeredNetworkGenerator<TestNet> gen(config, 5, 5);
    TestNet net;
    gen.generate(net);
    
    // Consolidate sources/sinks if needed
    if (!net.is_single_source())
      net.make_super_source();
    if (!net.is_single_sink())
      net.make_super_sink();
    
    auto flow = dinic_maximum_flow(net);
    
    // More density generally means more flow capacity
    EXPECT_GT(flow, 0.0);
  }
}
 
 
//==============================================================================
// Factory Tests
//==============================================================================
 
TEST(FactoryTest, CreateAllGeneratorTypes)
{
  NetworkGeneratorConfig config;
  config.num_nodes = 10;
  config.density = 0.3;
  config.seed = 1234;
  
  auto gen_er = create_generator<TestNet>("erdos-renyi", config);
  EXPECT_NE(gen_er, nullptr);
  TestNet net_er;
  gen_er->generate(net_er);
  EXPECT_GT(net_er.vsize(), 0);
  
  auto gen_layered = create_generator<TestNet>("layered", config);
  EXPECT_NE(gen_layered, nullptr);
  TestNet net_layered;
  gen_layered->generate(net_layered);
  EXPECT_GT(net_layered.vsize(), 0);
  
  auto gen_grid = create_generator<TestNet>("grid", config);
  EXPECT_NE(gen_grid, nullptr);
  TestNet net_grid;
  gen_grid->generate(net_grid);
  EXPECT_GT(net_grid.vsize(), 0);
  
  auto gen_bipartite = create_generator<TestNet>("bipartite", config);
  EXPECT_NE(gen_bipartite, nullptr);
  TestNet net_bipartite;
  gen_bipartite->generate(net_bipartite);
  EXPECT_GT(net_bipartite.vsize(), 0);
}
 
TEST(FactoryTest, InvalidTypeThrows)
{
  NetworkGeneratorConfig config;
  
  EXPECT_THROW(create_generator<TestNet>("invalid-type", config),
               std::invalid_argument);
}
 
 
int main(int argc, char** argv)
{
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}