Functional Graph
(graph/functional_graph.hpp)
- View this file on GitHub
- Last update: 2026-08-24 02:34:24+09:00
- Include:
#include "graph/functional_graph.hpp"
Overview
FunctionalGraph represents a directed graph in which every vertex has exactly
one outgoing edge. It decomposes the graph into directed cycles and the trees
that feed into them. Besides large successor jumps and directed reachability
distances, it can enumerate orbits and paths, count visits during a bounded
walk, and find the first meeting of two synchronized walkers.
Construct it directly from a successor array: successor[v] is the vertex
reached after one step from v. Self-loops and disconnected components are
supported. The object is static; call build again to replace the graph.
Public Fields
| Field | Meaning |
|---|---|
component_count |
Number of weakly connected components, equivalently the number of directed cycles. |
successor[v] |
Vertex reached from v after one step. |
predecessors[v] |
Vertices whose successor is v, including the preceding cycle vertex when v is on a cycle. |
cycles[c] |
Vertices of component c’s cycle in successor order. |
component[v] |
Component and cycle id containing v. |
component_size[c] |
Number of vertices in component c, including its cycle and all attached trees. |
cycle_entry[v] |
First cycle vertex reached from v. A cycle vertex is its own entry. |
cycle_position[v] |
Position of cycle_entry[v] in cycles[component[v]]. |
distance_to_cycle[v] |
Number of steps from v to cycle_entry[v]. |
All vertex indices and component indices are zero-based.
Interface
| Method | Exact signature | Description | Complexity |
|---|---|---|---|
| Default constructor | FunctionalGraph() |
Constructs an empty graph. | $O(1)$ |
| Constructor | explicit FunctionalGraph(const std::vector<int>& successor) |
Builds from a successor array. | $O(N\log N)$ time and memory |
build |
void build(const std::vector<int>& successor) |
Replaces the graph and rebuilds all metadata. | $O(N\log N)$ time and memory |
size |
int size() const |
Returns the number of vertices. | $O(1)$ |
empty |
bool empty() const |
Returns whether there are no vertices. | $O(1)$ |
same_component |
bool same_component(int first, int second) const |
Tests whether two vertices belong to the same weakly connected component. | $O(1)$ |
on_cycle |
bool on_cycle(int vertex) const |
Tests whether a vertex lies on a directed cycle. | $O(1)$ |
cycle_size |
int cycle_size(int vertex) const |
Returns the length of the cycle eventually reached from a vertex. | $O(1)$ |
orbit_size |
int orbit_size(int vertex) const |
Returns the number of distinct vertices visited before the walk first repeats. | $O(1)$ |
jump |
int jump(int vertex, std::uint64_t steps) const |
Returns the vertex reached after exactly steps successor edges. |
$O(\log N)$ |
distance |
long long distance(int from, int to) const |
Returns the minimum number of successor edges from from to to, or -1 if to is unreachable. |
$O(\log N)$ |
reachable |
bool reachable(int from, int to) const |
Tests directed reachability along successor edges. | $O(\log N)$ |
path |
std::vector<int> path(int from, int to) const |
Returns the minimum directed path including both endpoints, or an empty vector if unreachable. | $O(D + \log N)$ time and $O(D)$ output memory, where $D$ is the returned distance |
orbit |
std::vector<int> orbit(int vertex) const |
Returns the distinct vertices of the walk in order, stopping immediately before the first repetition. | $O(K)$ time and output memory, where $K$ is orbit_size(vertex)
|
visit_count |
std::uint64_t visit_count(int from, int to, std::uint64_t step_count) const |
Counts times t in [0, step_count) for which the walk from from is at to. |
$O(\log N)$ |
first_meeting_time |
long long first_meeting_time(int first, int second) const |
Returns the minimum t such that both synchronized walks occupy the same vertex after t steps, or -1 if they never meet. |
$O(\log N)$ |
first_meeting_vertex |
int first_meeting_vertex(int first, int second) const |
Returns the vertex at the first synchronized meeting, or -1 if none exists. |
$O(\log N)$ |
Construction asserts that every successor is a valid vertex. Query methods assert that their vertex arguments are valid. No query mutates the object.
Algorithm
Vertices with indegree zero are repeatedly removed. The vertices left behind are exactly the directed cycles. A traversal over reverse edges then assigns each removed vertex to its cycle entry and records its distance from the cycle.
Binary lifting handles the acyclic prefix of a walk. Once a walk reaches its
cycle, jump reduces the remaining 64-bit step count modulo the cycle length.
This avoids storing 64 ancestors per vertex while still accepting every
std::uint64_t step count.
For a target outside a cycle, a walk can visit it at most once. For a target on
a cycle, subsequent visits are separated by the cycle length; visit_count
uses this fact after finding the first visit.
Two synchronized walks can merge before reaching a cycle only when they have the same distance to that cycle and feed into the same cycle entry. Binary lifting finds their first common tail vertex. Otherwise, their eventual cycle positions are compared after adjusting for their different entry times. Matching cycle phases meet as soon as both walkers have reached the cycle; different phases never meet.
Example
#include "graph/functional_graph.hpp"
#include <cstdint>
#include <iostream>
#include <vector>
int main() {
// 0 -> 1 -> 2 -> 0, and 4 -> 3 -> 2.
m1une::graph::FunctionalGraph graph(std::vector<int>{1, 2, 0, 2, 3});
std::cout << graph.jump(4, 4) << '\n'; // 1
std::cout << graph.distance(4, 1) << '\n'; // 4
std::cout << graph.cycle_entry[4] << '\n'; // 2
std::cout << graph.cycle_size(4) << '\n'; // 3
std::cout << graph.orbit_size(4) << '\n'; // 5
std::cout << graph.visit_count(4, 2, 6) << '\n'; // 2
}
Required by
Verified with
- verify/graph/cow_game.test.cpp
- verify/graph/functional_graph.test.cpp
- verify/graph/graph_algorithms.test.cpp
- verify/graph/range_edge_graph.test.cpp
Code
#ifndef M1UNE_GRAPH_FUNCTIONAL_GRAPH_HPP
#define M1UNE_GRAPH_FUNCTIONAL_GRAPH_HPP 1
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <queue>
#include <utility>
#include <vector>
namespace m1une {
namespace graph {
struct FunctionalGraph {
int component_count;
std::vector<int> successor;
std::vector<std::vector<int>> predecessors;
std::vector<std::vector<int>> cycles;
std::vector<int> component;
std::vector<int> component_size;
std::vector<int> cycle_entry;
std::vector<int> cycle_position;
std::vector<int> distance_to_cycle;
private:
std::vector<std::vector<int>> _up;
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < size());
}
int advance_before_cycle(int vertex, int steps) const {
assert(0 <= steps && steps <= distance_to_cycle[vertex]);
int bit = 0;
while (steps > 0) {
if (steps & 1) vertex = _up[bit][vertex];
steps >>= 1;
bit++;
}
return vertex;
}
public:
FunctionalGraph() : component_count(0) {}
explicit FunctionalGraph(const std::vector<int>& successor_) {
build(successor_);
}
void build(const std::vector<int>& successor_) {
successor = successor_;
const int n = size();
for (int to : successor) assert(0 <= to && to < n);
component_count = 0;
predecessors.assign(n, {});
cycles.clear();
component.assign(n, -1);
cycle_entry.assign(n, -1);
cycle_position.assign(n, -1);
distance_to_cycle.assign(n, -1);
std::vector<int> indegree(n, 0);
for (int vertex = 0; vertex < n; vertex++) {
predecessors[successor[vertex]].push_back(vertex);
indegree[successor[vertex]]++;
}
std::queue<int> queue;
std::vector<char> removed(n, false);
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) queue.push(vertex);
}
while (!queue.empty()) {
const int vertex = queue.front();
queue.pop();
removed[vertex] = true;
const int to = successor[vertex];
indegree[to]--;
if (indegree[to] == 0) queue.push(to);
}
for (int start = 0; start < n; start++) {
if (removed[start] || component[start] != -1) continue;
const int component_id = int(cycles.size());
std::vector<int> cycle;
int vertex = start;
do {
const int position = int(cycle.size());
cycle.push_back(vertex);
component[vertex] = component_id;
cycle_entry[vertex] = vertex;
cycle_position[vertex] = position;
distance_to_cycle[vertex] = 0;
vertex = successor[vertex];
} while (vertex != start);
cycles.push_back(std::move(cycle));
}
component_count = int(cycles.size());
for (const std::vector<int>& cycle : cycles) {
for (int vertex : cycle) queue.push(vertex);
}
while (!queue.empty()) {
const int vertex = queue.front();
queue.pop();
for (int from : predecessors[vertex]) {
if (component[from] != -1) continue;
component[from] = component[vertex];
cycle_entry[from] = cycle_entry[vertex];
cycle_position[from] = cycle_position[vertex];
distance_to_cycle[from] = distance_to_cycle[vertex] + 1;
queue.push(from);
}
}
component_size.assign(component_count, 0);
for (int component_id : component) component_size[component_id]++;
int log = 1;
while ((std::uint64_t(1) << log) <= std::uint64_t(n)) log++;
_up.assign(log, successor);
for (int bit = 1; bit < log; bit++) {
for (int vertex = 0; vertex < n; vertex++) {
_up[bit][vertex] = _up[bit - 1][_up[bit - 1][vertex]];
}
}
}
int size() const {
return int(successor.size());
}
bool empty() const {
return successor.empty();
}
bool same_component(int first, int second) const {
check_vertex(first);
check_vertex(second);
return component[first] == component[second];
}
bool on_cycle(int vertex) const {
check_vertex(vertex);
return distance_to_cycle[vertex] == 0;
}
int cycle_size(int vertex) const {
check_vertex(vertex);
return int(cycles[component[vertex]].size());
}
int orbit_size(int vertex) const {
check_vertex(vertex);
return distance_to_cycle[vertex] + cycle_size(vertex);
}
int jump(int vertex, std::uint64_t steps) const {
check_vertex(vertex);
const int tail_length = distance_to_cycle[vertex];
if (steps < std::uint64_t(tail_length)) {
return advance_before_cycle(vertex, int(steps));
}
steps -= std::uint64_t(tail_length);
const int entry = cycle_entry[vertex];
const int length = cycle_size(entry);
const int offset = int(steps % std::uint64_t(length));
const int position = (cycle_position[entry] + offset) % length;
return cycles[component[vertex]][position];
}
long long distance(int from, int to) const {
check_vertex(from);
check_vertex(to);
if (!same_component(from, to)) return -1;
if (!on_cycle(to)) {
if (distance_to_cycle[from] < distance_to_cycle[to]) return -1;
const int difference = distance_to_cycle[from] - distance_to_cycle[to];
return advance_before_cycle(from, difference) == to ? difference : -1;
}
const int entry = cycle_entry[from];
const int length = cycle_size(from);
int cycle_distance = cycle_position[to] - cycle_position[entry];
if (cycle_distance < 0) cycle_distance += length;
return static_cast<long long>(distance_to_cycle[from]) + cycle_distance;
}
bool reachable(int from, int to) const {
return distance(from, to) != -1;
}
std::vector<int> path(int from, int to) const {
const long long path_length = distance(from, to);
if (path_length == -1) return {};
std::vector<int> result;
result.reserve(path_length + 1);
for (long long step = 0; step <= path_length; step++) {
result.push_back(from);
from = successor[from];
}
return result;
}
std::vector<int> orbit(int vertex) const {
check_vertex(vertex);
const int length = orbit_size(vertex);
std::vector<int> result;
result.reserve(length);
for (int step = 0; step < length; step++) {
result.push_back(vertex);
vertex = successor[vertex];
}
return result;
}
std::uint64_t visit_count(
int from,
int to,
std::uint64_t step_count
) const {
const long long first_visit = distance(from, to);
if (first_visit == -1 ||
std::uint64_t(first_visit) >= step_count) {
return 0;
}
if (!on_cycle(to)) return 1;
const std::uint64_t remaining =
step_count - 1 - std::uint64_t(first_visit);
return 1 + remaining / std::uint64_t(cycle_size(to));
}
long long first_meeting_time(int first, int second) const {
check_vertex(first);
check_vertex(second);
if (!same_component(first, second)) return -1;
if (first == second) return 0;
const int first_depth = distance_to_cycle[first];
const int second_depth = distance_to_cycle[second];
if (first_depth == second_depth &&
cycle_entry[first] == cycle_entry[second]) {
int elapsed = 0;
for (int bit = int(_up.size()) - 1; bit >= 0; bit--) {
const int steps = 1 << bit;
if (first_depth - elapsed < steps) continue;
const int next_first = _up[bit][first];
const int next_second = _up[bit][second];
if (next_first == next_second) continue;
first = next_first;
second = next_second;
elapsed += steps;
}
return elapsed + 1;
}
const int length = cycle_size(first);
int first_phase =
cycle_position[first] - first_depth % length;
int second_phase =
cycle_position[second] - second_depth % length;
if (first_phase < 0) first_phase += length;
if (second_phase < 0) second_phase += length;
if (first_phase != second_phase) return -1;
return std::max(first_depth, second_depth);
}
int first_meeting_vertex(int first, int second) const {
const long long time = first_meeting_time(first, second);
if (time == -1) return -1;
return jump(first, std::uint64_t(time));
}
};
} // namespace graph
} // namespace m1une
#endif // M1UNE_GRAPH_FUNCTIONAL_GRAPH_HPP#line 1 "graph/functional_graph.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <queue>
#include <utility>
#include <vector>
namespace m1une {
namespace graph {
struct FunctionalGraph {
int component_count;
std::vector<int> successor;
std::vector<std::vector<int>> predecessors;
std::vector<std::vector<int>> cycles;
std::vector<int> component;
std::vector<int> component_size;
std::vector<int> cycle_entry;
std::vector<int> cycle_position;
std::vector<int> distance_to_cycle;
private:
std::vector<std::vector<int>> _up;
void check_vertex(int vertex) const {
assert(0 <= vertex && vertex < size());
}
int advance_before_cycle(int vertex, int steps) const {
assert(0 <= steps && steps <= distance_to_cycle[vertex]);
int bit = 0;
while (steps > 0) {
if (steps & 1) vertex = _up[bit][vertex];
steps >>= 1;
bit++;
}
return vertex;
}
public:
FunctionalGraph() : component_count(0) {}
explicit FunctionalGraph(const std::vector<int>& successor_) {
build(successor_);
}
void build(const std::vector<int>& successor_) {
successor = successor_;
const int n = size();
for (int to : successor) assert(0 <= to && to < n);
component_count = 0;
predecessors.assign(n, {});
cycles.clear();
component.assign(n, -1);
cycle_entry.assign(n, -1);
cycle_position.assign(n, -1);
distance_to_cycle.assign(n, -1);
std::vector<int> indegree(n, 0);
for (int vertex = 0; vertex < n; vertex++) {
predecessors[successor[vertex]].push_back(vertex);
indegree[successor[vertex]]++;
}
std::queue<int> queue;
std::vector<char> removed(n, false);
for (int vertex = 0; vertex < n; vertex++) {
if (indegree[vertex] == 0) queue.push(vertex);
}
while (!queue.empty()) {
const int vertex = queue.front();
queue.pop();
removed[vertex] = true;
const int to = successor[vertex];
indegree[to]--;
if (indegree[to] == 0) queue.push(to);
}
for (int start = 0; start < n; start++) {
if (removed[start] || component[start] != -1) continue;
const int component_id = int(cycles.size());
std::vector<int> cycle;
int vertex = start;
do {
const int position = int(cycle.size());
cycle.push_back(vertex);
component[vertex] = component_id;
cycle_entry[vertex] = vertex;
cycle_position[vertex] = position;
distance_to_cycle[vertex] = 0;
vertex = successor[vertex];
} while (vertex != start);
cycles.push_back(std::move(cycle));
}
component_count = int(cycles.size());
for (const std::vector<int>& cycle : cycles) {
for (int vertex : cycle) queue.push(vertex);
}
while (!queue.empty()) {
const int vertex = queue.front();
queue.pop();
for (int from : predecessors[vertex]) {
if (component[from] != -1) continue;
component[from] = component[vertex];
cycle_entry[from] = cycle_entry[vertex];
cycle_position[from] = cycle_position[vertex];
distance_to_cycle[from] = distance_to_cycle[vertex] + 1;
queue.push(from);
}
}
component_size.assign(component_count, 0);
for (int component_id : component) component_size[component_id]++;
int log = 1;
while ((std::uint64_t(1) << log) <= std::uint64_t(n)) log++;
_up.assign(log, successor);
for (int bit = 1; bit < log; bit++) {
for (int vertex = 0; vertex < n; vertex++) {
_up[bit][vertex] = _up[bit - 1][_up[bit - 1][vertex]];
}
}
}
int size() const {
return int(successor.size());
}
bool empty() const {
return successor.empty();
}
bool same_component(int first, int second) const {
check_vertex(first);
check_vertex(second);
return component[first] == component[second];
}
bool on_cycle(int vertex) const {
check_vertex(vertex);
return distance_to_cycle[vertex] == 0;
}
int cycle_size(int vertex) const {
check_vertex(vertex);
return int(cycles[component[vertex]].size());
}
int orbit_size(int vertex) const {
check_vertex(vertex);
return distance_to_cycle[vertex] + cycle_size(vertex);
}
int jump(int vertex, std::uint64_t steps) const {
check_vertex(vertex);
const int tail_length = distance_to_cycle[vertex];
if (steps < std::uint64_t(tail_length)) {
return advance_before_cycle(vertex, int(steps));
}
steps -= std::uint64_t(tail_length);
const int entry = cycle_entry[vertex];
const int length = cycle_size(entry);
const int offset = int(steps % std::uint64_t(length));
const int position = (cycle_position[entry] + offset) % length;
return cycles[component[vertex]][position];
}
long long distance(int from, int to) const {
check_vertex(from);
check_vertex(to);
if (!same_component(from, to)) return -1;
if (!on_cycle(to)) {
if (distance_to_cycle[from] < distance_to_cycle[to]) return -1;
const int difference = distance_to_cycle[from] - distance_to_cycle[to];
return advance_before_cycle(from, difference) == to ? difference : -1;
}
const int entry = cycle_entry[from];
const int length = cycle_size(from);
int cycle_distance = cycle_position[to] - cycle_position[entry];
if (cycle_distance < 0) cycle_distance += length;
return static_cast<long long>(distance_to_cycle[from]) + cycle_distance;
}
bool reachable(int from, int to) const {
return distance(from, to) != -1;
}
std::vector<int> path(int from, int to) const {
const long long path_length = distance(from, to);
if (path_length == -1) return {};
std::vector<int> result;
result.reserve(path_length + 1);
for (long long step = 0; step <= path_length; step++) {
result.push_back(from);
from = successor[from];
}
return result;
}
std::vector<int> orbit(int vertex) const {
check_vertex(vertex);
const int length = orbit_size(vertex);
std::vector<int> result;
result.reserve(length);
for (int step = 0; step < length; step++) {
result.push_back(vertex);
vertex = successor[vertex];
}
return result;
}
std::uint64_t visit_count(
int from,
int to,
std::uint64_t step_count
) const {
const long long first_visit = distance(from, to);
if (first_visit == -1 ||
std::uint64_t(first_visit) >= step_count) {
return 0;
}
if (!on_cycle(to)) return 1;
const std::uint64_t remaining =
step_count - 1 - std::uint64_t(first_visit);
return 1 + remaining / std::uint64_t(cycle_size(to));
}
long long first_meeting_time(int first, int second) const {
check_vertex(first);
check_vertex(second);
if (!same_component(first, second)) return -1;
if (first == second) return 0;
const int first_depth = distance_to_cycle[first];
const int second_depth = distance_to_cycle[second];
if (first_depth == second_depth &&
cycle_entry[first] == cycle_entry[second]) {
int elapsed = 0;
for (int bit = int(_up.size()) - 1; bit >= 0; bit--) {
const int steps = 1 << bit;
if (first_depth - elapsed < steps) continue;
const int next_first = _up[bit][first];
const int next_second = _up[bit][second];
if (next_first == next_second) continue;
first = next_first;
second = next_second;
elapsed += steps;
}
return elapsed + 1;
}
const int length = cycle_size(first);
int first_phase =
cycle_position[first] - first_depth % length;
int second_phase =
cycle_position[second] - second_depth % length;
if (first_phase < 0) first_phase += length;
if (second_phase < 0) second_phase += length;
if (first_phase != second_phase) return -1;
return std::max(first_depth, second_depth);
}
int first_meeting_vertex(int first, int second) const {
const long long time = first_meeting_time(first, second);
if (time == -1) return -1;
return jump(first, std::uint64_t(time));
}
};
} // namespace graph
} // namespace m1une