-#ifndef __FPA__BASE__ALGORITHM__HXX__
-#define __FPA__BASE__ALGORITHM__HXX__
+// =========================================================================
+// @author Leonardo Florez Valencia
+// @email florez-l@javeriana.edu.co
+// =========================================================================
-#include <queue>
-#include <itkProcessObject.h>
+#ifndef __fpa__Base__Algorithm__hxx__
+#define __fpa__Base__Algorithm__hxx__
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Algorithm< V, C, R, S, VC, B >::_TNode::
-_TNode( )
- : Result( TResult( 0 ) ),
- FrontId( -1 ),
- Label( Self::FarLabel )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( )
+ : Superclass( )
{
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Algorithm< V, C, R, S, VC, B >::_TNode::
-~_TNode( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+TEvent( const TVertex& v, unsigned long fid, bool intoq )
+ : Superclass( ),
+ Vertex( v ),
+ FrontId( fid ),
+ IntoQueue( intoq )
{
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
-TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, S, VC, B >::
-GetMinimumSpanningTree( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+~TEvent( )
{
- return(
- dynamic_cast< TMinimumSpanningTree* >(
- this->itk::ProcessObject::GetOutput(
- this->m_MinimumSpanningTreeIndex
- )
- )
- );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
-TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, S, VC, B >::
-GetMinimumSpanningTree( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+const char*
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+GetEventName( ) const
{
- return(
- dynamic_cast< const TMinimumSpanningTree* >(
- this->itk::ProcessObject::GetOutput(
- this->m_MinimumSpanningTreeIndex
- )
- )
- );
+ return( "fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent" );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-GraftMinimumSpanningTree( itk::DataObject* obj )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+bool
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+CheckEvent( const itk::EventObject* e ) const
{
- TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
- if( mst != NULL )
- this->GraftNthOutput( this->m_MinimumSpanningTreeIndex, mst );
+ return( dynamic_cast< const Self* >( e ) != NULL );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-InvokeEvent( const itk::EventObject& e )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+itk::EventObject*
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::TEvent::
+MakeObject( ) const
{
- if( this->m_ThrowEvents )
- this->Superclass::InvokeEvent( e );
+ return( new Self );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-InvokeEvent( const itk::EventObject& e ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e )
{
- if( this->m_ThrowEvents )
+ TEvent a;
+ if( a.CheckEvent( &e ) )
+ {
+ if( this->m_VisualDebug )
+ this->Superclass::InvokeEvent( e );
+ }
+ else
this->Superclass::InvokeEvent( e );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-AddSeed( const TVertex& s, const TResult& r )
-{
- _TNode ns;
- ns.Parent = s;
- ns.Result = r;
- ns.FrontId = this->m_SeedVertices.size( );
- ns.Label = Self::FrontLabel;
- this->m_Seeds[ s ] = ns;
- this->m_SeedVertices.push_back( s );
- this->Modified( );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
-TVertex& fpa::Base::Algorithm< V, C, R, S, VC, B >::
-GetSeed( const unsigned int& id ) const
-{
- return( this->m_SeedVertices[ id ] );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-ClearSeeds( )
-{
- this->m_Seeds.clear( );
- this->m_SeedVertices.clear( );
- this->Modified( );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-unsigned long fpa::Base::Algorithm< V, C, R, S, VC, B >::
-GetNumberOfSeeds( ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+InvokeEvent( const itk::EventObject& e ) const
{
- return( this->m_Seeds.size( ) );
+ TEvent a;
+ if( a.CheckEvent( &e ) )
+ {
+ if( this->m_VisualDebug )
+ this->Superclass::InvokeEvent( e );
+ }
+ else
+ this->Superclass::InvokeEvent( e );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Algorithm< V, C, R, S, VC, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
Algorithm( )
: Superclass( ),
- m_ThrowEvents( false ),
- m_StopAtOneFront( false )
+ _TMarksInterface( this ),
+ _TSeedsInterface( this ),
+ m_VisualDebug( false )
{
- this->m_MinimumSpanningTreeIndex = this->GetNumberOfRequiredOutputs( );
- this->SetNumberOfRequiredOutputs( this->m_MinimumSpanningTreeIndex + 1 );
- this->itk::ProcessObject::SetNthOutput(
- this->m_MinimumSpanningTreeIndex, TMinimumSpanningTree::New( )
- );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-fpa::Base::Algorithm< V, C, R, S, VC, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
~Algorithm( )
{
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
GenerateData( )
{
- unsigned long N = this->m_Seeds.size( );
- if( N == 0 )
- return;
+ this->InvokeEvent( itk::StartEvent( ) );
- this->InvokeEvent( TStartEvent( ) );
+ // Init objects
this->_BeforeGenerateData( );
+ this->_ConfigureOutput( this->m_InitValue );
+ this->_InitMarks( this->GetSeeds( ).size( ) );
+ TNodes seeds = this->_UnifySeeds( );
+ this->_PrepareSeeds( seeds );
+
+ // Init queue
+ this->_QueueInit( );
+ typename TNodes::const_iterator sIt = seeds.begin( );
+ for( ; sIt != seeds.end( ); ++sIt )
+ {
+ this->_QueuePush( *sIt );
+ this->InvokeEvent( TEvent( sIt->Vertex, sIt->FrontId, true ) );
- this->m_Collisions.clear( );
- this->m_Collisions.
- resize( N, _TCollisionsRow( N, _TCollision( TVertex( ), false ) ) );
- this->_InitResults( );
- this->_InitMarks( );
- this->_InitQueue( );
- this->_Loop( );
- this->_AfterGenerateData( );
- this->InvokeEvent( TEndEvent( ) );
-}
+ } // rof
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_Loop( )
-{
- this->InvokeEvent( TStartLoopEvent( ) );
- this->_BeforeLoop( );
- while( !( this->_IsQueueEmpty( ) ) )
+ // Main loop
+ while( this->_QueueSize( ) > 0 )
{
// Get next candidate
- TVertex vertex;
- _TNode node;
- this->_QueuePop( vertex, node );
- if( this->_Node( vertex ).Label == Self::AliveLabel )
- continue;
-
- // Mark it as "Alive" and update final result
- node.Label = Self::AliveLabel;
- this->_Mark( vertex, node );
- this->_SetResult( vertex, node );
- this->InvokeEvent( TAliveEvent( vertex, node.FrontId ) );
-
- // Check if a forced stop condition arises
- if( !( this->_NeedToStop( ) ) )
+ TNode node = this->_QueuePop( );
+ this->InvokeEvent( TEvent( node.Vertex, node.FrontId, false ) );
+ if( !( this->_IsMarked( node.Vertex ) ) )
{
- // Compute neighborhood
- _TVertices neighborhood;
- this->_Neighborhood( neighborhood, vertex );
-
- // Iterate over neighbors
- typename _TVertices::iterator nIt = neighborhood.begin( );
- while( nIt != neighborhood.end( ) )
+ // Mark it
+ if( this->_Mark( node.Vertex, node.FrontId ) )
{
- _TNode neighbor = this->_Node( *nIt );
- if( neighbor.Label == Self::AliveLabel )
+ // Update output value
+ this->_UpdateOutputValue( node );
+
+ // Add neighborhood
+ TNeighborhood neighbors = this->_GetNeighbors( node.Vertex );
+ typename TNeighborhood::const_iterator nIt = neighbors.begin( );
+ bool coll = false;
+ while( nIt != neighbors.end( ) && !coll )
{
- // Update collisions
- if( this->_UpdateCollisions( vertex, *nIt ) )
+ if( this->_IsMarked( *nIt ) )
{
- this->_QueueClear( );
- nIt = neighborhood.end( );
- continue;
+ // Invoke stop at collisions
+ if( this->_Collisions( node.Vertex, *nIt ) )
+ {
+ this->_QueueClear( );
+ coll = true;
- } // fi
- }
- else
- {
- // Add new candidate to queue
- if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) )
- {
- neighbor.FrontId = node.FrontId;
- neighbor.Parent = vertex;
- neighbor.Label = Self::FrontLabel;
- this->_QueuePush( *nIt, neighbor );
- this->_Mark( *nIt, neighbor );
- this->InvokeEvent( TFrontEvent( *nIt, node.FrontId ) );
+ } // fi
}
else
- this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
-
- } // fi
- ++nIt;
-
- } // elihw
- }
- else
- this->_QueueClear( );
-
- } // elihw
- this->_AfterLoop( );
- this->InvokeEvent( TEndLoopEvent( ) );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_BeforeGenerateData( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_AfterGenerateData( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_BeforeLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_AfterLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_UpdateCollisions( const TVertex& a, const TVertex& b )
-{
- bool ret = false;
- _TNode na = this->_Node( a );
- _TNode nb = this->_Node( b );
- long fa = na.FrontId;
- long fb = nb.FrontId;
-
- if( fa != fb )
- {
- // Mark collision, if it is new
- bool exists = this->m_Collisions[ fa ][ fb ].second;
- exists &= this->m_Collisions[ fb ][ fa ].second;
-
- if( !exists )
- {
- this->m_Collisions[ fa ][ fb ].first = a;
- this->m_Collisions[ fa ][ fb ].second = true;
- this->m_Collisions[ fb ][ fa ].first = b;
- this->m_Collisions[ fb ][ fa ].second = true;
-
- // Stop if one front is desired
- if( this->m_StopAtOneFront )
- {
- // Perform a depth-first iteration on front graph
- unsigned long N = this->GetNumberOfSeeds( );
- unsigned long count = 0;
- std::vector< bool > m( N, false );
- std::queue< unsigned long > q;
- q.push( 0 );
- while( !q.empty( ) )
- {
- unsigned long f = q.front( );
- q.pop( );
+ {
+ TNode nnode;
+ nnode.Vertex = *nIt;
+ nnode.Parent = node.Vertex;
+ nnode.FrontId = node.FrontId;
+ if( this->_ComputeOutputValue( nnode ) )
+ {
+ this->_QueuePush( nnode );
+ this->InvokeEvent( TEvent( nnode.Vertex, nnode.FrontId, true ) );
- if( m[ f ] )
- continue;
- m[ f ] = true;
- count++;
+ } // fi
- for( unsigned int n = 0; n < N; ++n )
- if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
- q.push( n );
+ } // fi
+ ++nIt;
} // elihw
- ret = ( count == N );
} // fi
} // fi
+ this->_FinishOneLoop( );
- } // fi
- return( ret );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-bool fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_NeedToStop( ) const
-{
- return( false );
-}
-
-// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_Node( const TVertex& v )
-{
- typename _TNodes::iterator vIt = this->m_Marks.find( v );
- if( vIt == this->m_Marks.end( ) )
- {
- _TNode new_node;
- new_node.Parent = v;
- new_node.Result = TResult( 0 );
- new_node.FrontId = -1;
- new_node.Label = Self::FarLabel;
- this->m_Marks[ v ] = new_node;
- vIt = this->m_Marks.find( v );
+ } // elihw
- } // fi
- return( vIt->second );
+ // Finish
+ this->_AfterGenerateData( );
+ this->InvokeEvent( itk::EndEvent( ) );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-const typename fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_TNode& fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_Node( const TVertex& v ) const
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_BeforeGenerateData( )
{
- typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
- return( vIt->second );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_InitMarks( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_AfterGenerateData( )
{
- this->m_Marks.clear( );
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_Mark( const TVertex& v, const _TNode& node )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_FinishOneLoop( )
{
- this->m_Marks[ v ] = node;
}
// -------------------------------------------------------------------------
-template< class V, class C, class R, class S, class VC, class B >
-void fpa::Base::Algorithm< V, C, R, S, VC, B >::
-_InitQueue( )
+template< class _TFilter, class _TMarksInterface, class _TSeedsInterface >
+void fpa::Base::Algorithm< _TFilter, _TMarksInterface, _TSeedsInterface >::
+_QueueInit( )
{
this->_QueueClear( );
- for(
- typename _TNodes::const_iterator sIt = this->m_Seeds.begin( );
- sIt != this->m_Seeds.end( );
- sIt++
- )
- {
- this->_QueuePush( sIt->first, sIt->second );
- this->_Mark( sIt->first, sIt->second );
-
- } // rof
}
-#endif // __FPA__BASE__ALGORITHM__HXX__
+#endif // __fpa__Base__Algorithm__hxx__
// eof - $RCSfile$
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff