Updated weighted rips libraries to make use of OOP--now WeightedRips inherits from Rips. It is possible that logging for WeightedRips does not work.
--- a/include/topology/rips.h Thu Jul 02 15:42:44 2009 -0700
+++ b/include/topology/rips.h Mon Jul 13 19:44:04 2009 -0700
@@ -84,7 +84,7 @@
DistanceType distance(const Simplex& s1, const Simplex& s2) const;
- private:
+ protected:
class WithinDistance;
template<class Functor, class NeighborTest>
@@ -96,7 +96,7 @@
const Functor& functor,
bool check_initial = true) const;
- private:
+ protected:
const Distances& distances_;
};
@@ -111,7 +111,7 @@
bool operator()(Vertex u, Vertex v) const { return distances_(u, v) <= max_; }
- private:
+ protected:
const Distances& distances_;
DistanceType max_;
};
@@ -127,7 +127,7 @@
DistanceType operator()(const Simplex& s) const;
- private:
+ protected:
const Distances& distances_;
};
@@ -150,7 +150,7 @@
return e1 < e2;
}
- private:
+ protected:
Evaluator eval_;
};
--- a/include/topology/weighted-rips.h Thu Jul 02 15:42:44 2009 -0700
+++ b/include/topology/weighted-rips.h Mon Jul 13 19:44:04 2009 -0700
@@ -4,6 +4,7 @@
#include <vector>
#include <string>
#include "simplex.h"
+#include "rips.h"
#include <boost/iterator/counting_iterator.hpp>
@@ -19,9 +20,11 @@
* for iterating over IndexTypes as well as a method size().
*/
template<class Distances_, class Simplex_ = Simplex<typename Distances_::IndexType, typename Distances_::DistanceType> >
-class WeightedRips
+class WeightedRips : public Rips<Distances_, Simplex_>
{
public:
+
+ /* redeclaring the typedefs because they cannot be inherited at compile-time */
typedef Distances_ Distances;
typedef typename Distances::IndexType IndexType;
typedef typename Distances::DistanceType DistanceType;
@@ -32,114 +35,29 @@
class Evaluator;
class Comparison;
- class ComparePair;
public:
WeightedRips(const Distances& distances):
- distances_(distances) {}
-
- // Calls functor f on each simplex in the k-skeleton of the weighted 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 weighted 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 weighted 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 weighted 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())); }
+ Rips<Distances_, Simplex_>(distances) {}
- 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 WeightedRips<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 WeightedRips<Distances_, Simplex_>::Evaluator: public std::unary_function<const Simplex&, DistanceType>
+class WeightedRips<Distances_, Simplex_>::Evaluator: public Rips<Distances_, Simplex_>::Evaluator
{
public:
- typedef Simplex_ Simplex;
-
Evaluator(const Distances& distances):
- distances_(distances) {}
+ Rips<Distances_, Simplex_>::Evaluator(distances) {}
- DistanceType operator()(const Simplex& s) const;
-
- private:
- const Distances& distances_;
+ DistanceType operator()(const Simplex& s) const { return s.data(); }
};
-/* TODO: I'm pretty sure we don't even need this anymore */
template<class Distances_, class Simplex_>
-class WeightedRips<Distances_, Simplex_>::Comparison: public std::binary_function<const Simplex&, const Simplex&, bool>
+class WeightedRips<Distances_, Simplex_>::Comparison: public Rips<Distances_, Simplex_>::Comparison
{
public:
- typedef Simplex_ Simplex;
-
Comparison(const Distances& distances):
- eval_(distances) {}
+ Rips<Distances_, Simplex_>::Comparison(distances) {}
bool operator()(const Simplex& s1, const Simplex& s2) const
{
@@ -147,29 +65,8 @@
return s1.dimension() < s2.dimension();
return s1.data() < s2.data();
}
-
- private:
- Evaluator eval_;
};
-/* TODO: May need to change this function for weighted Rips, I'm not sure */
-template<class Distances_, class Simplex_>
-struct WeightedRips<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_;
-};
-
-
#include "weighted-rips.hpp"
#endif // __WEIGHTED_RIPS_H__
--- a/include/topology/weighted-rips.hpp Thu Jul 02 15:42:44 2009 -0700
+++ b/include/topology/weighted-rips.hpp Mon Jul 13 19:44:04 2009 -0700
@@ -16,178 +16,3 @@
#ifdef COUNTERS
static Counter* cClique = GetCounter("rips/clique"); /* TODO: same here */
#endif // COUNTERS
-
-template<class D, class S>
-template<class Functor, class Iterator>
-void
-WeightedRips<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
-WeightedRips<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
-WeightedRips<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
-WeightedRips<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
-WeightedRips<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 WeightedRips<Distances_, Simplex_>::DistanceType
-WeightedRips<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 WeightedRips<Distances_, Simplex_>::DistanceType
-WeightedRips<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 WeightedRips<Distances_, Simplex_>::DistanceType
-WeightedRips<Distances_, Simplex_>::Evaluator::
-operator()(const Simplex& s) const
-{
- return s.data();
-}