External flow and potential maps can be used in MinCostMaxFlow.
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_TRAITS_H
20 #define LEMON_BITS_TRAITS_H
22 #include <lemon/bits/utility.h>
25 ///\brief Traits for graphs and maps
29 template <typename _Graph, typename _Item>
30 class ItemSetTraits {};
33 template <typename Graph, typename Enable = void>
34 struct NodeNotifierIndicator {
35 typedef InvalidType Type;
37 template <typename Graph>
38 struct NodeNotifierIndicator<
40 typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type
42 typedef typename Graph::NodeNotifier Type;
45 template <typename _Graph>
46 class ItemSetTraits<_Graph, typename _Graph::Node> {
51 typedef typename Graph::Node Item;
52 typedef typename Graph::NodeIt ItemIt;
54 typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;
56 template <typename _Value>
57 class Map : public Graph::template NodeMap<_Value> {
59 typedef typename Graph::template NodeMap<_Value> Parent;
60 typedef typename Graph::template NodeMap<_Value> Type;
61 typedef typename Parent::Value Value;
63 Map(const Graph& _graph) : Parent(_graph) {}
64 Map(const Graph& _graph, const Value& _value)
65 : Parent(_graph, _value) {}
71 template <typename Graph, typename Enable = void>
72 struct EdgeNotifierIndicator {
73 typedef InvalidType Type;
75 template <typename Graph>
76 struct EdgeNotifierIndicator<
78 typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type
80 typedef typename Graph::EdgeNotifier Type;
83 template <typename _Graph>
84 class ItemSetTraits<_Graph, typename _Graph::Edge> {
89 typedef typename Graph::Edge Item;
90 typedef typename Graph::EdgeIt ItemIt;
92 typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;
94 template <typename _Value>
95 class Map : public Graph::template EdgeMap<_Value> {
97 typedef typename Graph::template EdgeMap<_Value> Parent;
98 typedef typename Graph::template EdgeMap<_Value> Type;
99 typedef typename Parent::Value Value;
101 Map(const Graph& _graph) : Parent(_graph) {}
102 Map(const Graph& _graph, const Value& _value)
103 : Parent(_graph, _value) {}
108 template <typename Graph, typename Enable = void>
109 struct UEdgeNotifierIndicator {
110 typedef InvalidType Type;
112 template <typename Graph>
113 struct UEdgeNotifierIndicator<
115 typename enable_if<typename Graph::UEdgeNotifier::Notifier, void>::type
117 typedef typename Graph::UEdgeNotifier Type;
120 template <typename _Graph>
121 class ItemSetTraits<_Graph, typename _Graph::UEdge> {
124 typedef _Graph Graph;
126 typedef typename Graph::UEdge Item;
127 typedef typename Graph::UEdgeIt ItemIt;
129 typedef typename UEdgeNotifierIndicator<Graph>::Type ItemNotifier;
131 template <typename _Value>
132 class Map : public Graph::template UEdgeMap<_Value> {
134 typedef typename Graph::template UEdgeMap<_Value> Parent;
135 typedef typename Graph::template UEdgeMap<_Value> Type;
136 typedef typename Parent::Value Value;
138 Map(const Graph& _graph) : Parent(_graph) {}
139 Map(const Graph& _graph, const Value& _value)
140 : Parent(_graph, _value) {}
145 template <typename Graph, typename Enable = void>
146 struct ANodeNotifierIndicator {
147 typedef InvalidType Type;
149 template <typename Graph>
150 struct ANodeNotifierIndicator<
152 typename enable_if<typename Graph::ANodeNotifier::Notifier, void>::type
154 typedef typename Graph::ANodeNotifier Type;
157 template <typename _Graph>
158 class ItemSetTraits<_Graph, typename _Graph::ANode> {
161 typedef _Graph Graph;
163 typedef typename Graph::ANode Item;
164 typedef typename Graph::ANodeIt ItemIt;
166 typedef typename ANodeNotifierIndicator<Graph>::Type ItemNotifier;
168 template <typename _Value>
169 class Map : public Graph::template ANodeMap<_Value> {
171 typedef typename Graph::template ANodeMap<_Value> Parent;
172 typedef typename Graph::template ANodeMap<_Value> Type;
173 typedef typename Parent::Value Value;
175 Map(const Graph& _graph) : Parent(_graph) {}
176 Map(const Graph& _graph, const Value& _value)
177 : Parent(_graph, _value) {}
182 template <typename Graph, typename Enable = void>
183 struct BNodeNotifierIndicator {
184 typedef InvalidType Type;
186 template <typename Graph>
187 struct BNodeNotifierIndicator<
189 typename enable_if<typename Graph::BNodeNotifier::Notifier, void>::type
191 typedef typename Graph::BNodeNotifier Type;
194 template <typename _Graph>
195 class ItemSetTraits<_Graph, typename _Graph::BNode> {
198 typedef _Graph Graph;
200 typedef typename Graph::BNode Item;
201 typedef typename Graph::BNodeIt ItemIt;
203 typedef typename BNodeNotifierIndicator<Graph>::Type ItemNotifier;
205 template <typename _Value>
206 class Map : public Graph::template BNodeMap<_Value> {
208 typedef typename Graph::template BNodeMap<_Value> Parent;
209 typedef typename Graph::template BNodeMap<_Value> Type;
210 typedef typename Parent::Value Value;
212 Map(const Graph& _graph) : Parent(_graph) {}
213 Map(const Graph& _graph, const Value& _value)
214 : Parent(_graph, _value) {}
220 template <typename Map, typename Enable = void>
222 typedef False ReferenceMapTag;
224 typedef typename Map::Key Key;
225 typedef typename Map::Value Value;
227 typedef const Value ConstReturnValue;
228 typedef const Value ReturnValue;
231 template <typename Map>
233 Map, typename enable_if<typename Map::ReferenceMapTag, void>::type >
235 typedef True ReferenceMapTag;
237 typedef typename Map::Key Key;
238 typedef typename Map::Value Value;
240 typedef typename Map::ConstReference ConstReturnValue;
241 typedef typename Map::Reference ReturnValue;
243 typedef typename Map::ConstReference ConstReference;
244 typedef typename Map::Reference Reference;
247 template <typename MatrixMap, typename Enable = void>
248 struct MatrixMapTraits {
249 typedef False ReferenceMapTag;
251 typedef typename MatrixMap::FirstKey FirstKey;
252 typedef typename MatrixMap::SecondKey SecondKey;
253 typedef typename MatrixMap::Value Value;
255 typedef const Value ConstReturnValue;
256 typedef const Value ReturnValue;
259 template <typename MatrixMap>
260 struct MatrixMapTraits<
261 MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,
264 typedef True ReferenceMapTag;
266 typedef typename MatrixMap::FirstKey FirstKey;
267 typedef typename MatrixMap::SecondKey SecondKey;
268 typedef typename MatrixMap::Value Value;
270 typedef typename MatrixMap::ConstReference ConstReturnValue;
271 typedef typename MatrixMap::Reference ReturnValue;
273 typedef typename MatrixMap::ConstReference ConstReference;
274 typedef typename MatrixMap::Reference Reference;
277 // Indicators for the tags
279 template <typename Graph, typename Enable = void>
280 struct NodeNumTagIndicator {
281 static const bool value = false;
284 template <typename Graph>
285 struct NodeNumTagIndicator<
287 typename enable_if<typename Graph::NodeNumTag, void>::type
289 static const bool value = true;
292 template <typename Graph, typename Enable = void>
293 struct EdgeNumTagIndicator {
294 static const bool value = false;
297 template <typename Graph>
298 struct EdgeNumTagIndicator<
300 typename enable_if<typename Graph::EdgeNumTag, void>::type
302 static const bool value = true;
305 template <typename Graph, typename Enable = void>
306 struct FindEdgeTagIndicator {
307 static const bool value = false;
310 template <typename Graph>
311 struct FindEdgeTagIndicator<
313 typename enable_if<typename Graph::FindEdgeTag, void>::type
315 static const bool value = true;
318 template <typename Graph, typename Enable = void>
319 struct UndirectedTagIndicator {
320 static const bool value = false;
323 template <typename Graph>
324 struct UndirectedTagIndicator<
326 typename enable_if<typename Graph::UndirectedTag, void>::type
328 static const bool value = true;
331 template <typename Graph, typename Enable = void>
332 struct BuildTagIndicator {
333 static const bool value = false;
336 template <typename Graph>
337 struct BuildTagIndicator<
339 typename enable_if<typename Graph::BuildTag, void>::type
341 static const bool value = true;