author Dmitriy Morozov <>
Tue, 23 Dec 2008 11:40:38 -0800
changeset 101 9efac05d629b
parent 97 0a9bd3f34419
child 103 2ac129839e02
permissions -rw-r--r--
Changed Simplex::boundary() to be iterator-based (replaced it with boundary_begin() and boundary_end())


#include "static-persistence.h"
#include <utilities/types.h>

static Counter*  cTrailLength =             GetCounter("persistence/pair/traillength");     // the size of matrix U in RU decomposition
#endif // COUNTERS

template<class Data, class OrderDescriptor_, class ConsistencyIndex>
struct TrailData_: public Data
    typedef TrailData_<Data, OrderDescriptor_, ConsistencyIndex>                Self;

    typedef typename OrderTraits<typename OrderDescriptor_::
                                          template RebindData<Self>::
                                          other>::Index                         OrderIndex;
    typedef typename OrderDescriptor_::
                     Chains::template rebind<OrderIndex>::other::Chain          Trail;
    template<class Comparison>
    struct ConsistencyComparison
        typedef             const OrderIndex&                                   first_argument_type;
        typedef             const OrderIndex&                                   second_argument_type;
        typedef             bool                                                result_type;

        ConsistencyComparison(const Comparison& cmp = Comparison()): cmp_(cmp)  {}

        bool operator()(const OrderIndex& a, const OrderIndex& b) const         { return cmp_(a->consistency, b->consistency); }

        Comparison      cmp_;

    Trail                                                                       trail;
    ConsistencyIndex                                                            consistency;

 * Class: DynamicPersistenceTrails
 * Derives from StaticPersistence and allows one to update persistence 
 * after a transposition of two contiguous simplices in a filtration. 
 * In addition to reduced cycles, it stores each OrderElement's trails,
 * i.e. in addition to matrix R, it stores matrix U in vineyard notation.
 * Template parameters:
 *   Data_ -                auxilliary contents to store with each OrderElement
 *   OrderDescriptor_ -     class describing how the order is stored; it defaults to <VectorOrderDescriptor> 
 *                          which serves as a prototypical class
// TODO: perhaps Consistency should be wrapped into a ConsistencyDescriptor that somehow knows how to initialize it. 
// That way one could provide a simple consistency descriptor that just stored some integers describing the original 
// position, or one could provide consistency that is references into the complex
template<class Data_ =                  Empty, 
         class OrderDescriptor_ =       VectorOrderDescriptor<>,
         class ConsistencyIndex_ =      size_t,
         class ConsistencyComparison_ = std::less<ConsistencyIndex_> >
class DynamicPersistenceTrails: 
    public StaticPersistence<TrailData_<Data_, OrderDescriptor_, ConsistencyIndex_>, 
        typedef         Data_                                                           Data;
        typedef         TrailData_<Data_, OrderDescriptor_, ConsistencyIndex_>          TrailData;
        typedef         StaticPersistence<TrailData, OrderDescriptor_>                  Parent;
        typedef         typename Parent::Traits                                         Traits;
        typedef         typename Parent::OrderDescriptor                                OrderDescriptor;
        typedef         typename Parent::OrderComparison                                OrderComparison;
        typedef         typename Parent::OrderIndex                                     OrderIndex;
        typedef         ConsistencyIndex_                                               ConsistencyIndex;
        typedef         ThreeOutcomeCompare<
                            typename TrailData::
                            template ConsistencyComparison<ConsistencyComparison_> >    ConsistencyComparison;

         * Constructor: DynamicPersistenceTrails()
         * TODO: write a description
         * Template parameters:
         *   Filtration -           filtration of the complex whose persistence we are computing
        template<class Filtration>      DynamicPersistenceTrails(const Filtration&              f, 
                                                                 const OrderComparison&         ocmp =  OrderComparison(),
                                                                 const ConsistencyComparison_&  ccmp =  ConsistencyComparison_());
        void                            pair_simplices();

        // Function: transpose(i)
        // Tranpose i and the next element. 
        // Returns: true iff the pairing switched.
        bool                            transpose(OrderIndex i)                         { return transpose(i, TranspositionVisitor()); }
        template<class Visitor>
        bool                            transpose(OrderIndex i, const Visitor& visitor = Visitor());

        using                           Parent::begin;
        using                           Parent::end;

        // Struct: TranspositionVisitor
        // For example, a VineardVisitor could implement this archetype.
        struct TranspositionVisitor
            // Function: transpose(i)
            // This function is called before transposition is processed 
            // (at the very beginning of <transpose(i, visitor)>). It is meant to update any structures 
            // that may need to be updated, but perhaps it has other uses as well.
            void                        transpose(OrderIndex i) const                   {}

            // Function: switched(i, type)
            // This function is called after the transposition if the switch in pairing has occured.
            // `i` is the index of the preceding simplex after the transposition. 
            // `type` indicates the <SwitchType>.
            void                        switched(OrderIndex i, SwitchType type) const   {}

        using                           Parent::order;

        void                            swap(OrderIndex i, OrderIndex j);
        void                            pairing_switch(OrderIndex i, OrderIndex j);

        struct PairingTrailsVisitor: public Parent::PairVisitor 
            // TODO: this is specialized for std::vector
                                        PairingTrailsVisitor(OrderIndex bg, ConsistencyComparison ccmp): 
                                            bg_(bg), ccmp_(ccmp)                        {}

            void                        init(OrderIndex i) const                        { i->consistency = i - bg_; i->trail.append(i, ccmp_); Count(cTrailLength); }
            void                        update(OrderIndex j, OrderIndex i) const        { i->pair->trail.append(j, ccmp_); Count(cTrailLength); }

            OrderIndex                  bg_;
            ConsistencyComparison       ccmp_;

        ConsistencyComparison           ccmp_;

#include "dynamic-persistence.hpp"