From 5d304d5720cd23ab9aa1179a147ae1e12ee17950 Mon Sep 17 00:00:00 2001 From: Arnur Nigmetov Date: Wed, 5 Jul 2017 10:01:51 -0700 Subject: Price adjustment; maxIterNum increased For high Wasserstein powers price adjustment (subtract minimal price) is needed. --- geom_matching/wasserstein/CMakeLists.txt | 3 + geom_matching/wasserstein/include/auction_oracle.h | 25 ++-- .../wasserstein/include/auction_runner_gs.h | 8 +- .../wasserstein/include/auction_runner_jac.h | 4 +- geom_matching/wasserstein/include/basic_defs_ws.h | 4 +- geom_matching/wasserstein/include/def_debug_ws.h | 4 +- .../wasserstein/include/dnn/local/kd-tree.h | 2 +- .../wasserstein/include/dnn/local/kd-tree.hpp | 29 +++-- geom_matching/wasserstein/include/wasserstein.h | 22 ++-- geom_matching/wasserstein/src/auction_oracle.cpp | 129 +++++++++++---------- .../wasserstein/src/auction_runner_gs.cpp | 24 ++-- .../wasserstein/src/auction_runner_jac.cpp | 16 +-- geom_matching/wasserstein/src/basic_defs.cpp | 16 +-- geom_matching/wasserstein/src/wasserstein.cpp | 18 +-- 14 files changed, 169 insertions(+), 135 deletions(-) diff --git a/geom_matching/wasserstein/CMakeLists.txt b/geom_matching/wasserstein/CMakeLists.txt index b823ca5..c8d8a56 100644 --- a/geom_matching/wasserstein/CMakeLists.txt +++ b/geom_matching/wasserstein/CMakeLists.txt @@ -1,5 +1,8 @@ project (wasserstein) cmake_minimum_required (VERSION 2.8.9) + +set(CMAKE_EXPORT_COMPILE_COMMANDS ON) + include (GenerateExportHeader) # Default to Release diff --git a/geom_matching/wasserstein/include/auction_oracle.h b/geom_matching/wasserstein/include/auction_oracle.h index e803218..ef6ec53 100644 --- a/geom_matching/wasserstein/include/auction_oracle.h +++ b/geom_matching/wasserstein/include/auction_oracle.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code @@ -54,7 +54,7 @@ struct CompPairsBySecondStruct { } }; -// +// struct CompPairsBySecondGreaterStruct { bool operator()(const IdxValPair& a, const IdxValPair& b) const { @@ -105,17 +105,22 @@ public: handle = push(newVal); } - size_t size() const - { + 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() + handle_type ordered_begin() { return _heap.begin(); } - handle_type ordered_end() + handle_type ordered_end() { return _heap.end(); } @@ -211,9 +216,9 @@ struct AuctionOracleLazyHeapRestricted final : AuctionOracleAbstract { std::vector diagHeapHandles; std::vector heapHandlesIndices; // debug - + DebugOptimalBid getOptimalBidDebug(const IdxType bidderIdx); - + // for diagonal points bool bestDiagonalItemsComputed; size_t bestDiagonalItemIdx; @@ -292,7 +297,7 @@ struct AuctionOracleRestricted final : AuctionOracleAbstract { 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 + // data std::vector> weightMatrix; double maxVal; constexpr static bool isRestricted = true; diff --git a/geom_matching/wasserstein/include/auction_runner_gs.h b/geom_matching/wasserstein/include/auction_runner_gs.h index 7968fa9..ce139f1 100644 --- a/geom_matching/wasserstein/include/auction_runner_gs.h +++ b/geom_matching/wasserstein/include/auction_runner_gs.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2016, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code @@ -34,7 +34,7 @@ derivative works thereof, in binary and source code form. #include "auction_oracle.h" //#define KEEP_UNASSIGNED_ORDERED -// if this symbol is defined, +// if this symbol is defined, // unassigned bidders are processed in a lexicographic order. // See LexicogrCompDiagramPoint comparator. @@ -80,7 +80,7 @@ public: double getWassersteinDistance(); double getWassersteinCost(); double getRelativeError() const { return relativeError; }; - static constexpr int maxIterNum { 25 }; // maximal number of iterations of epsilon-scaling + static constexpr int maxIterNum { 35 }; // maximal number of iterations of epsilon-scaling private: // private data std::vector bidders, items; diff --git a/geom_matching/wasserstein/include/auction_runner_jac.h b/geom_matching/wasserstein/include/auction_runner_jac.h index 524498a..d8cada6 100644 --- a/geom_matching/wasserstein/include/auction_runner_jac.h +++ b/geom_matching/wasserstein/include/auction_runner_jac.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2016, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code diff --git a/geom_matching/wasserstein/include/basic_defs_ws.h b/geom_matching/wasserstein/include/basic_defs_ws.h index 474af22..a87ccd3 100644 --- a/geom_matching/wasserstein/include/basic_defs_ws.h +++ b/geom_matching/wasserstein/include/basic_defs_ws.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -62,7 +62,7 @@ struct Point { #endif }; -struct DiagramPoint +struct DiagramPoint { // data members // Points above the diagonal have type NORMAL diff --git a/geom_matching/wasserstein/include/def_debug_ws.h b/geom_matching/wasserstein/include/def_debug_ws.h index 6751556..d4450b2 100644 --- a/geom_matching/wasserstein/include/def_debug_ws.h +++ b/geom_matching/wasserstein/include/def_debug_ws.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements diff --git a/geom_matching/wasserstein/include/dnn/local/kd-tree.h b/geom_matching/wasserstein/include/dnn/local/kd-tree.h index 7e01072..13eaf27 100644 --- a/geom_matching/wasserstein/include/dnn/local/kd-tree.h +++ b/geom_matching/wasserstein/include/dnn/local/kd-tree.h @@ -49,7 +49,7 @@ namespace dnn void init(const Range& range); DistanceType weight(PointHandle p) { return weights_[indices_[p]]; } - void increase_weight(PointHandle p, DistanceType w); + void change_weight(PointHandle p, DistanceType w); HandleDistance find(PointHandle q) const; Result findR(PointHandle q, DistanceType r) const; // all neighbors within r diff --git a/geom_matching/wasserstein/include/dnn/local/kd-tree.hpp b/geom_matching/wasserstein/include/dnn/local/kd-tree.hpp index 6b0852c..22108aa 100644 --- a/geom_matching/wasserstein/include/dnn/local/kd-tree.hpp +++ b/geom_matching/wasserstein/include/dnn/local/kd-tree.hpp @@ -164,11 +164,15 @@ search(PointHandle q, ResultsFunctor& rf) const template void dnn::KDTree:: -increase_weight(PointHandle p, DistanceType w) +change_weight(PointHandle p, DistanceType w) { size_t idx = indices_[p]; - // weight should only increase - assert( weights_[idx] <= w ); + + if ( weights_[idx] == w ) { + return; + } + + bool weight_increases = ( weights_[idx] < w ); weights_[idx] = w; typedef std::tuple KDTreeNode; @@ -223,10 +227,21 @@ increase_weight(PointHandle p, DistanceType w) min_w = weights_[im]; } - if (subtree_weights_[im] < min_w ) // increase weight - subtree_weights_[im] = min_w; - else - break; + if (weight_increases) { + + if (subtree_weights_[im] < min_w ) // increase weight + subtree_weights_[im] = min_w; + else + break; + + } else { + + if (subtree_weights_[im] > min_w ) // decrease weight + subtree_weights_[im] = min_w; + else + break; + + } } } diff --git a/geom_matching/wasserstein/include/wasserstein.h b/geom_matching/wasserstein/include/wasserstein.h index 155d79d..c3e9280 100644 --- a/geom_matching/wasserstein/include/wasserstein.h +++ b/geom_matching/wasserstein/include/wasserstein.h @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code @@ -43,18 +43,18 @@ namespace geom_ws { using PairVector = std::vector>; // get Wasserstein distance between two persistence diagrams -double wassersteinDistVec(const std::vector& A, - const std::vector& B, - const double q, +double wassersteinDistVec(const std::vector& A, + const std::vector& B, + const double q, const double delta, const double _internal_p = std::numeric_limits::infinity(), const double _initialEpsilon = 0.0, const double _epsFactor = 0.0); // get Wasserstein cost (distance^q) between two persistence diagrams -double wassersteinCostVec(const std::vector& A, - const std::vector& B, - const double q, +double wassersteinCostVec(const std::vector& A, + const std::vector& B, + const double q, const double delta, const double _internal_p = std::numeric_limits::infinity(), const double _initialEpsilon = 0.0, @@ -119,7 +119,7 @@ double wassersteinDist(PairContainer& A, PairContainer& B, const double q, const if (b_empty) dgmB.clear(); - + return wassersteinDistVec(dgmA, dgmB, q, delta, _internal_p, _initialEpsilon, _epsFactor); } @@ -146,7 +146,7 @@ double wassersteinCost(PairContainer& A, PairContainer& B, const double q, const dgmA.push_back(DiagramPoint(x, y, DiagramPoint::DIAG)); dgmB.push_back(DiagramPoint(x, y, DiagramPoint::NORMAL)); } - + return wassersteinCostVec(dgmA, dgmB, q, delta, _internal_p, _initialEpsilon, _epsFactor); } @@ -157,7 +157,7 @@ double wassersteinCost(PairContainer& A, PairContainer& B, const double q, const bool readDiagramPointSet(const char* fname, PairVector& result); bool readDiagramPointSet(const std::string& fname, PairVector& result); void removeDuplicates(PairVector& dgmA, PairVector& dgmB); - + } // end of namespace geom_ws #endif diff --git a/geom_matching/wasserstein/src/auction_oracle.cpp b/geom_matching/wasserstein/src/auction_oracle.cpp index f13ffe6..b19c0ae 100644 --- a/geom_matching/wasserstein/src/auction_oracle.cpp +++ b/geom_matching/wasserstein/src/auction_oracle.cpp @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements @@ -53,8 +53,8 @@ double AuctionOracleAbstract::getValueForBidder(size_t bidderIdx, size_t itemIdx // AuctionOracleLazyHeap // ***************************** -AuctionOracleLazyHeap::AuctionOracleLazyHeap(const std::vector& b, - const std::vector& g, +AuctionOracleLazyHeap::AuctionOracleLazyHeap(const std::vector& b, + const std::vector& g, double _wassersteinPower, const double internal_p) : AuctionOracleAbstract(b, g, _wassersteinPower, internal_p), @@ -160,9 +160,9 @@ DebugOptimalBid AuctionOracleLazyHeap::getOptimalBidDebug(IdxType bidderIdx) updateQueueForBidder(bidderIdx); DebugOptimalBid result; - + auto pHeap = lossesHeap[bidderIdx]; - auto topIter = pHeap->ordered_begin(); + auto topIter = pHeap->ordered_begin(); result.bestItemIdx = topIter->first; result.bestItemValue = topIter->second; ++topIter; // now points to the second-best items @@ -177,16 +177,16 @@ DebugOptimalBid AuctionOracleLazyHeap::getOptimalBidDebug(IdxType bidderIdx) return result; } -IdxValPair AuctionOracleLazyHeap::getOptimalBid(const IdxType bidderIdx) +IdxValPair AuctionOracleLazyHeap::getOptimalBid(const IdxType bidderIdx) { assert(bidderIdx >=0 and bidderIdx < static_cast(bidders.size()) ); assert(lossesHeap.at(bidderIdx) != nullptr); assert(lossesHeap[bidderIdx]->size() >= 2); updateQueueForBidder(bidderIdx); - + auto pHeap = lossesHeap[bidderIdx]; - auto topIter = pHeap->ordered_begin(); + auto topIter = pHeap->ordered_begin(); IdxType bestItemIdx = topIter->first; double bestItemValue = topIter->second; ++topIter; // now points to the second-best items @@ -198,8 +198,8 @@ IdxValPair AuctionOracleLazyHeap::getOptimalBid(const IdxType bidderIdx) #endif // bid value: price + value difference + epsilon - return std::make_pair(bestItemIdx, - prices[bestItemIdx] + + return std::make_pair(bestItemIdx, + prices[bestItemIdx] + ( secondBestItemValue - bestItemValue ) + epsilon ); } @@ -208,8 +208,8 @@ IdxValPair AuctionOracleLazyHeap::getOptimalBid(const IdxType bidderIdx) // AuctionOracleLazyHeapRestricted // ***************************** -AuctionOracleLazyHeapRestricted::AuctionOracleLazyHeapRestricted(const std::vector& b, - const std::vector& g, +AuctionOracleLazyHeapRestricted::AuctionOracleLazyHeapRestricted(const std::vector& b, + const std::vector& g, double _wassersteinPower, double internal_p) : AuctionOracleAbstract(b, g, _wassersteinPower), @@ -299,7 +299,7 @@ void AuctionOracleLazyHeapRestricted::fillInLossesHeap(void) assert( itemsIndicesForHeapHandles.at(bidderIdx).at(itemIdx) > 0 ); DiagramPoint item { items[itemIdx] }; if ( item.isNormal() ) { - // item can be assigned to bidder, store in heap + // item can be assigned to bidder, store in heap IdxValPair vp { itemIdx, weightMatrix[bidderIdx][itemIdx] + prices[itemIdx] }; lossesHeapHandles[bidderIdx].push_back( lossesHeap[bidderIdx]->push(vp) ); // keep corresponding index in itemsIndicesForHeapHandles @@ -363,14 +363,14 @@ DebugOptimalBid AuctionOracleLazyHeapRestricted::getOptimalBidDebug(IdxType bidd // todo: store precomputed distance? double projItemValue = pow(distLp(bidder, projItem, internal_p), wassersteinPower) + prices[projItemIdx]; candItems.push_back( std::make_pair(projItemIdx, projItemValue) ); - + if (bidder.isNormal()) { assert(lossesHeap.at(bidderIdx) != nullptr); assert(lossesHeap[bidderIdx]->size() >= 2); updateQueueForBidder(bidderIdx); auto pHeap = lossesHeap[bidderIdx]; assert( pHeap != nullptr ); - auto topIter = pHeap->ordered_begin(); + auto topIter = pHeap->ordered_begin(); candItems.push_back( *topIter ); ++topIter; // now points to the second-best items candItems.push_back( *topIter ); @@ -391,7 +391,7 @@ DebugOptimalBid AuctionOracleLazyHeapRestricted::getOptimalBidDebug(IdxType bidd assert(candItems[2].second >= candItems[1].second); assert(candItems[1].second >= candItems[0].second); } - + result.bestItemIdx = candItems[0].first; result.secondBestItemIdx = candItems[1].first; result.bestItemValue = candItems[0].second; @@ -460,7 +460,7 @@ DebugOptimalBid AuctionOracleLazyHeapRestricted::getOptimalBidDebug(IdxType bidd return result; } -IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderIdx) +IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderIdx) { IdxType bestItemIdx; //IdxType secondBestItemIdx; @@ -476,7 +476,7 @@ IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderId //assert(projItem.id == bidder.projId); // todo: store precomputed distance? double projItemValue = pow(distLp(bidder, projItem, internal_p), wassersteinPower) + prices[projItemIdx]; - + if (bidder.isDiagonal()) { // for diagonal bidder the only normal point has already been added // the other 2 candidates are diagonal items only, get from the heap @@ -509,8 +509,8 @@ IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderId //secondBestItemIdx = secondBestDiagonalItemIdx; } } else { - // for normal bidder get 2 best items among non-diagonal (=normal) points - // from the corresponding heap + // for normal bidder get 2 best items among non-diagonal (=normal) points + // from the corresponding heap assert(diagItemsHeap.size() > 1); updateQueueForBidder(bidderIdx); auto topNormIter = lossesHeap[bidderIdx]->ordered_begin(); @@ -519,7 +519,7 @@ IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderId topNormIter++; double secondBestNormalItemValue { topNormIter->second }; //IdxType secondBestNormalItemIdx { topNormIter->first }; - + if ( projItemValue < bestNormalItemValue) { bestItemIdx = projItemIdx; bestItemValue = projItemValue; @@ -618,8 +618,8 @@ IdxValPair AuctionOracleLazyHeapRestricted::getOptimalBid(const IdxType bidderId // AuctionOracleKDTree // ***************************** -AuctionOracleKDTree::AuctionOracleKDTree(const std::vector& _bidders, - const std::vector& _items, +AuctionOracleKDTree::AuctionOracleKDTree(const std::vector& _bidders, + const std::vector& _items, double _wassersteinPower, double internal_p) : AuctionOracleAbstract(_bidders, _items, _wassersteinPower, internal_p), @@ -668,7 +668,7 @@ AuctionOracleKDTree::AuctionOracleKDTree(const std::vector& _bidde dnnPointHandlesAll.push_back(&dnnPointsAll[i]); } kdtreeAll = new dnn::KDTree(traits, dnnPointHandlesAll, wassersteinPower); - + size_t handleIdx {0}; for(size_t itemIdx = 0; itemIdx < items.size(); ++itemIdx) { if (items[itemIdx].isDiagonal() ) { @@ -676,7 +676,7 @@ AuctionOracleKDTree::AuctionOracleKDTree(const std::vector& _bidde diagHeapHandles.push_back(diagItemsHeap.push(std::make_pair(itemIdx, 0))); } } - //to-do: remove maxVal from + //to-do: remove maxVal from maxVal = 3*getFurthestDistance3Approx(_bidders, _items); maxVal = pow(maxVal, wassersteinPower); weightAdjConst = maxVal; @@ -691,10 +691,10 @@ DebugOptimalBid AuctionOracleKDTree::getOptimalBidDebug(IdxType bidderIdx) bidderDnn[1] = bidder.getRealY(); std::vector candItems; - + if ( bidder.isDiagonal() ) { - // + // auto twoBestItems = kdtree->findK(bidderDnn, 2); candItems.push_back( std::make_pair(twoBestItems[0].p->id(), twoBestItems[0].d) ); candItems.push_back( std::make_pair(twoBestItems[1].p->id(), twoBestItems[1].d) ); @@ -738,7 +738,7 @@ DebugOptimalBid AuctionOracleKDTree::getOptimalBidDebug(IdxType bidderIdx) // checking code /* - + DebugOptimalBid debugMyResult(result); DebugOptimalBid debugNaiveResult; debugNaiveResult.bestItemValue = 1e20; @@ -800,7 +800,7 @@ IdxValPair AuctionOracleKDTree::getOptimalBid(IdxType bidderIdx) return result; } /* -a_{ij} = d_{ij} +a_{ij} = d_{ij} value_{ij} = a_{ij} + price_j */ void AuctionOracleKDTree::setPrice(IdxType itemIdx, double newPrice) @@ -812,13 +812,13 @@ void AuctionOracleKDTree::setPrice(IdxType itemIdx, double newPrice) if ( items[itemIdx].isNormal() ) { assert(0 <= itemIdx and itemIdx < kdtreeItems.size()); assert(0 <= kdtreeItems[itemIdx] and kdtreeItems[itemIdx] < dnnPointHandles.size()); - kdtree->increase_weight( dnnPointHandles[kdtreeItems[itemIdx]], newPrice); - kdtreeAll->increase_weight( dnnPointHandlesAll[itemIdx], newPrice); + kdtree->change_weight( dnnPointHandles[kdtreeItems[itemIdx]], newPrice); + kdtreeAll->change_weight( dnnPointHandlesAll[itemIdx], newPrice); } else { - kdtreeAll->increase_weight( dnnPointHandlesAll[itemIdx], newPrice); + kdtreeAll->change_weight( dnnPointHandlesAll[itemIdx], newPrice); assert(diagHeapHandles.size() > heapHandlesIndices.at(itemIdx)); diagItemsHeap.decrease(diagHeapHandles[heapHandlesIndices[itemIdx]], std::make_pair(itemIdx, newPrice)); - } + } } void AuctionOracleKDTree::adjustPrices(void) @@ -831,7 +831,7 @@ AuctionOracleKDTree::~AuctionOracleKDTree() delete kdtreeAll; } -void AuctionOracleKDTree::setEpsilon(double newVal) +void AuctionOracleKDTree::setEpsilon(double newVal) { assert(newVal >= 0.0); epsilon = newVal; @@ -840,8 +840,8 @@ void AuctionOracleKDTree::setEpsilon(double newVal) // ***************************** // AuctionOracleRestricted // ***************************** -AuctionOracleRestricted::AuctionOracleRestricted(const std::vector& b, - const std::vector& g, +AuctionOracleRestricted::AuctionOracleRestricted(const std::vector& b, + const std::vector& g, double _wassersteinPower, double internal_p) : AuctionOracleAbstract(b, g, _wassersteinPower, internal_p), @@ -866,12 +866,12 @@ AuctionOracleRestricted::AuctionOracleRestricted(const std::vector } } -IdxValPair AuctionOracleRestricted::getOptimalBid(const IdxType bidderIdx) +IdxValPair AuctionOracleRestricted::getOptimalBid(const IdxType bidderIdx) { assert(bidderIdx >=0 and bidderIdx < static_cast(bidders.size()) ); const auto bidder = bidders[bidderIdx]; - + IdxType bestItemIdx { -1 }; double bestItemValue { std::numeric_limits::max() }; //IdxType secondBestItemIdx { -1 }; @@ -921,9 +921,9 @@ IdxValPair AuctionOracleRestricted::getOptimalBid(const IdxType bidderIdx) //std::cout << "getOptimalBid: bidderIdx = " << bidderIdx << "; bestItemIdx = " << bestItemIdx << "; bestItemsDist= " << (weightAdjConst - bestItemValue) << "; bestItemsPrice = " << prices[bestItemIdx] << "; secondBestItemIdx = " << topIter->first << "; secondBestDist= " << (weightAdjConst - secondBestItemValue) << "; secondBestPrice = " << prices[topIter->first] << "; bid = " << prices[bestItemIdx] + ( bestItemValue - secondBestItemValue ) + epsilon << "; epsilon = " << epsilon << std::endl; // bid value: price + value difference + epsilon - - return std::make_pair(bestItemIdx, - prices[bestItemIdx] + + + return std::make_pair(bestItemIdx, + prices[bestItemIdx] + ( -bestItemValue + secondBestItemValue ) + epsilon ); } @@ -938,8 +938,8 @@ void AuctionOracleRestricted::setPrice(const IdxType itemIdx, const double newPr // AuctionOracleKDTreeRestricted // ***************************** -AuctionOracleKDTreeRestricted::AuctionOracleKDTreeRestricted(const std::vector& _bidders, - const std::vector& _items, +AuctionOracleKDTreeRestricted::AuctionOracleKDTreeRestricted(const std::vector& _bidders, + const std::vector& _items, const double _wassersteinPower, const double internal_p) : AuctionOracleAbstract(_bidders, _items, _wassersteinPower, internal_p), @@ -972,7 +972,7 @@ AuctionOracleKDTreeRestricted::AuctionOracleKDTreeRestricted(const std::vector(traits, dnnPointHandles, wassersteinPower); - + size_t handleIdx {0}; for(size_t itemIdx = 0; itemIdx < items.size(); ++itemIdx) { if (items[itemIdx].isDiagonal()) { @@ -980,7 +980,7 @@ AuctionOracleKDTreeRestricted::AuctionOracleKDTreeRestricted(const std::vectorid() }; double bestNormalItemValue { twoBestItems[0].d }; // if there is only one off-diagonal point in the second diagram, - // kd-tree will not return the second candidate. + // kd-tree will not return the second candidate. // Set its value to inf, so it will always lose to the value of the projection double secondBestNormalItemValue { twoBestItems.size() == 1 ? std::numeric_limits::max() : twoBestItems[1].d }; @@ -1231,28 +1231,39 @@ IdxValPair AuctionOracleKDTreeRestricted::getOptimalBid(IdxType bidderIdx) return result; } /* -a_{ij} = d_{ij} +a_{ij} = d_{ij} value_{ij} = a_{ij} + price_j */ void AuctionOracleKDTreeRestricted::setPrice(IdxType itemIdx, double newPrice) { assert(prices.size() == items.size()); assert( 0 < diagHeapHandles.size() and diagHeapHandles.size() <= items.size()); - assert(newPrice > prices.at(itemIdx)); + // adjustPrices decreases prices + bool itemGoesDown = newPrice > prices[itemIdx]; + //assert(newPrice > prices.at(itemIdx)); prices[itemIdx] = newPrice; if ( items[itemIdx].isNormal() ) { assert(0 <= itemIdx and itemIdx < kdtreeItems.size()); assert(0 <= kdtreeItems[itemIdx] and kdtreeItems[itemIdx] < dnnPointHandles.size()); - kdtree->increase_weight( dnnPointHandles[kdtreeItems[itemIdx]], newPrice); + kdtree->change_weight( dnnPointHandles[kdtreeItems[itemIdx]], newPrice); } else { assert(diagHeapHandles.size() > heapHandlesIndices.at(itemIdx)); - diagItemsHeap.decrease(diagHeapHandles[heapHandlesIndices[itemIdx]], std::make_pair(itemIdx, newPrice)); + if (itemGoesDown) { + diagItemsHeap.decrease(diagHeapHandles[heapHandlesIndices[itemIdx]], std::make_pair(itemIdx, newPrice)); + } else { + diagItemsHeap.increase(diagHeapHandles[heapHandlesIndices[itemIdx]], std::make_pair(itemIdx, newPrice)); + } bestDiagonalItemsComputed = false; } } void AuctionOracleKDTreeRestricted::adjustPrices(void) { + double minPrice = *(std::min_element(prices.begin(), prices.end())); + std::transform(prices.begin(), prices.end(), prices.begin(), [minPrice](double a) { return a - minPrice; }); + for(size_t itemIdx = 0; itemIdx < items.size(); ++itemIdx) { + setPrice(itemIdx, prices[itemIdx]); + } } AuctionOracleKDTreeRestricted::~AuctionOracleKDTreeRestricted() @@ -1260,7 +1271,7 @@ AuctionOracleKDTreeRestricted::~AuctionOracleKDTreeRestricted() delete kdtree; } -void AuctionOracleKDTreeRestricted::setEpsilon(double newVal) +void AuctionOracleKDTreeRestricted::setEpsilon(double newVal) { assert(newVal >= 0.0); epsilon = newVal; diff --git a/geom_matching/wasserstein/src/auction_runner_gs.cpp b/geom_matching/wasserstein/src/auction_runner_gs.cpp index 83d88c5..6489a65 100644 --- a/geom_matching/wasserstein/src/auction_runner_gs.cpp +++ b/geom_matching/wasserstein/src/auction_runner_gs.cpp @@ -1,5 +1,5 @@ /* - + Copyright (c) 2016, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements @@ -46,7 +46,7 @@ derivative works thereof, in binary and source code form. namespace geom_ws { // ***************************** -// AuctionRunnerGS +// AuctionRunnerGS // ***************************** AuctionRunnerGS::AuctionRunnerGS(const std::vector& A, const std::vector& B, const double q, const double _delta, const double _internal_p, const double _initialEpsilon, const double _epsFactor) : @@ -60,7 +60,7 @@ AuctionRunnerGS::AuctionRunnerGS(const std::vector& A, const std:: delta(_delta), internal_p(_internal_p), initialEpsilon(_initialEpsilon), - epsilonCommonRatio(_epsFactor == 0.0 ? 5.0 : _epsFactor) + epsilonCommonRatio(_epsFactor == 0.0 ? 5.0 : _epsFactor) { assert(initialEpsilon >= 0.0 ); assert(epsilonCommonRatio >= 0.0 ); @@ -117,7 +117,7 @@ void AuctionRunnerGS::flushAssignment(void) #endif } assert(unassignedBidders.size() == bidders.size()); - //oracle->adjustPrices(); + oracle->adjustPrices(); } void AuctionRunnerGS::runAuction(void) @@ -134,7 +134,7 @@ void AuctionRunnerGS::runAuction(void) // choose some initial epsilon if (initialEpsilon == 0.0) oracle->setEpsilon(oracle->maxVal / 4.0); - else + else oracle->setEpsilon(initialEpsilon); assert( oracle->getEpsilon() > 0 ); int iterNum { 0 }; @@ -144,7 +144,7 @@ void AuctionRunnerGS::runAuction(void) flushAssignment(); runAuctionPhase(); iterNum++; - //std::cout << "Iteration " << iterNum << " completed. " << std::endl; + //std::cout << "Iteration " << iterNum << " completed. " << std::endl; // result is d^q currentResult = getDistanceToQthPowerInternal(); double denominator = currentResult - numBidders * oracle->getEpsilon(); @@ -178,7 +178,7 @@ void AuctionRunnerGS::runAuction(void) oracle->setEpsilon( oracle->getEpsilon() / epsilonCommonRatio ); if (iterNum > maxIterNum) { #ifndef FOR_R_TDA - std::cerr << "Maximum iteration number exceeded, exiting. Current result is:"; + std::cerr << "Maximum iteration number exceeded, exiting. Current result is:"; std::cerr << wassersteinDistance << std::endl; #endif throw std::runtime_error("Maximum iteration number exceeded"); @@ -190,10 +190,10 @@ void AuctionRunnerGS::runAuction(void) for(size_t iterIdx = 0; iterIdx < iterResults.size(); ++iterIdx) { double trueRelError = ( iterResults.at(iterIdx) - currentResult ) / currentResult; auto iterCumulativeTime = iterTimes.at(iterIdx) - startMoment; - std::chrono::duration iterTime = ( iterIdx > 0) ? iterTimes[iterIdx] - iterTimes[iterIdx - 1] : iterTimes[iterIdx] - startMoment; + std::chrono::duration iterTime = ( iterIdx > 0) ? iterTimes[iterIdx] - iterTimes[iterIdx - 1] : iterTimes[iterIdx] - startMoment; std::cout << "iteration " << iterIdx << ", true rel. error " << - trueRelError << ", elapsed time " << - std::chrono::duration(iterCumulativeTime).count() << + trueRelError << ", elapsed time " << + std::chrono::duration(iterCumulativeTime).count() << ", iteration time " << iterTime.count() << std::endl; } #endif @@ -236,7 +236,7 @@ void AuctionRunnerGS::runAuctionPhase(void) #endif } - + double AuctionRunnerGS::getDistanceToQthPowerInternal(void) { sanityCheck(); diff --git a/geom_matching/wasserstein/src/auction_runner_jac.cpp b/geom_matching/wasserstein/src/auction_runner_jac.cpp index c807ec9..0b26a9f 100644 --- a/geom_matching/wasserstein/src/auction_runner_jac.cpp +++ b/geom_matching/wasserstein/src/auction_runner_jac.cpp @@ -1,5 +1,5 @@ /* - + Copyright (c) 2016, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements @@ -37,7 +37,7 @@ derivative works thereof, in binary and source code form. namespace geom_ws { // ***************************** -// AuctionRunnerJac +// AuctionRunnerJac // ***************************** AuctionRunnerJac::AuctionRunnerJac(const std::vector& A, const std::vector& B, const double q, const double _delta, const double _internal_p) : @@ -88,7 +88,7 @@ void AuctionRunnerJac::assignGoodToBidder(IdxType itemIdx, IdxType bidderIdx) } else { // the current owner of itemIdx gets my old item (OK if it's -1) biddersToItems[currItemOwner] = myOldItem; - // add the old owner of bids to the list of + // add the old owner of bids to the list of if ( -1 != myOldItem ) { #ifndef FOR_R_TDA std::cout << "This is not happening" << std::endl; @@ -183,7 +183,7 @@ void AuctionRunnerJac::flushAssignment(void) for(auto& g2b : itemsToBidders) { g2b = -1; } - //oracle->adjustPrices(); + oracle->adjustPrices(); } void AuctionRunnerJac::runAuction(void) @@ -198,7 +198,7 @@ void AuctionRunnerJac::runAuction(void) flushAssignment(); runAuctionPhase(); iterNum++; - //std::cout << "Iteration " << iterNum << " completed. " << std::endl; + //std::cout << "Iteration " << iterNum << " completed. " << std::endl; // result is d^q double currentResult = getDistanceToQthPowerInternal(); double denominator = currentResult - numBidders * oracle->getEpsilon(); @@ -220,7 +220,7 @@ void AuctionRunnerJac::runAuction(void) oracle->setEpsilon( oracle->getEpsilon() / epsilonCommonRatio ); if (iterNum > maxIterNum) { #ifndef FOR_R_TDA - std::cerr << "Maximum iteration number exceeded, exiting. Current result is:"; + std::cerr << "Maximum iteration number exceeded, exiting. Current result is:"; std::cerr << wassersteinDistance << std::endl; std::exit(1); #else @@ -274,7 +274,7 @@ void AuctionRunnerJac::runAuctionPhase(void) #endif } - + // assertion: the matching must be perfect double AuctionRunnerJac::getDistanceToQthPowerInternal(void) { diff --git a/geom_matching/wasserstein/src/basic_defs.cpp b/geom_matching/wasserstein/src/basic_defs.cpp index ec5dcec..b65ce25 100644 --- a/geom_matching/wasserstein/src/basic_defs.cpp +++ b/geom_matching/wasserstein/src/basic_defs.cpp @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements @@ -92,14 +92,14 @@ double distLp(const DiagramPoint& a, const DiagramPoint& b, const double p) if ( a.isNormal() or b.isNormal() ) { // distance between normal points is a usual l-inf distance return fabs(a.getRealX() - b.getRealX()) + fabs(a.getRealY() - b.getRealY()); - } else + } else return 0.0; - } + } if ( a.isNormal() or b.isNormal() ) { // distance between normal points is a usual l-inf distance return std::pow(std::pow(fabs(a.getRealX() - b.getRealX()), p) + std::pow(fabs(a.getRealY() - b.getRealY()), p), 1.0/p ); - } else + } else return 0.0; } @@ -130,7 +130,7 @@ std::ostream& operator<<(std::ostream& output, const DiagramPoint p) } #endif -DiagramPoint::DiagramPoint(double xx, double yy, Type ttype) : +DiagramPoint::DiagramPoint(double xx, double yy, Type ttype) : x(xx), y(yy), type(ttype) @@ -145,7 +145,7 @@ double DiagramPoint::getRealX() const { if (isNormal()) return x; - else + else return 0.5 * ( x + y); } @@ -153,7 +153,7 @@ double DiagramPoint::getRealY() const { if (isNormal()) return y; - else + else return 0.5 * ( x + y); } diff --git a/geom_matching/wasserstein/src/wasserstein.cpp b/geom_matching/wasserstein/src/wasserstein.cpp index b8a75ef..7cca705 100644 --- a/geom_matching/wasserstein/src/wasserstein.cpp +++ b/geom_matching/wasserstein/src/wasserstein.cpp @@ -1,5 +1,5 @@ /* - + Copyright (c) 2015, M. Kerber, D. Morozov, A. Nigmetov All rights reserved. @@ -12,7 +12,7 @@ Redistribution and use in source and binary forms, with or without modification, 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - + You are under no obligation whatsoever to provide any bug fixes, patches, or upgrades to the features, functionality or performance of the source code (Enhancements) to anyone; however, if you choose to make your Enhancements @@ -41,9 +41,9 @@ derivative works thereof, in binary and source code form. namespace geom_ws { -double wassersteinDistVec(const std::vector& A, - const std::vector& B, - const double q, +double wassersteinDistVec(const std::vector& A, + const std::vector& B, + const double q, const double delta, const double _internal_p, const double _initialEpsilon, @@ -103,9 +103,9 @@ double wassersteinDistVec(const std::vector& A, return result; } -double wassersteinCostVec(const std::vector& A, - const std::vector& B, - const double q, +double wassersteinCostVec(const std::vector& A, + const std::vector& B, + const double q, const double delta, const double _internal_p, const double _initialEpsilon, @@ -171,7 +171,7 @@ bool readDiagramPointSet(const char* fname, PairVector& result) if (line.empty()) { continue; } - // trim whitespaces + // trim whitespaces auto whiteSpaceFront = std::find_if_not(line.begin(),line.end(),isspace); auto whiteSpaceBack = std::find_if_not(line.rbegin(),line.rend(),isspace).base(); if (whiteSpaceBack <= whiteSpaceFront) { -- cgit v1.2.3