Traveling salesman problem (tools/tsp.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-01-25 08:45:50+09:00
• Include: #include "tools/tsp.hpp"

It solves the traveling salesman problem.

License

• CC0

Author

• anqooqie

Constructor

tsp<Directed> graph(std::size_t n);

It creates a graph which is not necessarily simple with $n$ vertices and $0$ edges. If Directed is true, the graph is directed. If Directed is false, the graph is undirected.

Constraints

• $n \geq 2$

Time Complexity

• $O(n^2)$

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, T w);

If Directed is true, it adds a directed edge oriented from $u$ to $v$ with cost $w$. If Directed is false, it adds an undirected edge between $u$ and $v$ with cost $w$. 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

get_edge

struct edge {
  std::size_t id;
  std::size_t from;
  std::size_t to;
  T cost;
};
edge graph.get_edge(std::size_t k);

It returns the $k$-th edge.

Constraints

• $0 \leq k < |E|$ where $|E|$ is the number of edges

Time Complexity

• $O(1)$

edges

const std::vector<edge>& graph.edges();

It returns all the edges in the graph. The edges are ordered in the same order as added by add_edge.

Constraints

• None

Time Complexity

• $O(1)$

query

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

It finds the shortest Hamilton cycle. If such the cycle does not exist, it returns std::nullopt. If such the cycle exists, it returns the total cost of the cycle, 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(2^n n^2)$

Depends on

• chmin function (tools/chmin.hpp)
• $2^x$ (tools/pow2.hpp)

Verified with

• tests/tsp.test.cpp

Code

#ifndef TOOLS_TSP_HPP
#define TOOLS_TSP_HPP

#include <cstddef>
#include <vector>
#include <limits>
#include <cassert>
#include <utility>
#include <algorithm>
#include <optional>
#include <tuple>
#include "tools/pow2.hpp"
#include "tools/chmin.hpp"

namespace tools {

  template <bool Directed, typename T>
  class tsp {
  public:
    struct edge {
      ::std::size_t id;
      ::std::size_t from;
      ::std::size_t to;
      T cost;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;

  public:
    tsp() = default;
    tsp(const ::tools::tsp<Directed, T>&) = default;
    tsp(::tools::tsp<Directed, T>&&) = default;
    ~tsp() = default;
    ::tools::tsp<Directed, T>& operator=(const ::tools::tsp<Directed, T>&) = default;
    ::tools::tsp<Directed, T>& operator=(::tools::tsp<Directed, T>&&) = default;

    explicit tsp(const ::std::size_t n) : m_graph(n, ::std::vector<::std::size_t>(n, ::std::numeric_limits<::std::size_t>::max())) {
      assert(n >= 2);
    }

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

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v, const T& w) {
      assert(u < this->size());
      assert(v < this->size());
      if constexpr (!Directed) {
        ::std::tie(u, v) = ::std::minmax({u, v});
      }
      this->m_edges.push_back(edge({this->m_edges.size(), u, v, w}));
      if (this->m_graph[u][v] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[u][v]].cost) {
        this->m_graph[u][v] = this->m_edges.size() - 1;
      }
      if constexpr (!Directed) {
        if (this->m_graph[v][u] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[v][u]].cost) {
          this->m_graph[v][u] = this->m_edges.size() - 1;
        }
      }
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const ::std::size_t k) const {
      assert(k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    ::std::optional<::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      auto dp = ::std::vector(::tools::pow2(this->size()), ::std::vector(this->size(), ::std::numeric_limits<T>::max()));
      dp[0][0] = 0;
      for (::std::size_t state = 1; state < ::tools::pow2(this->size()); ++state) {
        for (::std::size_t v = 0; v < this->size(); ++v) {
          if ((static_cast<::std::size_t>(1) << v) & state) {
            const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
            for (::std::size_t u = 0; u < this->size(); ++u) {
              if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
                if (dp[prev_state][u] < ::std::numeric_limits<T>::max()) {
                  ::tools::chmin(dp[state][v], dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost);
                }
              }
            }
          }
        }
      }

      ::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>> res;
      auto& [total_cost, vids, eids] = res;

      total_cost = dp[::tools::pow2(this->size()) - 1][0];
      if (total_cost == ::std::numeric_limits<T>::max()) return ::std::nullopt;

      ::std::size_t state = ::tools::pow2(this->size()) - 1;
      ::std::size_t v = 0;
      while (state > 0) {
        const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
        for (::std::size_t u = 0; u < this->size(); ++u) {
          if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
            if (dp[prev_state][u] < ::std::numeric_limits<T>::max() && dp[state][v] == dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost) {
              vids.push_back(u);
              eids.push_back(this->m_graph[u][v]);
              state = prev_state;
              v = u;
              break;
            }
          }
        }
      }

      ::std::reverse(vids.begin(), vids.end());
      ::std::reverse(eids.begin(), eids.end());

      return res;
    }
  };
}

#endif

#line 1 "tools/tsp.hpp"



#include <cstddef>
#include <vector>
#include <limits>
#include <cassert>
#include <utility>
#include <algorithm>
#include <optional>
#include <tuple>
#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/chmin.hpp"



#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 14 "tools/tsp.hpp"

namespace tools {

  template <bool Directed, typename T>
  class tsp {
  public:
    struct edge {
      ::std::size_t id;
      ::std::size_t from;
      ::std::size_t to;
      T cost;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;

  public:
    tsp() = default;
    tsp(const ::tools::tsp<Directed, T>&) = default;
    tsp(::tools::tsp<Directed, T>&&) = default;
    ~tsp() = default;
    ::tools::tsp<Directed, T>& operator=(const ::tools::tsp<Directed, T>&) = default;
    ::tools::tsp<Directed, T>& operator=(::tools::tsp<Directed, T>&&) = default;

    explicit tsp(const ::std::size_t n) : m_graph(n, ::std::vector<::std::size_t>(n, ::std::numeric_limits<::std::size_t>::max())) {
      assert(n >= 2);
    }

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

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v, const T& w) {
      assert(u < this->size());
      assert(v < this->size());
      if constexpr (!Directed) {
        ::std::tie(u, v) = ::std::minmax({u, v});
      }
      this->m_edges.push_back(edge({this->m_edges.size(), u, v, w}));
      if (this->m_graph[u][v] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[u][v]].cost) {
        this->m_graph[u][v] = this->m_edges.size() - 1;
      }
      if constexpr (!Directed) {
        if (this->m_graph[v][u] == ::std::numeric_limits<::std::size_t>::max() || w < this->m_edges[this->m_graph[v][u]].cost) {
          this->m_graph[v][u] = this->m_edges.size() - 1;
        }
      }
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const ::std::size_t k) const {
      assert(k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    ::std::optional<::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      auto dp = ::std::vector(::tools::pow2(this->size()), ::std::vector(this->size(), ::std::numeric_limits<T>::max()));
      dp[0][0] = 0;
      for (::std::size_t state = 1; state < ::tools::pow2(this->size()); ++state) {
        for (::std::size_t v = 0; v < this->size(); ++v) {
          if ((static_cast<::std::size_t>(1) << v) & state) {
            const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
            for (::std::size_t u = 0; u < this->size(); ++u) {
              if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
                if (dp[prev_state][u] < ::std::numeric_limits<T>::max()) {
                  ::tools::chmin(dp[state][v], dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost);
                }
              }
            }
          }
        }
      }

      ::std::tuple<T, ::std::vector<::std::size_t>, ::std::vector<::std::size_t>> res;
      auto& [total_cost, vids, eids] = res;

      total_cost = dp[::tools::pow2(this->size()) - 1][0];
      if (total_cost == ::std::numeric_limits<T>::max()) return ::std::nullopt;

      ::std::size_t state = ::tools::pow2(this->size()) - 1;
      ::std::size_t v = 0;
      while (state > 0) {
        const auto prev_state = state & ~(static_cast<::std::size_t>(1) << v);
        for (::std::size_t u = 0; u < this->size(); ++u) {
          if (this->m_graph[u][v] < ::std::numeric_limits<::std::size_t>::max()) {
            if (dp[prev_state][u] < ::std::numeric_limits<T>::max() && dp[state][v] == dp[prev_state][u] + this->m_edges[this->m_graph[u][v]].cost) {
              vids.push_back(u);
              eids.push_back(this->m_graph[u][v]);
              state = prev_state;
              v = u;
              break;
            }
          }
        }
      }

      ::std::reverse(vids.begin(), vids.end());
      ::std::reverse(eids.begin(), eids.end());

      return res;
    }
  };
}

Back to top page