#ifndef __FPA__BASE__ALGORITHM__H__
#define __FPA__BASE__ALGORITHM__H__
-#include <map>
+#include <functional>
+#include <set>
#include <utility>
#include <vector>
+#include <fpa/Config.h>
#include <fpa/Base/Events.h>
-#include <fpa/Base/MinimumSpanningTree.h>
namespace fpa
{
* vertex could be marked as "visited", "in the front", "not yet there"
* or "freezed".
*
- * @param V Vertex type.
- * @param C Vertex value type.
- * @param R Result value type.
- * @param S Space type where vertices are.
- * @param VC Vertex lexicographical compare.
- * @param B Base class for this algorithm. It should be any itk-based
- * filter (itk::ProcessObject).
+ * @param _TVertex Vertex type.
+ * @param _TScalar Scalar (real computations) type.
+ * @param _TFilter Base class for this algorithm. It should be any
+ * itk-based filter (itk::ProcessObject).
+ * @param _TVertexCompare Vertex lexicographical compare.
*
*/
- template< class V, class C, class R, class S, class VC, class B >
+ template< class _TVertex, class _TScalar, class _TFilter, class _TVertexCompare = std::less< _TVertex > >
class Algorithm
- : public B
+ : public _TFilter
{
public:
typedef Algorithm Self;
- typedef B Superclass;
+ typedef _TFilter Superclass;
typedef itk::SmartPointer< Self > Pointer;
typedef itk::SmartPointer< const Self > ConstPointer;
- typedef V TVertex;
- typedef C TValue;
- typedef R TResult;
- typedef S TSpace;
- typedef VC TVertexCompare;
+ // Template arguments
+ typedef _TVertex TVertex;
+ typedef _TScalar TScalar;
+ typedef _TFilter TFilter;
+ typedef _TVertexCompare TVertexCompare;
- fpa_Base_NewEvent( TStartEvent );
- fpa_Base_NewEvent( TStartLoopEvent );
- fpa_Base_NewEvent( TStartBacktrackingEvent );
- fpa_Base_NewEvent( TEndEvent );
- fpa_Base_NewEvent( TEndLoopEvent );
- fpa_Base_NewEvent( TEndBacktrackingEvent );
- fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
- fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
- fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
- fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );
+ // Some useful types
+ typedef unsigned long TFrontId;
- protected:
- typedef std::vector< TVertex > _TVertices;
- typedef std::pair< TVertex, bool > _TCollision;
- typedef std::vector< _TCollision > _TCollisionsRow;
- typedef std::vector< _TCollisionsRow > _TCollisions;
+ // Minigraph to represent collisions
+ typedef std::pair< TVertex, bool > TCollision;
+ typedef std::vector< TCollision > TCollisionsRow;
+ typedef std::vector< TCollisionsRow > TCollisions;
- /**
- */
- enum _TNodeLabel
+ enum TNodeLabel
{
FarLabel = 0,
FrontLabel,
};
/**
+ * WARNING: std::set< T > objects are immutable
*/
- class _TNode
+ struct TNode
{
- public:
- _TNode( );
- virtual ~_TNode( );
-
- public:
- TVertex Parent;
- TResult Result;
- short FrontId;
- char Label;
+ static const TVertexCompare VertexCompare;
+ TVertex Vertex;
+ mutable TVertex Parent;
+ mutable TScalar Result;
+ mutable TFrontId FrontId;
+ mutable TNodeLabel Label;
+ bool operator<( const TNode& other ) const
+ { return( VertexCompare( this->Vertex, other.Vertex ) ); }
};
- typedef std::map< TVertex, _TNode, TVertexCompare > _TNodes;
-
- public:
- typedef
- fpa::Base::MinimumSpanningTree< V, _TCollisions, VC >
- TMinimumSpanningTree;
+ typedef std::set< TNode > TNodes;
+ typedef std::vector< TVertex > TVertices;
public:
- itkTypeMacro( Algorithm, B );
+ itkTypeMacro( Algorithm, _TFilter );
- itkBooleanMacro( ThrowEvents );
itkBooleanMacro( StopAtOneFront );
-
- itkGetConstMacro( ThrowEvents, bool );
itkGetConstMacro( StopAtOneFront, bool );
+ itkSetMacro( StopAtOneFront, bool );
+ itkBooleanMacro( ThrowEvents );
+ itkGetConstMacro( ThrowEvents, bool );
itkSetMacro( ThrowEvents, bool );
- itkSetMacro( StopAtOneFront, bool );
- public:
- TMinimumSpanningTree* GetMinimumSpanningTree( );
- const TMinimumSpanningTree* GetMinimumSpanningTree( ) const;
- void GraftMinimumSpanningTree( itk::DataObject* obj );
+ fpa_Base_NewEvent( TStartEvent );
+ fpa_Base_NewEvent( TStartLoopEvent );
+ fpa_Base_NewEvent( TStartBacktrackingEvent );
+ fpa_Base_NewEvent( TEndEvent );
+ fpa_Base_NewEvent( TEndLoopEvent );
+ fpa_Base_NewEvent( TEndBacktrackingEvent );
+ fpa_Base_NewEventWithVertex( TCollisionEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TAliveEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TFrontEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TFreezeEvent, TVertex );
+ fpa_Base_NewEventWithVertex( TBacktrackingEvent, TVertex );
+ public:
virtual void InvokeEvent( const itk::EventObject& e );
virtual void InvokeEvent( const itk::EventObject& e ) const;
- void AddSeed( const TVertex& s, const TResult& r );
- const TVertex& GetSeed( const unsigned int& id ) const;
- void ClearSeeds( );
unsigned long GetNumberOfSeeds( ) const;
+ void AddSeed( const TVertex& s, const TScalar& v = TScalar( 0 ) );
+ void AddSeed( const TNode& n );
+ void RemoveSeed( const TVertex& s );
+ void RemoveAllSeeds( );
protected:
+ // Methods to extend itk-based architecture
Algorithm( );
virtual ~Algorithm( );
+ virtual void GenerateData( ) fpa_OVERRIDE;
- // Connection with itk's pipeline
- virtual void GenerateData( );
-
- // Main loop algorithm
+ // Front propagation generic methods
virtual void _Loop( );
- // Supporting methods for loop
+ // Front propagation methods to be overloaded
virtual void _BeforeGenerateData( );
virtual void _AfterGenerateData( );
virtual void _BeforeLoop( );
virtual void _AfterLoop( );
- // Methods to control forced stops
- virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
- virtual bool _NeedToStop( ) const;
-
- // Graph-related abstract methods
- virtual unsigned long _NumberOfVertices( ) const = 0;
- virtual const TValue& _VertexValue( const TVertex& v ) const = 0;
- virtual double _Distance(
- const TVertex& a, const TVertex& b
- ) const = 0;
- virtual bool _HasEdge( const TVertex& a, const TVertex& b ) const = 0;
- virtual void _Neighborhood(
- _TVertices& neighborhood, const TVertex& v
- ) const = 0;
-
- // Results-related abstract methods
- virtual bool _ComputeNeighborResult(
- TResult& result, const TVertex& neighbor, const TVertex& parent
- ) const = 0;
+ virtual void _InitMarks( ) = 0;
virtual void _InitResults( ) = 0;
- virtual const TResult& _Result( const TVertex& v ) const = 0;
- virtual void _SetResult( const TVertex& v, const _TNode& n ) = 0;
-
- // Marks-related abstract methods
- virtual _TNode& _Node( const TVertex& v );
- virtual const _TNode& _Node( const TVertex& v ) const;
- virtual void _InitMarks( );
- virtual void _Mark( const TVertex& v, const _TNode& node );
-
- // Queue-related abstract methods
- virtual void _InitQueue( );
- virtual bool _IsQueueEmpty( ) const = 0;
- virtual void _QueuePush( const TVertex& v, const _TNode& n ) = 0;
- virtual void _QueuePop( TVertex& v, _TNode& n ) = 0;
- virtual void _QueueClear( ) = 0;
+ virtual void _DeallocateAuxiliary( ) = 0;
+
+ virtual TFrontId _GetMark( const TVertex& v ) = 0;
+ virtual TFrontId _GetMark( const TNode& v );
+
+ virtual void _Visit( const TNode& n ) = 0;
+ virtual bool _NeedToStop( );
+
+ virtual TVertices _GetNeighborhood( const TVertex& v ) const = 0;
+ virtual TVertices _GetNeighborhood( const TNode& n ) const;
+
+ virtual bool _Result( TNode& node, const TNode& parent ) = 0;
+
+ virtual void _QueueClear( ) = 0;
+ virtual void _QueuePush( const TNode& node ) = 0;
+ virtual TNode _QueuePop( ) = 0;
+ virtual bool _IsQueueEmpty( ) const = 0;
+
+ virtual bool _UpdateCollisions( const TVertex& a, const TVertex& b );
private:
// Purposely not implemented
Self& operator=( const Self& other );
protected:
- bool m_ThrowEvents;
- bool m_StopAtOneFront;
- _TNodes m_Seeds;
- _TVertices m_SeedVertices;
- _TNodes m_Marks;
- _TCollisions m_Collisions;
-
- unsigned int m_MinimumSpanningTreeIndex;
+ TNodes m_Seeds;
+ TCollisions m_Collisions;
+ bool m_StopAtOneFront;
+ bool m_ThrowEvents;
};
} // ecapseman
} // ecapseman
-#include <fpa/Base/Algorithm.hxx>
+#ifndef ITK_MANUAL_INSTANTIATION
+# include <fpa/Base/Algorithm.hxx>
+#endif
#endif // __FPA__BASE__ALGORITHM__H__