GraphAlgorithms_tests.cpp

Go to the documentation of this file.

/*******************************************************************************
 * The software programs comprising "CGRA-ME" and the documentation provided
 * with them are copyright by its authors and the University of Toronto. Only
 * non-commercial, not-for-profit use of this software is permitted without ex-
 * plicit permission. This software is provided "as is" with no warranties or
 * guarantees of support. See the LICENCE for more details. You should have re-
 * ceived a copy of the full licence along with this software. If not, see
 * <http://cgra-me.ece.utoronto.ca/license/>.
 ******************************************************************************/
 
#include <CGRA/GraphAlgorithms.h>
 
#include <iostream>
 
#include <catch2/catch.hpp>
 
namespace {
 
 
StringIDGraph makeGraph_121() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
    auto fu2 = mrrg.insert("fu2");
 
    auto i_a = mrrg.insert("i_a");
    auto i_b = mrrg.insert("i_b");
 
    mrrg.link(fu1, i_a);
    mrrg.link(fu1, i_b);
    mrrg.link(i_a, fu2);
    mrrg.link(i_b, fu2);
 
    return mrrg;
}
 
StringIDGraph makeGraph_11211() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
    auto fu2 = mrrg.insert("fu2");
 
    auto f1out = mrrg.insert("f1out");
    auto r_a = mrrg.insert("r_a");
    auto r_b = mrrg.insert("r_b");
    auto f2in = mrrg.insert("f2in");
 
    mrrg.link(fu1, f1out);
    mrrg.link(f1out, r_a);
    mrrg.link(f1out, r_b);
    mrrg.link(r_a, f2in);
    mrrg.link(r_b, f2in);
    mrrg.link(f2in, fu2);
 
    return mrrg;
}
 
StringIDGraph makeGraph_12x21() {
    StringIDGraph g;
    auto fu1 = g.insert("fu1");
 
    auto fu1_out_a = g.insert(fu1, "fu1_out_a");
    auto fu1_out_b = g.insert(fu1, "fu1_out_b");
    auto xb_1_a = g.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_a");
    auto xb_1_b = g.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_b");
 
    auto fu2 = g.insertMultiFanin({xb_1_a, xb_1_b}, "fu2");
    (void)fu2;
 
    return g;
}
 
StringIDGraph makeGraph_Loop3Node() {
    StringIDGraph g;
    auto a = g.insert(   "a");
    auto b = g.insert(a, "b");
    auto c = g.insert(b, "c");
    g.link(c, a);
 
    return g;
}
 
StringIDGraph makeGraph_Loop3NodeWithExtraFanout() {
    auto g = makeGraph_Loop3Node();
    g.insert("a", "d");
    return g;
}
 
StringIDGraph makeGraph_12x21_with_loop() {
    auto g = makeGraph_12x21();
    g.link("fu2", "fu1");
    return g;
}
 
StringIDGraph makeGraph_12x2x21() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
 
    auto fu1_out_a = mrrg.insert(fu1, "fu1_out_a");
    auto fu1_out_b = mrrg.insert(fu1, "fu1_out_b");
    auto xb_1_a = mrrg.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_a");
    auto xb_1_b = mrrg.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_b");
    auto xb_2_a = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_a");
    auto xb_2_b = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_b");
 
    auto fu2 = mrrg.insertMultiFanin({xb_2_a, xb_2_b}, "fu2");
    (void)fu2;
 
    return mrrg;
}
 
StringIDGraph makeGraph_112x211() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
 
    auto fu1_out = mrrg.insert(fu1, "fu1_out");
    auto xb_1_a = mrrg.insert(fu1_out, "xb_1_a");
    auto xb_1_b = mrrg.insert(fu1_out, "xb_1_b");
    auto xb_2_a = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_a");
    auto xb_2_b = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_b");
 
    auto fu2_in =  mrrg.insertMultiFanin({xb_2_a, xb_2_b}, "fu2_in");
    auto fu2 = mrrg.insert(fu2_in, "fu2");
    (void)fu2;
 
    return mrrg;
}
 
StringIDGraph makeGraph_12x2x2x21() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
 
    auto fu1_out_a = mrrg.insert(fu1, "fu1_out_a");
    auto fu1_out_b = mrrg.insert(fu1, "fu1_out_b");
    auto xb_1_a = mrrg.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_a");
    auto xb_1_b = mrrg.insertMultiFanin({fu1_out_a, fu1_out_b}, "xb_1_b");
    auto xb_2_a = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_a");
    auto xb_2_b = mrrg.insertMultiFanin({xb_1_a, xb_1_b}, "xb_2_b");
    auto xb_3_a = mrrg.insertMultiFanin({xb_2_a, xb_2_b}, "xb_3_a");
    auto xb_3_b = mrrg.insertMultiFanin({xb_2_a, xb_2_b}, "xb_3_b");
 
    auto fu2 = mrrg.insertMultiFanin({xb_3_a, xb_3_b}, "fu2");
    (void)fu2;
 
    return mrrg;
}
 
StringIDGraph makeGraph_2unevenBranches() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
    auto fu2 = mrrg.insert("fu2");
 
    auto split = mrrg.insert("split");
    auto b1_1 = mrrg.insert("b1_1");
    auto b1_2 = mrrg.insert("b1_2");
    auto b1_3 = mrrg.insert("b1_3");
    auto join = mrrg.insert("join");
 
    mrrg.link(fu1, split);
    mrrg.link(split, b1_1);
    mrrg.link(b1_1, b1_2);
    mrrg.link(b1_2, b1_3);
    mrrg.link(b1_3, join);
    mrrg.link(split, join);
    mrrg.link(join, fu2);
 
    return mrrg;
}
 
StringIDGraph makeGraph_2branches1withCycle() {
    StringIDGraph mrrg;
    auto fu1 = mrrg.insert("fu1");
    auto fu2 = mrrg.insert("fu2");
 
    auto split = mrrg.insert("split");
    auto c_start = mrrg.insert("c_start");
    auto c1 = mrrg.insert("c1");
    auto c_end = mrrg.insert("c_end");
    auto c_rev = mrrg.insert("c_rev");
    auto join = mrrg.insert("join");
 
    mrrg.link(fu1, split);
    mrrg.link(split, join);
    mrrg.link(join, fu2);
 
    mrrg.link(split, c_start);
    mrrg.link(c_start, c1);
    mrrg.link(c1, c_end);
    mrrg.link(c_end, c_rev);
    mrrg.link(c_end, join);
 
    mrrg.link(c_rev, c_start);
 
    return mrrg;
}
 
template<typename Result, typename Expected>
void checkAllPathsFound(const Result& result, const Expected& expected_paths) {
    std::unordered_set<std::ptrdiff_t> expected_paths_found;
 
    for (auto& path : result) {
        std::ptrdiff_t i = 0;
        for (auto it = begin(expected_paths); it != end(expected_paths); ++it, ++i) {
            auto& epath = *it;
            if (are_ranges_same(path, epath)) {
                expected_paths_found.insert(i);
            }
        }
    }
 
    CHECK((std::ptrdiff_t)expected_paths_found.size() == (std::ptrdiff_t)expected_paths.size());
    CHECK((std::ptrdiff_t)result.size() == (std::ptrdiff_t)expected_paths.size());
}
 
} // end anon namespace
 
SCENARIO ("findNShortestPaths Tests", "[graph]") {
    const auto g_algos = GraphAlgorithms<StringIDGraph::VertexID>();
 
    GIVEN ("A 121 graph") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestPaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "i_a", "fu2", },
            { "fu1", "i_b", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A 121 graph and choice A is ignored") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestPaths(-1, graph, sources, findSingleVertex("fu2"), IgnoreVertexSetVisitor<StringIDGraph::VertexID>{{"i_a"}});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "i_b", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A 11211 graph") {
        const auto graph = makeGraph_11211();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestPaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "f1out", "r_a", "f2in", "fu2", },
            { "fu1", "f1out", "r_b", "f2in", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestPaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "split", "b1_1", "b1_2", "b1_3", "join", "fu2", },
            { "fu1", "split", "join", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with a cycle in one branch") {
        const auto graph = makeGraph_2branches1withCycle();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestPaths(3, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "split", "join", "fu2", },
            { "fu1", "split", "c_start", "c1", "c_end", "join", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        WHEN ("Finding one path") {
            const auto sources = singleItemSet("fu1");
            const auto result = g_algos.findNShortestPaths(1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
            THEN ("the shortest path should be found") {
                std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
                    { "fu1", "split", "join", "fu2", },
                };
 
                checkAllPathsFound(result, expected_paths);
            }
        }
    }
 
    GIVEN ("A graph with crossbars") {
        const auto graph = makeGraph_12x2x2x21();
        for (int i = 0; i <= 35; i += 1) {
            WHEN ("Finding " << i << " path(s)") {
                const auto sources = singleItemSet("fu1");
                const auto result = g_algos.findNShortestPaths(i, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
                const auto expected_num_paths = std::min(i,16);
                THEN (expected_num_paths << " path(s) should be found") {
                    CHECK(result.size() == expected_num_paths);
                }
            }
        }
    }
 
    GIVEN("A 12x21 graph") {
        const auto graph = makeGraph_12x21();
        const int num_paths = GENERATE(range(0,4+1));
        WHEN ("Finding " << num_paths << " path(s), exept paths with both fu1_out_a and xb_1_a") {
            const auto sources = singleItemSet("fu1");
            auto v = DebugVisitor<StringIDGraph::VertexID>{};
            const auto result = g_algos.findNShortestPaths(num_paths, graph, sources, findSingleVertex("fu2"), v, [](const auto& path) {
                return std::find(path.begin(), path.end(), "fu1_out_a") != path.end() || std::find(path.begin(), path.end(), "xb_1_a") != path.end();
            });
 
            THEN ("some paths may be found") {
                CHECK(result.size() == std::min(3,num_paths));
            }
        }
    }
 
    GIVEN("A 112x211 graph") {
        const auto graph = makeGraph_112x211();
        const int num_paths = GENERATE(range(0,5+1));
        WHEN ("Finding " << num_paths << " path(s), exept paths with both xb_1_a and xb_2_a") {
            const auto sources = singleItemSet("fu1");
            auto v = DebugVisitor<StringIDGraph::VertexID>{};
            const auto result = g_algos.findNShortestPaths(num_paths, graph, sources, findSingleVertex("fu2"), v, [](const auto& path) {
                return std::find(path.begin(), path.end(), "xb_1_a") != path.end() || std::find(path.begin(), path.end(), "xb_2_a") != path.end();
            });
 
            THEN ("some paths may be found") {
                CHECK(result.size() == std::min(3,num_paths));
            }
        }
    }
 
    GIVEN("A 112x211 graph") {
        const auto graph = makeGraph_112x211();
        const int num_paths = GENERATE(range(0,5+1));
        WHEN ("Finding " << num_paths << " path(s), exept paths with xb_2_a") {
            const auto sources = singleItemSet("fu1");
            auto v = DebugVisitor<StringIDGraph::VertexID>{};
            const auto result = g_algos.findNShortestPaths(num_paths, graph, sources, findSingleVertex("fu2"), v, [](const auto& path) {
                return std::find(path.begin(), path.end(), "xb_2_a") != path.end();
            });
 
            THEN ("some paths may be found") {
                CHECK(result.size() == std::min(2,num_paths));
            }
        }
    }
 
    GIVEN("A 12x2x21 graph") {
        const auto graph = makeGraph_12x2x21();
        const int num_paths = GENERATE(range(0,7+1));
        WHEN ("Finding " << num_paths << " path(s), exept paths with both fu1_out_a and xb_2_a") {
            const auto sources = singleItemSet("fu1");
            auto v = DebugVisitor<StringIDGraph::VertexID>{};
            const auto result = g_algos.findNShortestPaths(num_paths, graph, sources, findSingleVertex("fu2"), v, [](const auto& path) {
                return std::find(path.begin(), path.end(), "fu1_out_a") != path.end() || std::find(path.begin(), path.end(), "xb_2_a") != path.end();
            });
 
            THEN ("some paths may be found") {
                CHECK(result.size() == std::min(6,num_paths));
            }
        }
    }
 
    GIVEN("A 12x21 graph with loop") {
        const auto graph = makeGraph_12x21_with_loop();
        const int num_paths = GENERATE(range(0,5+1));
        WHEN ("Finding " << num_paths << " loop path(s)") {
            const auto sources = singleItemSet("fu1");
            auto v = DebugVisitor<StringIDGraph::VertexID>{};
            const auto result = g_algos.findNShortestPaths(num_paths, graph, sources, findSingleVertex("fu1"), v);
 
            THEN ("some paths may be found") {
                CHECK(result.size() == std::min(4,num_paths));
            }
        }
    }
}
 
SCENARIO ("findNShortestSimplePaths Tests", "[graph]") {
    const auto g_algos = GraphAlgorithms<StringIDGraph::VertexID>();
 
    GIVEN ("A 121 graph") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestSimplePaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "i_a", "fu2", },
            { "fu1", "i_b", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A 121 graph and choice A is ignored") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestSimplePaths(-1, graph, sources, findSingleVertex("fu2"), IgnoreVertexSetVisitor<StringIDGraph::VertexID>{{"i_a"}});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "i_b", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A 11211 graph") {
        const auto graph = makeGraph_11211();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestSimplePaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "f1out", "r_a", "f2in", "fu2", },
            { "fu1", "f1out", "r_b", "f2in", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestSimplePaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "split", "b1_1", "b1_2", "b1_3", "join", "fu2", },
            { "fu1", "split", "join", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with a cycle in one branch") {
        const auto graph = makeGraph_2branches1withCycle();
 
        const auto sources = singleItemSet("fu1");
        const auto result = g_algos.findNShortestSimplePaths(-1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
        std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
            { "fu1", "split", "join", "fu2", },
            { "fu1", "split", "c_start", "c1", "c_end", "join", "fu2", },
        };
 
        checkAllPathsFound(result, expected_paths);
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        WHEN ("Finding one path") {
            const auto sources = singleItemSet("fu1");
            const auto result = g_algos.findNShortestSimplePaths(1, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
            THEN ("the shortest path should be found") {
                std::vector<std::vector<StringIDGraph::VertexID>> expected_paths {
                    { "fu1", "split", "join", "fu2", },
                };
 
                checkAllPathsFound(result, expected_paths);
            }
        }
    }
 
    GIVEN ("A graph with crossbars") {
        const auto graph = makeGraph_12x2x2x21();
        for (int i = 0; i <= 35; i += 1) {
            WHEN ("Finding " << i << " path(s)") {
                const auto sources = singleItemSet("fu1");
                const auto result = g_algos.findNShortestSimplePaths(i, graph, sources, findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
 
                const auto expected_num_paths = std::min(i,16);
                THEN (expected_num_paths << " path(s) should be found") {
                    CHECK(result.size() == expected_num_paths);
                }
            }
        }
    }
}
 
 
SCENARIO ("depthFirstVisit Tests", "[graph]") {
    const auto g_algos = GraphAlgorithms<StringIDGraph::VertexID>();
 
    GIVEN ("A 121 graph") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "i_a", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A 121 graph and choice A is ignored") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), IgnoreVertexSetVisitor<StringIDGraph::VertexID>{{"i_a"}});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "i_b", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A 11211 graph") {
        const auto graph = makeGraph_11211();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "f1out", "r_a", "f2in", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "split", "b1_1", "b1_2", "b1_3", "join", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A graph with uneven branches - find the other path") {
        const auto graph = makeGraph_2unevenBranches();
 
        const auto sources = singleItemSet("fu1");
        IgnoreEdgeSetVisitor<StringIDGraph::VertexID> path_ignorer {{{"b1_2", "b1_3"}}};
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), path_ignorer);
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "split", "join", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A graph with a cycle in one branch") {
        const auto graph = makeGraph_2branches1withCycle();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.depthFirstVisit(graph, *begin(sources), findSingleVertex("fu2"), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "split", "join", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
}
 
SCENARIO ("wavedBreadthFirstVisit Tests", "[graph]") {
    const auto g_algos = GraphAlgorithms<StringIDGraph::VertexID>();
 
    GIVEN ("A 121 graph") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.wavedBreadthFirstVisit(graph, sources, visitAllVertices(), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "i_a", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A 11211 graph") {
        const auto graph = makeGraph_11211();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.wavedBreadthFirstVisit(graph, sources, visitAllVertices(), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "f1out", "r_a", "f2in", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A graph with uneven branches") {
        const auto graph = makeGraph_2unevenBranches();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.wavedBreadthFirstVisit(graph, sources, visitAllVertices(), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "split", "join", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
 
    GIVEN ("A graph with a cycle in one branch") {
        const auto graph = makeGraph_2branches1withCycle();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_data = g_algos.wavedBreadthFirstVisit(graph, sources, visitAllVertices(), DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "split", "join", "fu2",
        };
 
        CHECK(are_ranges_same(result.path, expected_path));
    }
}
 
template <typename VertexID = StringIDGraph::VertexID, typename Cost = int>
auto vertexCosterWithDefault(Cost default_, std::map<VertexID, Cost> costs) {
    return [=](const VertexID& v) {
        auto lookup = costs.find(v);
        return lookup == costs.end() ? default_ : lookup->second;
    };
}
 
SCENARIO ("dijkstraVisit Tests", "[graph]") {
    const auto g_algos = GraphAlgorithms<StringIDGraph::VertexID>();
 
    GIVEN ("A 121 graph -- prefer b") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_coster = [](const auto& v) { return v == "i_b" ? 1 : 2; };
        const auto vertex_data = g_algos.dijkstraVisit(graph, sources, vertex_coster, DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "i_b", "fu2",
        };
 
        CHECK(result.path == expected_path);
    }
 
    GIVEN ("A 121 graph -- prefer a") {
        const auto graph = makeGraph_121();
 
        const auto sources = singleItemSet("fu1");
        const auto vertex_coster = [](const auto& v) { return v == "i_a" ? 1 : 2; };
        const auto vertex_data = g_algos.dijkstraVisit(graph, sources, vertex_coster, DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(sources, "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "i_a", "fu2",
        };
 
        CHECK(result.path == expected_path);
    }
 
    GIVEN ("A 12x21 graph -- neg cost to other source") {
        const auto graph = makeGraph_12x21();
 
        const auto sources = std::set<StringIDGraph::VertexID>{"fu1", "xb_1_a"};
        const auto vertex_coster = [](const auto& v) {
            if (v == "fu1_out_a") return -2;
            if (v == "xb_1_b") return 2;
            return 1;
        };
        const auto vertex_data = g_algos.dijkstraVisit(graph, sources, vertex_coster, DebugVisitor<StringIDGraph::VertexID>{});
        const auto result = g_algos.singleTraceback(singleItemSet("fu1"), "fu2", vertex_data);
 
        std::vector<StringIDGraph::VertexID> expected_path {
            "fu1", "fu1_out_a", "xb_1_a", "fu2",
        };
 
        CHECK(result.path == expected_path);
    }
}
 
 
namespace {
 
struct BFSCallbackTestDescription {
    using VertexID = StringIDGraph::VertexID;
    using MyGraphAlgorithms = GraphAlgorithms<VertexID>;
    std::string graph_description;
    std::set<std::string> sources;
    int expected_num_edges_not_visited_and_not_skipped; // expected No. of edges that won't be seen in the search
    std::vector<std::set<std::string>> vertex_order;
    StringIDGraph graph;
};
 
struct BFSCallbackTest_UseWavedBreadthFirstVisit {
    std::string name = "wavedBreadthFirstVisit";
 
    template<typename GAlgo, typename G, typename Sources, typename V>
    decltype(auto) invoke(GAlgo&& g_algos, G&& graph, Sources&& sources, V&& visitor) const {
        return g_algos.wavedBreadthFirstVisit(graph, sources, visitAllVertices(), visitor);
    }
 
    template<typename Test, typename RV, typename AllEdges>
    void check_result(const Test& test, const RV& bfv_result, const AllEdges& edges_visited_or_skipped) const {
        // check that all edges visited are present
        std::decay_t<decltype(edges_visited_or_skipped)> edges_in_result;
        for (const auto& v_and_vdata : bfv_result) {
            for (const auto& fanin : v_and_vdata.second.fanin) {
                edges_in_result.insert({fanin, v_and_vdata.first});
            }
        }
        CHECK(edges_in_result == edges_visited_or_skipped);
    }
};
 
struct BFSCallbackTest_UseBreadthFirstVisit {
    std::string name = "breadthFirstVisit";
 
    template<typename GAlgo, typename G, typename Sources, typename V>
    decltype(auto) invoke(GAlgo&& g_algos, G&& graph, Sources&& sources, V&& visitor) const {
        return g_algos.breadthFirstVisit(graph, sources, visitor);
    }
 
    template<typename Test, typename RV, typename AllEdges>
    void check_result(const Test& test, const RV& bfv_result, const AllEdges& edges_visited_or_skipped) const {
        (void)test; (void)bfv_result; (void)edges_visited_or_skipped; // nothing to check, yet
    }
};
 
struct BFSCallbackTest_UseDijkstraVisit_UniformCost {
    std::string name = "dijkstraVisit";
 
    template<typename GAlgo, typename G, typename Sources, typename V>
    decltype(auto) invoke(GAlgo&& g_algos, G&& graph, Sources&& sources, V&& visitor) const {
        const auto vertex_coster = [](auto&&) { return 1; }; // so it behaves like a BFS
        return g_algos.dijkstraVisit(graph, sources, vertex_coster, visitor);
    }
 
    template<typename Test, typename RV, typename AllEdges>
    void check_result(const Test& test, const RV& bfv_result, const AllEdges& edges_visited_or_skipped) const {
        (void)test; (void)bfv_result; (void)edges_visited_or_skipped; // nothing to check, yet
    }
};
 
} // end anon namespace
 
TEMPLATE_TEST_CASE("BreadthFirstVisit Callback Tests", "",
    BFSCallbackTest_UseWavedBreadthFirstVisit,
    BFSCallbackTest_UseBreadthFirstVisit,
    BFSCallbackTest_UseDijkstraVisit_UniformCost
) {
    const auto& test = GENERATE(values<BFSCallbackTestDescription>({
        { "121",                  {"fu1"},            0, { {"fu1"},        {"i_a","i_b"},    {"fu2"} },       makeGraph_121() },
        { "121",                  {"fu1","i_a"},      0, { {"fu1","i_a"},  {"i_b","fu2"} },                   makeGraph_121() },
        { "121",                  {"i_a"},            3, { {"i_a"},        {"fu2"} },                         makeGraph_121() },
        { "121",           {"fu1","i_a","i_b","fu2"}, 0, { {"fu1","i_a","i_b","fu2"} },                       makeGraph_121() },
        { "Loop3Node",            {"a"},              0, { {"a"},          {"b"},            {"c"} },         makeGraph_Loop3Node() },
        { "Loop3Node",            {"a","c"},          0, { {"a","c"},      {"b"}, },                          makeGraph_Loop3Node() },
        { "Loop3NodeWithExtraFanout", {"a"},          0, { {"a"},          {"b","d"},        {"c"} },         makeGraph_Loop3NodeWithExtraFanout() },
        { "2unevenBranches",      {"fu1"},            0, { {"fu1"},        {"split"},        {"b1_1","join"},     {"b1_2","fu2"},  {"b1_3"} },                makeGraph_2unevenBranches() },
        { "2branches1withCycle",  {"fu1"},            0, { {"fu1"},        {"split"},        {"c_start","join"},  {"fu2","c1"},    {"c_end"},   {"c_rev"} },  makeGraph_2branches1withCycle() },
    }));
 
    using Catch::Detail::stringify; // non public... but unlikely to change
    const auto g_algos = typename std::remove_reference_t<decltype(test)>::MyGraphAlgorithms();
    using VertexID = typename std::remove_reference_t<decltype(test)>::VertexID;
    using Visitor = EventRecordingVisitor<VertexID, DebugVisitor<VertexID>>;
 
    const TestType bfv_name_and_func;
 
    GIVEN("A " << test.graph_description << " graph") {
        const auto& graph = test.graph;
        WHEN("Running " << bfv_name_and_func.name << ", starting at " << stringify(test.sources)) {
            auto eventVisitor = Visitor{};
            const auto bfv_result = bfv_name_and_func.invoke(g_algos, graph, test.sources, eventVisitor);
 
            THEN("Vertices and edges were visited in the right order") {
                auto vertices_visited = std::set<VertexID>{};
                auto edges_visited = std::set<std::pair<VertexID,VertexID>>{};
                auto edges_skipped = std::set<std::pair<VertexID,VertexID>>{};
                auto vertices_visited_this_wave = std::set<VertexID>{};
                auto targets_of_edges_in_this_wave = std::set<VertexID>{};
                auto targets_of_edges_visited = std::set<VertexID>{};
                auto vertex_order_it = test.vertex_order.begin();
 
                for (const auto& event : eventVisitor.examine_order) {
                    INFO("Checking event " << event);
                    // skip any events we don't know about
                    if (true
                        && event.type != Visitor::Event::onExamine
                        && event.type != Visitor::Event::onSkipped
                        && event.type != Visitor::Event::onExamineEdge
                        && event.type != Visitor::Event::onSkippedEdge
                        && event.type != Visitor::Event::onWaveEnd
                    ) { continue; }
 
                    // remaining events, but visited everything? error
                    REQUIRE(vertex_order_it != test.vertex_order.end());
 
                    INFO(
                        "In wave " << 1 + std::distance(test.vertex_order.begin(), vertex_order_it)
                        << "/" << test.vertex_order.size() << ": " << stringify(*vertex_order_it)
                    );
 
                    // the next wave, or empty if none.
                    std::decay_t<decltype(*vertex_order_it)> expected_next_wave;
                    if (std::next(vertex_order_it) != test.vertex_order.end()) {
                        expected_next_wave = *std::next(vertex_order_it);
                    }
 
                    INFO("Expected next wave " << stringify(expected_next_wave));
 
                    const auto advance_wave = [&]{
                        // have we visited everything?
                        CHECK(vertices_visited_this_wave == *vertex_order_it);
                        CHECK(expected_next_wave == targets_of_edges_in_this_wave);
 
                        // advance the wave
                        ++vertex_order_it;
                        vertices_visited_this_wave.clear();
                        targets_of_edges_in_this_wave.clear();
                    };
 
                    if (event.type == Visitor::Event::onExamine) {
                        const auto& v = event.v1;
 
                        if (not vertex_order_it->count(v)) {
                            advance_wave();
                        }
 
                        // supposed to be in this wave
                        CHECK(vertex_order_it->count(v));
                        // unique in this wave
                        CHECK(vertices_visited_this_wave.insert(v).second);
                        // unique in this visit
                        CHECK(vertices_visited.insert(v).second);
 
 
                    } else if (event.type == Visitor::Event::onSkipped) {
                        const auto& v = event.v1;
 
                        // should have already visited it
                        CHECK(vertices_visited.count(v));
 
                    } else if (event.type == Visitor::Event::onExamineEdge) {
                        const auto next_wave_it = std::next(vertex_order_it);
                        const auto& source = event.v1;
                        const auto& target = event.v2;
 
                        // can't be on the last wave
                        REQUIRE(next_wave_it != test.vertex_order.end());
                        // source is in this wave
                        CHECK(vertex_order_it->count(source));
                        // target is in the next wave
                        CHECK(expected_next_wave.count(target));
                        // can't have already visited it
                        CHECK(edges_visited.insert({source, target}).second);
                        // must not have already skipped it
                        CHECK(edges_skipped.count({source, target}) == 0);
                        // already visited source
                        CHECK(vertices_visited_this_wave.count(source));
                        // one one edge per vertex in next wave (others are onSkippedEdge)
                        CHECK(targets_of_edges_in_this_wave.insert(target).second);
                        // one one edge per vertex ever
                        CHECK(targets_of_edges_visited.insert(target).second);
 
                    } else if (event.type == Visitor::Event::onSkippedEdge) {
                        const auto& source = event.v1;
                        const auto& target = event.v2;
 
                        // must have already visited source
                        CHECK(vertices_visited.count(source));
                        // must have already seen an edge with target target, or it's a source
                        CHECK((targets_of_edges_visited.count(target) || test.sources.count(target)));
                        // can't have already skipped it
                        CHECK(edges_skipped.insert({source, target}).second);
                        // must not have visited this edge
                        CHECK(edges_visited.count({source, target}) == 0);
 
                    } else if (event.type == Visitor::Event::onWaveEnd) {
                        advance_wave();
                    }
                }
 
                // should have reached the end
                CHECK((vertex_order_it == test.vertex_order.end() || std::next(vertex_order_it) == test.vertex_order.end()));
                // should be empty at the end
                CHECK(targets_of_edges_in_this_wave.empty());
 
                const auto edges_visited_or_skipped = [&]() { // (immediately invoked)
                    auto result = edges_visited;
                    std::copy(edges_skipped.begin(), edges_skipped.end(), std::inserter(result, result.end()));
                    return result;
                }();
 
                const auto num_edges_expected = std::accumulate(graph.fanout_lists.begin(), graph.fanout_lists.end(), 0,
                    [](const auto& lhs, const auto& elem) { return lhs + (std::ptrdiff_t)elem.second.size(); }
                ) - test.expected_num_edges_not_visited_and_not_skipped;
 
                CHECK(edges_visited_or_skipped.size() == num_edges_expected);
 
                AND_THEN("the return value should be as expected") {
                    bfv_name_and_func.check_result(test, bfv_result, edges_visited_or_skipped);
                }
            }
        }
    }
}