graph/basic_graph.cpp

• View this file on GitHub
• Last update: 2021-12-28 21:38:32+09:00

Depends on

• utility/index_offset.cpp

Verified with

• test/heavy_light_decomposition.test.cpp
• test/strongly_connected_components.test.cpp

Code

#pragma once
#include <cassert>
#include <utility>
#include <vector>
#include "../utility/index_offset.cpp"

template <class E = int> class BasicGraph {
    std::vector<std::vector<E>> graph;

  public:
    BasicGraph() : graph() {}
    explicit BasicGraph(const int n) : graph(n) {}

    class EdgePtr {
        friend class BasicGraph;
        int u, e;
        BasicGraph* self;

        explicit EdgePtr(const int u, const int e, BasicGraph* p) : u(u), e(e), self(p) {}

      public:
        EdgePtr() : u(0), e(0), self(nullptr) {}
        int src() const { return u; }
        E& operator*() const { return self->graph[u][e]; }
        E* operator->() const { return &self->graph[u][e]; }
    };

    int size() const { return graph.size(); }
    std::vector<E>& operator[](const int u) {
        assert(0 <= u and u < size());
        return graph[u];
    }
    const std::vector<E>& operator[](const int u) const {
        assert(0 <= u and u < size());
        return graph[u];
    }

    int add_vertex() {
        graph.emplace_back();
        return size() - 1;
    }
    IndexOffset add_vertices(int n) {
        IndexOffset ret(size(), n);
        while (n--) graph.emplace_back();
        return ret;
    }

    template <class... Args> EdgePtr add_edge(const int u, Args&&... args) {
        assert(0 <= u and u < size());
        const int e = graph[u].size();
        graph[u].emplace_back(std::forward<Args>(args)...);
        return EdgePtr(u, e, this);
    }
};

#line 2 "graph/basic_graph.cpp"
#include <cassert>
#include <utility>
#include <vector>
#line 3 "utility/index_offset.cpp"

class IndexOffset {
    int offset, len;

  public:
    constexpr IndexOffset() noexcept : offset(), len() {}
    explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
    constexpr int size() const { return len; }
    constexpr int operator[](const int i) const noexcept {
        assert(i < len);
        return offset + i;
    }
    constexpr int to_idx(const int i) const noexcept {
        assert(offset <= i and i < offset + len);
        return i - offset;
    }
};
#line 6 "graph/basic_graph.cpp"

template <class E = int> class BasicGraph {
    std::vector<std::vector<E>> graph;

  public:
    BasicGraph() : graph() {}
    explicit BasicGraph(const int n) : graph(n) {}

    class EdgePtr {
        friend class BasicGraph;
        int u, e;
        BasicGraph* self;

        explicit EdgePtr(const int u, const int e, BasicGraph* p) : u(u), e(e), self(p) {}

      public:
        EdgePtr() : u(0), e(0), self(nullptr) {}
        int src() const { return u; }
        E& operator*() const { return self->graph[u][e]; }
        E* operator->() const { return &self->graph[u][e]; }
    };

    int size() const { return graph.size(); }
    std::vector<E>& operator[](const int u) {
        assert(0 <= u and u < size());
        return graph[u];
    }
    const std::vector<E>& operator[](const int u) const {
        assert(0 <= u and u < size());
        return graph[u];
    }

    int add_vertex() {
        graph.emplace_back();
        return size() - 1;
    }
    IndexOffset add_vertices(int n) {
        IndexOffset ret(size(), n);
        while (n--) graph.emplace_back();
        return ret;
    }

    template <class... Args> EdgePtr add_edge(const int u, Args&&... args) {
        assert(0 <= u and u < size());
        const int e = graph[u].size();
        graph[u].emplace_back(std::forward<Args>(args)...);
        return EdgePtr(u, e, this);
    }
};

Back to top page