RS_Dijkstra.h

ファイルコンテンツ

// 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