Cycle detection on a graph (tools/cycle_detection.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-09-02 09:37:09+09:00
• Include: #include "tools/cycle_detection.hpp"

It reports one of the cycles in a given graph if it exists.

License

• CC0

Author

• anqooqie

Constructor

cycle_detection<DIRECTED> graph(std::size_t n);

It creates a graph with $n$ vertices and $0$ edges. If DIRECTED is true, the graph is directed. If DIRECTED is false, the graph is undirected.

Constraints

• None

Time Complexity

• $O(n)$

size

std::size_t graph.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

add_edge

std::size_t graph.add_edge(std::size_t u, std::size_t v);

If DIRECTED is true, it adds a directed edge oriented from $u$ to $v$. If DIRECTED is false, it adds an undirected edge between $u$ and $v$. It returns an integer $k$ such that this is the $k$-th edge that is added.

Constraints

• $0 \leq u < n$
• $0 \leq v < n$

Time Complexity

• $O(1)$ amortized

query

std::optional<std::pair<std::vector<std::size_t>, std::vector<std::size_t>>> graph.query();

It finds one of the cycles in a given graph. If such the cycle does not exist, it returns std::nullopt. If such the cycle exists, it returns the indices of the vertices which are contained in the cycle and the indices of the edges which are contained in the cycle.

Constraints

• None

Time Complexity

• $O(n)$

Verified with

• tests/cycle_detection/directed.test.cpp
• tests/cycle_detection/undirected.test.cpp

Code

#ifndef TOOLS_CYCLE_DETECTION_HPP
#define TOOLS_CYCLE_DETECTION_HPP

#include <vector>
#include <cstddef>
#include <utility>
#include <cassert>
#include <optional>
#include <stack>
#include <tuple>
#include <limits>
#include <algorithm>

namespace tools {
  template <bool DIRECTED>
  class cycle_detection {
  private:
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;

  public:
    cycle_detection() = default;
    cycle_detection(const ::tools::cycle_detection<DIRECTED>&) = default;
    cycle_detection(::tools::cycle_detection<DIRECTED>&&) = default;
    ~cycle_detection() = default;
    ::tools::cycle_detection<DIRECTED>& operator=(const ::tools::cycle_detection<DIRECTED>&) = default;
    ::tools::cycle_detection<DIRECTED>& operator=(::tools::cycle_detection<DIRECTED>&&) = default;

    explicit cycle_detection(const ::std::size_t n) :
      m_graph(n) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v) {
      assert(u < this->size());
      assert(v < this->size());

      this->m_graph[u].push_back(this->m_edges.size());
      if (!DIRECTED) {
        this->m_graph[v].push_back(this->m_edges.size());
      }
      this->m_edges.emplace_back(u, v);
      return this->m_edges.size() - 1;
    }

    ::std::optional<::std::pair<::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      ::std::stack<std::tuple<bool, ::std::size_t, ::std::size_t>> stack;
      for (::std::size_t v = 0; v < this->size(); ++v) {
        stack.emplace(false, v, ::std::numeric_limits<::std::size_t>::max());
        stack.emplace(true, v, ::std::numeric_limits<::std::size_t>::max());
      }
      ::std::vector<bool> pre(this->size(), false);
      ::std::vector<bool> post(this->size(), false);
      ::std::vector<::std::size_t> prev(this->size(), ::std::numeric_limits<::std::size_t>::max());
      while (!stack.empty()) {
        const auto [is_pre, here, from] = stack.top();
        stack.pop();
        if (post[here]) continue;

        if (is_pre) {
          prev[here] = from;
          if (pre[here]) {
            ::std::vector<::std::size_t> vids, eids({from});
            for (::std::size_t v = this->m_edges[from].first ^ (DIRECTED ? 0 : this->m_edges[from].second ^ here); v != here; v = this->m_edges[prev[v]].first ^ (DIRECTED ? 0 : this->m_edges[prev[v]].second ^ v)) {
              vids.push_back(v);
              eids.push_back(prev[v]);
            }
            vids.push_back(here);
            ::std::reverse(vids.begin(), vids.end());
            ::std::reverse(eids.begin(), eids.end());
            return ::std::make_optional(::std::make_pair(vids, eids));
          }
          pre[here] = true;
          for (const auto eid : this->m_graph[here]) {
            if (eid != from) {
              stack.emplace(false, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
              stack.emplace(true, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
            }
          }
        } else {
          post[here] = true;
        }
      }

      return ::std::nullopt;
    }
  };
}

#endif

#line 1 "tools/cycle_detection.hpp"



#include <vector>
#include <cstddef>
#include <utility>
#include <cassert>
#include <optional>
#include <stack>
#include <tuple>
#include <limits>
#include <algorithm>

namespace tools {
  template <bool DIRECTED>
  class cycle_detection {
  private:
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;

  public:
    cycle_detection() = default;
    cycle_detection(const ::tools::cycle_detection<DIRECTED>&) = default;
    cycle_detection(::tools::cycle_detection<DIRECTED>&&) = default;
    ~cycle_detection() = default;
    ::tools::cycle_detection<DIRECTED>& operator=(const ::tools::cycle_detection<DIRECTED>&) = default;
    ::tools::cycle_detection<DIRECTED>& operator=(::tools::cycle_detection<DIRECTED>&&) = default;

    explicit cycle_detection(const ::std::size_t n) :
      m_graph(n) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v) {
      assert(u < this->size());
      assert(v < this->size());

      this->m_graph[u].push_back(this->m_edges.size());
      if (!DIRECTED) {
        this->m_graph[v].push_back(this->m_edges.size());
      }
      this->m_edges.emplace_back(u, v);
      return this->m_edges.size() - 1;
    }

    ::std::optional<::std::pair<::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      ::std::stack<std::tuple<bool, ::std::size_t, ::std::size_t>> stack;
      for (::std::size_t v = 0; v < this->size(); ++v) {
        stack.emplace(false, v, ::std::numeric_limits<::std::size_t>::max());
        stack.emplace(true, v, ::std::numeric_limits<::std::size_t>::max());
      }
      ::std::vector<bool> pre(this->size(), false);
      ::std::vector<bool> post(this->size(), false);
      ::std::vector<::std::size_t> prev(this->size(), ::std::numeric_limits<::std::size_t>::max());
      while (!stack.empty()) {
        const auto [is_pre, here, from] = stack.top();
        stack.pop();
        if (post[here]) continue;

        if (is_pre) {
          prev[here] = from;
          if (pre[here]) {
            ::std::vector<::std::size_t> vids, eids({from});
            for (::std::size_t v = this->m_edges[from].first ^ (DIRECTED ? 0 : this->m_edges[from].second ^ here); v != here; v = this->m_edges[prev[v]].first ^ (DIRECTED ? 0 : this->m_edges[prev[v]].second ^ v)) {
              vids.push_back(v);
              eids.push_back(prev[v]);
            }
            vids.push_back(here);
            ::std::reverse(vids.begin(), vids.end());
            ::std::reverse(eids.begin(), eids.end());
            return ::std::make_optional(::std::make_pair(vids, eids));
          }
          pre[here] = true;
          for (const auto eid : this->m_graph[here]) {
            if (eid != from) {
              stack.emplace(false, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
              stack.emplace(true, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
            }
          }
        } else {
          post[here] = true;
        }
      }

      return ::std::nullopt;
    }
  };
}

Back to top page