18 #include <list> |
18 #include <list> |
19 #include <memory> |
19 #include <memory> |
20 #include <utility> |
20 #include <utility> |
21 |
21 |
22 //#include <sage_graph.h> |
22 //#include <sage_graph.h> |
23 //#include <hugo/list_graph.h> |
23 //#include <lemon/list_graph.h> |
24 //#include <hugo/graph_wrapper.h> |
24 //#include <lemon/graph_wrapper.h> |
25 #include <hugo/invalid.h> |
25 #include <lemon/invalid.h> |
26 //#include <bfs_dfs.h> |
26 //#include <bfs_dfs.h> |
27 //#include <stp.h> |
27 //#include <stp.h> |
28 //#include <hugo/max_flow.h> |
28 //#include <lemon/max_flow.h> |
29 //#include <augmenting_flow.h> |
29 //#include <augmenting_flow.h> |
30 //#include <iter_map.h> |
30 //#include <iter_map.h> |
31 |
31 |
32 using std::cout; |
32 using std::cout; |
33 using std::cin; |
33 using std::cin; |
34 using std::endl; |
34 using std::endl; |
35 |
35 |
36 namespace hugo { |
36 namespace lemon { |
37 |
37 |
38 |
38 |
39 /// \addtogroup misc |
39 /// \addtogroup misc |
40 /// @{ |
40 /// @{ |
41 |
41 |
42 /// \brief A partitioned vector with iterable classes. |
42 /// \brief A partitioned vector with iterable classes. |
43 /// |
43 /// |
44 /// This class implements a container in which the data is stored in an |
44 /// This class implements a container in which the data is stored in an |
45 /// stl vector, the range is partitioned into sets and each set is |
45 /// stl vector, the range is partitioned into sets and each set is |
46 /// doubly linked in a list. |
46 /// doubly linked in a list. |
47 /// That is, each class is iterable by hugo iterators, and any member of |
47 /// That is, each class is iterable by lemon iterators, and any member of |
48 /// the vector can bo moved to an other class. |
48 /// the vector can bo moved to an other class. |
49 template <typename T> |
49 template <typename T> |
50 class IterablePartition { |
50 class IterablePartition { |
51 protected: |
51 protected: |
52 struct Node { |
52 struct Node { |
61 }; |
61 }; |
62 std::vector<Tip> tips; |
62 std::vector<Tip> tips; |
63 public: |
63 public: |
64 /// The classes are indexed by integers from \c 0 to \c classNum()-1. |
64 /// The classes are indexed by integers from \c 0 to \c classNum()-1. |
65 int classNum() const { return tips.size(); } |
65 int classNum() const { return tips.size(); } |
66 /// This hugo style iterator iterates through a class. |
66 /// This lemon style iterator iterates through a class. |
67 class ClassIt; |
67 class ClassIt; |
68 /// Constructor. The number of classes is to be given which is fixed |
68 /// Constructor. The number of classes is to be given which is fixed |
69 /// over the life of the container. |
69 /// over the life of the container. |
70 /// The partition classes are indexed from 0 to class_num-1. |
70 /// The partition classes are indexed from 0 to class_num-1. |
71 IterablePartition(int class_num) { |
71 IterablePartition(int class_num) { |
155 bool valid(const ClassIt& it) const { return it.i!=-1; } |
155 bool valid(const ClassIt& it) const { return it.i!=-1; } |
156 }; |
156 }; |
157 |
157 |
158 /// \brief Wrappers for LP solvers |
158 /// \brief Wrappers for LP solvers |
159 /// |
159 /// |
160 /// This class implements a hugo wrapper for glpk. |
160 /// This class implements a lemon wrapper for glpk. |
161 /// Later other LP-solvers will be wrapped into hugo. |
161 /// Later other LP-solvers will be wrapped into lemon. |
162 /// The aim of this class is to give a general surface to different |
162 /// The aim of this class is to give a general surface to different |
163 /// solvers, i.e. it makes possible to write algorithms using LP's, |
163 /// solvers, i.e. it makes possible to write algorithms using LP's, |
164 /// in which the solver can be changed to an other one easily. |
164 /// in which the solver can be changed to an other one easily. |
165 class LPSolverWrapper { |
165 class LPSolverWrapper { |
166 public: |
166 public: |