#ifndef __FPA__BASE__ALGORITHM__HXX__
#define __FPA__BASE__ALGORITHM__HXX__
-#include <algorithm>
-#include <limits>
#include <queue>
+#include <itkProcessObject.h>
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
+_TNode( )
+ : Result( TResult( 0 ) ),
+ FrontId( -1 ),
+ Label( Self::FarLabel )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::_TNode::
+~_TNode( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
+GetMinimumSpanningTree( )
+{
+ return(
+ dynamic_cast< TMinimumSpanningTree* >(
+ this->itk::ProcessObject::GetOutput( 1 )
+ )
+ );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TMinimumSpanningTree* fpa::Base::Algorithm< V, C, R, VC, B >::
+GetMinimumSpanningTree( ) const
+{
+ return(
+ dynamic_cast< const TMinimumSpanningTree* >(
+ this->itk::ProcessObject::GetOutput( 1 )
+ )
+ );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+GraftMinimumSpanningTree( itk::DataObject* obj )
+{
+ TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
+ if( mst != NULL )
+ this->GraftNthOutput( 1, mst );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
InvokeEvent( const itk::EventObject& e )
{
if( this->m_ThrowEvents )
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
InvokeEvent( const itk::EventObject& e ) const
{
if( this->m_ThrowEvents )
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-AddSeed( const TVertex& s, const TResult& v )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+AddSeed( const TVertex& s, const TResult& r )
{
- this->m_Seeds.push_back( _TNode( s, v, this->m_Seeds.size( ) ) );
+ _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 T, class B >
-const typename fpa::Base::Algorithm< T, B >::
-TVertex& fpa::Base::Algorithm< T, B >::
-GetSeed( const unsigned long& i ) const
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+TVertex& fpa::Base::Algorithm< V, C, R, VC, B >::
+GetSeed( const unsigned int& id ) const
{
- return( this->m_Seeds[ i ].Vertex );
+ return( this->m_SeedVertices[ id ] );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
ClearSeeds( )
{
this->m_Seeds.clear( );
+ this->m_SeedVertices.clear( );
this->Modified( );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-unsigned long fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+unsigned long fpa::Base::Algorithm< V, C, R, VC, B >::
GetNumberOfSeeds( ) const
{
return( this->m_Seeds.size( ) );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::
Algorithm( )
: Superclass( ),
- m_StopAtOneFront( false ),
- m_ThrowEvents( false )
+ m_ThrowEvents( false ),
+ m_StopAtOneFront( false )
{
+ this->m_MinimumSpanningTreeIndex = this->GetNumberOfRequiredOutputs( );
+ this->SetNumberOfRequiredOutputs( this->m_MinimumSpanningTreeIndex + 1 );
+ this->itk::ProcessObject::SetNthOutput(
+ this->m_MinimumSpanningTreeIndex, TMinimumSpanningTree::New( )
+ );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Algorithm< V, C, R, VC, B >::
~Algorithm( )
{
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
GenerateData( )
{
- this->AllocateOutputs( );
-
unsigned long N = this->m_Seeds.size( );
if( N == 0 )
return;
- this->m_CollisionSites.clear( );
- this->m_CollisionSites.
- resize( N, _TCollisionSitesRow( N, _TCollision( TVertex( ), false ) ) );
-
- this->_BeforeMainLoop( );
- this->_InitializeMarks( );
- this->_InitializeResults( );
- this->_InitializeQueue( );
- this->_Loop( );
- this->_AfterMainLoop( );
- this->InvokeEvent( TEndEvent( ) );
-}
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_BeforeMainLoop( )
-{
-}
+ this->InvokeEvent( TStartEvent( ) );
+ this->_BeforeGenerateData( );
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_AfterMainLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_BeforeLoop( )
-{
-}
-
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_AfterLoop( )
-{
+ 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( ) );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
_Loop( )
{
+ this->InvokeEvent( TStartLoopEvent( ) );
this->_BeforeLoop( );
while( !( this->_IsQueueEmpty( ) ) )
{
- _TNode n = this->_QueuePop( );
- if( this->_IsMarked( n.Vertex ) )
+ // Get next candidate
+ TVertex vertex;
+ _TNode node;
+ this->_QueuePop( vertex, node );
+ if( this->_Node( vertex ).Label == Self::AliveLabel )
continue;
- this->_Mark( n );
- this->InvokeEvent( TMarkEvent( n ) );
- if( this->_UpdateResult( n ) )
+ // 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( ) ) )
{
- if( !( this->_CheckStopCondition( ) ) )
+ // Compute neighborhood
+ _TVertices neighborhood;
+ this->_Neighborhood( neighborhood, vertex );
+
+ // Iterate over neighbors
+ typename _TVertices::iterator nIt = neighborhood.begin( );
+ while( nIt != neighborhood.end( ) )
{
- _TNodes N;
- this->_Neighs( n, N );
- typename _TNodes::iterator nnIt = N.begin( );
- while( nnIt != N.end( ) )
+ _TNode neighbor = this->_Node( *nIt );
+ if( neighbor.Label == Self::AliveLabel )
{
- if( this->_IsMarked( nnIt->Vertex ) )
+ // Update collisions
+ if( this->_UpdateCollisions( vertex, *nIt ) )
{
- // Update real front identifier
- nnIt->FrontId = this->_FrontId( nnIt->Vertex );
-
- // Update collisions
- if( this->_CheckCollisions( n, *nnIt ) )
- {
- if( this->m_StopAtOneFront )
- {
- this->_QueueClear( );
- nnIt = N.end( );
-
- } // fi
+ this->_QueueClear( );
+ nIt = neighborhood.end( );
+ continue;
- } // fi
+ } // 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 ) );
}
else
- {
- if( this->_UpdateNeigh( *nnIt, n ) )
- {
- nnIt->Parent = n.Vertex;
- this->_QueuePush( *nnIt );
- this->InvokeEvent( TFrontEvent( *nnIt ) );
+ this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) );
- } // fi
+ } // fi
+ ++nIt;
- } // fi
- if( nnIt != N.end( ) )
- nnIt++;
-
- } // elihw
- }
- else
- this->_QueueClear( );
-
- } // fi
+ } // elihw
+ }
+ else
+ this->_QueueClear( );
} // elihw
this->_AfterLoop( );
+ this->InvokeEvent( TEndLoopEvent( ) );
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_BeforeGenerateData( )
+{
}
// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckCollisions( const _TNode& a, const _TNode& b )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_AfterGenerateData( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_BeforeLoop( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_AfterLoop( )
+{
+}
+
+// -------------------------------------------------------------------------
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Algorithm< V, C, R, VC, B >::
+_UpdateCollisions( const TVertex& a, const TVertex& b )
{
bool ret = false;
- if( a.FrontId != b.FrontId )
+ _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_CollisionSites[ a.FrontId ][ b.FrontId ].second;
- exists &= this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second;
+ bool exists = this->m_Collisions[ fa ][ fb ].second;
+ exists &= this->m_Collisions[ fb ][ fa ].second;
+
if( !exists )
{
- this->m_CollisionSites[ a.FrontId ][ b.FrontId ].first = a.Vertex;
- this->m_CollisionSites[ a.FrontId ][ b.FrontId ].second = true;
- this->m_CollisionSites[ b.FrontId ][ a.FrontId ].first = b.Vertex;
- this->m_CollisionSites[ b.FrontId ][ a.FrontId ].second = true;
+ 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 C = 0;
+ unsigned long count = 0;
std::vector< bool > m( N, false );
std::queue< unsigned long > q;
q.push( 0 );
if( m[ f ] )
continue;
m[ f ] = true;
- C++;
+ count++;
for( unsigned int n = 0; n < N; ++n )
- if( this->m_CollisionSites[ f ][ n ].second && !m[ n ] )
+ if( this->m_Collisions[ f ][ n ].second && !m[ n ] )
q.push( n );
} // elihw
- ret = ( C == N );
+ ret = ( count == N );
} // fi
}
// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_CheckStopCondition( )
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Algorithm< V, C, R, VC, B >::
+_NeedToStop( ) const
{
return( false );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_UpdateResult( _TNode& n )
+template< class V, class C, class R, class VC, class B >
+typename fpa::Base::Algorithm< V, C, R, VC, B >::
+_TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
+_Node( const TVertex& v )
{
- return( true );
-}
+ 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 );
-// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_InitializeMarks( )
-{
- this->m_Marks.clear( );
+ } // fi
+ return( vIt->second );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-bool fpa::Base::Algorithm< T, B >::
-_IsMarked( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+const typename fpa::Base::Algorithm< V, C, R, VC, B >::
+_TNode& fpa::Base::Algorithm< V, C, R, VC, B >::
+_Node( const TVertex& v ) const
{
- return( this->m_Marks.find( v ) != this->m_Marks.end( ) );
+ typename _TNodes::const_iterator vIt = this->m_Marks.find( v );
+ return( vIt->second );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-_TFrontId fpa::Base::Algorithm< T, B >::
-_FrontId( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_InitMarks( )
{
- typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
- if( mIt != this->m_Marks.end( ) )
- return( mIt->second.FrontId );
- else
- return( std::numeric_limits< _TFrontId >::max( ) );
+ this->m_Marks.clear( );
}
// -------------------------------------------------------------------------
-template< class T, class B >
-typename fpa::Base::Algorithm< T, B >::
-TVertex fpa::Base::Algorithm< T, B >::
-_Parent( const TVertex& v ) const
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_Mark( const TVertex& v, const _TNode& node )
{
- typename _TMarks::const_iterator mIt = this->m_Marks.find( v );
- if( mIt == this->m_Marks.end( ) )
- return( TVertex( ) );
- else
- return( mIt->second.Parent );
+ this->m_Marks[ v ] = node;
}
// -------------------------------------------------------------------------
-template< class T, class B >
-void fpa::Base::Algorithm< T, B >::
-_Mark( const _TNode& n )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Algorithm< V, C, R, VC, B >::
+_InitQueue( )
{
- this->m_Marks[ n.Vertex ] = n;
+ 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__
git://git.creatis.insa-lyon.fr / FrontAlgorithms.git / blobdiff