Library
This documentation is automatically generated by online-judge-tools/verification-helper
Digraph
(src/graph/digraph.h)
- View this file on GitHub
- Last update: 2021-11-30 17:55:32+09:00
Depends on
Required by
Verified with
- test/aizu-online-judge/GRL_1_A.test.cpp
- test/aizu-online-judge/GRL_3_C.test.cpp
- test/aizu-online-judge/GRL_4_A.test.cpp
- test/library-checker/scc.test.cpp
- test/library-checker/shortest_path.test.cpp
Code
#pragma once
/**
* @file digraph.h
* @brief Digraph
*/
#include "base.h"
namespace workspace {
template <class _Attr = _graph_impl::null,
class _List = std::vector<edge<_Attr>>>
class digraph : public graph_base<_Attr, _List> {
public:
using base_type = graph_base<_Attr, _List>;
using typename base_type::edge_type;
using typename base_type::node_type;
using typename base_type::size_type;
using base_type::size;
using base_type::operator[];
digraph(size_type __n = 0) : base_type(__n) {}
auto scc() const noexcept;
};
template <class _Weight, class _Attr = _graph_impl::null,
class _List = std::vector<weighted_edge<_Weight, _Attr>>>
using weighted_digraph = digraph<_Attr, _List>;
} // namespace workspace#line 2 "src/graph/digraph.h"
/**
* @file digraph.h
* @brief Digraph
*/
#line 2 "src/graph/base.h"
/**
* @file base.h
* @brief Base
*/
#include <algorithm>
#include <cassert>
#include <list>
#include <numeric>
#include <vector>
#line 2 "src/graph/edge.h"
/**
* @file edge.h
* @brief Edge
*/
#line 2 "lib/cxx17"
#line 2 "lib/cxx14"
#ifndef _CXX14_CONSTEXPR
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
#endif
#line 4 "lib/cxx17"
#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif
#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif
#include <iterator>
#if __cplusplus < 201703L
namespace std {
/**
* @brief Return the size of a container.
* @param __cont Container.
*/
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
-> decltype(__cont.size()) {
return __cont.size();
}
/**
* @brief Return the size of an array.
*/
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
return _Nm;
}
/**
* @brief Return whether a container is empty.
* @param __cont Container.
*/
template <typename _Container>
[[nodiscard]] constexpr auto empty(const _Container& __cont) noexcept(
noexcept(__cont.empty())) -> decltype(__cont.empty()) {
return __cont.empty();
}
/**
* @brief Return whether an array is empty (always false).
*/
template <typename _Tp, size_t _Nm>
[[nodiscard]] constexpr bool empty(const _Tp (&)[_Nm]) noexcept {
return false;
}
/**
* @brief Return whether an initializer_list is empty.
* @param __il Initializer list.
*/
template <typename _Tp>
[[nodiscard]] constexpr bool empty(initializer_list<_Tp> __il) noexcept {
return __il.size() == 0;
}
struct monostate {};
} // namespace std
#else
#include <variant>
#endif
#line 9 "src/graph/edge.h"
namespace workspace {
namespace _graph_impl {
// Default edge attribute.
struct null {};
} // namespace _graph_impl
template <class _Weight, class _Attr = _graph_impl::null>
struct weighted_edge : _Attr {
using attribute = _Attr;
using value_type = _Weight;
using node_type = size_t;
node_type tail, head;
value_type weight{};
constexpr weighted_edge() = default;
template <class... _Args>
constexpr weighted_edge(node_type __u, node_type __v, value_type __c = 0,
_Args &&...__args) noexcept
: _Attr{std::forward<_Args>(__args)...},
tail(__u),
head(__v),
weight(__c) {}
constexpr bool operator<(const weighted_edge &__e) const noexcept {
return weight < __e.weight;
}
constexpr bool operator<=(const weighted_edge &__e) const noexcept {
return weight <= __e.weight;
}
constexpr bool operator>(const weighted_edge &__e) const noexcept {
return weight > __e.weight;
}
constexpr bool operator>=(const weighted_edge &__e) const noexcept {
return weight >= __e.weight;
}
};
template <class _Attr = _graph_impl::null>
struct edge : weighted_edge<int, _Attr> {
using base_type = weighted_edge<int, _Attr>;
using typename base_type::node_type;
using base_type::operator<;
using base_type::operator>;
constexpr edge() = default;
template <class... _Args>
constexpr edge(node_type __u, node_type __v, _Args &&...__args) noexcept
: base_type(__u, __v, __u != __v, std::forward<_Args>(__args)...) {}
};
template <size_t _Nm, class _Attr>
constexpr std::tuple_element_t<_Nm, edge<_Attr>> &get(
edge<_Attr> &__e) noexcept {
if _CXX17_CONSTEXPR (_Nm > 1)
return __e;
else if _CXX17_CONSTEXPR (_Nm)
return __e.head;
else
return __e.tail;
}
template <size_t _Nm, class _Attr>
constexpr const std::tuple_element_t<_Nm, edge<_Attr>> &get(
const edge<_Attr> &__e) noexcept {
if _CXX17_CONSTEXPR (_Nm > 1)
return __e;
else if _CXX17_CONSTEXPR (_Nm)
return __e.head;
else
return __e.tail;
}
template <size_t _Nm, class _Attr>
constexpr std::tuple_element_t<_Nm, edge<_Attr>> &&get(
edge<_Attr> &&__e) noexcept {
return std::move(get<_Nm>(__e));
}
template <size_t _Nm, class _Weight, class _Attr>
constexpr const std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &get(
const weighted_edge<_Weight, _Attr> &__e) noexcept {
if _CXX17_CONSTEXPR (_Nm > 2)
return __e;
else if _CXX17_CONSTEXPR (_Nm > 1)
return __e.weight;
else if _CXX17_CONSTEXPR (_Nm)
return __e.head;
else
return __e.tail;
}
template <size_t _Nm, class _Weight, class _Attr>
constexpr std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &get(
weighted_edge<_Weight, _Attr> &__e) noexcept {
if _CXX17_CONSTEXPR (_Nm > 2)
return __e;
else if _CXX17_CONSTEXPR (_Nm > 1)
return __e.weight;
else if _CXX17_CONSTEXPR (_Nm)
return __e.head;
else
return __e.tail;
}
template <size_t _Nm, class _Weight, class _Attr>
constexpr std::tuple_element_t<_Nm, weighted_edge<_Weight, _Attr>> &&get(
weighted_edge<_Weight, _Attr> &&__e) noexcept {
return std::move(get<_Nm>(__e));
}
} // namespace workspace
namespace std {
template <class _Attr>
struct tuple_size<workspace::edge<_Attr>> : integral_constant<size_t, 3> {};
template <>
struct tuple_size<workspace::edge<>> : integral_constant<size_t, 2> {};
template <class _Weight, class _Attr>
struct tuple_size<workspace::weighted_edge<_Weight, _Attr>>
: integral_constant<size_t, 4> {};
template <class _Weight>
struct tuple_size<workspace::weighted_edge<_Weight>>
: integral_constant<size_t, 3> {};
template <size_t _Nm, class _Attr>
struct tuple_element<_Nm, workspace::edge<_Attr>> {
using type = std::conditional_t<(_Nm < 2), size_t, _Attr>;
};
template <size_t _Nm, class _Weight, class _Attr>
struct tuple_element<_Nm, workspace::weighted_edge<_Weight, _Attr>> {
using type = std::conditional_t<(_Nm < 2), size_t,
std::conditional_t<_Nm == 2, _Weight, _Attr>>;
};
} // namespace std
#line 2 "src/graph/queue.h"
/**
* @file queue.h
* @brief Queue
*/
#include <queue>
#include <stack>
namespace workspace {
namespace _graph_impl {
template <class _Base, class = void> struct stl_queue : _Base {
auto pop() noexcept {
auto __tmp = std::move(_Base::front());
_Base::pop();
return __tmp;
}
};
template <class _Base>
struct stl_queue<_Base, std::__void_t<decltype(std::declval<_Base>().top())>>
: _Base {
auto pop() noexcept {
auto __tmp = std::move(_Base::top());
_Base::pop();
return __tmp;
}
};
} // namespace _graph_impl
} // namespace workspace
#line 16 "src/graph/base.h"
namespace workspace {
template <class _Attr = _graph_impl::null,
class _List = std::vector<edge<_Attr>>>
class graph_base : public std::vector<_List> {
public:
using container_type = std::vector<_List>;
using typename container_type::size_type;
using container_type::size;
using container_type::operator[];
using node_type = size_type;
using edge_type = typename _List::value_type;
using weight_type = typename edge_type::value_type;
graph_base(size_type __n = 0) : container_type(__n) {}
/**
* @brief Add some nodes to the graph.
* @param __n Number of nodes added
* @return List of indices of the nodes.
*/
auto add_nodes(size_type __n) noexcept {
std::vector<node_type> __ret(__n);
std::iota(__ret.begin(), __ret.end(), size());
container_type::resize(__n + size());
return __ret;
}
node_type add_node() noexcept { return add_nodes(1).front(); }
template <class... _Args>
decltype(auto) add_edge(node_type __u, node_type __v,
_Args &&...__args) noexcept {
assert(__u < size()), assert(__v < size());
return operator[](__u).emplace_back(__u, __v,
std::forward<_Args>(__args)...)
#if __cplusplus <= 201402L
,
operator[](__u).back()
#endif
;
}
decltype(auto) add_edge(const edge_type &__e) noexcept {
assert(__e.tail < size()), assert(__e.head < size());
return operator[](__e.tail).emplace_back(__e)
#if __cplusplus <= 201402L
,
operator[](__e.tail).back()
#endif
;
}
/**
* @brief Single-source DFS.
* @return Edges of DFS-tree in the search order.
*/
decltype(auto) dfs(node_type __r) const noexcept {
node_type __a[]{__r};
return dfs(__a, __a + 1);
}
/**
* @brief Multi-source DFS.
* @return Edges of DFS-tree in the search order.
*/
template <class _Iterator>
decltype(auto) dfs(_Iterator __first, _Iterator __last) const noexcept {
return search<std::stack<edge_type, std::vector<edge_type>>>(__first,
__last);
}
/**
* @brief Single-source DFS in the complement graph.
* @return Edges of DFS-tree in the search order.
*/
decltype(auto) compl_dfs(node_type __r) const noexcept {
node_type __a[]{__r};
return compl_dfs(__a, __a + 1);
}
/**
* @brief Multi-source DFS in the complement graph.
* @return Edges of DFS-tree in the search order.
*/
template <class _Iterator>
decltype(auto) compl_dfs(_Iterator __first, _Iterator __last) const noexcept {
return compl_search<std::stack<edge_type, std::vector<edge_type>>>(__first,
__last);
}
/**
* @brief Single-source BFS.
* @return Edges of BFS-tree in the search order.
*/
decltype(auto) bfs(node_type __r) const noexcept {
node_type __a[]{__r};
return bfs(__a, __a + 1);
}
/**
* @brief Multi-source BFS.
* @return Edges of BFS-tree in the search order.
*/
template <class _Iterator>
decltype(auto) bfs(_Iterator __first, _Iterator __last) const noexcept {
return search<std::queue<edge_type>>(__first, __last);
}
/**
* @brief Single-source BFS in the complement graph.
* @return Edges of BFS-tree in the search order.
*/
decltype(auto) compl_bfs(node_type __r) const noexcept {
node_type __a[]{__r};
return compl_bfs(__a, __a + 1);
}
/**
* @brief Multi-source BFS in the complement graph.
* @return Edges of BFS-tree in the search order.
*/
template <class _Iterator>
decltype(auto) compl_bfs(_Iterator __first, _Iterator __last) const noexcept {
return compl_search<std::queue<edge_type>>(__first, __last);
}
/**
* @brief Single-source Dijkstra's algorithm.
* @return Edges of shortest path tree in the search order.
*/
decltype(auto) dijkstra(node_type __r) const noexcept {
node_type __a[]{__r};
return dijkstra(__a, __a + 1);
}
/**
* @brief Multi-source Dijkstra's algorithm.
* @return Edges of shortest path tree in the search order.
*/
template <class _Iterator>
decltype(auto) dijkstra(_Iterator __first, _Iterator __last) const noexcept {
return distance_from<std::priority_queue<edge_type, std::vector<edge_type>,
std::greater<edge_type>>>(__first,
__last);
}
/**
* @brief Single-source Bellman-Ford algorithm.
* @return Edges of shortest path tree in the search order.
*/
decltype(auto) bellman_ford() const noexcept {
std::vector<node_type> __a(size());
return bellman_ford(__a.begin(), __a.end());
}
/**
* @brief Multi-source Bellman-Ford algorithm.
* @return Edges of shortest path tree in the search order.
*/
decltype(auto) bellman_ford(node_type __r) const noexcept {
node_type __a[]{__r};
return bellman_ford(__a, __a + 1);
}
template <class _Iterator>
decltype(auto) bellman_ford(_Iterator __first,
_Iterator __last) const noexcept {
return distance_from<std::queue<edge_type>>(__first, __last);
}
decltype(auto) warshall_floyd(node_type __r) const noexcept;
protected:
/**
* @brief Search from given vertex set.
* @tparam _Container Queue.
*/
template <class _Container, class _Iterator>
auto search(_Iterator __first, _Iterator __last) const noexcept {
static std::vector<int_fast8_t> __visited;
__visited.resize(size());
std::vector<edge_type> __tree;
static _graph_impl::stl_queue<_Container> __queue;
for (auto __s = __first; __s != __last; __visited[*__s++] = true)
for (auto &&__e : operator[](*__s)) __queue.emplace(__e);
while (!__queue.empty()) {
auto &&__p = __queue.pop();
if (__visited[__p.head]) continue;
__visited[__p.head] = true;
for (auto &&__e : operator[](__p.head)) __queue.emplace(__e);
__tree.emplace_back(std::move(__p));
}
while (__first != __last) __visited[*__first++] = false;
for (auto &&__e : __tree) __visited[__e.head] = false;
return __tree;
}
template <class _Container, class _Iterator>
auto compl_search(_Iterator __first, _Iterator __last) const noexcept;
/**
* @brief Get distance from given vertex set.
* @tparam _Container Queue.
*/
template <class _Container, class _Iterator>
auto distance_from(_Iterator __first, _Iterator __last) const noexcept {
struct dist_type {
bool nil = true;
weight_type value;
bool update(const weight_type &__x) noexcept {
return nil || __x < value ? nil = false, value = __x, true : false;
}
};
static _graph_impl::stl_queue<_Container> __queue;
static std::vector<dist_type> __dist;
__dist.resize(size());
std::vector<edge_type> __tree;
for (; __first != __last; ++__first) __queue.emplace(*__first, *__first);
while (!__queue.empty()) {
auto &&__p = __queue.pop();
if (__dist[__p.head].update(__p.weight)) {
for (auto __e : operator[](__p.head))
__e.weight = __p.weight + __e.weight, __queue.emplace(std::move(__e));
if (__p.tail != __p.head) __tree.emplace_back(std::move(__p));
}
}
for (auto &&__e : __tree)
__dist[__e.head].nil = __dist[__e.tail].nil = true;
__tree.erase(std::remove_if(__tree.begin(), __tree.end(),
[&](auto &&__e) {
return __dist[__e.head].value < __e.weight;
}),
__tree.end());
return __tree;
}
};
} // namespace workspace
#line 9 "src/graph/digraph.h"
namespace workspace {
template <class _Attr = _graph_impl::null,
class _List = std::vector<edge<_Attr>>>
class digraph : public graph_base<_Attr, _List> {
public:
using base_type = graph_base<_Attr, _List>;
using typename base_type::edge_type;
using typename base_type::node_type;
using typename base_type::size_type;
using base_type::size;
using base_type::operator[];
digraph(size_type __n = 0) : base_type(__n) {}
auto scc() const noexcept;
};
template <class _Weight, class _Attr = _graph_impl::null,
class _List = std::vector<weighted_edge<_Weight, _Attr>>>
using weighted_digraph = digraph<_Attr, _List>;
} // namespace workspace