diff options
Diffstat (limited to 'geom_bottleneck/bottleneck/include/bound_match.h')
-rw-r--r-- | geom_bottleneck/bottleneck/include/bound_match.h | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/geom_bottleneck/bottleneck/include/bound_match.h b/geom_bottleneck/bottleneck/include/bound_match.h new file mode 100644 index 0000000..2e2d369 --- /dev/null +++ b/geom_bottleneck/bottleneck/include/bound_match.h @@ -0,0 +1,80 @@ +/* + Copyrigth 2015, D. Morozov, M. Kerber, A. Nigmetov + + This file is part of GeomBottleneck. + + GeomBottleneck is free software: you can redistribute it and/or modify + it under the terms of the Lesser GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + GeomBottleneck 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. See the + Lesser GNU General Public License for more details. + + You should have received a copy of the Lesser GNU General Public License + along with GeomBottleneck. If not, see <http://www.gnu.org/licenses/>. + +*/ + +#ifndef BOUND_MATCH_H +#define BOUND_MATCH_H + +#include <unordered_map> + +#include "basic_defs_bt.h" +#include "neighb_oracle.h" + + +namespace geom_bt { +typedef std::vector<DiagramPoint> Path; + +class Matching { +public: + Matching(const DiagramPointSet& AA, const DiagramPointSet& BB) : A(AA), B(BB) {}; + DiagramPointSet getExposedVertices(bool forA = true) const ; + bool isExposed(const DiagramPoint& p) const; + void getAllAdjacentVertices(const DiagramPointSet& setIn, DiagramPointSet& setOut, bool forA = true) const; + void increase(const Path& augmentingPath); + void checkAugPath(const Path& augPath) const; + bool getMatchedVertex(const DiagramPoint& p, DiagramPoint& result) const; + bool isPerfect() const; + void trimMatching(const double newThreshold); + friend std::ostream& operator<<(std::ostream& output, const Matching& m); +private: + DiagramPointSet A; + DiagramPointSet B; + std::unordered_map<DiagramPoint, DiagramPoint, DiagramPointHash> AToB, BToA; + void matchVertices(const DiagramPoint& pA, const DiagramPoint& pB); + void sanityCheck() const; +}; + + + +class BoundMatchOracle { +public: + BoundMatchOracle(DiagramPointSet psA, DiagramPointSet psB, double dEps, bool useRS = true); + bool isMatchLess(double r); + void setInnerOracle(NeighbOracleAbstract* innerOracle) { neighbOracle = innerOracle; } + bool buildMatchingForThreshold(const double r); + ~BoundMatchOracle(); +private: + DiagramPointSet A, B; + Matching M; + void printLayerGraph(void); + void buildLayerGraph(double r); + void buildLayerOracles(double r); + bool buildAugmentingPath(const DiagramPoint startVertex, Path& result); + void removeFromLayer(const DiagramPoint& p, const int layerIdx); + NeighbOracleAbstract* neighbOracle; + bool augPathExist; + std::vector<DiagramPointSet> layerGraph; + std::vector<NeighbOracle*> layerOracles; + double distEpsilon; + bool useRangeSearch; + double prevQueryValue; +}; + +} +#endif |