double sweep
(include/emthrm/graph/tree/double_sweep.hpp)

• View this file on GitHub
• Last update: 2023-05-12 15:57:02+09:00
• Include: #include "emthrm/graph/tree/double_sweep.hpp"

木の直径を求めるアルゴリズムである。

木の直径

木の最遠頂点間距離である。

時間計算量

$O(\lvert V \rvert)$

仕様

名前	戻り値
template <typename CostType> std::pair<CostType, std::vector<int>> double_sweep(const std::vector<std::vector<Edge<CostType>>>& graph);	グラフ $\mathrm{graph}$ の直径とその経路

参考文献

• Gabriel Y. Handler: Minimax Location of a Facility in an Undirected Tree Graph, Transportation Science, Vol. 7, No. 3, pp. 287–293 (1973). https://doi.org/10.1287/trsc.7.3.287
• http://www.prefield.com/algorithm/graph/tree_diameter.html

TODO

• 頂点の重みを基にした直径
  • https://github.com/beet-aizu/library/blob/master/tree/diameterforvertex.cpp

Submissons

https://judge.yosupo.jp/submission/40074

Depends on

• 辺 (include/emthrm/graph/edge.hpp)

Verified with

• グラフ/木/double sweep (test/graph/tree/double_sweep.test.cpp)

Code

#ifndef EMTHRM_GRAPH_TREE_DOUBLE_SWEEP_HPP_
#define EMTHRM_GRAPH_TREE_DOUBLE_SWEEP_HPP_

#include <cassert>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>

#include "emthrm/graph/edge.hpp"

namespace emthrm {

template <typename CostType>
std::pair<CostType, std::vector<int>> double_sweep(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const auto dfs1 = [&graph](auto dfs1, const int par, const int ver)
      -> std::pair<CostType, int> {
    std::pair<CostType, int> res{0, ver};
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) {
        std::pair<CostType, int> child = dfs1(dfs1, ver, e.dst);
        child.first += e.cost;
        if (child.first > res.first) res = child;
      }
    }
    return res;
  };
  const int s = dfs1(dfs1, -1, 0).second;
  const auto [diameter, t] = dfs1(dfs1, -1, s);
  std::vector<int> path{s};
  const auto dfs2 = [&graph, t, &path](auto dfs2, const int par, const int ver)
      -> bool {
    if (ver == t) return true;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par) {
        path.emplace_back(e);
        if (dfs2(dfs2, ver, e)) return true;
        path.pop_back();
      }
    }
    return false;
  };
  assert(dfs2(dfs2, -1, s));
  return {diameter, path};
}

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_TREE_DOUBLE_SWEEP_HPP_

#line 1 "include/emthrm/graph/tree/double_sweep.hpp"



#include <cassert>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 11 "include/emthrm/graph/tree/double_sweep.hpp"

namespace emthrm {

template <typename CostType>
std::pair<CostType, std::vector<int>> double_sweep(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const auto dfs1 = [&graph](auto dfs1, const int par, const int ver)
      -> std::pair<CostType, int> {
    std::pair<CostType, int> res{0, ver};
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) {
        std::pair<CostType, int> child = dfs1(dfs1, ver, e.dst);
        child.first += e.cost;
        if (child.first > res.first) res = child;
      }
    }
    return res;
  };
  const int s = dfs1(dfs1, -1, 0).second;
  const auto [diameter, t] = dfs1(dfs1, -1, s);
  std::vector<int> path{s};
  const auto dfs2 = [&graph, t, &path](auto dfs2, const int par, const int ver)
      -> bool {
    if (ver == t) return true;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (e != par) {
        path.emplace_back(e);
        if (dfs2(dfs2, ver, e)) return true;
        path.pop_back();
      }
    }
    return false;
  };
  assert(dfs2(dfs2, -1, s));
  return {diameter, path};
}

}  // namespace emthrm

Back to top page