1.1 --- a/src/hugo/dijkstra.h	Fri Jun 18 12:43:20 2004 +0000
     1.2 +++ b/src/hugo/dijkstra.h	Wed Jun 30 14:50:31 2004 +0000
     1.3 @@ -72,16 +72,129 @@
     1.4      typedef typename Graph::template NodeMap<ValueType> DistMap;
     1.5  
     1.6    private:
     1.7 -    const Graph& G;
     1.8 -    const LM& length;
     1.9 -    PredMap predecessor;
    1.10 -    PredNodeMap pred_node;
    1.11 -    DistMap distance;
    1.12 +    const Graph *G;
    1.13 +    const LM *length;
    1.14 +    //    bool local_length;
    1.15 +    PredMap *predecessor;
    1.16 +    bool local_predecessor;
    1.17 +    PredNodeMap *pred_node;
    1.18 +    bool local_pred_node;
    1.19 +    DistMap *distance;
    1.20 +    bool local_distance;
    1.21 +
    1.22 +    ///Initialize maps
    1.23 +    
    1.24 +    ///\todo Error if \c G or are \c NULL. What about \c length
    1.25 +    ///\todo Better memory allocation (instead of new).
    1.26 +    void init_maps() 
    1.27 +    {
    1.28 +//       if(!length) {
    1.29 +// 	local_length = true;
    1.30 +// 	length = new LM(G);
    1.31 +//       }
    1.32 +      if(!predecessor) {
    1.33 +	local_predecessor = true;
    1.34 +	predecessor = new PredMap(*G);
    1.35 +      }
    1.36 +      if(!pred_node) {
    1.37 +	local_pred_node = true;
    1.38 +	pred_node = new PredNodeMap(*G);
    1.39 +      }
    1.40 +      if(!distance) {
    1.41 +	local_distance = true;
    1.42 +	distance = new DistMap(*G);
    1.43 +      }
    1.44 +    }
    1.45      
    1.46    public :
    1.47      
    1.48      Dijkstra(const Graph& _G, const LM& _length) :
    1.49 -      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    1.50 +      G(&_G), length(&_length),
    1.51 +      predecessor(NULL), pred_node(NULL), distance(NULL),
    1.52 +      local_predecessor(false), local_pred_node(false), local_distance(false)
    1.53 +    { }
    1.54 +    
    1.55 +    ~Dijkstra() 
    1.56 +    {
    1.57 +      //      if(local_length) delete length;
    1.58 +      if(local_predecessor) delete predecessor;
    1.59 +      if(local_pred_node) delete pred_node;
    1.60 +      if(local_distance) delete distance;
    1.61 +    }
    1.62 +
    1.63 +    ///Sets the graph the algorithm will run on.
    1.64 +
    1.65 +    ///Sets the graph the algorithm will run on.
    1.66 +    ///\return <tt> (*this) </tt>
    1.67 +    Dijkstra &setGraph(const Graph &_G) 
    1.68 +    {
    1.69 +      G = &_G;
    1.70 +      return *this;
    1.71 +    }
    1.72 +    ///Sets the length map.
    1.73 +
    1.74 +    ///Sets the length map.
    1.75 +    ///\return <tt> (*this) </tt>
    1.76 +    Dijkstra &setLengthMap(const LM &m) 
    1.77 +    {
    1.78 +//       if(local_length) {
    1.79 +// 	delete length;
    1.80 +// 	local_length=false;
    1.81 +//       }
    1.82 +      length = &m;
    1.83 +      return *this;
    1.84 +    }
    1.85 +
    1.86 +    ///Sets the map storing the predecessor edges.
    1.87 +
    1.88 +    ///Sets the map storing the predecessor edges.
    1.89 +    ///If you don't use this function before calling \ref run(),
    1.90 +    ///it will allocate one. The destuctor deallocates this
    1.91 +    ///automatically allocated map, of course.
    1.92 +    ///\return <tt> (*this) </tt>
    1.93 +    Dijkstra &setPredMap(PredMap &m) 
    1.94 +    {
    1.95 +      if(local_predecessor) {
    1.96 +	delete predecessor;
    1.97 +	local_predecessor=false;
    1.98 +      }
    1.99 +      predecessor = &m;
   1.100 +      return *this;
   1.101 +    }
   1.102 +
   1.103 +    ///Sets the map storing the predecessor nodes.
   1.104 +
   1.105 +    ///Sets the map storing the predecessor nodes.
   1.106 +    ///If you don't use this function before calling \ref run(),
   1.107 +    ///it will allocate one. The destuctor deallocates this
   1.108 +    ///automatically allocated map, of course.
   1.109 +    ///\return <tt> (*this) </tt>
   1.110 +    Dijkstra &setPredNodeMap(PredNodeMap &m) 
   1.111 +    {
   1.112 +      if(local_pred_node) {
   1.113 +	delete pred_node;
   1.114 +	local_pred_node=false;
   1.115 +      }
   1.116 +      pred_node = &m;
   1.117 +      return *this;
   1.118 +    }
   1.119 +
   1.120 +    ///Sets the map storing the distances calculated by the algorithm.
   1.121 +
   1.122 +    ///Sets the map storing the distances calculated by the algorithm.
   1.123 +    ///If you don't use this function before calling \ref run(),
   1.124 +    ///it will allocate one. The destuctor deallocates this
   1.125 +    ///automatically allocated map, of course.
   1.126 +    ///\return <tt> (*this) </tt>
   1.127 +    Dijkstra &setDistMap(DistMap &m) 
   1.128 +    {
   1.129 +      if(local_distance) {
   1.130 +	delete distance;
   1.131 +	local_distance=false;
   1.132 +      }
   1.133 +      distance = &m;
   1.134 +      return *this;
   1.135 +    }
   1.136      
   1.137      void run(Node s);
   1.138      
   1.139 @@ -91,17 +204,18 @@
   1.140      ///\pre \ref run() must be called before using this function.
   1.141      ///\warning If node \c v in unreachable from the root the return value
   1.142      ///of this funcion is undefined.
   1.143 -    ValueType dist(Node v) const { return distance[v]; }
   1.144 +    ValueType dist(Node v) const { return (*distance)[v]; }
   1.145  
   1.146      ///Returns the 'previous edge' of the shortest path tree.
   1.147  
   1.148      ///For a node \c v it returns the 'previous edge' of the shortest path tree,
   1.149      ///i.e. it returns the last edge from a shortest path from the root to \c
   1.150 -    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
   1.151 +    ///v. It is \ref INVALID
   1.152 +    ///if \c v is unreachable from the root or if \c v=s. The
   1.153      ///shortest path tree used here is equal to the shortest path tree used in
   1.154      ///\ref predNode(Node v).  \pre \ref run() must be called before using
   1.155      ///this function.
   1.156 -    Edge pred(Node v) const { return predecessor[v]; }
   1.157 +    Edge pred(Node v) const { return (*predecessor)[v]; }
   1.158  
   1.159      ///Returns the 'previous node' of the shortest path tree.
   1.160  
   1.161 @@ -111,27 +225,27 @@
   1.162      ///\c v=s. The shortest path tree used here is equal to the shortest path
   1.163      ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
   1.164      ///using this function.
   1.165 -    Node predNode(Node v) const { return pred_node[v]; }
   1.166 +    Node predNode(Node v) const { return (*pred_node)[v]; }
   1.167      
   1.168      ///Returns a reference to the NodeMap of distances.
   1.169  
   1.170      ///Returns a reference to the NodeMap of distances. \pre \ref run() must
   1.171      ///be called before using this function.
   1.172 -    const DistMap &distMap() const { return distance;}
   1.173 +    const DistMap &distMap() const { return *distance;}
   1.174   
   1.175      ///Returns a reference to the shortest path tree map.
   1.176  
   1.177      ///Returns a reference to the NodeMap of the edges of the
   1.178      ///shortest path tree.
   1.179      ///\pre \ref run() must be called before using this function.
   1.180 -    const PredMap &predMap() const { return predecessor;}
   1.181 +    const PredMap &predMap() const { return *predecessor;}
   1.182   
   1.183      ///Returns a reference to the map of nodes of shortest paths.
   1.184  
   1.185      ///Returns a reference to the NodeMap of the last but one nodes of the
   1.186      ///shortest path tree.
   1.187      ///\pre \ref run() must be called before using this function.
   1.188 -    const PredNodeMap &predNodeMap() const { return pred_node;}
   1.189 +    const PredNodeMap &predNodeMap() const { return *pred_node;}
   1.190  
   1.191      ///Checks if a node is reachable from the root.
   1.192  
   1.193 @@ -140,7 +254,7 @@
   1.194      ///\todo Is this what we want?
   1.195      ///\pre \ref run() must be called before using this function.
   1.196      ///
   1.197 -    bool reached(Node v) { return G.valid(predecessor[v]); }
   1.198 +    bool reached(Node v) { return G->valid((*predecessor)[v]); }
   1.199      
   1.200    };
   1.201    
   1.202 @@ -160,14 +274,15 @@
   1.203    template <typename GR, typename LM,
   1.204  	    template<class,class,class,class> class Heap >
   1.205    void Dijkstra<GR,LM,Heap>::run(Node s) {
   1.206 -    
   1.207 -    NodeIt u;
   1.208 -    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
   1.209 -      predecessor.set(u,INVALID);
   1.210 -      pred_node.set(u,INVALID);
   1.211 +
   1.212 +    init_maps();
   1.213 +
   1.214 +    for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
   1.215 +      predecessor->set(u,INVALID);
   1.216 +      pred_node->set(u,INVALID);
   1.217      }
   1.218      
   1.219 -    typename GR::template NodeMap<int> heap_map(G,-1);
   1.220 +    typename GR::template NodeMap<int> heap_map(*G,-1);
   1.221      
   1.222      typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
   1.223        std::less<ValueType> > 
   1.224 @@ -182,32 +297,29 @@
   1.225  	Node v=heap.top(); 
   1.226  	ValueType oldvalue=heap[v];
   1.227  	heap.pop();
   1.228 -	distance.set(v, oldvalue);
   1.229 +	distance->set(v, oldvalue);
   1.230  	
   1.231 -	{ //FIXME this bracket is for e to be local
   1.232 -	  OutEdgeIt e;
   1.233 -	for(G.first(e, v);
   1.234 -	    G.valid(e); G.next(e)) {
   1.235 -	  Node w=G.bNode(e); 
   1.236 +	  
   1.237 +	for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
   1.238 +	  Node w=G->bNode(e); 
   1.239  	  
   1.240  	  switch(heap.state(w)) {
   1.241  	  case HeapType::PRE_HEAP:
   1.242 -	    heap.push(w,oldvalue+length[e]); 
   1.243 -	    predecessor.set(w,e);
   1.244 -	    pred_node.set(w,v);
   1.245 +	    heap.push(w,oldvalue+(*length)[e]); 
   1.246 +	    predecessor->set(w,e);
   1.247 +	    pred_node->set(w,v);
   1.248  	    break;
   1.249  	  case HeapType::IN_HEAP:
   1.250 -	    if ( oldvalue+length[e] < heap[w] ) {
   1.251 -	      heap.decrease(w, oldvalue+length[e]); 
   1.252 -	      predecessor.set(w,e);
   1.253 -	      pred_node.set(w,v);
   1.254 +	    if ( oldvalue+(*length)[e] < heap[w] ) {
   1.255 +	      heap.decrease(w, oldvalue+(*length)[e]); 
   1.256 +	      predecessor->set(w,e);
   1.257 +	      pred_node->set(w,v);
   1.258  	    }
   1.259  	    break;
   1.260  	  case HeapType::POST_HEAP:
   1.261  	    break;
   1.262  	  }
   1.263  	}
   1.264 -      } //FIXME tis bracket
   1.265        }
   1.266    }
   1.267