From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h | 130 ++++++++++++++++++++++++++ 1 file changed, 130 insertions(+) create mode 100644 src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h (limited to 'src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h') diff --git a/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h new file mode 100644 index 0000000..5f7713c --- /dev/null +++ b/src/3rdparty/adaptagrams/libvpsc/solve_VPSC.h @@ -0,0 +1,130 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libvpsc - A solver for the problem of Variable Placement with + * Separation Constraints. + * + * Copyright (C) 2005-2013 Monash University + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * See the file LICENSE.LGPL distributed with the library. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * + * Author(s): Tim Dwyer + * Michael Wybrow +*/ + +// +// TODO: Really, we should have three classes: VPSC, IncrementalVPSC and +// StaticVPSC, where the latter two inherit from VPSC. StaticVPSC would be +// the equivalent of what is currently VPSC. +// Also, a lot of the code specific to one or other of these concrete +// implementations should be moved from Block and Blocks: e.g. mergeLeft etc. +// +#ifndef VPSC_SOLVE_VPSC_H +#define VPSC_SOLVE_VPSC_H + +#include + +/** + * @namespace vpsc + * @brief libvpsc: Variable Placement with Separation Constraints + * quadratic program solver library. + * + * You should use VPSC via an instance of the IncSolver or Solver classes. + */ +namespace vpsc { +class Variable; +typedef std::vector Variables; +class Constraint; +class Blocks; +typedef std::vector Constraints; + +/** + * @brief Static solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of separation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. + * + * @sa IncSolver + */ +class Solver { +public: + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + virtual bool solve(); + + Solver(Variables const &vs, Constraints const &cs); + virtual ~Solver(); + //! @brief Returns the Variables in this problem instance. + //! @returns A vector of Variable objects. + Variables const & getVariables() { return vs; } +protected: + Blocks *bs; + size_t m; + std::vector const &cs; + size_t n; + std::vector const &vs; + bool needsScaling; + + void printBlocks(); + void copyResult(); +private: + void refine(); + bool constraintGraphIsCyclic(const unsigned n, Variable* const vs[]); + bool blockGraphIsCyclic(); +}; + +/** + * @brief Incremental solver for Variable Placement with Separation Constraints + * problem instance + * + * This class attempts to solve a least-squares problem subject to a set + * of sepation constraints. The solve() and satisfy() methods return true + * if any constraints are active, in both cases false means an unconstrained + * optimum has been found. This is an incremental version of that allows + * refinement after blocks are moved. This version is preferred if you are + * using VPSC in an interactive context. + * + * @sa Solver + */ +class IncSolver : public Solver { +public: + IncSolver(Variables const &vs, Constraints const &cs); + //! @brief Results in an approximate solution subject to the constraints. + //! @return true if any constraints are active, or false if an unconstrained + bool satisfy(); + //! @brief Results in an optimum solution subject to the constraints + //! @return true if any constraints are active, or false if an unconstrained + //! optimum has been found. + bool solve(); + //! @brief Adds a constraint to the existing VPSC solver. + //! + //! @param constraint The new additional constraint to add. + void addConstraint(Constraint *constraint); +private: + void moveBlocks(); + void splitBlocks(); + + unsigned splitCnt; + Constraints inactive; + Constraints violated; + Constraint* mostViolated(Constraints &l); +}; + +} +#endif // VPSC_SOLVE_VPSC_H -- cgit v1.2.3