summaryrefslogtreecommitdiff
path: root/geom_matching/wasserstein/include/auction_oracle.h
diff options
context:
space:
mode:
Diffstat (limited to 'geom_matching/wasserstein/include/auction_oracle.h')
-rw-r--r--geom_matching/wasserstein/include/auction_oracle.h288
1 files changed, 9 insertions, 279 deletions
diff --git a/geom_matching/wasserstein/include/auction_oracle.h b/geom_matching/wasserstein/include/auction_oracle.h
index ef6ec53..d285a1f 100644
--- a/geom_matching/wasserstein/include/auction_oracle.h
+++ b/geom_matching/wasserstein/include/auction_oracle.h
@@ -26,285 +26,15 @@ derivative works thereof, in binary and source code form.
*/
-#ifndef AUCTION_ORACLE_H
-#define AUCTION_ORACLE_H
+#ifndef HERA_AUCTION_ORACLE_H
+#define HERA_AUCTION_ORACLE_H
+// all oracle classes are in separate h-hpp files
+// this file comprises all of them
-#define USE_BOOST_HEAP
+#include "auction_oracle_base.h"
+#include "auction_oracle_kdtree_restricted.h"
+#include "auction_oracle_kdtree_single_diag.h"
+#include "auction_oracle_stupid_sparse_restricted.h"
-#include <map>
-#include <memory>
-#include <set>
-#include <list>
-
-#ifdef USE_BOOST_HEAP
-#include <boost/heap/d_ary_heap.hpp>
-#endif
-
-#include "basic_defs_ws.h"
-#include "dnn/geometry/euclidean-fixed.h"
-#include "dnn/local/kd-tree.h"
-
-namespace geom_ws {
-
-struct CompPairsBySecondStruct {
- bool operator()(const IdxValPair& a, const IdxValPair& b) const
- {
- return a.second < b.second;
- }
-};
-
-//
-struct CompPairsBySecondGreaterStruct {
- bool operator()(const IdxValPair& a, const IdxValPair& b) const
- {
- return a.second > b.second;
- }
-};
-
-struct CompPairsBySecondLexStruct {
- bool operator()(const IdxValPair& a, const IdxValPair& b) const
- {
- return a.second < b.second or (a.second == b.second and a.first > b.first);
- }
-};
-
-struct CompPairsBySecondLexGreaterStruct {
- bool operator()(const IdxValPair& a, const IdxValPair& b) const
- {
- return a.second > b.second or (a.second == b.second and a.first > b.first);
- }
-};
-
-using ItemsTimePair = std::pair<IdxType, int>;
-
-using UpdateList = std::list<ItemsTimePair>;
-using UpdateListIter = UpdateList::iterator;
-
-
-#ifdef USE_BOOST_HEAP
-using LossesHeap = boost::heap::d_ary_heap<IdxValPair, boost::heap::arity<2>, boost::heap::mutable_<true>, boost::heap::compare<CompPairsBySecondGreaterStruct>>;
-#else
-template<class ComparisonStruct>
-class IdxValHeap {
-public:
- using InternalKeeper = std::set<IdxValPair, ComparisonStruct>;
- using handle_type = typename InternalKeeper::iterator;
- // methods
- handle_type push(const IdxValPair& val)
- {
- auto resPair = _heap.insert(val);
- assert(resPair.second);
- assert(resPair.first != _heap.end());
- return resPair.first;
- }
-
- void decrease(handle_type& handle, const IdxValPair& newVal)
- {
- _heap.erase(handle);
- handle = push(newVal);
- }
-
- void increase(handle_type& handle, const IdxValPair& newVal)
- {
- _heap.erase(handle);
- handle = push(newVal);
-
- size_t size() const
- {
- return _heap.size();
- }
-
- handle_type ordered_begin()
- {
- return _heap.begin();
- }
-
- handle_type ordered_end()
- {
- return _heap.end();
- }
-
-
-private:
- std::set<IdxValPair, ComparisonStruct> _heap;
-};
-
-// if we store losses, the minimal value should come first
-using LossesHeap = IdxValHeap<CompPairsBySecondLexStruct>;
-#endif
-
-struct DebugOptimalBid {
- DebugOptimalBid() : bestItemIdx(-1), bestItemValue(-666.666), secondBestItemIdx(-1), secondBestItemValue(-666.666) {};
- IdxType bestItemIdx;
- double bestItemValue;
- IdxType secondBestItemIdx;
- double secondBestItemValue;
-};
-
-struct AuctionOracleAbstract {
- AuctionOracleAbstract(const std::vector<DiagramPoint>& _bidders, const std::vector<DiagramPoint>& _items, const double _wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- ~AuctionOracleAbstract() {}
- virtual IdxValPair getOptimalBid(const IdxType bidderIdx) = 0;
- virtual void setPrice(const IdxType itemsIdx, const double newPrice) = 0;
- virtual void adjustPrices(void) = 0;
- double getEpsilon() { return epsilon; };
- virtual void setEpsilon(double newEpsilon) { assert(newEpsilon >= 0.0); epsilon = newEpsilon; };
- std::vector<double> getPrices() { return prices; }
-protected:
- const std::vector<DiagramPoint>& bidders;
- const std::vector<DiagramPoint>& items;
- std::vector<double> prices;
- double wassersteinPower;
- double epsilon;
- double internal_p;
- double getValueForBidder(size_t bidderIdx, size_t itemsIdx);
-};
-
-struct AuctionOracleLazyHeap final : AuctionOracleAbstract {
- AuctionOracleLazyHeap(const std::vector<DiagramPoint>& bidders, const std::vector<DiagramPoint>& items, const double wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- ~AuctionOracleLazyHeap();
- // data members
- // temporarily make everything public
- std::vector<std::vector<double>> weightMatrix;
- //double weightAdjConst;
- double maxVal;
- // vector of heaps to find the best items
- std::vector<LossesHeap*> lossesHeap;
- std::vector<std::vector<LossesHeap::handle_type>> lossesHeapHandles;
- // methods
- void fillInLossesHeap(void);
- void setPrice(const IdxType itemsIdx, const double newPrice) override final;
- IdxValPair getOptimalBid(const IdxType bidderIdx) override final;
- double getMatchingWeight(const std::vector<IdxType>& biddersToItems) const;
- void adjustPrices(void) override final;
- // to update the queue in lazy fashion
- std::vector<UpdateListIter> itemsIterators;
- UpdateList updateList;
- std::vector<int> biddersUpdateMoments;
- int updateCounter;
- void updateQueueForBidder(const IdxType bidderIdx);
- // debug
- DebugOptimalBid getOptimalBidDebug(const IdxType bidderIdx);
-};
-
-struct AuctionOracleLazyHeapRestricted final : AuctionOracleAbstract {
- AuctionOracleLazyHeapRestricted(const std::vector<DiagramPoint>& bidders, const std::vector<DiagramPoint>& items, const double wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- ~AuctionOracleLazyHeapRestricted();
- // data members
- // temporarily make everything public
- std::vector<std::vector<double>> weightMatrix;
- //double weightAdjConst;
- double maxVal;
- // vector of heaps to find the best items
- std::vector<LossesHeap*> lossesHeap;
- std::vector<std::vector<size_t>> itemsIndicesForHeapHandles;
- std::vector<std::vector<LossesHeap::handle_type>> lossesHeapHandles;
- // methods
- void fillInLossesHeap(void);
- void setPrice(const IdxType itemsIdx, const double newPrice) override final;
- IdxValPair getOptimalBid(const IdxType bidderIdx) override final;
- double getMatchingWeight(const std::vector<IdxType>& biddersToItems) const;
- void adjustPrices(void) override final;
- // to update the queue in lazy fashion
- std::vector<UpdateListIter> itemsIterators;
- UpdateList updateList;
- std::vector<int> biddersUpdateMoments;
- int updateCounter;
- void updateQueueForBidder(const IdxType bidderIdx);
- LossesHeap diagItemsHeap;
- std::vector<LossesHeap::handle_type> diagHeapHandles;
- std::vector<size_t> heapHandlesIndices;
- // debug
-
- DebugOptimalBid getOptimalBidDebug(const IdxType bidderIdx);
-
- // for diagonal points
- bool bestDiagonalItemsComputed;
- size_t bestDiagonalItemIdx;
- double bestDiagonalItemValue;
- size_t secondBestDiagonalItemIdx;
- double secondBestDiagonalItemValue;
-};
-
-struct AuctionOracleKDTree final : AuctionOracleAbstract {
- typedef dnn::Point<2, double> DnnPoint;
- typedef dnn::PointTraits<DnnPoint> DnnTraits;
-
- AuctionOracleKDTree(const std::vector<DiagramPoint>& bidders, const std::vector<DiagramPoint>& items, const double wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- ~AuctionOracleKDTree();
- // data members
- // temporarily make everything public
- double maxVal;
- double weightAdjConst;
- dnn::KDTree<DnnTraits>* kdtree;
- std::vector<DnnPoint> dnnPoints;
- std::vector<DnnPoint*> dnnPointHandles;
- dnn::KDTree<DnnTraits>* kdtreeAll;
- std::vector<DnnPoint> dnnPointsAll;
- std::vector<DnnPoint*> dnnPointHandlesAll;
- LossesHeap diagItemsHeap;
- std::vector<LossesHeap::handle_type> diagHeapHandles;
- std::vector<size_t> heapHandlesIndices;
- std::vector<size_t> kdtreeItems;
- // vector of heaps to find the best items
- void setPrice(const IdxType itemsIdx, const double newPrice) override final;
- IdxValPair getOptimalBid(const IdxType bidderIdx) override final;
- void adjustPrices(void) override final;
- // debug routines
- DebugOptimalBid getOptimalBidDebug(IdxType bidderIdx);
- void setEpsilon(double newVal) override final;
-};
-
-struct AuctionOracleKDTreeRestricted final : AuctionOracleAbstract {
- typedef dnn::Point<2, double> DnnPoint;
- typedef dnn::PointTraits<DnnPoint> DnnTraits;
-
- AuctionOracleKDTreeRestricted(const std::vector<DiagramPoint>& bidders, const std::vector<DiagramPoint>& items, const double wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- ~AuctionOracleKDTreeRestricted();
- // data members
- // temporarily make everything public
- double maxVal;
- double weightAdjConst;
- dnn::KDTree<DnnTraits>* kdtree;
- std::vector<DnnPoint> dnnPoints;
- std::vector<DnnPoint*> dnnPointHandles;
- std::vector<DnnPoint> dnnPointsAll;
- std::vector<DnnPoint*> dnnPointHandlesAll;
- LossesHeap diagItemsHeap;
- std::vector<LossesHeap::handle_type> diagHeapHandles;
- std::vector<size_t> heapHandlesIndices;
- std::vector<size_t> kdtreeItems;
- // vector of heaps to find the best items
- void setPrice(const IdxType itemsIdx, const double newPrice) override final;
- IdxValPair getOptimalBid(const IdxType bidderIdx) override final;
- void adjustPrices(void) override final;
- // debug routines
- DebugOptimalBid getOptimalBidDebug(IdxType bidderIdx);
- void setEpsilon(double newVal) override final;
-
-
- bool bestDiagonalItemsComputed;
- size_t bestDiagonalItemIdx;
- double bestDiagonalItemValue;
- size_t secondBestDiagonalItemIdx;
- double secondBestDiagonalItemValue;
-};
-
-struct AuctionOracleRestricted final : AuctionOracleAbstract {
- AuctionOracleRestricted(const std::vector<DiagramPoint>& bidders, const std::vector<DiagramPoint>& items, const double wassersteinPower, const double _internal_p = std::numeric_limits<double>::infinity());
- IdxValPair getOptimalBid(const IdxType bidderIdx) override;
- void setPrice(const IdxType itemsIdx, const double newPrice) override;
- void adjustPrices(void) override {};
- void setEpsilon(double newEpsilon) override { assert(newEpsilon >= 0.0); epsilon = newEpsilon; };
- // data
- std::vector<std::vector<double>> weightMatrix;
- double maxVal;
- constexpr static bool isRestricted = true;
-};
-
-std::ostream& operator<< (std::ostream& output, const DebugOptimalBid& db);
-
-} // end of namespace geom_ws
-
-#endif
+#endif // HERA_AUCTION_ORACLE_H
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-03 15:11:02 +0000