1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#pragma once


#include <utility>
#include <vector><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "structure/graph.hpp"


namespace uni {

namespace internal {


template<class Graph>
std::pair<typename Graph::cost_type, typename Graph::node_type> farthest(const Graph& tree, const typename Graph::node_type v, const typename Graph::node_type p, std::vector<typename Graph::node_type> *const prev = nullptr) {
    std::pair<typename Graph::cost_type, typename Graph::node_type> res = { 0, v };

    for(auto nv : tree[v]) {
        if(nv.to == p) continue;

        auto next = farthest(tree, nv.to, v, prev);
        next.first += nv.cost;

        if(res.first < next.first) {
            if(prev) prev->operator[](nv.to) = v;
            res = next;
        }
    }

    return res;
}


} // namespace internal


template<class Graph>
auto tree_diamiter(const Graph& tree, std::vector<typename Graph::node_type> *const prev = nullptr) {
    const auto p = farthest(tree, 0, -1);
    return farthest(tree, p.second, -1, prev);
}



} // namespace uni