edmonds_karp_test.cpp

#include <catch2/catch.hpp>

#include <gp-bnb/edmonds_karp.hpp>
#include <gp-bnb/graph.hpp>
#include <gp-bnb/metis_reader.hpp>

// Tests for Edmonds-Karp Max Flow algorithm

TEST_CASE("EdmondsKarpMaxFlow") {
    // Same graph instance as in IBFS test
    std::vector<std::vector<node_id>> adjacency_list {
        { 2, 7 },           // 1
        { 1, 3, 4 },        // 2
        { 2, 5 },           // 3
        { 2, 5 },           // 4
        { 3, 4, 6},         // 5
        { 5, 8 },           // 6
        { 1, 8 },           // 7
        { 6, 7 }            // 8
    };

    graph g(adjacency_list);

    std::vector<node_id> sources { 1 };
    std::vector<node_id> sinks { 8 };

    edmonds_karp ek = edmonds_karp(g);

	ek.reset(sources, sinks);
    ek.run();
    int max_flow = ek.get_max_flow();

    REQUIRE(max_flow == 2);

    //Testing multiple sources and sinks
    std::vector<std::vector<node_id>> adjacency_list2 {
        { 5, 2, 3 },
        { 1, 3, 4 },
        { 5, 4, 2, 1 },
        { 2, 3, 6, 7 },
        { 1, 3, 6 },
        { 5, 4, 7 },
        { 6, 4 }
    };

    graph g2(adjacency_list2);

    // 1 Case for g2
    std::vector<node_id> sources2 { 1 };
    std::vector<node_id> sinks2 { 6, 7 };

    edmonds_karp ek2 = edmonds_karp(g2);

	ek2.reset(sources2, sinks2);
    ek2.run();
    int max_flow2 = ek2.get_max_flow();

    REQUIRE(max_flow2 == 3);

    // 2 Case for g2
    std::vector<node_id> sources3 { 2, 3 };
    std::vector<node_id> sinks3 { 5, 6 };
    edmonds_karp ek3 = edmonds_karp(g2);

	ek3.reset(sources3, sinks3);
    ek3.run();
    int max_flow3 = ek3.get_max_flow();

    REQUIRE(max_flow3 == 4);

    // 3 Case for g2 (balanced 2-partition)
    std::vector<node_id> sources4 { 1, 4, 6 };
    std::vector<node_id> sinks4 { 2, 3, 5, 7 };
    edmonds_karp ek4 = edmonds_karp(g2);

	ek4.reset(sources4, sinks4);
    ek4.run();
    int max_flow4 = ek4.get_max_flow();

    REQUIRE(max_flow4 == 8);

    // 4 Case for g2 (balanced 2-partition)
    std::vector<node_id> sources5 { 1, 2, 3, 5 };
    std::vector<node_id> sinks5 { 4, 6, 7 };
    edmonds_karp ek5 = edmonds_karp(g2);

	ek5.reset(sources5, sinks5);
    ek5.run();
    int max_flow5 = ek5.get_max_flow();

    REQUIRE(max_flow5 == 3);

    // Testing on a graph with ~1000 nodes
    std::string graph_file = "../test/inputs/delaunay_n10.graph";
    graph g3 = metis_reader().read(graph_file);

    std::vector<node_id> sources6 = {1, 3, 8, 9, 100};
    std::vector<node_id> sinks6 = {50, 60, 88};

    edmonds_karp ek6 = edmonds_karp(g3);

	ek6.reset(sources6, sinks6);
    ek6.run();
    int max_flow6 = ek6.get_max_flow();

    REQUIRE(max_flow6 == 18);

    // Testing add_source() function with delaunay_n10.graph
    std::vector<node_id> sources7 = {1, 3, 8, 9, 100};
    std::vector<node_id> sinks7 = {50, 60, 88};

    edmonds_karp ek7 = edmonds_karp(g3);

	ek7.reset(sources7, sinks7);
    ek7.run();

    int max_flow7 = ek7.get_max_flow();

    REQUIRE(max_flow7 == 18);

}