qbpp.hpp File Reference

QUBO++, a C++ library for generating expressions for binary and spin variables. More...

#include <tbb/blocked_range.h>
#include <tbb/parallel_for.h>
#include <tbb/parallel_reduce.h>
#include <tbb/parallel_sort.h>
#include <algorithm>
#include <boost/container/small_vector.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/endian/conversion.hpp>
#include <boost/multi_array.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <chrono>
#include <cmath>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <memory>
#include <mutex>
#include <optional>
#include <sstream>
#include <string>
#include <thread>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <variant>
#include <vector>

Include dependency graph for qbpp.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	qbpp::impl::var_hash
struct	qbpp::impl::vars_hash
class	qbpp::Inf
class	qbpp::Vector< T >
class	qbpp::Var
class	qbpp::impl::VarSet
class	qbpp::impl::IndexVarMapper
class	qbpp::Term
class	qbpp::Expr
class	qbpp::VarIntCore
class	qbpp::VarInt
class	qbpp::Model
class	qbpp::QuadModel
struct	qbpp::QuadModel::Impl
class	qbpp::impl::BitVector
class	qbpp::Sol
class	qbpp::SolHolder

Namespaces
	qbpp
	Generates a QUBO Expression for the Graph Coloring Problem using QUBO++ library.
	qbpp::impl

Macros
#define	VERSION   "2025-01-15"
#define	THROW_MESSAGE(...)   file_line(__FILE__, __LINE__, __VA_ARGS__)
#define	TERM_CAPACITY   4
#define	MAXDEG   0
#define	COEFF_TYPE   int32_t
#define	ENERGY_TYPE   int64_t

Typedefs
using	qbpp::Vars = boost::container::small_vector< Var, 2 >
using	qbpp::Terms = std::vector< Term >
using	qbpp::int128_t = boost::multiprecision::int128_t
using	qbpp::uint128_t = boost::multiprecision::uint128_t
using	qbpp::int256_t = boost::multiprecision::int256_t
using	qbpp::uint256_t = boost::multiprecision::uint256_t
using	qbpp::int512_t = boost::multiprecision::int512_t
using	qbpp::uint512_t = boost::multiprecision::uint512_t
using	qbpp::int1024_t = boost::multiprecision::int1024_t
using	qbpp::uint1024_t = boost::multiprecision::uint1024_t
using	qbpp::cpp_int = boost::multiprecision::cpp_int
using	qbpp::vindex_t = uint32_t
using	qbpp::var_val_t = int8_t
using	qbpp::coeff_t = COEFF_TYPE
using	qbpp::energy_t = ENERGY_TYPE
using	qbpp::MapList = std::list< std::pair< std::variant< Var, VarInt >, Expr > >
using	qbpp::MapDict = std::unordered_map< Var, Expr, impl::var_hash >
using	qbpp::VarValMap = std::unordered_map< Var, var_val_t, impl::var_hash >
using	qbpp::VarIndexMap = std::unordered_map< Var, vindex_t, impl::var_hash >
using	qbpp::VarExprMap = std::unordered_map< Var, Expr, impl::var_hash >
using	qbpp::VarsCoeffMap = std::unordered_map< Vars, coeff_t, impl::vars_hash >

Functions
template<typename... Args>
std::string	qbpp::file_line (const char *file, int line, Args... args)
Var	qbpp::var (const std::string &var_str)
Var	qbpp::var ()
std::string	qbpp::str (Var var)
std::string	qbpp::str (const char *param)
std::string	qbpp::str (const Vars &vars)
std::string	qbpp::str (const Term &term)
std::string	qbpp::str (const Expr &expr, const std::string &prefix)
std::string	qbpp::str (const Model &model)
std::string	qbpp::str (const QuadModel &quad_model)
std::string	qbpp::str (const Sol &sol)
std::string	qbpp::str (const MapList &map_list)
std::string	qbpp::str_short (const Expr &expr)
std::ostream &	qbpp::operator<< (std::ostream &os, Var var)
std::ostream &	qbpp::operator<< (std::ostream &os, const Term &term)
std::ostream &	qbpp::operator<< (std::ostream &os, const Expr &expr)
std::ostream &	qbpp::operator<< (std::ostream &os, const Model &model)
std::ostream &	qbpp::operator<< (std::ostream &os, const QuadModel &quad_model)
std::ostream &	qbpp::operator<< (std::ostream &os, const Sol &sol)
void	qbpp::sort_vars_in_place (Vars &vars)
Vars	qbpp::sort_vars (const Vars &vars)
Vars	qbpp::sort_vars_as_binary (const Vars &vars)
Vars	qbpp::sort_vars_as_spin (const Vars &vars)
Expr	qbpp::simplify (const Expr &expr, Vars(*sort_vars_func)(const Vars &))
Expr	qbpp::simplify_as_binary (const Expr &expr)
Expr	qbpp::simplify_as_spin (const Expr &expr)
bool	qbpp::is_simplified (const Expr &expr)
bool	qbpp::is_binary (const Expr &expr)
template<typename T >
Vector< Expr >	qbpp::sqr (const Vector< T > &arg)
template<typename T >
auto	qbpp::sqr (const Vector< Vector< T >> &arg) -> Vector< decltype(sqr(arg[0]))>
energy_t	qbpp::eval (const Expr &expr, const Sol &sol)
energy_t	qbpp::eval (const Expr &expr, const MapList &map_list)
Expr	qbpp::reduce (const Expr &expr)
Expr	qbpp::binary_to_spin (const Expr &expr)
Expr	qbpp::spin_to_binary (const Expr &expr)
template<typename T >
Vector< Expr >	qbpp::binary_to_spin (const Vector< T > &arg)
template<typename T >
auto	qbpp::binary_to_spin (const Vector< Vector< T >> &arg) -> Vector< decltype(binary_to_spin(arg[0]))>
template<typename T >
Vector< Expr >	qbpp::spin_to_binary (const Vector< T > &arg)
template<typename T >
auto	qbpp::spin_to_binary (const Vector< Vector< T >> &arg) -> Vector< decltype(spin_to_binary(arg[0]))>
Vector< Expr >	qbpp::get_row (const Vector< Vector< Expr >> &vec, vindex_t index)
Vector< Expr >	qbpp::get_col (const Vector< Vector< Expr >> &vec, size_t index)
double	qbpp::get_time ()
vindex_t	qbpp::all_var_count ()
template<typename T >
Expr	qbpp::sum (const Vector< T > &items)
template<typename T >
Vector< Vector< Expr > >	qbpp::transpose (const Vector< Vector< T >> &vec)
Expr	qbpp::operator- (const Expr &expr)
Expr	qbpp::operator- (Expr &&expr)
energy_t	qbpp::toInt (const Expr &expr)
VarValMap	qbpp::list_to_var_val (const MapList &map_list)
std::string	qbpp::str (int8_t val)
template<typename T >
auto	qbpp::str (const T &val) -> decltype(std::to_string(val))
template<typename T >
auto	qbpp::str (T val) -> decltype(val.str())
template<typename T >
T	qbpp::abs (T val)
energy_t	qbpp::gcd (energy_t a, energy_t b)
std::string	qbpp::str_impl (const Vars &vars, std::function< std::string(Var)> str)
std::string	qbpp::str_impl (const Term &term, std::function< std::string(Var)> str)
std::string	qbpp::str_impl (const Expr &expr, std::function< std::string(Var)> str)
std::string	qbpp::str (const impl::BitVector &bit_vector)
std::string	qbpp::str (const Expr &expr)
std::string	qbpp::str (const Expr &expr, const std::string &prefix, const std::string &separator[[maybe_unused]]=",")
template<typename T >
std::string	qbpp::str (const Vector< T > &vec, const std::string &prefix="", const std::string &separator=",")
std::ostream &	qbpp::operator<< (std::ostream &os, const VarInt &var_int)
std::ostream &	qbpp::operator<< (std::ostream &os, const MapList &map_list)
template<typename T >
std::ostream &	qbpp::operator<< (std::ostream &os, const Vector< T > &vec)
template<typename T >
std::ostream &	qbpp::operator<< (std::ostream &os, const std::pair< std::string, Vector< T >> &vec)
template<typename T >
Expr	qbpp::impl::equal (const T &lhs, const T &rhs)
template<typename T >
Expr	qbpp::impl::equal (const std::vector< T > &lhs, const std::vector< T > &rhs)
MapDict	qbpp::list_to_dict (const MapList &map_list)
Expr	qbpp::replace (const Term &term, const MapDict &map_dict)
energy_t	qbpp::eval (const Term &term, const VarValMap &var_val_map)
energy_t	qbpp::eval (const Term &term, const Sol &sol)
Expr	qbpp::replace (const Expr &expr, const MapList &map_list)
energy_t	qbpp::eval_var_val_map (const Expr &expr, const VarValMap &var_val_map)
template<typename T , typename... Args, typename = typename std::enable_if<std::is_integral<T>::value>::type>
auto	qbpp::var (const std::string &var_str, T size, Args... args)
template<typename T , typename... Args, typename = typename std::enable_if<std::is_integral<T>::value>::type>
auto	qbpp::var (T size, Args... args)
VarIntCore	qbpp::var_int (const std::string &var_str)
VarIntCore	qbpp::var_int ()
template<typename T , typename... Args>
auto	qbpp::var_int (const std::string &var_str, T size, Args... args)
std::vector< coeff_t >	qbpp::comp_coeffs (energy_t min_val, energy_t max_val, energy_t base_coeff=1)
VarInt	qbpp::new_var_int (const std::string &var_str, energy_t min_val, energy_t max_val, energy_t base_coeff=1)
VarInt	qbpp::new_var_int (const VarIntCore &var_int_core, energy_t min_val, energy_t max_val, energy_t base_coeff=1)
auto	qbpp::operator<= (energy_t lhs, VarIntCore &&rhs)
template<typename T >
auto	qbpp::operator<= (energy_t lhs, Vector< T > &&rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< energy_t, T > lhs, energy_t rhs)
std::pair< energy_t, Vector< VarIntCore > >	qbpp::operator<= (energy_t lhs, const Vector< VarIntCore > &rhs)
auto	qbpp::operator<= (const std::pair< energy_t, Vector< VarIntCore >> lhs, energy_t rhs)
void	qbpp::operator<= (energy_t, Var)=delete
void	qbpp::operator<= (Var, energy_t)=delete
Expr	qbpp::expr ()
Vector< Expr >	qbpp::expr (vindex_t size)
template<typename T , typename... Args>
auto	qbpp::expr (T size, Args... args)
template<typename T >
Expr	qbpp::toExpr (const T &arg)
Expr	qbpp::toExpr (const Expr &arg)
Vector< Expr >	qbpp::toExpr (const Vector< Expr > &arg)
template<typename T >
auto	qbpp::toExpr (const Vector< T > &arg)
template<typename T >
auto	qbpp::toExpr (const std::vector< T > &arg)
Vector< Expr >	qbpp::toExpr (const std::initializer_list< Expr > &list)
template<typename T >
auto	qbpp::toExpr (const std::initializer_list< T > &list)
Vector< Vector< Expr > >	qbpp::toExpr (const std::initializer_list< std::initializer_list< Expr >> &list)
Vector< Vector< Vector< Expr > > >	qbpp::toExpr (const std::initializer_list< std::initializer_list< std::initializer_list< Expr >>> &list)
Vector< Vector< Vector< Vector< Expr > > > >	qbpp::toExpr (const std::initializer_list< std::initializer_list< std::initializer_list< std::initializer_list< Expr >>>> &list)
Expr &&	qbpp::operator* (Expr &&lhs, Expr &&rhs)
Expr &&	qbpp::operator* (Expr &&lhs, const Expr &rhs)
Expr &&	qbpp::operator* (const Expr &lhs, Expr &&rhs)
Expr	qbpp::operator* (const Expr &lhs, const Expr &rhs)
Expr &&	qbpp::operator+ (Expr &&lhs, Expr &&rhs)
Expr &&	qbpp::operator+ (Expr &&lhs, const Expr &rhs)
Expr &&	qbpp::operator+ (const Expr &lhs, Expr &&rhs)
Expr	qbpp::operator+ (const Expr &lhs, const Expr &rhs)
Expr &&	qbpp::operator- (Expr &&lhs, Expr &&rhs)
Expr &&	qbpp::operator- (Expr &&lhs, const Expr &rhs)
Expr &&	qbpp::operator- (const Expr &lhs, Expr &&rhs)
Expr	qbpp::operator- (const Expr &lhs, const Expr &rhs)
Expr &&	qbpp::operator/ (Expr &&expr, energy_t val)
Expr	qbpp::operator/ (const Expr &expr, energy_t val)
Expr	qbpp::operator+ (Expr &&expr)
const Expr &	qbpp::operator+ (const Expr &expr)
Expr	qbpp::sqr (const Expr &expr)
energy_t	qbpp::gcd (const Expr &expr)
Expr	qbpp::operator== (const Expr &expr, energy_t val)
Expr	qbpp::comparison (const Expr &expr, energy_t minimum, energy_t maximum)
std::pair< energy_t, Expr >	qbpp::operator<= (energy_t min_val, const Expr &expr)
Expr	qbpp::operator<= (const std::pair< energy_t, Expr > &pair, energy_t max_val)
Expr	qbpp::operator<= (const std::pair< energy_t, Expr > &pair, Inf val)
std::pair< energy_t, Expr >	qbpp::operator<= (Inf val, const Expr &expr)
Expr	qbpp::simplify_seq (const Expr &expr, Vars(*sort_vars_func)(const Vars &)=sort_vars)
template<typename T >
Vector< T >	qbpp::simplify (const Vector< T > &vec, Vars(*sort_vars_func)(const Vars &)=sort_vars)
template<typename T >
auto	qbpp::simplify_as_binary (const Vector< T > &arg)
template<typename T >
auto	qbpp::simplify_as_spin (const Vector< T > &arg)
Expr	qbpp::reduce_sum (const Term &term)
Expr	qbpp::reduce_cascade (const Term &term)
template<typename T , typename U >
Vector< Expr >	qbpp::operator+ (const Vector< T > &lhs, const Vector< U > &rhs)
template<typename T , typename U >
auto	qbpp::operator+ (const Vector< Vector< T >> &lhs, const Vector< Vector< U >> &rhs)
template<typename T >
Vector< Expr >	qbpp::operator+ (const Vector< T > &lhs, const Expr &rhs)
template<typename T >
Vector< Expr >	qbpp::operator+ (Vector< T > &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator+ (const Vector< Vector< T >> &lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator+ (Vector< Vector< T >> &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator+ (const Expr &lhs, const Vector< T > &rhs)
template<typename T >
auto	qbpp::operator+ (const Expr &lhs, Vector< T > &&rhs)
template<typename T , typename U >
Vector< Expr >	qbpp::operator* (const Vector< T > &lhs, const Vector< U > &rhs)
template<typename T , typename U >
auto	qbpp::operator* (const Vector< Vector< T >> &lhs, const Vector< Vector< U >> &rhs)
template<typename T >
Vector< Expr >	qbpp::operator* (const Vector< T > &lhs, const Expr &rhs)
template<typename T >
Vector< Expr >	qbpp::operator* (Vector< T > &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator* (const Vector< Vector< T >> &lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator* (Vector< Vector< T >> &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator* (const Expr &lhs, const Vector< T > &rhs)
template<typename T >
auto	qbpp::operator* (const Expr &lhs, Vector< T > &&rhs)
template<typename T , typename U >
Vector< Expr >	qbpp::operator- (const Vector< T > &lhs, const Vector< U > &rhs)
template<typename T , typename U >
auto	qbpp::operator- (const Vector< Vector< T >> &lhs, const Vector< Vector< U >> &rhs)
template<typename T >
Vector< Expr >	qbpp::operator- (const Vector< T > &lhs, const Expr &rhs)
template<typename T >
Vector< Expr >	qbpp::operator- (Vector< T > &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator- (const Vector< Vector< T >> &lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator- (Vector< Vector< T >> &&lhs, const Expr &rhs)
template<typename T >
auto	qbpp::operator- (const Expr &lhs, const Vector< T > &rhs)
template<typename T >
auto	qbpp::operator/ (const Vector< T > &lhs, energy_t rhs)
template<typename T >
auto	qbpp::operator+ (const Vector< T > &lhs)
template<typename T >
auto	qbpp::operator- (const Vector< T > &lhs)
template<typename T >
auto	qbpp::operator== (const Vector< T > &lhs, energy_t rhs)
template<typename T >
auto	qbpp::operator<= (energy_t lhs, const Vector< T > &rhs)
template<typename T >
auto	qbpp::operator<= (Inf lhs, const Vector< T > &rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< energy_t, Vector< T >> &lhs, energy_t rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< energy_t, Vector< T >> &lhs, Inf rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< Inf, Vector< T >> &lhs, energy_t rhs)
template<typename T >
auto	qbpp::operator<= (energy_t lhs, const Vector< Vector< T >> &rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< energy_t, Vector< Vector< T >>> &lhs, energy_t rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< energy_t, Vector< Vector< T >>> &lhs, Inf rhs)
template<typename T >
auto	qbpp::operator<= (const std::pair< Inf, Vector< Vector< T >>> &lhs, energy_t rhs)
template<typename T >
Expr	qbpp::sum (const T &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::sum (const Vector< Vector< T >> &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::total_sum_impl (const T &item)
template<typename T >
Expr	qbpp::total_sum_impl (const Vector< T > &items)
template<typename T >
qbpp::Expr	qbpp::total_sum (const T &arg[[maybe_unused]])
template<typename T >
qbpp::Expr	qbpp::total_sum (const Vector< T > &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::total_sum (const Vector< Vector< T >> &items)
template<typename T >
Expr	qbpp::vector_sum (const T &items[[maybe_unused]])
template<typename T >
Expr	qbpp::vector_sum (const Vector< T > &items[[maybe_unused]])
template<typename T >
auto	qbpp::vector_sum_impl (const T &items)
template<typename T >
auto	qbpp::vector_sum_impl (const Vector< T > &items)
template<typename T >
auto	qbpp::vector_sum_impl (const Vector< Vector< T >> &items)
template<typename T >
auto	qbpp::vector_sum (const Vector< Vector< T >> &items)
template<typename T >
Expr	qbpp::product (const T &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::product (const Vector< Vector< T >> &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::product (const Vector< T > &items)
template<typename T >
Expr	qbpp::total_product_impl (const T &item)
template<typename T >
Expr	qbpp::total_product_impl (const Vector< T > &items)
template<typename T >
Expr	qbpp::total_product (const Vector< Vector< T >> &items)
template<typename T >
Expr	qbpp::total_product (const T &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::total_product (const Vector< T > &arg[[maybe_unused]])
template<typename T >
Expr	qbpp::vector_product (const T &items[[maybe_unused]])
template<typename T >
Expr	qbpp::vector_product (const Vector< T > &items[[maybe_unused]])
template<typename T >
auto	qbpp::vector_product_impl (const T &items)
template<typename T >
auto	qbpp::vector_product_impl (const Vector< T > &items)
template<typename T >
auto	qbpp::vector_product_impl (const Vector< Vector< T >> &items)
template<typename T >
auto	qbpp::vector_product (const Vector< Vector< T >> &items)
template<typename T >
auto	qbpp::toInt (const Vector< T > &arg)
template<typename T >
Vector< energy_t >	qbpp::eval_var_val_map (const Vector< T > &arg, const VarValMap &var_val_map)
template<typename T >
Vector< energy_t >	qbpp::eval (const Vector< T > &arg, const MapList &map_list)
template<typename T >
auto	qbpp::eval_var_val_map (const Vector< Vector< T >> &arg, const VarValMap &var_val_map)
template<typename T >
auto	qbpp::eval (const Vector< Vector< T >> &arg, const MapList &map_list)
template<typename T >
Vector< Expr >	qbpp::replace (const Vector< T > &arg, const MapList &map_list)
template<typename T >
auto	qbpp::replace (const Vector< Vector< T >> &arg, const MapList &map_list)
template<typename T , typename F >
auto	qbpp::element_wise (const Vector< T > &arg, F func)
template<typename T >
Vector< Expr >	qbpp::reduce (const Vector< T > &arg)
template<typename T >
auto	qbpp::reduce (const Vector< Vector< T >> &arg)
template<typename T >
energy_t	qbpp::gcd (const Vector< T > &vec)
int32_t	qbpp::onehot_to_int (const Vector< var_val_t > &vec)
template<typename T >
auto	qbpp::onehot_to_int (const Vector< Vector< T >> &vec)
std::tuple< bool, size_t, size_t, coeff_t, coeff_t >	qbpp::check_if_simplified_as_binary (const Expr &expr)

Variables
const vindex_t	qbpp::vindex_limit = std::numeric_limits<vindex_t>::max()
const Inf	qbpp::inf

Detailed Description

QUBO++, a C++ library for generating expressions for binary and spin variables.

This library provides classes and functions for generating and manipulating expressions and polynomials for binary and spin variables. The library is designed to be simple and easy to use.

Note

Only for non-commercial use, evaluation, and research purposes with no warranties. Redistribution is strictly prohibited. This software includes components from Intel® Threading Building Blocks (oneTBB), licensed under the Apache License 2.0.

Author

Koji Nakano

Copyright

2025, Koji Nakano

Version

2025-01-18

Definition in file qbpp.hpp.

Macro Definition Documentation

VERSION

#define VERSION   "2025-01-15"

Definition at line 18 of file qbpp.hpp.

THROW_MESSAGE

#define THROW_MESSAGE

(

...

)

file_line(__FILE__, __LINE__, __VA_ARGS__)

Definition at line 86 of file qbpp.hpp.

TERM_CAPACITY

#define TERM_CAPACITY   4

Definition at line 88 of file qbpp.hpp.

MAXDEG

#define MAXDEG   0

Definition at line 92 of file qbpp.hpp.

COEFF_TYPE

#define COEFF_TYPE   int32_t

Definition at line 115 of file qbpp.hpp.

ENERGY_TYPE

#define ENERGY_TYPE   int64_t

Definition at line 119 of file qbpp.hpp.