COIN-OR::LEMON - Graph Library

Changeset 1119:d3504fc075dc in lemon-0.x for src


Ignore:
Timestamp:
02/03/05 17:08:56 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1518
Message:

Two incomplete additions:

  • Exceptions
  • bool map indication reached nodes (NullMap? by default)
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/dijkstra.h

    r1117 r1119  
    2525#include <lemon/bin_heap.h>
    2626#include <lemon/invalid.h>
     27#include <lemon/error.h>
     28#include <lemon/maps.h>
    2729
    2830namespace lemon {
     31
     32
     33  class UninitializedData : public LogicError {};
     34
    2935
    3036/// \addtogroup flowalgs
     
    6874 
    6975    ///\todo Please document...
    70     ///
     76    ///\todo The graph alone may be insufficient for the initialization
    7177    static PredMap *createPredMap(const GR &G)
    7278    {
     
    8692    {
    8793      return new PredNodeMap(G);
     94    }
     95
     96    ///The type of the map that stores whether a nodes is reached.
     97 
     98    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     99    ///By default it is a NullMap.
     100    ///\todo If it is set to a real map, Dijkstra::reached() should read this.
     101    ///\todo named parameter to set this type, function to read and write.
     102    typedef NullMap<typename Graph::Node,bool> ReachedMap;
     103    ///Instantiates a ReachedMap.
     104 
     105    ///\todo Please document...
     106    ///
     107    static ReachedMap *createReachedMap(const GR &G)
     108    {
     109      return new ReachedMap();
    88110    }
    89111    ///The type of the map that stores the dists of the nodes.
     
    146168  class Dijkstra {
    147169  public:
     170    ///Exception thrown by dijkstra.
     171    class UninitializedData : public lemon::UninitializedData {};
     172
    148173    typedef TR Traits;
    149174    ///The type of the underlying graph.
     
    168193    ///nodes of the shortest paths.
    169194    typedef typename TR::PredNodeMap PredNodeMap;
     195    ///The type of the map indicating if a node is reached.
     196    typedef typename TR::ReachedMap ReachedMap;
    170197    ///The type of the map that stores the dists of the nodes.
    171198    typedef typename TR::DistMap DistMap;
     
    178205    const LengthMap *length;
    179206    ///Pointer to the map of predecessors edges.
    180     PredMap *predecessor;
    181     ///Indicates if \ref predecessor is locally allocated (\c true) or not.
    182     bool local_predecessor;
     207    PredMap *_pred;
     208    ///Indicates if \ref _pred is locally allocated (\c true) or not.
     209    bool local_pred;
    183210    ///Pointer to the map of predecessors nodes.
    184211    PredNodeMap *pred_node;
     
    189216    ///Indicates if \ref distance is locally allocated (\c true) or not.
    190217    bool local_distance;
     218    ///Pointer to the map of reached status of the nodes.
     219    ReachedMap *_reached;
     220    ///Indicates if \ref _reached is locally allocated (\c true) or not.
     221    bool local_reached;
    191222
    192223    ///The source node of the last execution.
     
    199230    void init_maps()
    200231    {
    201       if(!predecessor) {
    202         local_predecessor = true;
    203         predecessor = Traits::createPredMap(*G);
     232      if(!_pred) {
     233        local_pred = true;
     234        _pred = Traits::createPredMap(*G);
    204235      }
    205236      if(!pred_node) {
     
    210241        local_distance = true;
    211242        distance = Traits::createDistMap(*G);
     243      }
     244      if(!_reached) {
     245        local_reached = true;
     246        _reached = Traits::createReachedMap(*G);
    212247      }
    213248    }
     
    222257      static PredMap *createPredMap(const Graph &G)
    223258      {
    224         std::cerr << __FILE__ ":" << __LINE__ <<
    225           ": error: Special maps should be manually created" << std::endl;
    226         exit(1);
     259        throw UninitializedData();
    227260      }
    228261    };
     
    243276      static PredNodeMap *createPredNodeMap(const Graph &G)
    244277      {
    245         std::cerr << __FILE__ ":" << __LINE__ <<
    246           ": error: Special maps should be manually created" << std::endl;
    247         exit(1);
     278        throw UninitializedData();
    248279      }
    249280    };
     
    264295      static DistMap *createDistMap(const Graph &G)
    265296      {
    266         std::cerr << __FILE__ ":" << __LINE__ <<
    267           ": error: Special maps should be manually created" << std::endl;
    268         exit(1);
     297        throw UninitializedData();
    269298      }
    270299    };
     
    284313    Dijkstra(const Graph& _G, const LengthMap& _length) :
    285314      G(&_G), length(&_length),
    286       predecessor(NULL), local_predecessor(false),
     315      _pred(NULL), local_pred(false),
    287316      pred_node(NULL), local_pred_node(false),
    288       distance(NULL), local_distance(false)
     317      distance(NULL), local_distance(false),
     318      _reached(NULL), local_reached(false)
    289319    { }
    290320   
     
    292322    ~Dijkstra()
    293323    {
    294       if(local_predecessor) delete predecessor;
     324      if(local_pred) delete _pred;
    295325      if(local_pred_node) delete pred_node;
    296326      if(local_distance) delete distance;
     327      if(local_reached) delete _reached;
    297328    }
    298329
     
    316347    Dijkstra &predMap(PredMap &m)
    317348    {
    318       if(local_predecessor) {
    319         delete predecessor;
    320         local_predecessor=false;
    321       }
    322       predecessor = &m;
     349      if(local_pred) {
     350        delete _pred;
     351        local_pred=false;
     352      }
     353      _pred = &m;
    323354      return *this;
    324355    }
     
    374405     
    375406      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    376         predecessor->set(u,INVALID);
     407        _pred->set(u,INVALID);
    377408        pred_node->set(u,INVALID);
     409        ///\todo *_reached is not set to false.
    378410      }
    379411     
     
    387419       
    388420        Node v=heap.top();
     421        _reached->set(v,true);
    389422        Value oldvalue=heap[v];
    390423        heap.pop();
     
    397430          case Heap::PRE_HEAP:
    398431            heap.push(w,oldvalue+(*length)[e]);
    399             predecessor->set(w,e);
     432            _pred->set(w,e);
    400433            pred_node->set(w,v);
    401434            break;
     
    403436            if ( oldvalue+(*length)[e] < heap[w] ) {
    404437              heap.decrease(w, oldvalue+(*length)[e]);
    405               predecessor->set(w,e);
     438              _pred->set(w,e);
    406439              pred_node->set(w,v);
    407440            }
     
    432465    ///this function.
    433466    ///\todo predEdge could be a better name.
    434     Edge pred(Node v) const { return (*predecessor)[v]; }
     467    Edge pred(Node v) const { return (*_pred)[v]; }
    435468
    436469    ///Returns the 'previous node' of the shortest path tree.
     
    455488    ///shortest path tree.
    456489    ///\pre \ref run() must be called before using this function.
    457     const PredMap &predMap() const { return *predecessor;}
     490    const PredMap &predMap() const { return *_pred;}
    458491 
    459492    ///Returns a reference to the map of nodes of shortest paths.
     
    470503    ///\pre \ref run() must be called before using this function.
    471504    ///
    472     bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     505    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
    473506   
    474507  };
     
    514547    typedef TR Base;
    515548
    516     ///The type of the underlying graph.
     549    //The type of the underlying graph.
    517550    typedef typename TR::Graph Graph;
    518     ///\e
     551    //\e
    519552    typedef typename Graph::Node Node;
    520     ///\e
     553    //\e
    521554    typedef typename Graph::NodeIt NodeIt;
    522     ///\e
     555    //\e
    523556    typedef typename Graph::Edge Edge;
    524     ///\e
     557    //\e
    525558    typedef typename Graph::OutEdgeIt OutEdgeIt;
    526559   
    527     ///The type of the map that stores the edge lengths.
     560    //The type of the map that stores the edge lengths.
    528561    typedef typename TR::LengthMap LengthMap;
    529     ///The type of the length of the edges.
     562    //The type of the length of the edges.
    530563    typedef typename LengthMap::Value Value;
    531     ///\brief The type of the map that stores the last
    532     ///edges of the shortest paths.
     564    //\brief The type of the map that stores the last
     565    //edges of the shortest paths.
    533566    typedef typename TR::PredMap PredMap;
    534     ///\brief The type of the map that stores the last but one
    535     ///nodes of the shortest paths.
     567    //\brief The type of the map that stores the last but one
     568    //nodes of the shortest paths.
    536569    typedef typename TR::PredNodeMap PredNodeMap;
    537     ///The type of the map that stores the dists of the nodes.
     570    //The type of the map that stores the dists of the nodes.
    538571    typedef typename TR::DistMap DistMap;
    539572
    540     ///The heap type used by the dijkstra algorithm.
     573    //The heap type used by the dijkstra algorithm.
    541574    typedef typename TR::Heap Heap;
    542575public:
     
    553586    void run()
    554587    {
     588      if(_source==0) throw UninitializedData();
    555589      Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
    556590      if(_pred) Dij.predMap(*(PredMap*)_pred);
Note: See TracChangeset for help on using the changeset viewer.