1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
2 #define __FPA__BASE__DIJKSTRA__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class R, class S, class VC, class MST, class B >
8 typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
9 TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
10 GetMinimumSpanningTree( )
13 dynamic_cast< TMinimumSpanningTree* >(
14 this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
19 // -------------------------------------------------------------------------
20 template< class V, class C, class R, class S, class VC, class MST, class B >
21 const typename fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
22 TMinimumSpanningTree* fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
23 GetMinimumSpanningTree( ) const
26 dynamic_cast< const TMinimumSpanningTree* >(
27 this->itk::ProcessObject::GetOutput( this->m_MSTIdx )
32 // -------------------------------------------------------------------------
33 template< class V, class C, class R, class S, class VC, class MST, class B >
34 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
35 GraftMinimumSpanningTree( itk::DataObject* obj )
37 TMinimumSpanningTree* mst = dynamic_cast< TMinimumSpanningTree* >( obj );
39 this->GraftNthOutput( this->m_MSTIdx, mst );
42 // -------------------------------------------------------------------------
43 template< class V, class C, class R, class S, class VC, class MST, class B >
44 fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
47 m_LocalCosts( false ),
48 m_FillNodeQueue( false )
50 this->m_MSTIdx = this->GetNumberOfRequiredOutputs( );
51 this->SetNumberOfRequiredOutputs( this->m_MSTIdx + 1 );
52 this->itk::ProcessObject::SetNthOutput(
53 this->m_MSTIdx, TMinimumSpanningTree::New( )
57 // -------------------------------------------------------------------------
58 template< class V, class C, class R, class S, class VC, class MST, class B >
59 fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
64 // -------------------------------------------------------------------------
65 template< class V, class C, class R, class S, class VC, class MST, class B >
66 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
67 _BeforeGenerateData( )
69 this->Superclass::_BeforeGenerateData( );
70 this->GetMinimumSpanningTree( )->SetFillNodeQueue( this->m_FillNodeQueue );
73 // -------------------------------------------------------------------------
74 template< class V, class C, class R, class S, class VC, class MST, class B >
75 bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
76 _ComputeNeighborResult(
77 TResult& result, const TVertex& neighbor, const TVertex& parent
80 result = this->_Cost( neighbor, parent );
81 result *= TResult( this->_Distance( neighbor, parent ) );
83 // WARNING: Dijkstra does not work on negative values!
84 if( result >= TResult( 0 ) )
86 _TNode pn = this->_Node( parent );
87 if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
95 // -------------------------------------------------------------------------
96 template< class V, class C, class R, class S, class VC, class MST, class B >
97 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
98 _SetResult( const TVertex& v, const _TNode& n )
100 this->GetMinimumSpanningTree( )->SetNode( v, n.Parent, n.FrontId, n.Result );
103 // -------------------------------------------------------------------------
104 template< class V, class C, class R, class S, class VC, class MST, class B >
105 bool fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
106 _IsQueueEmpty( ) const
108 return( this->m_Queue.empty( ) );
111 // -------------------------------------------------------------------------
112 template< class V, class C, class R, class S, class VC, class MST, class B >
113 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
114 _QueuePush( const TVertex& v, const _TNode& n )
119 this->m_Queue.push_back( qn );
120 std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
123 // -------------------------------------------------------------------------
124 template< class V, class C, class R, class S, class VC, class MST, class B >
125 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
126 _QueuePop( TVertex& v, _TNode& n )
128 _TQueueNode qn = this->m_Queue.front( );
129 std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
130 this->m_Queue.pop_back( );
135 // -------------------------------------------------------------------------
136 template< class V, class C, class R, class S, class VC, class MST, class B >
137 void fpa::Base::Dijkstra< V, C, R, S, VC, MST, B >::
140 this->m_Queue.clear( );
143 #endif // __FPA__BASE__DIJKSTRA__HXX__