COIN-OR::LEMON - Graph Library

Changeset 247:fefccf1bdc23 in lemon-0.x


Ignore:
Timestamp:
03/26/04 15:03:02 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@347
Message:

Heap is now a template-template parameter

Location:
src/work/alpar/dijkstra
Files:
2 edited

Legend:

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

    r222 r247  
    3030  //double pre_time=currTime();
    3131  tim.reset();
    32   Dijkstra <SmartGraph,
    33     SmartGraph::EdgeMap<int>,
    34     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
    35     > dijkstra_test(G, cap);
     32//   Dijkstra <SmartGraph,
     33//     SmartGraph::EdgeMap<int>,
     34//     FibHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> >
     35//     > dijkstra_test(G, cap);
     36 
     37  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, FibHeap >
     38    dijkstra_test(G, cap);
    3639 
    3740  dijkstra_test.run(s);
     
    4548  //pre_time=currTime();
    4649  tim.reset();
    47   Dijkstra < SmartGraph,
    48     SmartGraph::EdgeMap<int>,
    49     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
    50     dijkstra_test2(G, cap);
     50//   Dijkstra < SmartGraph,
     51//     SmartGraph::EdgeMap<int>,
     52//     BinHeap<SmartGraph::Node, int, SmartGraph::NodeMap<int> > >
     53//     dijkstra_test2(G, cap);
     54 
     55  Dijkstra <SmartGraph, SmartGraph::EdgeMap<int>, BinHeap >
     56    dijkstra_test2(G, cap);
    5157 
    5258  dijkstra_test2.run(s);
  • src/work/alpar/dijkstra/dijkstra.h

    r242 r247  
    6969  template <typename Graph,
    7070            typename LengthMap=typename Graph::EdgeMap<int>,
    71             typename Heap=BinHeap <typename Graph::Node,
    72                                    typename LengthMap::ValueType,
    73                                    typename Graph::NodeMap<int> > >
     71            template <class,class,class> class Heap = BinHeap >
     72//          typename Heap=BinHeap <typename Graph::Node,
     73//                                 typename LengthMap::ValueType,
     74//                                 typename Graph::NodeMap<int> > >
    7475#endif
    7576  class Dijkstra{
     
    105106      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
    106107   
    107 
    108108    void run(Node s);
    109109   
     
    174174  ///- The shortest path tree.
    175175  ///- The distance of each node from the source.
    176   template <typename Graph, typename LengthMap, typename Heap >
     176  template <typename Graph, typename LengthMap,
     177            template<class,class,class> class Heap >
    177178  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
    178179   
     
    192193    typename Graph::NodeMap<int> heap_map(G,-1);
    193194   
    194     Heap heap(heap_map);
     195    //Heap heap(heap_map);
     196    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
    195197   
    196198    heap.push(s,0);
     
    208210         
    209211          switch(heap.state(w)) {
    210           case Heap::PRE_HEAP:
     212          case heap.PRE_HEAP:
    211213            //      reach.set(w,true);
    212214            heap.push(w,oldvalue+length[e]);
     
    214216            pred_node.set(w,v);
    215217            break;
    216           case Heap::IN_HEAP:
     218          case heap.IN_HEAP:
    217219            if ( oldvalue+length[e] < heap[w] ) {
    218220              heap.decrease(w, oldvalue+length[e]);
     
    221223            }
    222224            break;
    223           case Heap::POST_HEAP:
     225          case heap.POST_HEAP:
    224226            break;
    225227          }
Note: See TracChangeset for help on using the changeset viewer.