equal
deleted
inserted
replaced
20 #define LEMON_MIN_MEAN_CYCLE_H |
20 #define LEMON_MIN_MEAN_CYCLE_H |
21 |
21 |
22 /// \ingroup min_cost_flow |
22 /// \ingroup min_cost_flow |
23 /// |
23 /// |
24 /// \file |
24 /// \file |
25 /// \brief Karp algorithm for finding a minimum mean cycle. |
25 /// \brief Karp's algorithm for finding a minimum mean (directed) cycle. |
26 |
26 |
|
27 #include <vector> |
27 #include <lemon/graph_utils.h> |
28 #include <lemon/graph_utils.h> |
28 #include <lemon/topology.h> |
29 #include <lemon/topology.h> |
29 #include <lemon/path.h> |
30 #include <lemon/path.h> |
30 |
31 |
31 namespace lemon { |
32 namespace lemon { |
61 typedef Path<Graph> Path; |
62 typedef Path<Graph> Path; |
62 typedef std::vector<Node> NodeVector; |
63 typedef std::vector<Node> NodeVector; |
63 |
64 |
64 protected: |
65 protected: |
65 |
66 |
66 /// \brief Data sturcture for path data. |
67 /// \brief Data structure for path data. |
67 struct PathData |
68 struct PathData |
68 { |
69 { |
69 bool found; |
70 bool found; |
70 Length dist; |
71 Length dist; |
71 Edge pred; |
72 Edge pred; |
148 for (NodeIt v(graph); v != INVALID; ++v) { |
149 for (NodeIt v(graph); v != INVALID; ++v) { |
149 if (comp[v] == comp_cnt) nodes.push_back(v); |
150 if (comp[v] == comp_cnt) nodes.push_back(v); |
150 } |
151 } |
151 // Creating vectors for all nodes |
152 // Creating vectors for all nodes |
152 int n = nodes.size(); |
153 int n = nodes.size(); |
153 for (int i = 0; i < nodes.size(); ++i) { |
154 for (int i = 0; i < n; ++i) { |
154 dmap[nodes[i]].resize(n + 1); |
155 dmap[nodes[i]].resize(n + 1); |
155 } |
156 } |
156 } |
157 } |
157 |
158 |
158 /// \brief Processes all rounds of computing required path data for |
159 /// \brief Processes all rounds of computing required path data for |