Port preflow push max flow alg. from svn -r3516 (#176)
Namely,
- port the files
- apply the migrate script
- apply the unify script
- break the long lines in lemon/preflow.h
- convert the .dim test file to .lgf
- fix compilation problems
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_VECTOR_MAP_H
20 #define LEMON_BITS_VECTOR_MAP_H
25 #include <lemon/core.h>
26 #include <lemon/bits/alteration_notifier.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concepts/maps.h>
34 //\brief Vector based graph maps.
39 // \brief Graph map based on the std::vector storage.
41 // The VectorMap template class is graph map structure that automatically
42 // updates the map when a key is added to or erased from the graph.
43 // This map type uses std::vector to store the values.
45 // \tparam _Graph The graph this map is attached to.
46 // \tparam _Item The item type of the graph items.
47 // \tparam _Value The value type of the map.
48 template <typename _Graph, typename _Item, typename _Value>
50 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
53 // The container type of the map.
54 typedef std::vector<_Value> Container;
58 // The graph type of the map.
60 // The item type of the map.
62 // The reference map tag.
63 typedef True ReferenceMapTag;
65 // The key type of the map.
67 // The value type of the map.
71 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
74 typedef VectorMap Map;
75 // The base class of the map.
76 typedef typename Notifier::ObserverBase Parent;
78 // The reference type of the map;
79 typedef typename Container::reference Reference;
80 // The const reference type of the map;
81 typedef typename Container::const_reference ConstReference;
84 // \brief Constructor to attach the new map into the notifier.
86 // It constructs a map and attachs it into the notifier.
87 // It adds all the items of the graph to the map.
88 VectorMap(const Graph& graph) {
89 Parent::attach(graph.notifier(Item()));
90 container.resize(Parent::notifier()->maxId() + 1);
93 // \brief Constructor uses given value to initialize the map.
95 // It constructs a map uses a given value to initialize the map.
96 // It adds all the items of the graph to the map.
97 VectorMap(const Graph& graph, const Value& value) {
98 Parent::attach(graph.notifier(Item()));
99 container.resize(Parent::notifier()->maxId() + 1, value);
103 // \brief Copy constructor
106 VectorMap(const VectorMap& _copy) : Parent() {
107 if (_copy.attached()) {
108 Parent::attach(*_copy.notifier());
109 container = _copy.container;
113 // \brief Assign operator.
115 // This operator assigns for each item in the map the
116 // value mapped to the same item in the copied map.
117 // The parameter map should be indiced with the same
118 // itemset because this assign operator does not change
119 // the container of the map.
120 VectorMap& operator=(const VectorMap& cmap) {
121 return operator=<VectorMap>(cmap);
125 // \brief Template assign operator.
127 // The given parameter should be conform to the ReadMap
128 // concecpt and could be indiced by the current item set of
129 // the NodeMap. In this case the value for each item
130 // is assigned by the value of the given ReadMap.
131 template <typename CMap>
132 VectorMap& operator=(const CMap& cmap) {
133 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
134 const typename Parent::Notifier* nf = Parent::notifier();
136 for (nf->first(it); it != INVALID; nf->next(it)) {
144 // \brief The subcript operator.
146 // The subscript operator. The map can be subscripted by the
147 // actual items of the graph.
148 Reference operator[](const Key& key) {
149 return container[Parent::notifier()->id(key)];
152 // \brief The const subcript operator.
154 // The const subscript operator. The map can be subscripted by the
155 // actual items of the graph.
156 ConstReference operator[](const Key& key) const {
157 return container[Parent::notifier()->id(key)];
161 // \brief The setter function of the map.
163 // It the same as operator[](key) = value expression.
164 void set(const Key& key, const Value& value) {
165 (*this)[key] = value;
170 // \brief Adds a new key to the map.
172 // It adds a new key to the map. It is called by the observer notifier
173 // and it overrides the add() member function of the observer base.
174 virtual void add(const Key& key) {
175 int id = Parent::notifier()->id(key);
176 if (id >= int(container.size())) {
177 container.resize(id + 1);
181 // \brief Adds more new keys to the map.
183 // It adds more new keys to the map. It is called by the observer notifier
184 // and it overrides the add() member function of the observer base.
185 virtual void add(const std::vector<Key>& keys) {
186 int max = container.size() - 1;
187 for (int i = 0; i < int(keys.size()); ++i) {
188 int id = Parent::notifier()->id(keys[i]);
193 container.resize(max + 1);
196 // \brief Erase a key from the map.
198 // Erase a key from the map. It is called by the observer notifier
199 // and it overrides the erase() member function of the observer base.
200 virtual void erase(const Key& key) {
201 container[Parent::notifier()->id(key)] = Value();
204 // \brief Erase more keys from the map.
206 // It erases more keys from the map. It is called by the observer notifier
207 // and it overrides the erase() member function of the observer base.
208 virtual void erase(const std::vector<Key>& keys) {
209 for (int i = 0; i < int(keys.size()); ++i) {
210 container[Parent::notifier()->id(keys[i])] = Value();
214 // \brief Build the map.
216 // It builds the map. It is called by the observer notifier
217 // and it overrides the build() member function of the observer base.
218 virtual void build() {
219 int size = Parent::notifier()->maxId() + 1;
220 container.reserve(size);
221 container.resize(size);
224 // \brief Clear the map.
226 // It erases all items from the map. It is called by the observer notifier
227 // and it overrides the clear() member function of the observer base.
228 virtual void clear() {