COIN-OR::LEMON - Graph Library

Changeset 688:bdc429a557f2 in lemon-0.x for src


Ignore:
Timestamp:
06/30/04 16:50:31 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@938
Message:
  • Now, it is possible to have Dijkstra store its result directly in given maps.
  • More docs.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/dijkstra.h

    r584 r688  
    7373
    7474  private:
    75     const Graph& G;
    76     const LM& length;
    77     PredMap predecessor;
    78     PredNodeMap pred_node;
    79     DistMap distance;
     75    const Graph *G;
     76    const LM *length;
     77    //    bool local_length;
     78    PredMap *predecessor;
     79    bool local_predecessor;
     80    PredNodeMap *pred_node;
     81    bool local_pred_node;
     82    DistMap *distance;
     83    bool local_distance;
     84
     85    ///Initialize maps
     86   
     87    ///\todo Error if \c G or are \c NULL. What about \c length
     88    ///\todo Better memory allocation (instead of new).
     89    void init_maps()
     90    {
     91//       if(!length) {
     92//      local_length = true;
     93//      length = new LM(G);
     94//       }
     95      if(!predecessor) {
     96        local_predecessor = true;
     97        predecessor = new PredMap(*G);
     98      }
     99      if(!pred_node) {
     100        local_pred_node = true;
     101        pred_node = new PredNodeMap(*G);
     102      }
     103      if(!distance) {
     104        local_distance = true;
     105        distance = new DistMap(*G);
     106      }
     107    }
    80108   
    81109  public :
    82110   
    83111    Dijkstra(const Graph& _G, const LM& _length) :
    84       G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
     112      G(&_G), length(&_length),
     113      predecessor(NULL), pred_node(NULL), distance(NULL),
     114      local_predecessor(false), local_pred_node(false), local_distance(false)
     115    { }
     116   
     117    ~Dijkstra()
     118    {
     119      //      if(local_length) delete length;
     120      if(local_predecessor) delete predecessor;
     121      if(local_pred_node) delete pred_node;
     122      if(local_distance) delete distance;
     123    }
     124
     125    ///Sets the graph the algorithm will run on.
     126
     127    ///Sets the graph the algorithm will run on.
     128    ///\return <tt> (*this) </tt>
     129    Dijkstra &setGraph(const Graph &_G)
     130    {
     131      G = &_G;
     132      return *this;
     133    }
     134    ///Sets the length map.
     135
     136    ///Sets the length map.
     137    ///\return <tt> (*this) </tt>
     138    Dijkstra &setLengthMap(const LM &m)
     139    {
     140//       if(local_length) {
     141//      delete length;
     142//      local_length=false;
     143//       }
     144      length = &m;
     145      return *this;
     146    }
     147
     148    ///Sets the map storing the predecessor edges.
     149
     150    ///Sets the map storing the predecessor edges.
     151    ///If you don't use this function before calling \ref run(),
     152    ///it will allocate one. The destuctor deallocates this
     153    ///automatically allocated map, of course.
     154    ///\return <tt> (*this) </tt>
     155    Dijkstra &setPredMap(PredMap &m)
     156    {
     157      if(local_predecessor) {
     158        delete predecessor;
     159        local_predecessor=false;
     160      }
     161      predecessor = &m;
     162      return *this;
     163    }
     164
     165    ///Sets the map storing the predecessor nodes.
     166
     167    ///Sets the map storing the predecessor nodes.
     168    ///If you don't use this function before calling \ref run(),
     169    ///it will allocate one. The destuctor deallocates this
     170    ///automatically allocated map, of course.
     171    ///\return <tt> (*this) </tt>
     172    Dijkstra &setPredNodeMap(PredNodeMap &m)
     173    {
     174      if(local_pred_node) {
     175        delete pred_node;
     176        local_pred_node=false;
     177      }
     178      pred_node = &m;
     179      return *this;
     180    }
     181
     182    ///Sets the map storing the distances calculated by the algorithm.
     183
     184    ///Sets the map storing the distances calculated by the algorithm.
     185    ///If you don't use this function before calling \ref run(),
     186    ///it will allocate one. The destuctor deallocates this
     187    ///automatically allocated map, of course.
     188    ///\return <tt> (*this) </tt>
     189    Dijkstra &setDistMap(DistMap &m)
     190    {
     191      if(local_distance) {
     192        delete distance;
     193        local_distance=false;
     194      }
     195      distance = &m;
     196      return *this;
     197    }
    85198   
    86199    void run(Node s);
     
    92205    ///\warning If node \c v in unreachable from the root the return value
    93206    ///of this funcion is undefined.
    94     ValueType dist(Node v) const { return distance[v]; }
     207    ValueType dist(Node v) const { return (*distance)[v]; }
    95208
    96209    ///Returns the 'previous edge' of the shortest path tree.
     
    98211    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
    99212    ///i.e. it returns the last edge from a shortest path from the root to \c
    100     ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
     213    ///v. It is \ref INVALID
     214    ///if \c v is unreachable from the root or if \c v=s. The
    101215    ///shortest path tree used here is equal to the shortest path tree used in
    102216    ///\ref predNode(Node v).  \pre \ref run() must be called before using
    103217    ///this function.
    104     Edge pred(Node v) const { return predecessor[v]; }
     218    Edge pred(Node v) const { return (*predecessor)[v]; }
    105219
    106220    ///Returns the 'previous node' of the shortest path tree.
     
    112226    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
    113227    ///using this function.
    114     Node predNode(Node v) const { return pred_node[v]; }
     228    Node predNode(Node v) const { return (*pred_node)[v]; }
    115229   
    116230    ///Returns a reference to the NodeMap of distances.
     
    118232    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    119233    ///be called before using this function.
    120     const DistMap &distMap() const { return distance;}
     234    const DistMap &distMap() const { return *distance;}
    121235 
    122236    ///Returns a reference to the shortest path tree map.
     
    125239    ///shortest path tree.
    126240    ///\pre \ref run() must be called before using this function.
    127     const PredMap &predMap() const { return predecessor;}
     241    const PredMap &predMap() const { return *predecessor;}
    128242 
    129243    ///Returns a reference to the map of nodes of shortest paths.
     
    132246    ///shortest path tree.
    133247    ///\pre \ref run() must be called before using this function.
    134     const PredNodeMap &predNodeMap() const { return pred_node;}
     248    const PredNodeMap &predNodeMap() const { return *pred_node;}
    135249
    136250    ///Checks if a node is reachable from the root.
     
    141255    ///\pre \ref run() must be called before using this function.
    142256    ///
    143     bool reached(Node v) { return G.valid(predecessor[v]); }
     257    bool reached(Node v) { return G->valid((*predecessor)[v]); }
    144258   
    145259  };
     
    161275            template<class,class,class,class> class Heap >
    162276  void Dijkstra<GR,LM,Heap>::run(Node s) {
    163    
    164     NodeIt u;
    165     for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
    166       predecessor.set(u,INVALID);
    167       pred_node.set(u,INVALID);
    168     }
    169    
    170     typename GR::template NodeMap<int> heap_map(G,-1);
     277
     278    init_maps();
     279
     280    for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
     281      predecessor->set(u,INVALID);
     282      pred_node->set(u,INVALID);
     283    }
     284   
     285    typename GR::template NodeMap<int> heap_map(*G,-1);
    171286   
    172287    typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
     
    183298        ValueType oldvalue=heap[v];
    184299        heap.pop();
    185         distance.set(v, oldvalue);
     300        distance->set(v, oldvalue);
    186301       
    187         { //FIXME this bracket is for e to be local
    188           OutEdgeIt e;
    189         for(G.first(e, v);
    190             G.valid(e); G.next(e)) {
    191           Node w=G.bNode(e);
     302         
     303        for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
     304          Node w=G->bNode(e);
    192305         
    193306          switch(heap.state(w)) {
    194307          case HeapType::PRE_HEAP:
    195             heap.push(w,oldvalue+length[e]);
    196             predecessor.set(w,e);
    197             pred_node.set(w,v);
     308            heap.push(w,oldvalue+(*length)[e]);
     309            predecessor->set(w,e);
     310            pred_node->set(w,v);
    198311            break;
    199312          case HeapType::IN_HEAP:
    200             if ( oldvalue+length[e] < heap[w] ) {
    201               heap.decrease(w, oldvalue+length[e]);
    202               predecessor.set(w,e);
    203               pred_node.set(w,v);
     313            if ( oldvalue+(*length)[e] < heap[w] ) {
     314              heap.decrease(w, oldvalue+(*length)[e]);
     315              predecessor->set(w,e);
     316              pred_node->set(w,v);
    204317            }
    205318            break;
     
    208321          }
    209322        }
    210       } //FIXME tis bracket
    211323      }
    212324  }
Note: See TracChangeset for help on using the changeset viewer.