src/graph/sp/dijkstra/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	42 / 0 / 42
Functions:	100.0%	3 / 0 / 3
Branches:	83.3%	30 / 0 / 36

    src/graph/sp/dijkstra/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../ds/heap/radix/lib.hpp"
      
        #include "../../../util/traits/math/lib.hpp"
      
        #include "../../ds/graph_c/lib.hpp"
      
        namespace tifa_libs {
      
        // relax(now, to)
      
        template <wgraph_c G, class F, class T = TPN G::Et>
      
        requires(!sint_c<T>) && requires(F relex, u32 now, u32 to) { relex(now, to); }
      
        2202
        CEXP vec<T> dijkstra(G CR g, u32 s, F&& relax, T INF = inf_v<T>) NE {
      
        4404
          vec<T> dis(g.vsize(), INF);
      
        2202
          vecb vis(g.vsize());
      
        2202
          rheap<T, u32> q;
      
        2202
          q.emplace(dis[s] = 0, s);
      
          6/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✓ Branch 1 taken 478589 times.
✓ Branch 2 taken 56 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✓ Branch 1 taken 4631835 times.
✓ Branch 2 taken 29 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✓ Branch 1 taken 273744 times.
✓ Branch 2 taken 2117 times.

        5386370
          while (!q.empty()) {
      
        5384168
            auto [dis_now, u] = q.top();
      
          3/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 478589 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✗ Branch 0 not taken.
✓ Branch 1 taken 4631835 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✗ Branch 0 not taken.
✓ Branch 1 taken 273744 times.

        5384168
            if (dis_now > INF) dis_now = INF;
      
          6/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✓ Branch 3 taken 69231 times.
✓ Branch 4 taken 409358 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✓ Branch 3 taken 732464 times.
✓ Branch 4 taken 3899371 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✓ Branch 3 taken 145025 times.
✓ Branch 4 taken 128719 times.

        5384168
            if (q.pop(); vis[u]) continue;
      
          6/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✓ Branch 8 taken 1107636 times.
✓ Branch 9 taken 409358 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✓ Branch 8 taken 8665967 times.
✓ Branch 9 taken 3899371 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✓ Branch 8 taken 3775226 times.
✓ Branch 9 taken 128719 times.

        17986277
            for (vis[u] = true; auto [v, w] : g[u])
      
          6/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✓ Branch 2 taken 478533 times.
✓ Branch 3 taken 629103 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✓ Branch 2 taken 4631806 times.
✓ Branch 3 taken 4034161 times.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✓ Branch 2 taken 271627 times.
✓ Branch 3 taken 3503599 times.

        13548829
              if (dis[u] + w < dis[v])
      
          3/6std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int):
✓ Branch 5 taken 478533 times.
✗ Branch 6 not taken.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long):
✓ Branch 5 taken 4631806 times.
✗ Branch 6 not taken.
std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long):
✓ Branch 5 taken 271627 times.
✗ Branch 6 not taken.

        5381966
                if (relax(u, v), dis[v] = dis[u] + w; !vis[v]) q.emplace(dis[v], v);
      
          }
      
        2202
          return dis;
      
        2202
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../ds/heap/radix/lib.hpp"
4			#include "../../../util/traits/math/lib.hpp"
5			#include "../../ds/graph_c/lib.hpp"
6
7			namespace tifa_libs {
8
9			// relax(now, to)
10			template <wgraph_c G, class F, class T = TPN G::Et>
11			requires(!sint_c<T>) && requires(F relex, u32 now, u32 to) { relex(now, to); }
12		2202	CEXP vec<T> dijkstra(G CR g, u32 s, F&& relax, T INF = inf_v<T>) NE {
13		4404	vec<T> dis(g.vsize(), INF);
14		2202	vecb vis(g.vsize());
15		2202	rheap<T, u32> q;
16		2202	q.emplace(dis[s] = 0, s);
17	6/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✓ Branch 1 taken 478589 times. ✓ Branch 2 taken 56 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✓ Branch 1 taken 4631835 times. ✓ Branch 2 taken 29 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✓ Branch 1 taken 273744 times. ✓ Branch 2 taken 2117 times.	5386370	while (!q.empty()) {
18		5384168	auto [dis_now, u] = q.top();
19	3/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 478589 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✗ Branch 0 not taken. ✓ Branch 1 taken 4631835 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✗ Branch 0 not taken. ✓ Branch 1 taken 273744 times.	5384168	if (dis_now > INF) dis_now = INF;
20	6/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✓ Branch 3 taken 69231 times. ✓ Branch 4 taken 409358 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✓ Branch 3 taken 732464 times. ✓ Branch 4 taken 3899371 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✓ Branch 3 taken 145025 times. ✓ Branch 4 taken 128719 times.	5384168	if (q.pop(); vis[u]) continue;
21	6/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✓ Branch 8 taken 1107636 times. ✓ Branch 9 taken 409358 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✓ Branch 8 taken 8665967 times. ✓ Branch 9 taken 3899371 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✓ Branch 8 taken 3775226 times. ✓ Branch 9 taken 128719 times.	17986277	for (vis[u] = true; auto [v, w] : g[u])
22	6/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✓ Branch 2 taken 478533 times. ✓ Branch 3 taken 629103 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✓ Branch 2 taken 4631806 times. ✓ Branch 3 taken 4034161 times. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✓ Branch 2 taken 271627 times. ✓ Branch 3 taken 3503599 times.	13548829	if (dis[u] + w < dis[v])
23	3/6 std::vector<unsigned int, std::allocator<unsigned int> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned int): ✓ Branch 5 taken 478533 times. ✗ Branch 6 not taken. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, main::{lambda(unsigned int, unsigned int)#1}, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, main::{lambda(unsigned int, unsigned int)#1}&&, unsigned long): ✓ Branch 5 taken 4631806 times. ✗ Branch 6 not taken. std::vector<unsigned long, std::allocator<unsigned long> > tifa_libs::dijkstra<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> >, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long>(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > const&, unsigned int, tifa_libs::fn_0::{lambda((auto:1&&)...)#1} const&, unsigned long): ✓ Branch 5 taken 271627 times. ✗ Branch 6 not taken.	5381966	if (relax(u, v), dis[v] = dis[u] + w; !vis[v]) q.emplace(dis[v], v);
24			}
25		2202	return dis;
26		2202	}
27
28			} // namespace tifa_libs
29