動的なグラフ構造体
(src/graph/class/dynamic-graph.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/graph/class/dynamic-graph.hpp"

コンストラクタ

DynamicGraph< edge >(usize n)

頂点数 n のグラフを定義する。

制約

• $0 \leq n$

edge の制約

• 辺のコストを表す型として cost_type が公開されていること。
• 辺の始点、終点、コスト、辺番号としてメンバ変数 from, to, cost, id をもつこと。また、この順にコンストラクタを呼べること。

size

usize size()

グラフの頂点数を返す。

add_directed_edge

void add_directed_edge(usize from, usize to, cost_type cost = 1)

from から to へのコストcostの有向辺をグラフに追加する。 cost を指定しなかった場合、その辺のコストは 1 になる。

辺には追加された順に 0-indexed で辺番号が割り振られる。

add_undirected_edge

void add_undirected_edge(usize u, usize v, cost_type cost = 1)

u から v へのコスト cost の無向辺をグラフに追加する。 cost を指定しなかった場合、その辺のコストは 1 になる。

辺には追加された順に 0-indexed で辺番号が割り振られる。

operator[]

(1)       Edges &operator[](const usize &v)
(2) const Edges &operator[](const usize &v) const

v を始点とする辺のリストを返す。

Depends on

• size alias (src/cpp-template/header/size-alias.hpp)

Required by

• 重みあり単一始点最短経路 (Single Source Shortest Path in Unweighted Graph, SPFA) (src/graph/single-source-shortest-path/in-weighted-graph.hpp)

Verified with

• test/aoj/grl_1_a/dynamic-graph.test.cpp
• test/aoj/grl_1_b/dynamic-graph.test.cpp
• test/aoj/grl_1_b/static-graph.test.cpp

Code

#pragma once

#include "src/cpp-template/header/size-alias.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename Edge >
  class DynamicGraph {

    using Edges = std::vector< Edge >;

   protected:
    std::vector< Edges > g;
    usize edge_count;

   public:
    using cost_type = typename Edge::cost_type;

    DynamicGraph() = default;
    explicit DynamicGraph(usize n): g(n), edge_count(0) {}

    usize size() const {
      return g.size();
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      assert(from < size());
      assert(to < size());
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u < size());
      assert(v < size());
      assert(u != v);
      g[u].emplace_back(u, v, cost, edge_count);
      g[v].emplace_back(v, u, cost, edge_count++);
    }

    Edges operator[](const usize &v) {
      return g[v];
    }

    const Edges operator[](const usize &v) const {
      return g[v];
    }
  };

} // namespace luz

#line 2 "src/graph/class/dynamic-graph.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/graph/class/dynamic-graph.hpp"

#include <cassert>
#include <vector>

namespace luz {

  template < typename Edge >
  class DynamicGraph {

    using Edges = std::vector< Edge >;

   protected:
    std::vector< Edges > g;
    usize edge_count;

   public:
    using cost_type = typename Edge::cost_type;

    DynamicGraph() = default;
    explicit DynamicGraph(usize n): g(n), edge_count(0) {}

    usize size() const {
      return g.size();
    }

    void add_directed_edge(usize from, usize to, cost_type cost = 1) {
      assert(from < size());
      assert(to < size());
      g[from].emplace_back(from, to, cost, edge_count++);
    }

    void add_undirected_edge(usize u, usize v, cost_type cost = 1) {
      assert(u < size());
      assert(v < size());
      assert(u != v);
      g[u].emplace_back(u, v, cost, edge_count);
      g[v].emplace_back(v, u, cost, edge_count++);
    }

    Edges operator[](const usize &v) {
      return g[v];
    }

    const Edges operator[](const usize &v) const {
      return g[v];
    }
  };

} // namespace luz

Back to top page