author Dmitriy Morozov <>
Thu, 18 Dec 2008 16:43:42 -0800
changeset 97 0a9bd3f34419
parent 42 07510f86b517
child 100 884f70adc576
permissions -rw-r--r--
Intermediate commit while converting to the new architecture * Converted Filtration into StaticPersistence and DynamicPersistenceTrails (both right now work with the underlying std::vector rather than std::list order) * Filtration is now just an auxilliary glue (a map between Complex and Persistence) * Whether chains are vectors or lists can be interchanged * Added PersistenceDiagram with a simple bottleneck_distance() function * Converted triangle, alphashapes3d, and cech-complex examples * Lots of organizational changes (factoring utilities out into containers.h, indirect.h, property-maps.h) * Trying to document along the way with NaturalDocs-type comments

 * Author: Dmitriy Morozov
 * Department of Computer Science, Duke University, 2005 -- 2008


#include "utilities/log.h"

#include "filtration.h"
#include "simplex.h"
#include "utilities/consistencylist.h"
#include <boost/utility.hpp>
#include <list>
#include "utilities/types.h"

#include <boost/serialization/access.hpp>
#include <boost/serialization/vector.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/nvp.hpp>

template<class VI, 
		 class Smplx = SimplexWithAttachment<VI>, 
		 class FltrSmplx = FiltrationSimplex<Smplx>,
		 class Vnrd = Vineyard<FltrSmplx> >
class LowerStarFiltration: public Filtration<Smplx, FltrSmplx, Vnrd>
		// Treat VertexIndex as an iterator
		typedef					VI													VertexIndex;		
		typedef					Smplx												Simplex;
		typedef					Filtration<Simplex>									Parent;
		typedef					typename Parent::Vineyard							Vineyard;

		typedef					typename Parent::Index								Index;
		typedef					typename Parent::const_Index						const_Index;
		typedef					typename Parent::Cycle								Cycle;
		typedef					typename Parent::Trail								Trail;
		typedef					typename Simplex::Cycle 							SimplexBoundaryCycle;

		template<class IndexType>		
		class 					VertexType;

		struct 					VertexDescriptor;
		typedef					ConsistencyList<VertexDescriptor>					VertexOrder;
		typedef					typename VertexOrder::iterator						VertexOrderIndex;
		typedef					typename VertexOrder::const_iterator				const_VertexOrderIndex;
		typedef 				typename VertexOrder::LessThanComparison			VertexOrderComparison;
		struct					SimplexAttachmentComparison;

								template<class VertexCmp>							
								LowerStarFiltration(VertexIndex begin, VertexIndex end, const VertexCmp& cmp, Vineyard* vineyard);

		using 					Parent::size;
		using 					Parent::begin;
		using 					Parent::end;
		VertexIndex				num_vertices() const								{ return vertex_order.size(); }
		const VertexOrderComparison& 
								get_vertex_cmp() const								{ return vertex_cmp; }
		Index 					append(const Simplex& s);
		bool					transpose_vertices(const VertexOrderIndex& voi);

		/// Hint function: if unsure, should return true
		virtual bool			neighbors(VertexIndex v1, VertexIndex v2) const		{ return true; }

		bool 					transpose(Index i);
		void					assert_pairing(Index i);
		VertexOrder				vertex_order;	
		VertexOrderComparison	vertex_cmp;
	/* Serialization */
		LowerStarFiltration()														{}
		friend class boost::serialization::access;
		template<class Archive>
		void save(Archive& ar, version_type ) const									{ ar << BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent); }

		template<class Archive>
		void load(Archive& ar, version_type );


 * Helper class that describes lower star vertex type. Defines essential
 * methods that LowerStarFiltration expects from its vertex type. Actual 
 * vertex types should inherit from it.
template<class VI, class Smplx, class FltrSmplx, class Vnrd>
template<class IndexType_> 
class LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
		typedef					IndexType_													IndexType;

		VertexType(IndexType ii = 0): i_(ii)												{}
		IndexType				index() const												{ return i_; }
		void					set_index(IndexType i)										{ i_ = i; }
		VertexOrderIndex		get_order() const											{ return order_; }
		void					set_order(const VertexOrderIndex& o)						{ order_ = o; }

		IndexType				i_;
		VertexOrderIndex		order_;

template<class VI, class Smplx, class FltrSmplx, class Vnrd>
struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
	VertexDescriptor(VertexIndex vi, Index si): 
		vertex_index(vi), simplex_index(si)		
	VertexIndex			vertex_index;
	Index				simplex_index;

template<class VI, class Smplx, class FltrSmplx, class Vnrd>
struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
	bool operator()(const Simplex& first, const Simplex& second) const;
	VertexOrderComparison	vertex_cmp;

#include "lowerstarfiltration.hpp"