/*
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 .
*/
#ifndef BOUND_MATCH_H
#define BOUND_MATCH_H
#include
#include "basic_defs_bt.h"
#include "neighb_oracle.h"
namespace geom_bt {
typedef std::vector 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 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 layerGraph;
std::vector layerOracles;
double distEpsilon;
bool useRangeSearch;
double prevQueryValue;
};
}
#endif