GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 16 / 0 / 16
Functions: 100.0% 2 / 0 / 2
Branches: 91.7% 11 / 0 / 12
src/graph/mst/kruskal/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../ds/dsu/basic/lib.hpp"
4 #include "../../../tree/ds/lib.hpp"
5 #include "../../ds/alist/lib.hpp"
6
7 namespace tifa_libs {
8
9 //! edges MUST be sorted
10 template <class T>
11 73 CEXP tree<alist<T>> kruskal(vec<edge_t<T>> sorted_a, u32 n) NE {
12 73 tree<alist<T>> tr(n);
13 73 dsu_basic dsu(n);
14
3/4
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > > tifa_libs::kruskal<long>(std::vector<tifa_libs::edge_t<long>, std::allocator<tifa_libs::edge_t<long> > >, unsigned int):
✓ Branch 5 taken 6669628 times.
✗ Branch 6 not taken.
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > tifa_libs::kruskal<unsigned int>(std::vector<tifa_libs::edge_t<unsigned int>, std::allocator<tifa_libs::edge_t<unsigned int> > >, unsigned int):
✓ Branch 5 taken 5397114 times.
✓ Branch 6 taken 1 time.
 12066743 for (u32 m = n - 1; auto [w, u, v] : sorted_a) {
15
4/4
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > > tifa_libs::kruskal<long>(std::vector<tifa_libs::edge_t<long>, std::allocator<tifa_libs::edge_t<long> > >, unsigned int):
✓ Branch 1 taken 2129721 times.
✓ Branch 2 taken 4539907 times.
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > tifa_libs::kruskal<unsigned int>(std::vector<tifa_libs::edge_t<unsigned int>, std::allocator<tifa_libs::edge_t<unsigned int> > >, unsigned int):
✓ Branch 1 taken 4700570 times.
✓ Branch 2 taken 696544 times.
 12066742 if (dsu.merge(u, v)) tr.add_arc(u, v, w), tr.add_arc(v, u, w), --m;
16
4/4
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<long> > > tifa_libs::kruskal<long>(std::vector<tifa_libs::edge_t<long>, std::allocator<tifa_libs::edge_t<long> > >, unsigned int):
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 6669612 times.
tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > tifa_libs::kruskal<unsigned int>(std::vector<tifa_libs::edge_t<unsigned int>, std::allocator<tifa_libs::edge_t<unsigned int> > >, unsigned int):
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 5397058 times.
 12066742 if (!m) break;
17 }
18 73 return tr;
19 73 }
20
21 } // namespace tifa_libs
22