COIN-OR::LEMON - Graph Library

Changeset 1710:f531c16dd923 in lemon-0.x for lemon/johnson.h


Ignore:
Timestamp:
10/06/05 11:37:53 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2237
Message:

Bug solved in named parameters
Simplify my Johnson algorithm

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/johnson.h

    r1699 r1710  
    2525#include <lemon/list_graph.h>
    2626#include <lemon/graph_utils.h>
    27 #include <lemon/dfs.h>
    2827#include <lemon/dijkstra.h>
    2928#include <lemon/belmann_ford.h>
     
    173172  /// \author Balazs Dezso
    174173
     174#ifdef DOXYGEN
     175  template <typename _Graph, typename _LengthMap, typename _Traits>
     176#else
    175177  template <typename _Graph=ListGraph,
    176178            typename _LengthMap=typename _Graph::template EdgeMap<int>,
    177179            typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
     180#endif
    178181  class Johnson {
    179182  public:
     
    258261    ///
    259262    template <class T>
    260     class DefPredMap
    261       : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {};
     263    struct DefPredMap
     264      : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {
     265      typedef Johnson< Graph, LengthMap, DefPredMapTraits<T> > Create;
     266    };
    262267   
    263268    template <class T>
     
    274279    ///
    275280    template <class T>
    276     class DefDistMap
    277       : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {};
     281    struct DefDistMap
     282      : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {
     283      typedef Johnson< Graph, LengthMap, DefDistMapTraits<T> > Create;
     284    };
    278285   
    279286    template <class T>
     
    285292    /// OperationTraits type
    286293    ///
    287     /// \ref named-templ-param "Named parameter" for setting PredMap type
     294    /// \ref named-templ-param "Named parameter" for setting
     295    /// OperationTraits type
    288296    template <class T>
    289     class DefOperationTraits
    290       : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {};
     297    struct DefOperationTraits
     298      : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {
     299      typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
     300    };
    291301   
    292302    ///@}
     303
     304  protected:
     305
     306    Johnson() {}
    293307
    294308  public:     
     
    375389    /// - The distance between each node pairs.
    376390    void start() {
    377       typename BelmannFord<Graph, LengthMap>::
     391      typedef typename BelmannFord<Graph, LengthMap>::
    378392      template DefOperationTraits<OperationTraits>::
    379       BelmannFord belmannford(*graph, *length);
     393      template DefPredMap<NullMap<Node, Edge> >::
     394      Create BelmannFordType;
     395
     396      BelmannFordType belmannford(*graph, *length);
     397
     398      NullMap<Node, Edge> predMap;
     399
     400      belmannford.predMap(predMap);
    380401     
    381       belmannford.init();
    382 
    383       typename Graph::template NodeMap<bool> initial(*graph, false);
    384 
    385       {
    386         Dfs<Graph> dfs(*graph);
    387 
    388         dfs.init();
    389         for (NodeIt it(*graph); it != INVALID; ++it) {
    390           if (!dfs.reached(it)) {
    391             dfs.addSource(it);
    392             while (!dfs.emptyQueue()) {
    393               Edge edge = dfs.processNextEdge();
    394               initial.set(graph->target(edge), false);
    395             }
    396             initial.set(it, true);
    397           }
    398         }
    399         for (NodeIt it(*graph); it != INVALID; ++it) {
    400           if (initial[it]) {
    401             belmannford.addSource(it);
    402           }
    403         }
    404       }
    405 
     402      belmannford.init(OperationTraits::zero());
    406403      belmannford.start();
    407404
    408405      for (NodeIt it(*graph); it != INVALID; ++it) {
    409406        typedef PotentialDifferenceMap<Graph,
    410           typename BelmannFord<Graph, LengthMap>::DistMap> PotDiffMap;
     407          typename BelmannFordType::DistMap> PotDiffMap;
    411408        PotDiffMap potdiff(*graph, belmannford.distMap());
    412409        typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
Note: See TracChangeset for help on using the changeset viewer.