Random tree generator (tools/random_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-02-18 13:45:51+09:00
• Include: #include "tools/random_tree.hpp"
• Link: https://twitter.com/anta_prg/status/869633557362163712

It will generate random trees.

References

• あんたさんはTwitterを使っています: 「@DEGwer3456 https://t.co/iKbySxrK2D できました」 / Twitter

License

• unknown

Author

• anta

Constructor

random_tree<T> dist(std::size_t n);

It creates a generator to generate random trees with $n$ vertices. The type parameter <T> will be used as the type of vertex numbers.

Constraints

• $n \geq 1$

Time Complexity

• $O(1)$

size

std::size_t dist.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

operator()

template <typename R>
std::vector<std::pair<T, T>> dist.operator()(R& engine);

It returns edges of a randomly generated tree with $n$ vertices.

Constraints

• engine is a pseudorandom number generator.

Time Complexity

• $O(n)$

Verified with

• tests/random_tree.test.cpp

Code

#ifndef TOOLS_RANDOM_TREE_HPP
#define TOOLS_RANDOM_TREE_HPP

#include <cstddef>
#include <cassert>
#include <vector>
#include <utility>
#include <numeric>
#include <random>

// Source: https://twitter.com/anta_prg/status/869633557362163712
// License: unknown
// Author: anta

namespace tools {

  template <typename T>
  class random_tree {
  private:
    ::std::size_t m_size;

  public:
    random_tree() = default;
    random_tree(const ::tools::random_tree<T>&) = default;
    random_tree(::tools::random_tree<T>&&) = default;
    ~random_tree() = default;
    ::tools::random_tree<T>& operator=(const ::tools::random_tree<T>&) = default;
    ::tools::random_tree<T>& operator=(::tools::random_tree<T>&&) = default;

    explicit random_tree(const ::std::size_t n) : m_size(n) {
      assert(n >= 1);
    }

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

    template <typename R>
    ::std::vector<::std::pair<T, T>> operator()(R& engine) const {
      ::std::vector<::std::pair<T, T>> edges;

      ::std::vector<T> perm(this->size());
      ::std::iota(perm.begin(), perm.end(), 0);
      for (::std::size_t i = 0; i + 1 < this->size(); ++i) {
        const auto x = ::std::uniform_int_distribution<::std::size_t>(0, this->size() - i - 2)(engine);
        const auto y = ::std::uniform_int_distribution<::std::size_t>(0, this->size() - 1)(engine);
        ::std::swap(perm[i + 1], perm[i + 1 + x]);
        if (y < i + 1) ::std::swap(perm[i], perm[y]);
        edges.emplace_back(perm[i], perm[i + 1]);
      }

      return edges;
    }
  };
}

#endif

#line 1 "tools/random_tree.hpp"



#include <cstddef>
#include <cassert>
#include <vector>
#include <utility>
#include <numeric>
#include <random>

// Source: https://twitter.com/anta_prg/status/869633557362163712
// License: unknown
// Author: anta

namespace tools {

  template <typename T>
  class random_tree {
  private:
    ::std::size_t m_size;

  public:
    random_tree() = default;
    random_tree(const ::tools::random_tree<T>&) = default;
    random_tree(::tools::random_tree<T>&&) = default;
    ~random_tree() = default;
    ::tools::random_tree<T>& operator=(const ::tools::random_tree<T>&) = default;
    ::tools::random_tree<T>& operator=(::tools::random_tree<T>&&) = default;

    explicit random_tree(const ::std::size_t n) : m_size(n) {
      assert(n >= 1);
    }

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

    template <typename R>
    ::std::vector<::std::pair<T, T>> operator()(R& engine) const {
      ::std::vector<::std::pair<T, T>> edges;

      ::std::vector<T> perm(this->size());
      ::std::iota(perm.begin(), perm.end(), 0);
      for (::std::size_t i = 0; i + 1 < this->size(); ++i) {
        const auto x = ::std::uniform_int_distribution<::std::size_t>(0, this->size() - i - 2)(engine);
        const auto y = ::std::uniform_int_distribution<::std::size_t>(0, this->size() - 1)(engine);
        ::std::swap(perm[i + 1], perm[i + 1 + x]);
        if (y < i + 1) ::std::swap(perm[i], perm[y]);
        edges.emplace_back(perm[i], perm[i + 1]);
      }

      return edges;
    }
  };
}

Back to top page