 |
KiCad PCB EDA Suite
|
|
KiCad PCB EDA Suite
|
#include <boost/test/unit_test.hpp>#include <core/filter_kruskal.h>#include <core/union_find.h>#include <algorithm>#include <random>#include <tuple>#include <vector>Go to the source code of this file.
Functions | |
| BOOST_AUTO_TEST_CASE (MatchesPlainKruskal) | |
| Sizes are chosen to straddle KRUSKAL_THRESHOLD so both the recursive partitioning path and the direct sort path are exercised. | |
| BOOST_AUTO_TEST_CASE (AllWeightsEqual) | |
| Every weight identical is the case that breaks a naive pivot: the light partition can come back empty and the recursion never shrinks. | |
| BOOST_AUTO_TEST_CASE (FewDistinctWeights) | |
| BOOST_AUTO_TEST_CASE (DisconnectedGraphYieldsForest) | |
| A disconnected graph yields a spanning forest, not a tree, so the ComponentCount()-based early exit never fires and the recursion has to bottom out on its own. | |
| BOOST_AUTO_TEST_CASE (HonoursPreSeededForest) | |
| RN_NET seeds the forest with the connections the board already makes before handing over the candidate edges, so pre-united endpoints have to be filtered rather than selected. | |
| BOOST_AUTO_TEST_CASE (SelectionIsReproducible) | |
| Running the same input twice must give the same tree. | |
| BOOST_AUTO_TEST_CASE (SelectionIgnoresInputOrderAndOrientation) | |
| Reproducibility only follows if the comparator is a total order on undirected edges, which takes a canonical endpoint key. | |
| BOOST_AUTO_TEST_CASE (DegenerateInputs) | |
| BOOST_AUTO_TEST_CASE | ( | AllWeightsEqual | ) |
Every weight identical is the case that breaks a naive pivot: the light partition can come back empty and the recursion never shrinks.
Definition at line 189 of file test_filter_kruskal.cpp.
References rng.
| BOOST_AUTO_TEST_CASE | ( | DegenerateInputs | ) |
Definition at line 366 of file test_filter_kruskal.cpp.
References BOOST_CHECK_EQUAL().
| BOOST_AUTO_TEST_CASE | ( | DisconnectedGraphYieldsForest | ) |
A disconnected graph yields a spanning forest, not a tree, so the ComponentCount()-based early exit never fires and the recursion has to bottom out on its own.
Definition at line 223 of file test_filter_kruskal.cpp.
References rng.
| BOOST_AUTO_TEST_CASE | ( | FewDistinctWeights | ) |
Definition at line 206 of file test_filter_kruskal.cpp.
References rng.
| BOOST_AUTO_TEST_CASE | ( | HonoursPreSeededForest | ) |
RN_NET seeds the forest with the connections the board already makes before handing over the candidate edges, so pre-united endpoints have to be filtered rather than selected.
Definition at line 249 of file test_filter_kruskal.cpp.
References rng.
| BOOST_AUTO_TEST_CASE | ( | MatchesPlainKruskal | ) |
Sizes are chosen to straddle KRUSKAL_THRESHOLD so both the recursive partitioning path and the direct sort path are exercised.
Definition at line 171 of file test_filter_kruskal.cpp.
References BOOST_AUTO_TEST_CASE(), and rng.
| BOOST_AUTO_TEST_CASE | ( | SelectionIgnoresInputOrderAndOrientation | ) |
Reproducibility only follows if the comparator is a total order on undirected edges, which takes a canonical endpoint key.
Feed the same graph with the edge list shuffled and individual edges flipped end for end; the selected tree must not move. Rerunning an identical input, as the case above does, cannot detect the difference.
Definition at line 305 of file test_filter_kruskal.cpp.
References BOOST_REQUIRE(), expected, KI_MST::FilterKruskal(), and rng.
| BOOST_AUTO_TEST_CASE | ( | SelectionIsReproducible | ) |
Running the same input twice must give the same tree.
A randomised pivot would satisfy the weight check above but not this, and the ratsnest is drawn from the result.
Definition at line 273 of file test_filter_kruskal.cpp.
References rng.
1.13.2