#include <algorithm>
#include <utility>
#include <boost/utility.hpp>
#include <iostream>
#include <utilities/log.h>
#include <utilities/counter.h>
#include <utilities/indirect.h>
#include <boost/iterator/counting_iterator.hpp>
#include <functional>
#ifdef LOGGING
static rlog::RLogChannel* rlRips = DEF_CHANNEL("rips/info", rlog::Log_Debug);
static rlog::RLogChannel* rlRipsDebug = DEF_CHANNEL("rips/debug", rlog::Log_Debug);
#endif // LOGGING
#ifdef COUNTERS
static Counter* cClique = GetCounter("rips/clique");
#endif // COUNTERS
template<class D, class S>
template<class Functor, class Iterator>
void
Rips<D,S>::
generate(Dimension k, DistanceType max, const Functor& f, Iterator bg, Iterator end) const
{
rLog(rlRipsDebug, "Entered generate with %d indices", distances().size());
WithinDistance neighbor(distances(), max);
// current = empty
// candidates = everything
VertexContainer current;
VertexContainer candidates(bg, end);
bron_kerbosch(current, candidates, boost::prior(candidates.begin()), k, neighbor, f);
}
template<class D, class S>
template<class Functor, class Iterator>
void
Rips<D,S>::
vertex_cofaces(IndexType v, Dimension k, DistanceType max, const Functor& f, Iterator bg, Iterator end) const
{
WithinDistance neighbor(distances(), max);
// current = [v]
// candidates = everything - [v]
VertexContainer current; current.push_back(v);
VertexContainer candidates;
for (Iterator cur = bg; cur != end; ++cur)
if (*cur != v && neighbor(v, *cur))
candidates.push_back(*cur);
bron_kerbosch(current, candidates, boost::prior(candidates.begin()), k, neighbor, f);
}
template<class D, class S>
template<class Functor, class Iterator>
void
Rips<D,S>::
edge_cofaces(IndexType u, IndexType v, Dimension k, DistanceType max, const Functor& f, Iterator bg, Iterator end) const
{
rLog(rlRipsDebug, "In edge_cofaces(%d, %d)", u, v);
WithinDistance neighbor(distances(), max);
AssertMsg(neighbor(u,v), "The new edge must be in the complex");
// current = [u,v]
// candidates = everything - [u,v]
VertexContainer current; current.push_back(u); current.push_back(v);
VertexContainer candidates;
for (Iterator cur = bg; cur != end; ++cur)
if (*cur != u && *cur != v && neighbor(v,*cur) && neighbor(u,*cur))
{
candidates.push_back(*cur);
rLog(rlRipsDebug, " added candidate: %d", *cur);
}
bron_kerbosch(current, candidates, boost::prior(candidates.begin()), k, neighbor, f);
}
template<class D, class S>
template<class Functor, class Iterator>
void
Rips<D,S>::
cofaces(const Simplex& s, Dimension k, DistanceType max, const Functor& f, Iterator bg, Iterator end) const
{
rLog(rlRipsDebug, "In cofaces(%s)", tostring(s).c_str());
WithinDistance neighbor(distances(), max);
// current = s.vertices()
VertexContainer current(s.vertices().begin(), s.vertices().end());
// candidates = everything - s.vertices() that is a neighbor() of every vertex in the simplex
VertexContainer candidates;
typedef difference_iterator<Iterator,
typename VertexContainer::const_iterator,
std::less<Vertex> > DifferenceIterator;
for (DifferenceIterator cur = DifferenceIterator(bg, end, s.vertices().begin(), s.vertices().end());
cur != DifferenceIterator(end, end, s.vertices().end(), s.vertices().end());
++cur)
{
bool nghbr = true;
for (typename VertexContainer::const_iterator v = s.vertices().begin(); v != s.vertices().end(); ++v)
if (!neighbor(*v, *cur)) { nghbr = false; break; }
if (nghbr)
{
candidates.push_back(*cur);
rLog(rlRipsDebug, " added candidate: %d", *cur);
}
}
bron_kerbosch(current, candidates, boost::prior(candidates.begin()), k, neighbor, f, false);
}
template<class D, class S>
template<class Functor, class NeighborTest>
void
Rips<D,S>::
bron_kerbosch(VertexContainer& current,
const VertexContainer& candidates,
typename VertexContainer::const_iterator excluded,
Dimension max_dim,
const NeighborTest& neighbor,
const Functor& functor,
bool check_initial) const
{
rLog(rlRipsDebug, "Entered bron_kerbosch");
if (check_initial && !current.empty())
{
Simplex s(current);
rLog(rlRipsDebug, "Reporting simplex: %s", tostring(s).c_str());
functor(s);
}
if (current.size() == max_dim + 1)
return;
rLog(rlRipsDebug, "Traversing %d vertices", candidates.end() - boost::next(excluded));
for (typename VertexContainer::const_iterator cur = boost::next(excluded); cur != candidates.end(); ++cur)
{
current.push_back(*cur);
rLog(rlRipsDebug, " current.size() = %d, current.back() = %d", current.size(), current.back());
VertexContainer new_candidates;
for (typename VertexContainer::const_iterator ccur = candidates.begin(); ccur != cur; ++ccur)
if (neighbor(*ccur, *cur))
new_candidates.push_back(*ccur);
size_t ex = new_candidates.size();
for (typename VertexContainer::const_iterator ccur = boost::next(cur); ccur != candidates.end(); ++ccur)
if (neighbor(*ccur, *cur))
new_candidates.push_back(*ccur);
excluded = new_candidates.begin() + (ex - 1);
bron_kerbosch(current, new_candidates, excluded, max_dim, neighbor, functor);
current.pop_back();
}
}
template<class Distances_, class Simplex_>
typename Rips<Distances_, Simplex_>::DistanceType
Rips<Distances_, Simplex_>::
distance(const Simplex& s1, const Simplex& s2) const
{
DistanceType mx = 0;
for (typename Simplex::VertexContainer::const_iterator a = s1.vertices().begin(); a != s1.vertices().end(); ++a)
for (typename Simplex::VertexContainer::const_iterator b = s2.vertices().begin(); b != s2.vertices().end(); ++b)
mx = std::max(mx, distances_(*a,*b));
return mx;
}
template<class Distances_, class Simplex_>
typename Rips<Distances_, Simplex_>::DistanceType
Rips<Distances_, Simplex_>::
max_distance() const
{
DistanceType mx = 0;
for (IndexType a = distances_.begin(); a != distances_.end(); ++a)
for (IndexType b = boost::next(a); b != distances_.end(); ++b)
mx = std::max(mx, distances_(a,b));
return mx;
}
template<class Distances_, class Simplex_>
typename Rips<Distances_, Simplex_>::DistanceType
Rips<Distances_, Simplex_>::Evaluator::
operator()(const Simplex& s) const
{
DistanceType mx = 0;
for (typename Simplex::VertexContainer::const_iterator a = s.vertices().begin(); a != s.vertices().end(); ++a)
for (typename Simplex::VertexContainer::const_iterator b = boost::next(a); b != s.vertices().end(); ++b)
mx = std::max(mx, distances_(*a,*b));
return mx;
}
template<class Distances_>
ExplicitDistances<Distances_>::
ExplicitDistances(const Distances& distances):
size_(distances.size()), distances_((distances.size() * (distances.size() + 1))/2)
{
IndexType i = 0;
for (typename Distances::IndexType a = distances.begin(); a != distances.end(); ++a)
for (typename Distances::IndexType b = a; b != distances.end(); ++b)
{
distances_[i++] = distances(a,b);
}
}
template<class Distances_>
typename ExplicitDistances<Distances_>::DistanceType
ExplicitDistances<Distances_>::
operator()(IndexType a, IndexType b) const
{
if (a > b) std::swap(a,b);
return distances_[a*size_ - ((a*(a-1))/2) + (b-a)];
}