X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2Ffpa%2FBase%2FAlgorithm.hxx;h=5629af77c9436373f3ec5512ea0d6b0f89e0a0f8;hb=eb4acd3dde87a3e33593c3ce87d0d351dec23f69;hp=eb307580601ef9a85042165a46cd93b934afa94f;hpb=db33ebb226fd58f493b7db245fc8b807f895ee6e;p=FrontAlgorithms.git diff --git a/lib/fpa/Base/Algorithm.hxx b/lib/fpa/Base/Algorithm.hxx index eb30758..5629af7 100644 --- a/lib/fpa/Base/Algorithm.hxx +++ b/lib/fpa/Base/Algorithm.hxx @@ -2,10 +2,11 @@ #define __FPA__BASE__ALGORITHM__HXX__ #include +#include // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -fpa::Base::Algorithm< V, C, R, B >::_TNode:: +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 ), @@ -14,15 +15,55 @@ _TNode( ) } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -fpa::Base::Algorithm< V, C, R, B >::_TNode:: +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 V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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( ) +{ + 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 +{ + return( + dynamic_cast< const TMinimumSpanningTree* >( + this->itk::ProcessObject::GetOutput( + this->m_MinimumSpanningTreeIndex + ) + ) + ); +} + +// ------------------------------------------------------------------------- +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 ) +{ + TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj ); + if( mst != NULL ) + this->GraftNthOutput( this->m_MinimumSpanningTreeIndex, mst ); +} + +// ------------------------------------------------------------------------- +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 ) { if( this->m_ThrowEvents ) @@ -30,8 +71,8 @@ InvokeEvent( const itk::EventObject& e ) } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 { if( this->m_ThrowEvents ) @@ -39,66 +80,72 @@ InvokeEvent( const itk::EventObject& e ) const } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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.Vertex = s; ns.Parent = s; ns.Result = r; - ns.FrontId = this->m_Seeds.size( ); + ns.FrontId = this->m_SeedVertices.size( ); ns.Label = Self::FrontLabel; - this->m_Seeds.push_back( ns ); + this->m_Seeds[ s ] = ns; + this->m_SeedVertices.push_back( s ); this->Modified( ); } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -const typename fpa::Base::Algorithm< V, C, R, B >:: -TVertex& fpa::Base::Algorithm< V, C, R, B >:: +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_Seeds[ id ].Vertex ); + return( this->m_SeedVertices[ id ] ); } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 B > -unsigned long fpa::Base::Algorithm< V, C, R, B >:: +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 { return( this->m_Seeds.size( ) ); } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -fpa::Base::Algorithm< V, C, R, B >:: +template< class V, class C, class R, class S, class VC, class B > +fpa::Base::Algorithm< V, C, R, S, VC, B >:: Algorithm( ) : Superclass( ), 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 V, class C, class R, class B > -fpa::Base::Algorithm< V, C, R, B >:: +template< class V, class C, class R, class S, class VC, class B > +fpa::Base::Algorithm< V, C, R, S, VC, B >:: ~Algorithm( ) { } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +template< class V, class C, class R, class S, class VC, class B > +void fpa::Base::Algorithm< V, C, R, S, VC, B >:: GenerateData( ) { unsigned long N = this->m_Seeds.size( ); @@ -120,8 +167,8 @@ GenerateData( ) } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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( ) ); @@ -129,33 +176,34 @@ _Loop( ) while( !( this->_IsQueueEmpty( ) ) ) { // Get next candidate - _TNode candidate = this->_QueuePop( ); - if( this->_Node( candidate.Vertex ).Label == Self::AliveLabel ) + TVertex vertex; + _TNode node; + this->_QueuePop( vertex, node ); + if( this->_Node( vertex ).Label == Self::AliveLabel ) continue; // Mark it as "Alive" and update final result - candidate.Label = Self::AliveLabel; - this->_Mark( candidate ); - this->_SetResult( candidate.Vertex, candidate.Result ); - this->InvokeEvent( TAliveEvent( candidate.Vertex, candidate.FrontId ) ); + 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( ) ) ) { // Compute neighborhood _TVertices neighborhood; - this->_Neighborhood( neighborhood, candidate.Vertex ); + this->_Neighborhood( neighborhood, vertex ); // Iterate over neighbors typename _TVertices::iterator nIt = neighborhood.begin( ); while( nIt != neighborhood.end( ) ) { _TNode neighbor = this->_Node( *nIt ); - neighbor.Vertex = *nIt; if( neighbor.Label == Self::AliveLabel ) { // Update collisions - if( this->_UpdateCollisions( candidate.Vertex, *nIt ) ) + if( this->_UpdateCollisions( vertex, *nIt ) ) { this->_QueueClear( ); nIt = neighborhood.end( ); @@ -166,21 +214,17 @@ _Loop( ) else { // Add new candidate to queue - if( - this->_ComputeNeighborResult( - neighbor.Result, *nIt, candidate.Vertex - ) - ) + if( this->_ComputeNeighborResult( neighbor.Result, *nIt, vertex ) ) { - neighbor.FrontId = candidate.FrontId; - neighbor.Parent = candidate.Vertex; + neighbor.FrontId = node.FrontId; + neighbor.Parent = vertex; neighbor.Label = Self::FrontLabel; - this->_QueuePush( neighbor ); - this->_Mark( neighbor ); - this->InvokeEvent( TFrontEvent( *nIt, candidate.FrontId ) ); + this->_QueuePush( *nIt, neighbor ); + this->_Mark( *nIt, neighbor ); + this->InvokeEvent( TFrontEvent( *nIt, node.FrontId ) ); } else - this->InvokeEvent( TFreezeEvent( *nIt, candidate.FrontId ) ); + this->InvokeEvent( TFreezeEvent( *nIt, node.FrontId ) ); } // fi ++nIt; @@ -196,36 +240,36 @@ _Loop( ) } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 B > -bool fpa::Base::Algorithm< V, C, R, B >:: +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; @@ -242,9 +286,9 @@ _UpdateCollisions( const TVertex& a, const TVertex& b ) if( !exists ) { - this->m_Collisions[ fa ][ fb ].first = na.Vertex; + this->m_Collisions[ fa ][ fb ].first = a; this->m_Collisions[ fa ][ fb ].second = true; - this->m_Collisions[ fb ][ fa ].first = nb.Vertex; + this->m_Collisions[ fb ][ fa ].first = b; this->m_Collisions[ fb ][ fa ].second = true; // Stop if one front is desired @@ -282,16 +326,63 @@ _UpdateCollisions( const TVertex& a, const TVertex& b ) } // ------------------------------------------------------------------------- -template< class V, class C, class R, class B > -bool fpa::Base::Algorithm< V, C, R, B >:: +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 B > -void fpa::Base::Algorithm< V, C, R, B >:: +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 ); + + } // fi + return( vIt->second ); +} + +// ------------------------------------------------------------------------- +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 +{ + 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( ) +{ + 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 ) +{ + 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( ) { this->_QueueClear( ); @@ -301,8 +392,8 @@ _InitQueue( ) sIt++ ) { - this->_QueuePush( *sIt ); - this->_Mark( *sIt ); + this->_QueuePush( sIt->first, sIt->second ); + this->_Mark( sIt->first, sIt->second ); } // rof }