COIN-OR::LEMON - Graph Library

Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/dijkstra.h


Ignore:
Timestamp:
10/26/05 12:50:47 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269
Message:

Some modifications on shortest path algoritms:

  • heap traits
  • checked execution
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r1734 r1741  
    6262    /// \param G is the graph, to which we would like to define the
    6363    /// HeapCrossRef.
    64     /// \todo The graph alone may be insufficient for the initialization
    6564    static HeapCrossRef *createHeapCrossRef(const GR &G)
    6665    {
     
    7574    ///\sa Dijkstra
    7675    typedef BinHeap<typename Graph::Node, typename LM::Value,
    77                     typename GR::template NodeMap<int>,
    78                     std::less<Value> > Heap;
     76                    HeapCrossRef, std::less<Value> > Heap;
    7977
    8078    static Heap *createHeap(HeapCrossRef& R)
     
    361359      typedef CR HeapCrossRef;
    362360      typedef H Heap;
    363       static HeapCrossRef *createHeapCrossRef(const Graph &G) {
    364         return new HeapCrossRef(G);
    365       }
    366       static Heap *createHeap(HeapCrossRef &R)
     361      static HeapCrossRef *createHeapCrossRef(const Graph &) {
     362        throw UninitializedParameter();
     363      }
     364      static Heap *createHeap(HeapCrossRef &)
    367365      {
    368         return new Heap(R);
     366        throw UninitializedParameter();
    369367      }
    370368    };
     
    379377      : public Dijkstra< Graph, LengthMap, DefHeapTraits<H, CR> > {
    380378      typedef Dijkstra< Graph,  LengthMap, DefHeapTraits<H, CR> > Create;
     379    };
     380
     381    template <class H, class CR>
     382    struct DefStandardHeapTraits : public Traits {
     383      typedef CR HeapCrossRef;
     384      typedef H Heap;
     385      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
     386        return new HeapCrossRef(G);
     387      }
     388      static Heap *createHeap(HeapCrossRef &R)
     389      {
     390        return new Heap(R);
     391      }
     392    };
     393    ///\ref named-templ-param "Named parameter" for setting heap and cross
     394    ///reference type with automatic allocation
     395
     396    ///\ref named-templ-param "Named parameter" for setting heap and cross
     397    ///reference type. It can allocate the heap and the cross reference
     398    ///object if the cross reference's constructor waits for the graph as
     399    ///parameter and the heap's constructor waits for the cross reference.
     400    template <class H, class CR = typename Graph::template NodeMap<int> >
     401    struct DefStandardHeap
     402      : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
     403      typedef Dijkstra< Graph,  LengthMap, DefStandardHeapTraits<H, CR> >
     404      Create;
    381405    };
    382406   
     
    454478      }
    455479      _dist = &m;
     480      return *this;
     481    }
     482
     483    ///Sets the heap and the cross reference used by algorithm.
     484
     485    ///Sets the heap and the cross reference used by algorithm.
     486    ///If you don't use this function before calling \ref run(),
     487    ///it will allocate one. The destuctor deallocates this
     488    ///automatically allocated map, of course.
     489    ///\return <tt> (*this) </tt>
     490    Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
     491    {
     492      if(local_heap_cross_ref) {
     493        delete _heap_cross_ref;
     494        local_heap_cross_ref=false;
     495      }
     496      _heap_cross_ref = &crossRef;
     497      if(local_heap) {
     498        delete _heap;
     499        local_heap=false;
     500      }
     501      _heap = &heap;
    456502      return *this;
    457503    }
Note: See TracChangeset for help on using the changeset viewer.