#ifndef __RIPS_H__
#define __RIPS_H__
#include <vector>
#include <string>
#include "simplex.h"
#include <boost/iterator/counting_iterator.hpp>
/**
* Rips class
*
* Class providing basic operations to work with Rips complexes. It implements Bron-Kerbosch algorithm,
* and provides simple wrappers for various functions.
*
* Distances_ is expected to define types IndexType and DistanceType as well as
* provide operator()(...) which given two IndexTypes should return
* the distance between them. There should be methods begin() and end()
* for iterating over IndexTypes as well as a method size().
*/
template<class Distances_, class Simplex_ = Simplex<typename Distances_::IndexType> >
class Rips
{
public:
typedef Distances_ Distances;
typedef typename Distances::IndexType IndexType;
typedef typename Distances::DistanceType DistanceType;
typedef Simplex_ Simplex;
typedef typename Simplex::Vertex Vertex; // should be the same as IndexType
typedef typename Simplex::VertexContainer VertexContainer;
class Evaluator;
class Comparison;
class ComparePair;
public:
Rips(const Distances& distances):
distances_(distances) {}
// Calls functor f on each simplex in the k-skeleton of the Rips complex
template<class Functor, class Iterator>
void generate(Dimension k, DistanceType max, const Functor& f,
Iterator candidates_begin, Iterator candidates_end) const;
// Calls functor f on all the simplices of the Rips complex that contain the given vertex v
template<class Functor, class Iterator>
void vertex_cofaces(IndexType v, Dimension k, DistanceType max, const Functor& f,
Iterator candidates_begin, Iterator candidates_end) const;
// Calls functor f on all the simplices of the Rips complex that contain the given edge [u,v]
template<class Functor, class Iterator>
void edge_cofaces(IndexType u, IndexType v, Dimension k, DistanceType max, const Functor& f,
Iterator candidates_begin, Iterator candidates_end) const;
// Calls functor f on all the simplices of the Rips complex that contain the given Simplex s
// (unlike the previous methods it does not call the functor on the Simplex s itself)
template<class Functor, class Iterator>
void cofaces(const Simplex& s, Dimension k, DistanceType max, const Functor& f,
Iterator candidates_begin, Iterator candidates_end) const;
/* No Iterator argument means Iterator = IndexType and the range is [distances().begin(), distances().end()) */
template<class Functor>
void generate(Dimension k, DistanceType max, const Functor& f) const
{ generate(k, max, f, boost::make_counting_iterator(distances().begin()), boost::make_counting_iterator(distances().end())); }
template<class Functor>
void vertex_cofaces(IndexType v, Dimension k, DistanceType max, const Functor& f) const
{ vertex_cofaces(v, k, max, f, boost::make_counting_iterator(distances().begin()), boost::make_counting_iterator(distances().end())); }
template<class Functor>
void edge_cofaces(IndexType u, IndexType v, Dimension k, DistanceType max, const Functor& f) const
{ edge_cofaces(u, v, k, max, f, boost::make_counting_iterator(distances().begin()), boost::make_counting_iterator(distances().end())); }
template<class Functor>
void cofaces(const Simplex& s, Dimension k, DistanceType max, const Functor& f) const
{ cofaces(s, k, max, f, boost::make_counting_iterator(distances().begin()), boost::make_counting_iterator(distances().end())); }
const Distances& distances() const { return distances_; }
DistanceType max_distance() const;
DistanceType distance(const Simplex& s1, const Simplex& s2) const;
private:
class WithinDistance;
template<class Functor, class NeighborTest>
void bron_kerbosch(VertexContainer& current,
const VertexContainer& candidates,
typename VertexContainer::const_iterator excluded,
Dimension max_dim,
const NeighborTest& neighbor,
const Functor& functor,
bool check_initial = true) const;
private:
const Distances& distances_;
};
template<class Distances_, class Simplex_>
class Rips<Distances_, Simplex_>::WithinDistance: public std::binary_function<Vertex, Vertex, bool>
{
public:
WithinDistance(const Distances_& distances,
DistanceType max):
distances_(distances), max_(max) {}
bool operator()(Vertex u, Vertex v) const { return distances_(u, v) <= max_; }
private:
const Distances& distances_;
DistanceType max_;
};
template<class Distances_, class Simplex_>
class Rips<Distances_, Simplex_>::Evaluator: public std::unary_function<const Simplex&, DistanceType>
{
public:
typedef Simplex_ Simplex;
Evaluator(const Distances& distances):
distances_(distances) {}
DistanceType operator()(const Simplex& s) const;
private:
const Distances& distances_;
};
template<class Distances_, class Simplex_>
class Rips<Distances_, Simplex_>::Comparison: public std::binary_function<const Simplex&, const Simplex&, bool>
{
public:
typedef Simplex_ Simplex;
Comparison(const Distances& distances):
eval_(distances) {}
bool operator()(const Simplex& s1, const Simplex& s2) const
{
DistanceType e1 = eval_(s1),
e2 = eval_(s2);
if (e1 == e2)
return s1.dimension() < s2.dimension();
return e1 < e2;
}
private:
Evaluator eval_;
};
template<class Distances_, class Simplex_>
struct Rips<Distances_, Simplex_>::ComparePair:
public std::binary_function<const std::pair<IndexType, IndexType>&,
const std::pair<IndexType, IndexType>&,
bool>
{
ComparePair(const Distances& distances):
distances_(distances) {}
bool operator()(const std::pair<IndexType, IndexType>& a,
const std::pair<IndexType, IndexType>& b) { return distances_(a.first, a.second) <
distances_(b.first, b.second); }
const Distances& distances_;
};
/**
* Class: ExplicitDistances
* Stores the pairwise distances of Distances_ instance passed at construction.
* It's a protypical Distances template argument for the Rips complex.
*/
template<class Distances_>
class ExplicitDistances
{
public:
typedef Distances_ Distances;
typedef size_t IndexType;
typedef typename Distances::DistanceType DistanceType;
ExplicitDistances(const Distances& distances);
DistanceType operator()(IndexType a, IndexType b) const;
size_t size() const { return size_; }
IndexType begin() const { return 0; }
IndexType end() const { return size(); }
private:
std::vector<DistanceType> distances_;
size_t size_;
};
/**
* Class: PairwiseDistances
* Given a Container_ of points and a Distance_, it computes distances between elements
* in the container (given as instances of Index_ defaulted to unsigned) using the Distance_ functor.
*
* Container_ is assumed to be an std::vector. That simplifies a number of things.
*/
template<class Container_, class Distance_, typename Index_ = unsigned>
class PairwiseDistances
{
public:
typedef Container_ Container;
typedef Distance_ Distance;
typedef Index_ IndexType;
typedef typename Distance::result_type DistanceType;
PairwiseDistances(const Container& container,
const Distance& distance = Distance()):
container_(container), distance_(distance) {}
DistanceType operator()(IndexType a, IndexType b) const { return distance_(container_[a], container_[b]); }
size_t size() const { return container_.size(); }
IndexType begin() const { return 0; }
IndexType end() const { return size(); }
private:
const Container& container_;
Distance distance_;
};
#include "rips.hpp"
#endif // __RIPS_H__