m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Graph
(graph/graph.hpp)

Overview

m1une::graph::Graph<T> is an adjacency-list graph container for general directed and undirected graphs. It is meant to be the common input format for the graph algorithms in this directory.

The template parameter T is the edge-cost type. Use Graph<> when the graph is unweighted; it is the same as Graph<int> and every omitted edge cost defaults to 1.

Undirected edges are stored as two adjacency entries with the same edge id, so algorithms can distinguish logical edges from adjacency arcs.

Each edge also has an alive flag. Built-in graph algorithms ignore edges with alive == false, so you can logically delete an edge without physically removing it from the adjacency list.

Graph Orientation

Graph<T> itself supports both directed and undirected graphs.

Algorithm pages state whether they respect direction, require undirected edges, or ignore direction.

How to Use It

Create a graph with the number of vertices, then add edges.

Most algorithms iterate over g[v], where each element is an Edge<T> with from, to, cost, id, and alive.

Choose the cost type to match the algorithm. For example, use Graph<long long> for shortest paths with large weights.

Types

Type Description
Edge<T> Stores from, to, cost, id, and alive.
Graph<T> Stores std::vector<std::vector<Edge<T>>>.

Edge Fields and Methods

Member Type / Signature Description
from int Source vertex of this adjacency arc.
to int Destination vertex of this adjacency arc.
cost T Edge cost.
id int Logical edge id. The two arcs of an undirected edge share one id.
alive bool Whether this edge is active. Built-in algorithms skip inactive edges.
other int other(int v) const Returns the other endpoint of this edge. Use it only when v is one endpoint.

Methods

Method Type / Signature Description Complexity
Constructor Graph() Creates an empty graph. $O(1)$
Constructor explicit Graph(int n) Creates a graph with n vertices. $O(N)$
size int size() const Returns the number of vertices. $O(1)$
empty bool empty() const Returns whether the graph has no vertices. $O(1)$
edge_count int edge_count() const Returns the number of logical edges added. $O(1)$
add_vertex int add_vertex() Adds one vertex and returns its index. Amortized $O(1)$
add_directed_edge int add_directed_edge(int from, int to, T cost = T(1)) Adds one directed edge and returns its id. Amortized $O(1)$
add_edge int add_edge(int u, int v, T cost = T(1)) Adds one undirected edge and returns its id. Amortized $O(1)$
set_edge_alive void set_edge_alive(int id, bool alive) Sets the alive flag of every adjacency arc with edge id id. $O(1)$
erase_edge void erase_edge(int id) Marks edge id id as inactive. $O(1)$
revive_edge void revive_edge(int id) Marks edge id id as active. $O(1)$
is_edge_alive bool is_edge_alive(int id) const Returns whether edge id id is active. $O(1)$
operator[] const std::vector<Edge<T>>& operator[](int v) const Returns immutable adjacency list of vertex v. $O(1)$
operator[] std::vector<Edge<T>>& operator[](int v) Returns mutable adjacency list of vertex v. $O(1)$
adjacency const std::vector<std::vector<Edge<T>>>& adjacency() const Returns immutable adjacency lists. $O(1)$
adjacency std::vector<std::vector<Edge<T>>>& adjacency() Returns mutable adjacency lists. $O(1)$
edges std::vector<Edge<T>> edges(bool include_inactive = false) const Returns one entry per logical edge id. Inactive edges are skipped unless include_inactive is true. $O(N + M)$
reversed Graph<T> reversed() const Returns the graph with all arcs reversed. $O(N + M)$

Notes

edges() returns each logical edge once. For an undirected edge, only one of the two stored arcs is returned. This is useful for algorithms like Kruskal that must not process the same undirected edge twice.

erase_edge(id) is a logical deletion. The adjacency entries remain in memory, but built-in algorithms skip them. edge_count() still includes inactive edges. Use edges(true) if you need to inspect inactive edges too.

reversed() is mainly useful for directed graphs. It preserves edge ids and costs and alive flags while swapping every arc direction.

Example

#include "graph/graph.hpp"
#include <iostream>

int main() {
    m1une::graph::Graph<long long> g(3);
    g.add_directed_edge(0, 1, 5);
    int e = g.add_directed_edge(1, 2, 7);
    g.erase_edge(e);

    for (const auto& e : g[0]) {
        if (!e.alive) continue;
        std::cout << e.from << " -> " << e.to << " cost=" << e.cost << "\n";
    }
}

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_GRAPH_HPP
#define M1UNE_GRAPH_GRAPH_HPP 1

#include <array>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_GRAPH_HPP
#line 1 "graph/graph.hpp"



#include <array>
#include <cassert>
#include <utility>
#include <vector>

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une
Back to top page