Changeset - r413:532f34ea9cf3
« 412:62f978
« 411:c5f010
419:59d3aa »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Merge
0 2 0
merge default
0 files changed with 1 insertions and 24 deletions:
lemon/dijkstra.h
23
test/dijkstra_test.cc
1
1
↑ Collapse diff ↑
lemon/dijkstra.h
Ignore white space 6 line context
... ... 
@@ -45,47 +45,24 @@
45 45 
      return static_cast<Value>(0);
46 46 
    }
47 47 
    /// \brief Gives back the sum of the given two elements.
48 48 
    static Value plus(const Value& left, const Value& right) {
49 49 
      return left + right;
50 50 
    }
51 51 
    /// \brief Gives back true only if the first value is less than the second.
52 52 
    static bool less(const Value& left, const Value& right) {
53 53 
      return left < right;
54 54 
    }
55 55 
  };
56 56 

			




	57
	
	
		
  /// \brief Widest path operation traits for the Dijkstra algorithm class.


			




	58
	
	
		
  ///


			




	59
	
	
		
  /// This operation traits class defines all computational operations and


			




	60
	
	
		
  /// constants which are used in the Dijkstra algorithm for widest path


			




	61
	
	
		
  /// computation.


			




	62
	
	
		
  ///


			




	63
	
	
		
  /// \see DijkstraDefaultOperationTraits


			




	64
	
	
		
  template <typename Value>


			




	65
	
	
		
  struct DijkstraWidestPathOperationTraits {


			




	66
	
	
		
    /// \brief Gives back the maximum value of the type.


			




	67
	
	
		
    static Value zero() {


			




	68
	
	
		
      return std::numeric_limits<Value>::max();


			




	69
	
	
		
    }


			




	70
	
	
		
    /// \brief Gives back the minimum of the given two elements.


			




	71
	
	
		
    static Value plus(const Value& left, const Value& right) {


			




	72
	
	
		
      return std::min(left, right);


			




	73
	
	
		
    }


			




	74
	
	
		
    /// \brief Gives back true only if the first value is less than the second.


			




	75
	
	
		
    static bool less(const Value& left, const Value& right) {


			




	76
	
	
		
      return left < right;


			




	77
	
	
		
    }


			




	78
	
	
		
  };


			




	79
	
	
		

			




	80
	57
	
		
  ///Default traits class of Dijkstra class.


			




	81
	58
	
		

			




	82
	59
	
		
  ///Default traits class of Dijkstra class.


			




	83
	60
	
		
  ///\tparam GR The type of the digraph.


			




	84
	61
	
		
  ///\tparam LM The type of the length map.


			




	85
	62
	
		
  template<class GR, class LM>


			




	86
	63
	
		
  struct DijkstraDefaultTraits


			




	87
	64
	
		
  {


			




	88
	65
	
		
    ///The type of the digraph the algorithm runs on.


			




	89
	66
	
		
    typedef GR Digraph;


			




	90
	67
	
		

			




	91
	68
	
		
    ///The type of the map that stores the arc lengths.

			




        

    

    

    

        

            

                

                    test/dijkstra_test.cc
                

                

                  
                  
                  
                  Ignore white space
                  24 line context
                

                
                  
                
            

        

        

            

            



	...
	...
	
		
@@ -80,25 +80,25 @@


			




	80
	80
	
		
    s  = dijkstra_test.predNode(t);


			




	81
	81
	
		
    b  = dijkstra_test.reached(t);


			




	82
	82
	
		
    d  = dijkstra_test.distMap();


			




	83
	83
	
		
    p  = dijkstra_test.predMap();


			




	84
	84
	
		
    pp = dijkstra_test.path(t);


			




	85
	85
	
		
  }


			




	86
	86
	
		
  {


			




	87
	87
	
		
    DType


			




	88
	88
	
		
      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >


			




	89
	89
	
		
      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >


			




	90
	90
	
		
      ::SetProcessedMap<concepts::WriteMap<Node,bool> >


			




	91
	91
	
		
      ::SetStandardProcessedMap


			




	92
	
	
		
      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >


			




	
	92
	
		
      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >


			




	93
	93
	
		
      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >


			




	94
	94
	
		
      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >


			




	95
	95
	
		
      ::Create dijkstra_test(G,length);


			




	96
	96
	
		

			




	97
	97
	
		
    dijkstra_test.run(s);


			




	98
	98
	
		
    dijkstra_test.run(s,t);


			




	99
	99
	
		

			




	100
	100
	
		
    l  = dijkstra_test.dist(t);


			




	101
	101
	
		
    e  = dijkstra_test.predArc(t);


			




	102
	102
	
		
    s  = dijkstra_test.predNode(t);


			




	103
	103
	
		
    b  = dijkstra_test.reached(t);


			




	104
	104
	
		
    pp = dijkstra_test.path(t);


			




        

    






    
    



    


    

     
    
0 comments (0 inline)