COIN-OR::LEMON - Graph Library

Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/johnson.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/johnson.h

    r1723 r1741  
    107107    /// \see JohnsonDefaultOperationTraits
    108108    typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
     109
     110    /// The cross reference type used by heap.
     111
     112    /// The cross reference type used by heap.
     113    /// Usually it is \c Graph::NodeMap<int>.
     114    typedef typename Graph::template NodeMap<int> HeapCrossRef;
     115
     116    ///Instantiates a HeapCrossRef.
     117
     118    ///This function instantiates a \ref HeapCrossRef.
     119    /// \param graph is the graph, to which we would like to define the
     120    /// HeapCrossRef.
     121    static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
     122      return new HeapCrossRef(graph);
     123    }
     124   
     125    ///The heap type used by Dijkstra algorithm.
     126
     127    ///The heap type used by Dijkstra algorithm.
     128    ///
     129    ///\sa BinHeap
     130    ///\sa Dijkstra
     131    typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
     132                    HeapCrossRef, std::less<Value> > Heap;
     133
     134    ///Instantiates a Heap.
     135
     136    ///This function instantiates a \ref Heap.
     137    /// \param crossRef The cross reference for the heap.
     138    static Heap *createHeap(HeapCrossRef& crossRef) {
     139      return new Heap(crossRef);
     140    }
    109141 
    110142    /// \brief The type of the matrix map that stores the last edges of the
     
    122154    /// \param G is the graph, to which we would like to define the PredMap.
    123155    /// \todo The graph alone may be insufficient for the initialization
    124     static PredMap *createPredMap(const _Graph& graph) {
     156    static PredMap *createPredMap(const Graph& graph) {
    125157      return new PredMap(graph);
    126158    }
     
    159191  ///
    160192  /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
    161   /// with fibonacci heap O(n^2 * log(n) + n * e).
     193  /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
     194  /// implementation is slower than either binary heap implementation or the
     195  /// Floyd-Warshall algorithm.
    162196  ///
    163197  /// The type of the length is determined by the
     
    226260    /// \brief The operation traits.
    227261    typedef typename _Traits::OperationTraits OperationTraits;
     262    ///The cross reference type used for the current heap.
     263    typedef typename _Traits::HeapCrossRef HeapCrossRef;
     264    ///The heap type used by the dijkstra algorithm.
     265    typedef typename _Traits::Heap Heap;
    228266  private:
    229267    /// Pointer to the underlying graph.
     
    239277    ///Indicates if \ref _dist is locally allocated (\c true) or not.
    240278    bool local_dist;
     279    ///Pointer to the heap cross references.
     280    HeapCrossRef *_heap_cross_ref;
     281    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
     282    bool local_heap_cross_ref;
     283    ///Pointer to the heap.
     284    Heap *_heap;
     285    ///Indicates if \ref _heap is locally allocated (\c true) or not.
     286    bool local_heap;
    241287
    242288    /// Creates the maps if necessary.
     
    250296        _dist = Traits::createDistMap(*graph);
    251297      }
    252     }
    253    
     298      if (!_heap_cross_ref) {
     299        local_heap_cross_ref = true;
     300        _heap_cross_ref = Traits::createHeapCrossRef(*graph);
     301      }
     302      if (!_heap) {
     303        local_heap = true;
     304        _heap = Traits::createHeap(*_heap_cross_ref);
     305      }
     306    }
     307
    254308  public :
     309
     310    typedef Johnson Create;
    255311 
    256312    /// \name Named template parameters
     
    309365      typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
    310366    };
     367
     368    template <class H, class CR>
     369    struct DefHeapTraits : public Traits {
     370      typedef CR HeapCrossRef;
     371      typedef H Heap;
     372      static HeapCrossRef *createHeapCrossRef(const Graph &) {
     373        throw UninitializedParameter();
     374      }
     375      static Heap *createHeap(HeapCrossRef &)
     376      {
     377        throw UninitializedParameter();
     378      }
     379    };
     380    ///\ref named-templ-param "Named parameter" for setting heap and cross
     381    ///reference type
     382
     383    ///\ref named-templ-param "Named parameter" for setting heap and cross
     384    ///reference type
     385    ///
     386    template <class H, class CR = typename Graph::template NodeMap<int> >
     387    struct DefHeap
     388      : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > {
     389      typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
     390    };
     391
     392    template <class H, class CR>
     393    struct DefStandardHeapTraits : public Traits {
     394      typedef CR HeapCrossRef;
     395      typedef H Heap;
     396      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
     397        return new HeapCrossRef(G);
     398      }
     399      static Heap *createHeap(HeapCrossRef &R)
     400      {
     401        return new Heap(R);
     402      }
     403    };
     404    ///\ref named-templ-param "Named parameter" for setting heap and cross
     405    ///reference type with automatic allocation
     406
     407    ///\ref named-templ-param "Named parameter" for setting heap and cross
     408    ///reference type. It can allocate the heap and the cross reference
     409    ///object if the cross reference's constructor waits for the graph as
     410    ///parameter and the heap's constructor waits for the cross reference.
     411    template <class H, class CR = typename Graph::template NodeMap<int> >
     412    struct DefStandardHeap
     413      : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > {
     414      typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> >
     415      Create;
     416    };
    311417   
    312418    ///@}
     
    317423
    318424  public:     
     425
     426    typedef Johnson Create;
    319427   
    320428    /// \brief Constructor.
     
    325433      graph(&_graph), length(&_length),
    326434      _pred(0), local_pred(false),
    327       _dist(0), local_dist(false) {}
     435      _dist(0), local_dist(false),
     436      _heap_cross_ref(0), local_heap_cross_ref(false),
     437      _heap(0), local_heap(false) {}
    328438   
    329439    ///Destructor.
    330440    ~Johnson() {
    331       if(local_pred) delete _pred;
    332       if(local_dist) delete _dist;
     441      if (local_pred) delete _pred;
     442      if (local_dist) delete _dist;
     443      if (local_heap_cross_ref) delete _heap_cross_ref;
     444      if (local_heap) delete _heap;
    333445    }
    334446
     
    374486    }
    375487
    376     ///\name Execution control
    377     /// The simplest way to execute the algorithm is to use
    378     /// one of the member functions called \c run(...).
    379     /// \n
    380     /// If you need more control on the execution,
    381     /// Finally \ref start() will perform the actual path
    382     /// computation.
    383 
    384     ///@{
    385 
    386     /// \brief Initializes the internal data structures.
    387     ///
    388     /// Initializes the internal data structures.
    389     void init() {
    390       create_maps();
    391     }
    392    
    393     /// \brief Executes the algorithm.
    394     ///
    395     /// This method runs the %Johnson algorithm in order to compute
    396     /// the shortest path to each node pairs. The algorithm
    397     /// computes
    398     /// - The shortest path tree for each node.
    399     /// - The distance between each node pairs.
    400     void start() {
    401       typedef typename BelmannFord<Graph, LengthMap>::
    402       template DefOperationTraits<OperationTraits>::
    403       template DefPredMap<NullMap<Node, Edge> >::
    404       Create BelmannFordType;
    405 
    406       BelmannFordType belmannford(*graph, *length);
    407 
    408       NullMap<Node, Edge> predMap;
    409 
    410       belmannford.predMap(predMap);
     488  protected:
     489   
     490    typedef typename BelmannFord<Graph, LengthMap>::
     491    template DefOperationTraits<OperationTraits>::
     492    template DefPredMap<NullMap<Node, Edge> >::
     493    Create BelmannFordType;
     494
     495    void shiftedRun(const BelmannFordType& belmannford) {
    411496     
    412       belmannford.init(OperationTraits::zero());
    413       belmannford.start();
    414 
     497      typedef PotentialDifferenceMap<Graph,
     498      typename BelmannFordType::DistMap> PotDiffMap;
     499      PotDiffMap potdiff(*graph, belmannford.distMap());
     500      typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
     501      ShiftLengthMap shiftlen(*length, potdiff);
     502
     503      typename Dijkstra<Graph, ShiftLengthMap>::
     504      template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
     505
     506      dijkstra.heap(*_heap, *_heap_cross_ref);
     507     
    415508      for (NodeIt it(*graph); it != INVALID; ++it) {
    416         typedef PotentialDifferenceMap<Graph,
    417           typename BelmannFordType::DistMap> PotDiffMap;
    418         PotDiffMap potdiff(*graph, belmannford.distMap());
    419         typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
    420         ShiftLengthMap shiftlen(*length, potdiff);
    421         Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen);
    422509        dijkstra.run(it);
    423510        for (NodeIt jt(*graph); jt != INVALID; ++jt) {
     
    433520      }
    434521    }
     522
     523  public:   
     524
     525    ///\name Execution control
     526    /// The simplest way to execute the algorithm is to use
     527    /// one of the member functions called \c run(...).
     528    /// \n
     529    /// If you need more control on the execution,
     530    /// Finally \ref start() will perform the actual path
     531    /// computation.
     532
     533    ///@{
     534
     535    /// \brief Initializes the internal data structures.
     536    ///
     537    /// Initializes the internal data structures.
     538    void init() {
     539      create_maps();
     540    }
     541
     542    /// \brief Executes the algorithm.
     543    ///
     544    /// This method runs the %Johnson algorithm in order to compute
     545    /// the shortest path to each node pairs. The algorithm
     546    /// computes
     547    /// - The shortest path tree for each node.
     548    /// - The distance between each node pairs.
     549    void start() {
     550
     551      BelmannFordType belmannford(*graph, *length);
     552
     553      NullMap<Node, Edge> predMap;
     554
     555      belmannford.predMap(predMap);
     556     
     557      belmannford.init(OperationTraits::zero());
     558      belmannford.start();
     559
     560      shiftedRun(belmannford);
     561    }
     562
     563    /// \brief Executes the algorithm and checks the negatvie circles.
     564    ///
     565    /// This method runs the %Johnson algorithm in order to compute
     566    /// the shortest path to each node pairs. If the graph contains
     567    /// negative circle it gives back false. The algorithm
     568    /// computes
     569    /// - The shortest path tree for each node.
     570    /// - The distance between each node pairs.
     571    bool checkedStart() {
     572
     573      BelmannFordType belmannford(*graph, *length);
     574
     575      NullMap<Node, Edge> predMap;
     576
     577      belmannford.predMap(predMap);
     578     
     579      belmannford.init(OperationTraits::zero());
     580      if (!belmannford.checkedStart()) return false;
     581
     582      shiftedRun(belmannford);
     583      return true;
     584    }
     585
    435586   
    436587    /// \brief Runs %Johnson algorithm.
Note: See TracChangeset for help on using the changeset viewer.