gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small fixes related to BellmanFord (#51) - Add a missing #include. - Add a missing const keyword for negativeCycle(). - Test if negativeCycle() is const function.
0 2 0
default
2 files changed with 4 insertions and 1 deletions:
↑ Collapse diff ↑
Ignore white space 24 line context
... ...
@@ -14,24 +14,25 @@
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#ifndef LEMON_BELLMAN_FORD_H
20 20
#define LEMON_BELLMAN_FORD_H
21 21

	
22 22
/// \ingroup shortest_path
23 23
/// \file
24 24
/// \brief Bellman-Ford algorithm.
25 25

	
26
#include <lemon/list_graph.h>
26 27
#include <lemon/bits/path_dump.h>
27 28
#include <lemon/core.h>
28 29
#include <lemon/error.h>
29 30
#include <lemon/maps.h>
30 31
#include <lemon/path.h>
31 32

	
32 33
#include <limits>
33 34

	
34 35
namespace lemon {
35 36

	
36 37
  /// \brief Default OperationTraits for the BellmanFord algorithm class.
37 38
  ///  
... ...
@@ -766,25 +767,25 @@
766 767
    ///
767 768
    /// \pre Either \ref run() or \ref init() must be called before
768 769
    /// using this function.
769 770
    bool reached(Node v) const {
770 771
      return (*_dist)[v] != OperationTraits::infinity();
771 772
    }
772 773

	
773 774
    /// \brief Gives back a negative cycle.
774 775
    ///    
775 776
    /// This function gives back a directed cycle with negative total
776 777
    /// length if the algorithm has already found one.
777 778
    /// Otherwise it gives back an empty path.
778
    lemon::Path<Digraph> negativeCycle() {
779
    lemon::Path<Digraph> negativeCycle() const {
779 780
      typename Digraph::template NodeMap<int> state(*_gr, -1);
780 781
      lemon::Path<Digraph> cycle;
781 782
      for (int i = 0; i < int(_process.size()); ++i) {
782 783
        if (state[_process[i]] != -1) continue;
783 784
        for (Node v = _process[i]; (*_pred)[v] != INVALID;
784 785
             v = _gr->source((*_pred)[v])) {
785 786
          if (state[v] == i) {
786 787
            cycle.addFront((*_pred)[v]);
787 788
            for (Node u = _gr->source((*_pred)[v]); u != v;
788 789
                 u = _gr->source((*_pred)[u])) {
789 790
              cycle.addFront((*_pred)[u]);
790 791
            }
Ignore white space 6 line context
... ...
@@ -87,24 +87,25 @@
87 87

	
88 88
    bf_test.start();
89 89
    bf_test.checkedStart();
90 90
    bf_test.limitedStart(k);
91 91

	
92 92
    l  = const_bf_test.dist(t);
93 93
    e  = const_bf_test.predArc(t);
94 94
    s  = const_bf_test.predNode(t);
95 95
    b  = const_bf_test.reached(t);
96 96
    d  = const_bf_test.distMap();
97 97
    p  = const_bf_test.predMap();
98 98
    pp = const_bf_test.path(t);
99
    pp = const_bf_test.negativeCycle();
99 100
    
100 101
    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
101 102
  }
102 103
  {
103 104
    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
104 105
      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
105 106
      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
106 107
      ::Create bf_test(gr,length);
107 108

	
108 109
    LengthMap length_map;
109 110
    concepts::ReadWriteMap<Node,Arc> pred_map;
110 111
    concepts::ReadWriteMap<Node,Value> dist_map;
... ...
@@ -123,24 +124,25 @@
123 124
    b = bf_test.processNextRound();
124 125
    b = bf_test.processNextWeakRound();
125 126

	
126 127
    bf_test.start();
127 128
    bf_test.checkedStart();
128 129
    bf_test.limitedStart(k);
129 130

	
130 131
    l  = bf_test.dist(t);
131 132
    e  = bf_test.predArc(t);
132 133
    s  = bf_test.predNode(t);
133 134
    b  = bf_test.reached(t);
134 135
    pp = bf_test.path(t);
136
    pp = bf_test.negativeCycle();
135 137
  }
136 138
}
137 139

	
138 140
void checkBellmanFordFunctionCompile()
139 141
{
140 142
  typedef int Value;
141 143
  typedef concepts::Digraph Digraph;
142 144
  typedef Digraph::Arc Arc;
143 145
  typedef Digraph::Node Node;
144 146
  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
145 147

	
146 148
  Digraph g;
0 comments (0 inline)