RS_Dijkstra.h
Dijkstra's algorithm の実装
RS_Dijkstra.h
—
C header,
10 kB (10355 bytes)
ファイルコンテンツ
// This may look like C code, but it is really -*- C++ -*- // RTSS --- Railway Total System Simulator // (c) TAKAGI Ryo (at Kogakuin University) // RS_Dijkstra.h --- class RS_Dijkstra and related classes, solving the // shortest paths problem. // ----- // ChangeLog: // 2009. 10. 16 // The "directed graph" version complete. // ----- // ---- // Dijkstra's algorithm // ダイクストラ法 // ---- #ifndef RS_DIJKSTRA_H #define RS_DIJKSTRA_H #include <map> #include <iostream> #include <vector> #include "RS_FHeap.h" using std :: cerr ; using std :: endl ; using std :: vector ; using std :: map ; using std :: ostream ; using std :: string ; // ---- // Forward declarations // ---- template < class KC , class NID > class RS_DKBranch ; template < class KC , class NID > class RS_DKNode ; template < class KD , class NIX > std :: ostream & operator<< ( std :: ostream & ostr , const RS_DKNode < KD , NIX > & dkn ) ; // ---- // Dijkstra's Algorithm: the "node" of the graph // ダイクストラのアルゴリズム: グラフの「ノード」 // ---- template < class KC , class NID > class RS_DKNode { template < class KD , class NIX > friend std :: ostream & operator<< ( std :: ostream & ostr , const RS_DKNode < KD , NIX > & dkn ) ; private : string _name ; NID _nid ; typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * _heapent ; RS_DKBranch < KC , NID > * _dkb_in ; // ---- // Note: _blist_in contains branches coming into the node. Therefore, they // must have this node as "_n_out". Vice versa for _blist_out. // 注意: _blist_in はこのノードに「入ってくる」ブランチを保有する。従って, // このノードはそのブランチの _n_out となる。_blist_out はその逆。 // ---- vector < RS_DKBranch < KC , NID > * > _blist_in ; vector < RS_DKBranch < KC , NID > * > _blist_out ; mutable typename vector < RS_DKBranch < KC , NID > * > :: size_type _iter ; mutable bool _iter_to_start ; bool _marked ; bool _initial ; explicit RS_DKNode ( const RS_DKNode < KC , NID > & ) ; public : explicit RS_DKNode ( const NID & _nid_in , const string & _n_in ) : _nid ( _nid_in ) , _name ( _n_in ) , _heapent ( 0 ) , _dkb_in ( 0 ) , _blist_in () , _blist_out () , _iter ( 0 ) , _iter_to_start ( true ) , _marked ( false ) , _initial ( false ) {} void setHeapEntry ( typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * x ) { _heapent = x ; } // ---- // Functions setting branches in the graph initialisation process. // グラフの初期化プロセスにおいてブランチをセットする関数. // ---- void setIncomingBranch ( RS_DKBranch < KC , NID > * x ) { _blist_in . push_back ( x ) ; } void setOutgoingBranch ( RS_DKBranch < KC , NID > * x ) { _blist_out . push_back ( x ) ; } // ---- // Setting current incoming path, used to follow the shortest path tree. // 現在の最短経路が「入ってくる」ブランチ。最短経路木探索のため用いられる。 // ---- void setIncomingPath ( RS_DKBranch < KC , NID > * x ) { _dkb_in = x ; } void setAsMarked () { _marked = true ; } // ---- // Set as initial node // 始点ノードとセット // ---- void setAsInitial () { _initial = true ; } typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * getHeapEntry () const { return _heapent ; } RS_DKBranch < KC , NID > * getIncomingPath () const { return _dkb_in ; } const NID & getNodeID () const { return _nid ; } const string & getName () const { return _name ; } bool isMarked () const { return _marked ; } bool isUnreachable () const { return ! ( _initial || _dkb_in ) ; } RS_DKBranch < KC , NID > * getNextBranch () const { while ( true ) { if ( _iter_to_start ) { _iter_to_start = false ; } else { ++ _iter ; } if ( _iter >= _blist_out . size () ) return 0 ; if ( _blist_out [ _iter ] == _dkb_in ) { continue ; } return _blist_out [ _iter ] ; } } } ; template < class KD , class NIX > ostream & operator<< ( ostream & ostr , const RS_DKNode < KD , NIX > & dkn ) { ostr << dkn . getName () ; return ostr ; } // ---- // Declaration of template class RS_DKBranch // RS_DKBranch テンプレートクラスの宣言 // ---- template < class KC , class NID > class RS_DKBranch { private : KC _weight ; // ---- // Direction: in -> out. Node _n_in must have this branch in its // _blist_out. Node _n_out must have this branch in its _blist_in. // 方向: in -> out. このブランチは _n_in ノードの _blist_out に,そして // _n_out ノードの _blist_in に,それぞれ含まれなければならない。 // ---- RS_DKNode < KC , NID > * _n_in ; RS_DKNode < KC , NID > * _n_out ; public : explicit RS_DKBranch ( RS_DKNode < KC , NID > * _in , RS_DKNode < KC , NID > * _out , KC x ) : _weight ( x ) , _n_in ( _in ) , _n_out ( _out ) { _in -> setOutgoingBranch ( this ) ; _out -> setIncomingBranch ( this ) ; } RS_DKNode < KC , NID > * getOpposite ( RS_DKNode < KC , NID > * x ) { if ( _n_in == x ) return _n_out ; if ( _n_out == x ) return _n_in ; cerr << "Error: could not find opposite node" << endl ; exit ( 1 ) ; } const KC & getWeight () const { return _weight ; } } ; // ---- // Declaration of template class RS_Dijkstra // RS_Dijkstra テンプレートクラスの宣言 // ---- template < class KC , class NID > class RS_Dijkstra { // "Large number" for initialising a node. KC _large ; // Heap RS_FHeap < KC , RS_DKNode < KC , NID > > _hp ; // Vector container of RS_DKNode object instances // *** May have to consider using map container instead of vector *** map < const NID , RS_DKNode < KC , NID > * > _nlist ; // Vector container of RS_DKBranch object instances // *** May have to consider using map container instead of vector *** vector < RS_DKBranch < KC , NID > * > _blist ; public : explicit RS_Dijkstra ( const KC & _l_in ) : _large ( _l_in ) , _hp () , _nlist () , _blist () { } ~RS_Dijkstra () { for ( typename vector < RS_DKBranch < KC , NID > * > :: iterator ii = _blist . begin () ; ii != _blist . end () ; ++ ii ) { delete ( * ii ) ; } for ( typename map < const NID , RS_DKNode < KC , NID > * > :: iterator ii = _nlist . begin () ; ii != _nlist . end () ; ++ ii ) { typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * iix = ii -> second -> getHeapEntry () ; delete iix ; delete ii -> second ; } } void setNode ( const NID & _n_in ) { RS_DKNode < KC , NID > * _n = new RS_DKNode < KC , NID > ( _n_in , _n_in ) ; _nlist [ _n_in ] = _n ; typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * _e = new typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry ( _large , _n , & _hp ) ; _n -> setHeapEntry ( _e ) ; _hp . insert ( _e ) ; } RS_DKNode < KC , NID > * getNode ( const NID & _n_in ) { typename map < const NID , RS_DKNode < KC , NID > * > :: iterator _i_x = _nlist . find ( _n_in ) ; if ( _i_x == _nlist . end () ) { cerr << "Error: no node with ID \"" << _n_in << "\" in class RS_Dijkstra" << endl ; exit ( 1 ) ; } return _i_x -> second ; } void setBranch ( const NID & _nn_f , const NID & _nn_t , const KC & _wt ) { RS_DKNode < KC , NID > * _n_f = getNode ( _nn_f ) ; RS_DKNode < KC , NID > * _n_t = getNode ( _nn_t ) ; RS_DKBranch < KC , NID > * _b = new RS_DKBranch < KC , NID > ( _n_f , _n_t , _wt ) ; _blist . push_back ( _b ) ; } void setBidirectionalBranches ( const NID & _nn_f , const NID & _nn_t , const KC & _wt ) { setBranch ( _nn_f , _nn_t , _wt ) ; setBranch ( _nn_t , _nn_f , _wt ) ; } void run ( const NID & _start_nid ) { cerr << "Dijkstra's Algorithm: starting from node \"" << _start_nid << "\"" << endl ; RS_DKNode < KC , NID > * _n_st = getNode ( _start_nid ) ; _n_st -> setAsInitial () ; _n_st -> getHeapEntry () -> decreaseKey ( 0 ) ; typename RS_FHeap < KC , RS_DKNode < KC , NID > > :: Entry * _min = _hp . deleteMinimum () ; _min -> getEntryData () -> setAsMarked () ; cerr << "delete min, node = " << _min -> getEntryData () -> getName () << ", key = " << _min -> getKey () << endl ; while ( _hp . size () ) { while ( RS_DKBranch < KC , NID > * _bx = _min -> getEntryData () -> getNextBranch () ) { RS_DKNode < KC , NID > * _op = _bx -> getOpposite ( _min -> getEntryData () ) ; if ( _op -> isMarked () ) { continue ; } KC _nkey = _min -> getKey () + _bx -> getWeight () ; cerr << "decrease key, node = " << _op -> getName () << ", key " << _op -> getHeapEntry () -> getKey () << " -> " << _nkey ; if ( _nkey < _op -> getHeapEntry () -> getKey () ) { cerr << ", perform" << endl ; _op -> getHeapEntry () -> decreaseKey ( _nkey ) ; _op -> setIncomingPath ( _bx ) ; } else { cerr << ", not perform" << endl ; } } _min = _hp . deleteMinimum () ; _min -> getEntryData () -> setAsMarked () ; cerr << "delete min, node = " << _min -> getEntryData () -> getName () << ", key = " << _min -> getKey () << endl ; } for ( typename map < const NID , RS_DKNode < KC , NID > * > :: const_iterator ii = _nlist . begin () ; ii != _nlist . end () ; ++ ii ) { RS_DKNode < KC , NID > * _n = ii -> second ; cerr << "Node \"" << _n -> getName () << "\": " ; if ( _n -> isUnreachable () ) { cerr << "unreachable" << endl ; continue ; } cerr << _n -> getHeapEntry () -> getKey () << ": " << _n -> getName () ; while ( RS_DKBranch < KC , NID > * _bi = _n -> getIncomingPath () ) { cerr << "(" << _bi -> getWeight () << ")" ; _n = _bi -> getOpposite ( _n ) ; cerr << _n -> getName () ; } cerr << endl ; } } } ; #endif // RS_DIJKSTRA_H