r663:f2d6d3446adf
Fri, 24 Apr 2009 10:15:33
[Not Reviewed]
0 comments (0 inline)
0
2
0
86
80
| ... | ... |
@@ -8,159 +8,165 @@ |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 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_BITS_TRAITS_H |
| 20 | 20 |
#define LEMON_BITS_TRAITS_H |
| 21 | 21 |
|
| 22 | 22 |
//\file |
| 23 | 23 |
//\brief Traits for graphs and maps |
| 24 | 24 |
// |
| 25 | 25 |
|
| 26 | 26 |
#include <lemon/bits/enable_if.h> |
| 27 | 27 |
|
| 28 | 28 |
namespace lemon {
|
| 29 | 29 |
|
| 30 | 30 |
struct InvalidType {};
|
| 31 | 31 |
|
| 32 |
template <typename |
|
| 32 |
template <typename GR, typename _Item> |
|
| 33 | 33 |
class ItemSetTraits {};
|
| 34 | 34 |
|
| 35 | 35 |
|
| 36 |
template <typename |
|
| 36 |
template <typename GR, typename Enable = void> |
|
| 37 | 37 |
struct NodeNotifierIndicator {
|
| 38 | 38 |
typedef InvalidType Type; |
| 39 | 39 |
}; |
| 40 |
template <typename |
|
| 40 |
template <typename GR> |
|
| 41 | 41 |
struct NodeNotifierIndicator< |
| 42 |
Graph, |
|
| 43 |
typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type |
|
| 42 |
GR, |
|
| 43 |
typename enable_if<typename GR::NodeNotifier::Notifier, void>::type |
|
| 44 | 44 |
> {
|
| 45 |
typedef typename |
|
| 45 |
typedef typename GR::NodeNotifier Type; |
|
| 46 | 46 |
}; |
| 47 | 47 |
|
| 48 |
template <typename _Graph> |
|
| 49 |
class ItemSetTraits<_Graph, typename _Graph::Node> {
|
|
| 48 |
template <typename GR> |
|
| 49 |
class ItemSetTraits<GR, typename GR::Node> {
|
|
| 50 | 50 |
public: |
| 51 | 51 |
|
| 52 |
typedef |
|
| 52 |
typedef GR Graph; |
|
| 53 |
typedef GR Digraph; |
|
| 53 | 54 |
|
| 54 |
typedef typename Graph::Node Item; |
|
| 55 |
typedef typename Graph::NodeIt ItemIt; |
|
| 55 |
typedef typename GR::Node Item; |
|
| 56 |
typedef typename GR::NodeIt ItemIt; |
|
| 56 | 57 |
|
| 57 |
typedef typename NodeNotifierIndicator< |
|
| 58 |
typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier; |
|
| 58 | 59 |
|
| 59 |
template <typename _Value> |
|
| 60 |
class Map : public Graph::template NodeMap<_Value> {
|
|
| 60 |
template <typename V> |
|
| 61 |
class Map : public GR::template NodeMap<V> {
|
|
| 62 |
typedef typename GR::template NodeMap<V> Parent; |
|
| 63 |
|
|
| 61 | 64 |
public: |
| 62 |
typedef typename Graph::template NodeMap<_Value> Parent; |
|
| 63 |
typedef typename Graph::template NodeMap<_Value> Type; |
|
| 65 |
typedef typename GR::template NodeMap<V> Type; |
|
| 64 | 66 |
typedef typename Parent::Value Value; |
| 65 | 67 |
|
| 66 |
Map(const Graph& _digraph) : Parent(_digraph) {}
|
|
| 67 |
Map(const Graph& _digraph, const Value& _value) |
|
| 68 |
Map(const GR& _digraph) : Parent(_digraph) {}
|
|
| 69 |
Map(const GR& _digraph, const Value& _value) |
|
| 68 | 70 |
: Parent(_digraph, _value) {}
|
| 69 | 71 |
|
| 70 | 72 |
}; |
| 71 | 73 |
|
| 72 | 74 |
}; |
| 73 | 75 |
|
| 74 |
template <typename |
|
| 76 |
template <typename GR, typename Enable = void> |
|
| 75 | 77 |
struct ArcNotifierIndicator {
|
| 76 | 78 |
typedef InvalidType Type; |
| 77 | 79 |
}; |
| 78 |
template <typename |
|
| 80 |
template <typename GR> |
|
| 79 | 81 |
struct ArcNotifierIndicator< |
| 80 |
Graph, |
|
| 81 |
typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type |
|
| 82 |
GR, |
|
| 83 |
typename enable_if<typename GR::ArcNotifier::Notifier, void>::type |
|
| 82 | 84 |
> {
|
| 83 |
typedef typename |
|
| 85 |
typedef typename GR::ArcNotifier Type; |
|
| 84 | 86 |
}; |
| 85 | 87 |
|
| 86 |
template <typename _Graph> |
|
| 87 |
class ItemSetTraits<_Graph, typename _Graph::Arc> {
|
|
| 88 |
template <typename GR> |
|
| 89 |
class ItemSetTraits<GR, typename GR::Arc> {
|
|
| 88 | 90 |
public: |
| 89 | 91 |
|
| 90 |
typedef |
|
| 92 |
typedef GR Graph; |
|
| 93 |
typedef GR Digraph; |
|
| 91 | 94 |
|
| 92 |
typedef typename Graph::Arc Item; |
|
| 93 |
typedef typename Graph::ArcIt ItemIt; |
|
| 95 |
typedef typename GR::Arc Item; |
|
| 96 |
typedef typename GR::ArcIt ItemIt; |
|
| 94 | 97 |
|
| 95 |
typedef typename ArcNotifierIndicator< |
|
| 98 |
typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier; |
|
| 96 | 99 |
|
| 97 |
template <typename _Value> |
|
| 98 |
class Map : public Graph::template ArcMap<_Value> {
|
|
| 100 |
template <typename V> |
|
| 101 |
class Map : public GR::template ArcMap<V> {
|
|
| 102 |
typedef typename GR::template ArcMap<V> Parent; |
|
| 103 |
|
|
| 99 | 104 |
public: |
| 100 |
typedef typename Graph::template ArcMap<_Value> Parent; |
|
| 101 |
typedef typename Graph::template ArcMap<_Value> Type; |
|
| 105 |
typedef typename GR::template ArcMap<V> Type; |
|
| 102 | 106 |
typedef typename Parent::Value Value; |
| 103 | 107 |
|
| 104 |
Map(const Graph& _digraph) : Parent(_digraph) {}
|
|
| 105 |
Map(const Graph& _digraph, const Value& _value) |
|
| 108 |
Map(const GR& _digraph) : Parent(_digraph) {}
|
|
| 109 |
Map(const GR& _digraph, const Value& _value) |
|
| 106 | 110 |
: Parent(_digraph, _value) {}
|
| 107 | 111 |
}; |
| 108 | 112 |
|
| 109 | 113 |
}; |
| 110 | 114 |
|
| 111 |
template <typename |
|
| 115 |
template <typename GR, typename Enable = void> |
|
| 112 | 116 |
struct EdgeNotifierIndicator {
|
| 113 | 117 |
typedef InvalidType Type; |
| 114 | 118 |
}; |
| 115 |
template <typename |
|
| 119 |
template <typename GR> |
|
| 116 | 120 |
struct EdgeNotifierIndicator< |
| 117 |
Graph, |
|
| 118 |
typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type |
|
| 121 |
GR, |
|
| 122 |
typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type |
|
| 119 | 123 |
> {
|
| 120 |
typedef typename |
|
| 124 |
typedef typename GR::EdgeNotifier Type; |
|
| 121 | 125 |
}; |
| 122 | 126 |
|
| 123 |
template <typename _Graph> |
|
| 124 |
class ItemSetTraits<_Graph, typename _Graph::Edge> {
|
|
| 127 |
template <typename GR> |
|
| 128 |
class ItemSetTraits<GR, typename GR::Edge> {
|
|
| 125 | 129 |
public: |
| 126 | 130 |
|
| 127 |
typedef |
|
| 131 |
typedef GR Graph; |
|
| 132 |
typedef GR Digraph; |
|
| 128 | 133 |
|
| 129 |
typedef typename Graph::Edge Item; |
|
| 130 |
typedef typename Graph::EdgeIt ItemIt; |
|
| 134 |
typedef typename GR::Edge Item; |
|
| 135 |
typedef typename GR::EdgeIt ItemIt; |
|
| 131 | 136 |
|
| 132 |
typedef typename EdgeNotifierIndicator< |
|
| 137 |
typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier; |
|
| 133 | 138 |
|
| 134 |
template <typename _Value> |
|
| 135 |
class Map : public Graph::template EdgeMap<_Value> {
|
|
| 139 |
template <typename V> |
|
| 140 |
class Map : public GR::template EdgeMap<V> {
|
|
| 141 |
typedef typename GR::template EdgeMap<V> Parent; |
|
| 142 |
|
|
| 136 | 143 |
public: |
| 137 |
typedef typename Graph::template EdgeMap<_Value> Parent; |
|
| 138 |
typedef typename Graph::template EdgeMap<_Value> Type; |
|
| 144 |
typedef typename GR::template EdgeMap<V> Type; |
|
| 139 | 145 |
typedef typename Parent::Value Value; |
| 140 | 146 |
|
| 141 |
Map(const Graph& _digraph) : Parent(_digraph) {}
|
|
| 142 |
Map(const Graph& _digraph, const Value& _value) |
|
| 147 |
Map(const GR& _digraph) : Parent(_digraph) {}
|
|
| 148 |
Map(const GR& _digraph, const Value& _value) |
|
| 143 | 149 |
: Parent(_digraph, _value) {}
|
| 144 | 150 |
}; |
| 145 | 151 |
|
| 146 | 152 |
}; |
| 147 | 153 |
|
| 148 | 154 |
template <typename Map, typename Enable = void> |
| 149 | 155 |
struct MapTraits {
|
| 150 | 156 |
typedef False ReferenceMapTag; |
| 151 | 157 |
|
| 152 | 158 |
typedef typename Map::Key Key; |
| 153 | 159 |
typedef typename Map::Value Value; |
| 154 | 160 |
|
| 155 | 161 |
typedef Value ConstReturnValue; |
| 156 | 162 |
typedef Value ReturnValue; |
| 157 | 163 |
}; |
| 158 | 164 |
|
| 159 | 165 |
template <typename Map> |
| 160 | 166 |
struct MapTraits< |
| 161 | 167 |
Map, typename enable_if<typename Map::ReferenceMapTag, void>::type > |
| 162 | 168 |
{
|
| 163 | 169 |
typedef True ReferenceMapTag; |
| 164 | 170 |
|
| 165 | 171 |
typedef typename Map::Key Key; |
| 166 | 172 |
typedef typename Map::Value Value; |
| ... | ... |
@@ -183,118 +189,118 @@ |
| 183 | 189 |
typedef Value ConstReturnValue; |
| 184 | 190 |
typedef Value ReturnValue; |
| 185 | 191 |
}; |
| 186 | 192 |
|
| 187 | 193 |
template <typename MatrixMap> |
| 188 | 194 |
struct MatrixMapTraits< |
| 189 | 195 |
MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, |
| 190 | 196 |
void>::type > |
| 191 | 197 |
{
|
| 192 | 198 |
typedef True ReferenceMapTag; |
| 193 | 199 |
|
| 194 | 200 |
typedef typename MatrixMap::FirstKey FirstKey; |
| 195 | 201 |
typedef typename MatrixMap::SecondKey SecondKey; |
| 196 | 202 |
typedef typename MatrixMap::Value Value; |
| 197 | 203 |
|
| 198 | 204 |
typedef typename MatrixMap::ConstReference ConstReturnValue; |
| 199 | 205 |
typedef typename MatrixMap::Reference ReturnValue; |
| 200 | 206 |
|
| 201 | 207 |
typedef typename MatrixMap::ConstReference ConstReference; |
| 202 | 208 |
typedef typename MatrixMap::Reference Reference; |
| 203 | 209 |
}; |
| 204 | 210 |
|
| 205 | 211 |
// Indicators for the tags |
| 206 | 212 |
|
| 207 |
template <typename |
|
| 213 |
template <typename GR, typename Enable = void> |
|
| 208 | 214 |
struct NodeNumTagIndicator {
|
| 209 | 215 |
static const bool value = false; |
| 210 | 216 |
}; |
| 211 | 217 |
|
| 212 |
template <typename |
|
| 218 |
template <typename GR> |
|
| 213 | 219 |
struct NodeNumTagIndicator< |
| 214 |
Graph, |
|
| 215 |
typename enable_if<typename Graph::NodeNumTag, void>::type |
|
| 220 |
GR, |
|
| 221 |
typename enable_if<typename GR::NodeNumTag, void>::type |
|
| 216 | 222 |
> {
|
| 217 | 223 |
static const bool value = true; |
| 218 | 224 |
}; |
| 219 | 225 |
|
| 220 |
template <typename |
|
| 226 |
template <typename GR, typename Enable = void> |
|
| 221 | 227 |
struct ArcNumTagIndicator {
|
| 222 | 228 |
static const bool value = false; |
| 223 | 229 |
}; |
| 224 | 230 |
|
| 225 |
template <typename |
|
| 231 |
template <typename GR> |
|
| 226 | 232 |
struct ArcNumTagIndicator< |
| 227 |
Graph, |
|
| 228 |
typename enable_if<typename Graph::ArcNumTag, void>::type |
|
| 233 |
GR, |
|
| 234 |
typename enable_if<typename GR::ArcNumTag, void>::type |
|
| 229 | 235 |
> {
|
| 230 | 236 |
static const bool value = true; |
| 231 | 237 |
}; |
| 232 | 238 |
|
| 233 |
template <typename |
|
| 239 |
template <typename GR, typename Enable = void> |
|
| 234 | 240 |
struct EdgeNumTagIndicator {
|
| 235 | 241 |
static const bool value = false; |
| 236 | 242 |
}; |
| 237 | 243 |
|
| 238 |
template <typename |
|
| 244 |
template <typename GR> |
|
| 239 | 245 |
struct EdgeNumTagIndicator< |
| 240 |
Graph, |
|
| 241 |
typename enable_if<typename Graph::EdgeNumTag, void>::type |
|
| 246 |
GR, |
|
| 247 |
typename enable_if<typename GR::EdgeNumTag, void>::type |
|
| 242 | 248 |
> {
|
| 243 | 249 |
static const bool value = true; |
| 244 | 250 |
}; |
| 245 | 251 |
|
| 246 |
template <typename |
|
| 252 |
template <typename GR, typename Enable = void> |
|
| 247 | 253 |
struct FindArcTagIndicator {
|
| 248 | 254 |
static const bool value = false; |
| 249 | 255 |
}; |
| 250 | 256 |
|
| 251 |
template <typename |
|
| 257 |
template <typename GR> |
|
| 252 | 258 |
struct FindArcTagIndicator< |
| 253 |
Graph, |
|
| 254 |
typename enable_if<typename Graph::FindArcTag, void>::type |
|
| 259 |
GR, |
|
| 260 |
typename enable_if<typename GR::FindArcTag, void>::type |
|
| 255 | 261 |
> {
|
| 256 | 262 |
static const bool value = true; |
| 257 | 263 |
}; |
| 258 | 264 |
|
| 259 |
template <typename |
|
| 265 |
template <typename GR, typename Enable = void> |
|
| 260 | 266 |
struct FindEdgeTagIndicator {
|
| 261 | 267 |
static const bool value = false; |
| 262 | 268 |
}; |
| 263 | 269 |
|
| 264 |
template <typename |
|
| 270 |
template <typename GR> |
|
| 265 | 271 |
struct FindEdgeTagIndicator< |
| 266 |
Graph, |
|
| 267 |
typename enable_if<typename Graph::FindEdgeTag, void>::type |
|
| 272 |
GR, |
|
| 273 |
typename enable_if<typename GR::FindEdgeTag, void>::type |
|
| 268 | 274 |
> {
|
| 269 | 275 |
static const bool value = true; |
| 270 | 276 |
}; |
| 271 | 277 |
|
| 272 |
template <typename |
|
| 278 |
template <typename GR, typename Enable = void> |
|
| 273 | 279 |
struct UndirectedTagIndicator {
|
| 274 | 280 |
static const bool value = false; |
| 275 | 281 |
}; |
| 276 | 282 |
|
| 277 |
template <typename |
|
| 283 |
template <typename GR> |
|
| 278 | 284 |
struct UndirectedTagIndicator< |
| 279 |
Graph, |
|
| 280 |
typename enable_if<typename Graph::UndirectedTag, void>::type |
|
| 285 |
GR, |
|
| 286 |
typename enable_if<typename GR::UndirectedTag, void>::type |
|
| 281 | 287 |
> {
|
| 282 | 288 |
static const bool value = true; |
| 283 | 289 |
}; |
| 284 | 290 |
|
| 285 |
template <typename |
|
| 291 |
template <typename GR, typename Enable = void> |
|
| 286 | 292 |
struct BuildTagIndicator {
|
| 287 | 293 |
static const bool value = false; |
| 288 | 294 |
}; |
| 289 | 295 |
|
| 290 |
template <typename |
|
| 296 |
template <typename GR> |
|
| 291 | 297 |
struct BuildTagIndicator< |
| 292 |
Graph, |
|
| 293 |
typename enable_if<typename Graph::BuildTag, void>::type |
|
| 298 |
GR, |
|
| 299 |
typename enable_if<typename GR::BuildTag, void>::type |
|
| 294 | 300 |
> {
|
| 295 | 301 |
static const bool value = true; |
| 296 | 302 |
}; |
| 297 | 303 |
|
| 298 | 304 |
} |
| 299 | 305 |
|
| 300 | 306 |
#endif |
| ... | ... |
@@ -699,49 +699,49 @@ |
| 699 | 699 |
.onlyOneGroup("dist")
|
| 700 | 700 |
.boolOption("eps", "Also generate .eps output (prefix.eps)")
|
| 701 | 701 |
.boolOption("nonodes", "Draw the edges only in the generated .eps")
|
| 702 | 702 |
.boolOption("dir", "Directed digraph is generated (each arcs are replaced by two directed ones)")
|
| 703 | 703 |
.boolOption("2con", "Create a two connected planar digraph")
|
| 704 | 704 |
.optionGroup("alg","2con")
|
| 705 | 705 |
.boolOption("tree", "Create a min. cost spanning tree")
|
| 706 | 706 |
.optionGroup("alg","tree")
|
| 707 | 707 |
.boolOption("tsp", "Create a TSP tour")
|
| 708 | 708 |
.optionGroup("alg","tsp")
|
| 709 | 709 |
.boolOption("tsp2", "Create a TSP tour (tree based)")
|
| 710 | 710 |
.optionGroup("alg","tsp2")
|
| 711 | 711 |
.boolOption("dela", "Delaunay triangulation digraph")
|
| 712 | 712 |
.optionGroup("alg","dela")
|
| 713 | 713 |
.onlyOneGroup("alg")
|
| 714 | 714 |
.boolOption("rand", "Use time seed for random number generator")
|
| 715 | 715 |
.optionGroup("rand", "rand")
|
| 716 | 716 |
.intOption("seed", "Random seed", -1)
|
| 717 | 717 |
.optionGroup("rand", "seed")
|
| 718 | 718 |
.onlyOneGroup("rand")
|
| 719 | 719 |
.other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'")
|
| 720 | 720 |
.run(); |
| 721 | 721 |
|
| 722 | 722 |
if (ap["rand"]) {
|
| 723 |
int seed = time(0); |
|
| 723 |
int seed = int(time(0)); |
|
| 724 | 724 |
std::cout << "Random number seed: " << seed << std::endl; |
| 725 | 725 |
rnd = Random(seed); |
| 726 | 726 |
} |
| 727 | 727 |
if (ap.given("seed")) {
|
| 728 | 728 |
int seed = ap["seed"]; |
| 729 | 729 |
std::cout << "Random number seed: " << seed << std::endl; |
| 730 | 730 |
rnd = Random(seed); |
| 731 | 731 |
} |
| 732 | 732 |
|
| 733 | 733 |
std::string prefix; |
| 734 | 734 |
switch(ap.files().size()) |
| 735 | 735 |
{
|
| 736 | 736 |
case 0: |
| 737 | 737 |
prefix="lgf-gen-out"; |
| 738 | 738 |
break; |
| 739 | 739 |
case 1: |
| 740 | 740 |
prefix=ap.files()[0]; |
| 741 | 741 |
break; |
| 742 | 742 |
default: |
| 743 | 743 |
std::cerr << "\nAt most one prefix can be given\n\n"; |
| 744 | 744 |
exit(1); |
| 745 | 745 |
} |
| 746 | 746 |
|
| 747 | 747 |
double sum_sizes=0; |
0 comments (0 inline)