COIN-OR::LEMON - Graph Library

Changeset 1710:f531c16dd923 in lemon-0.x


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

Location:
lemon
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/belmann_ford.h

    r1699 r1710  
    168168  /// \author Balazs Dezso
    169169
     170#ifdef DOXYGEN
     171  template <typename _Graph, typename _LengthMap, typename _Traits>
     172#else
    170173  template <typename _Graph=ListGraph,
    171174            typename _LengthMap=typename _Graph::template EdgeMap<int>,
    172175            typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
     176#endif
    173177  class BelmannFord {
    174178  public:
     
    234238  public :
    235239 
     240    typedef BelmannFord Create;
     241
    236242    /// \name Named template parameters
    237243
     
    241247    struct DefPredMapTraits : public Traits {
    242248      typedef T PredMap;
    243       static PredMap *createPredMap(const Graph& graph) {
     249      static PredMap *createPredMap(const Graph&) {
    244250        throw UninitializedParameter();
    245251      }
     
    251257    ///
    252258    template <class T>
    253     class DefPredMap
    254       : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {};
     259    struct DefPredMap {
     260      typedef BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
     261    };
    255262   
    256263    template <class T>
     
    268275    ///
    269276    template <class T>
    270     class DefDistMap
    271       : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {};
     277    struct DefDistMap
     278      : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {
     279      typedef BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
     280    };
    272281   
    273282    template <class T>
     
    279288    /// OperationTraits type
    280289    ///
    281     /// \ref named-templ-param "Named parameter" for setting PredMap type
     290    /// \ref named-templ-param "Named parameter" for setting OperationTraits
     291    /// type
    282292    template <class T>
    283     class DefOperationTraits
     293    struct DefOperationTraits
    284294      : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
    285     public:
    286295      typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
    287       BelmannFord;
     296      Create;
    288297    };
    289298   
    290299    ///@}
     300
     301  protected:
     302   
     303    BelmannFord() {}
    291304
    292305  public:     
     
    363376    ///
    364377    /// Initializes the internal data structures.
    365     void init() {
     378    void init(const Value value = OperationTraits::infinity()) {
    366379      create_maps();
    367380      for (NodeIt it(*graph); it != INVALID; ++it) {
    368381        _pred->set(it, INVALID);
    369         _dist->set(it, OperationTraits::infinity());
     382        _dist->set(it, value);
    370383      }
    371384    }
     
    741754      return BelmannFordWizard<DefDistMapBase<T> >(*this);
    742755    }
     756
     757    template<class T>
     758    struct DefOperationTraitsBase : public Base {
     759      typedef T OperationTraits;
     760      DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
     761    };
     762   
     763    ///\brief \ref named-templ-param "Named parameter"
     764    ///function for setting OperationTraits type
     765    ///
     766    /// \ref named-templ-param "Named parameter"
     767    ///function for setting OperationTraits type
     768    ///
     769    template<class T>
     770    BelmannFordWizard<DefOperationTraitsBase<T> > distMap() {
     771      return BelmannFordWizard<DefDistMapBase<T> >(*this);
     772    }
    743773   
    744774    /// \brief Sets the source node, from which the BelmannFord algorithm runs.
  • lemon/bfs.h

    r1709 r1710  
    215215      }
    216216    }
    217    
    218   public :
    219  
     217
     218  protected:
     219   
     220    Bfs() {}
     221   
     222  public:
     223 
     224    typedef Bfs Create;
     225
    220226    ///\name Named template parameters
    221227
  • lemon/dfs.h

    r1709 r1710  
    215215      }
    216216    }
    217    
    218   public :
     217
     218  protected:
     219
     220    Dfs() {}
     221   
     222  public:
    219223
    220224    typedef Dfs Create;
  • lemon/dijkstra.h

    r1709 r1710  
    237237   
    238238  public :
     239
     240    typedef Dijkstra Create;
    239241 
    240242    ///\name Named template parameters
     
    321323    typename Graph::template NodeMap<int> _heap_map;
    322324    Heap _heap;
     325  protected:
     326
     327    Dijkstra() {}
     328
    323329  public:     
    324330   
  • lemon/floyd_warshall.h

    r1699 r1710  
    171171  /// \author Balazs Dezso
    172172
    173 
     173#ifdef DOXYGEN
     174  template <typename _Graph, typename _LengthMap typename _Traits >
     175#else
    174176  template <typename _Graph=ListGraph,
    175177            typename _LengthMap=typename _Graph::template EdgeMap<int>,
    176178            typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
     179#endif
    177180  class FloydWarshall {
    178181  public:
     
    257260    ///
    258261    template <class T>
    259     class DefPredMap
    260       : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {};
     262    struct DefPredMap
     263      : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {
     264      typedef FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > Create;
     265    };
    261266   
    262267    template <class T>
     
    273278    ///
    274279    template <class T>
    275     class DefDistMap
    276       : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {};
     280    struct DefDistMap
     281      : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {
     282      typedef FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > Create;
     283    };
    277284   
    278285    template <class T>
     
    286293    /// \ref named-templ-param "Named parameter" for setting PredMap type
    287294    template <class T>
    288     class DefOperationTraits
     295    struct DefOperationTraits
    289296      : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
     297      typedef FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> >
     298      Create;
    290299    };
    291300   
    292301    ///@}
    293302
     303  protected:
     304
     305    FloydWarshall() {}
     306
    294307  public:     
     308
     309    typedef FloydWarshall Create;
    295310   
    296311    /// \brief Constructor.
  • 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.