Changes in / [621:b536eaacb39b:624:1f631044c290] in lemon-main
- Files:
-
- 28 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/graph_to_eps_demo.cc
r440 r612 183 183 ListDigraph::NodeMap<Point> hcoords(h); 184 184 185 int cols=int(s qrt(double(palette.size())));185 int cols=int(std::sqrt(double(palette.size()))); 186 186 for(int i=0;i<int(paletteW.size());i++) { 187 187 Node n=h.addNode(); -
lemon/adaptors.h
r579 r617 110 110 template <typename V> 111 111 class NodeMap : public DGR::template NodeMap<V> { 112 typedef typename DGR::template NodeMap<V> Parent; 113 112 114 public: 113 114 typedef typename DGR::template NodeMap<V> Parent;115 116 115 explicit NodeMap(const Adaptor& adaptor) 117 116 : Parent(*adaptor._digraph) {} 118 119 117 NodeMap(const Adaptor& adaptor, const V& value) 120 118 : Parent(*adaptor._digraph, value) { } … … 135 133 template <typename V> 136 134 class ArcMap : public DGR::template ArcMap<V> { 135 typedef typename DGR::template ArcMap<V> Parent; 136 137 137 public: 138 139 typedef typename DGR::template ArcMap<V> Parent;140 141 138 explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor) 142 139 : Parent(*adaptor._digraph) {} 143 144 140 ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value) 145 141 : Parent(*adaptor._digraph, value) {} … … 256 252 template <typename V> 257 253 class NodeMap : public GR::template NodeMap<V> { 254 typedef typename GR::template NodeMap<V> Parent; 255 258 256 public: 259 typedef typename GR::template NodeMap<V> Parent;260 257 explicit NodeMap(const GraphAdaptorBase<GR>& adapter) 261 258 : Parent(*adapter._graph) {} … … 278 275 template <typename V> 279 276 class ArcMap : public GR::template ArcMap<V> { 277 typedef typename GR::template ArcMap<V> Parent; 278 280 279 public: 281 typedef typename GR::template ArcMap<V> Parent;282 280 explicit ArcMap(const GraphAdaptorBase<GR>& adapter) 283 281 : Parent(*adapter._graph) {} … … 299 297 template <typename V> 300 298 class EdgeMap : public GR::template EdgeMap<V> { 299 typedef typename GR::template EdgeMap<V> Parent; 300 301 301 public: 302 typedef typename GR::template EdgeMap<V> Parent;303 302 explicit EdgeMap(const GraphAdaptorBase<GR>& adapter) 304 303 : Parent(*adapter._graph) {} … … 322 321 template <typename DGR> 323 322 class ReverseDigraphBase : public DigraphAdaptorBase<DGR> { 323 typedef DigraphAdaptorBase<DGR> Parent; 324 324 public: 325 325 typedef DGR Digraph; 326 typedef DigraphAdaptorBase<DGR> Parent;327 326 protected: 328 327 ReverseDigraphBase() : Parent() { } … … 375 374 public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > { 376 375 #endif 376 typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent; 377 377 public: 378 378 /// The type of the adapted digraph. 379 379 typedef DGR Digraph; 380 typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent;381 380 protected: 382 381 ReverseDigraph() { } … … 404 403 template <typename DGR, typename NF, typename AF, bool ch = true> 405 404 class SubDigraphBase : public DigraphAdaptorBase<DGR> { 405 typedef DigraphAdaptorBase<DGR> Parent; 406 406 public: 407 407 typedef DGR Digraph; … … 410 410 411 411 typedef SubDigraphBase Adaptor; 412 typedef DigraphAdaptorBase<DGR> Parent;413 412 protected: 414 413 NF* _node_filter; … … 510 509 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 511 510 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 511 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 512 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 513 512 514 public: 513 515 typedef V Value; 514 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,515 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;516 516 517 517 NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) … … 536 536 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 537 537 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 538 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 539 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 540 538 541 public: 539 542 typedef V Value; 540 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,541 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;542 543 543 544 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) … … 563 564 class SubDigraphBase<DGR, NF, AF, false> 564 565 : public DigraphAdaptorBase<DGR> { 566 typedef DigraphAdaptorBase<DGR> Parent; 565 567 public: 566 568 typedef DGR Digraph; … … 569 571 570 572 typedef SubDigraphBase Adaptor; 571 typedef DigraphAdaptorBase<Digraph> Parent;572 573 protected: 573 574 NF* _node_filter; … … 651 652 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 652 653 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 654 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 655 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 656 653 657 public: 654 658 typedef V Value; 655 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,656 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;657 659 658 660 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) … … 677 679 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 678 680 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 681 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 682 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 683 679 684 public: 680 685 typedef V Value; 681 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,682 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;683 686 684 687 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) … … 864 867 template <typename GR, typename NF, typename EF, bool ch = true> 865 868 class SubGraphBase : public GraphAdaptorBase<GR> { 869 typedef GraphAdaptorBase<GR> Parent; 866 870 public: 867 871 typedef GR Graph; … … 870 874 871 875 typedef SubGraphBase Adaptor; 872 typedef GraphAdaptorBase<GR> Parent;873 876 protected: 874 877 … … 1017 1020 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1018 1021 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1022 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1023 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1024 1019 1025 public: 1020 1026 typedef V Value; 1021 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,1022 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;1023 1027 1024 1028 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) … … 1043 1047 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1044 1048 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1049 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1050 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1051 1045 1052 public: 1046 1053 typedef V Value; 1047 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,1048 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;1049 1054 1050 1055 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) … … 1069 1074 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1070 1075 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1076 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1077 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1078 1071 1079 public: 1072 1080 typedef V Value; 1073 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,1074 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;1075 1081 1076 1082 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) … … 1097 1103 class SubGraphBase<GR, NF, EF, false> 1098 1104 : public GraphAdaptorBase<GR> { 1105 typedef GraphAdaptorBase<GR> Parent; 1099 1106 public: 1100 1107 typedef GR Graph; … … 1103 1110 1104 1111 typedef SubGraphBase Adaptor; 1105 typedef GraphAdaptorBase<GR> Parent;1106 1112 protected: 1107 1113 NF* _node_filter; … … 1212 1218 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1213 1219 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1220 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1221 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1222 1214 1223 public: 1215 1224 typedef V Value; 1216 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,1217 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;1218 1225 1219 1226 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) … … 1238 1245 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1239 1246 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1247 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1248 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1249 1240 1250 public: 1241 1251 typedef V Value; 1242 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,1243 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;1244 1252 1245 1253 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor) … … 1264 1272 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1265 1273 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1274 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1275 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1276 1266 1277 public: 1267 1278 typedef V Value; 1268 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,1269 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;1270 1279 1271 1280 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) … … 1486 1495 true> > { 1487 1496 #endif 1488 public:1489 1490 typedef GR Digraph;1491 typedef NF NodeFilterMap;1492 1493 1497 typedef DigraphAdaptorExtender< 1494 1498 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1495 1499 true> > Parent; 1500 1501 public: 1502 1503 typedef GR Digraph; 1504 typedef NF NodeFilterMap; 1496 1505 1497 1506 typedef typename Parent::Node Node; … … 1549 1558 true> > { 1550 1559 1551 public:1552 typedef GR Graph;1553 typedef NF NodeFilterMap;1554 1560 typedef GraphAdaptorExtender< 1555 1561 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1556 1562 true> > Parent; 1557 1563 1564 public: 1565 1566 typedef GR Graph; 1567 typedef NF NodeFilterMap; 1568 1558 1569 typedef typename Parent::Node Node; 1570 1559 1571 protected: 1560 1572 ConstMap<typename GR::Edge, Const<bool, true> > const_true_map; … … 1630 1642 AF, false> > { 1631 1643 #endif 1632 public: 1644 typedef DigraphAdaptorExtender< 1645 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1646 AF, false> > Parent; 1647 1648 public: 1649 1633 1650 /// The type of the adapted digraph. 1634 1651 typedef DGR Digraph; 1635 1652 /// The type of the arc filter map. 1636 1653 typedef AF ArcFilterMap; 1637 1638 typedef DigraphAdaptorExtender<1639 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,1640 AF, false> > Parent;1641 1654 1642 1655 typedef typename Parent::Arc Arc; … … 1739 1752 EF, false> > { 1740 1753 #endif 1741 public: 1754 typedef GraphAdaptorExtender< 1755 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1756 EF, false> > Parent; 1757 1758 public: 1759 1742 1760 /// The type of the adapted graph. 1743 1761 typedef GR Graph; 1744 1762 /// The type of the edge filter map. 1745 1763 typedef EF EdgeFilterMap; 1746 1747 typedef GraphAdaptorExtender<1748 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,1749 EF, false> > Parent;1750 1764 1751 1765 typedef typename Parent::Edge Edge; … … 2112 2126 template <typename V> 2113 2127 class NodeMap : public DGR::template NodeMap<V> { 2128 typedef typename DGR::template NodeMap<V> Parent; 2129 2114 2130 public: 2115 2116 2131 typedef V Value; 2117 typedef typename DGR::template NodeMap<Value> Parent;2118 2132 2119 2133 explicit NodeMap(const UndirectorBase<DGR>& adaptor) … … 2138 2152 template <typename V> 2139 2153 class ArcMap 2140 : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > 2141 { 2154 : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > { 2155 typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent; 2156 2142 2157 public: 2143 2158 typedef V Value; 2144 typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;2145 2159 2146 2160 explicit ArcMap(const UndirectorBase<DGR>& adaptor) … … 2164 2178 template <typename V> 2165 2179 class EdgeMap : public Digraph::template ArcMap<V> { 2180 typedef typename Digraph::template ArcMap<V> Parent; 2181 2166 2182 public: 2167 2168 2183 typedef V Value; 2169 typedef typename Digraph::template ArcMap<V> Parent;2170 2184 2171 2185 explicit EdgeMap(const UndirectorBase<DGR>& adaptor) … … 2239 2253 public GraphAdaptorExtender<UndirectorBase<DGR> > { 2240 2254 #endif 2255 typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent; 2241 2256 public: 2242 2257 /// The type of the adapted digraph. 2243 2258 typedef DGR Digraph; 2244 typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;2245 2259 protected: 2246 2260 Undirector() { } … … 2450 2464 template <typename V> 2451 2465 class NodeMap : public GR::template NodeMap<V> { 2466 typedef typename GR::template NodeMap<V> Parent; 2467 2452 2468 public: 2453 2454 typedef typename GR::template NodeMap<V> Parent;2455 2469 2456 2470 explicit NodeMap(const OrienterBase<GR, DM>& adapter) … … 2475 2489 template <typename V> 2476 2490 class ArcMap : public GR::template EdgeMap<V> { 2491 typedef typename Graph::template EdgeMap<V> Parent; 2492 2477 2493 public: 2478 2479 typedef typename Graph::template EdgeMap<V> Parent;2480 2494 2481 2495 explicit ArcMap(const OrienterBase<GR, DM>& adapter) … … 2547 2561 public DigraphAdaptorExtender<OrienterBase<GR, DM> > { 2548 2562 #endif 2563 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent; 2549 2564 public: 2550 2565 … … 2554 2569 typedef DM DirectionMap; 2555 2570 2556 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;2557 2571 typedef typename Parent::Arc Arc; 2572 2558 2573 protected: 2559 2574 Orienter() { } 2575 2560 2576 public: 2561 2577 … … 2867 2883 template <typename DGR> 2868 2884 class SplitNodesBase { 2885 typedef DigraphAdaptorBase<const DGR> Parent; 2886 2869 2887 public: 2870 2888 2871 2889 typedef DGR Digraph; 2872 typedef DigraphAdaptorBase<const DGR> Parent;2873 2890 typedef SplitNodesBase Adaptor; 2874 2891 … … 3229 3246 template <typename V> 3230 3247 class NodeMap 3231 : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > 3232 { 3248 : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > { 3249 typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent; 3250 3233 3251 public: 3234 3252 typedef V Value; 3235 typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;3236 3253 3237 3254 NodeMap(const SplitNodesBase<DGR>& adaptor) … … 3255 3272 template <typename V> 3256 3273 class ArcMap 3257 : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > 3258 { 3274 : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > { 3275 typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent; 3276 3259 3277 public: 3260 3278 typedef V Value; 3261 typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;3262 3279 3263 3280 ArcMap(const SplitNodesBase<DGR>& adaptor) … … 3325 3342 : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > { 3326 3343 #endif 3344 typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent; 3345 3327 3346 public: 3328 3347 typedef DGR Digraph; 3329 typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent;3330 3348 3331 3349 typedef typename DGR::Node DigraphNode; -
lemon/bits/array_map.h
r503 r617 48 48 public: 49 49 // The graph type. 50 typedef _Graph Graph ;50 typedef _Graph GraphType; 51 51 // The item type. 52 52 typedef _Item Item; … … 64 64 typedef _Value& Reference; 65 65 66 // The map type. 67 typedef ArrayMap Map; 68 66 69 // The notifier type. 67 70 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier; 68 71 72 private: 73 69 74 // The MapBase of the Map which imlements the core regisitry function. 70 75 typedef typename Notifier::ObserverBase Parent; 71 76 72 private:73 77 typedef std::allocator<Value> Allocator; 74 78 … … 78 82 // 79 83 // Graph initialized map constructor. 80 explicit ArrayMap(const Graph & graph) {84 explicit ArrayMap(const GraphType& graph) { 81 85 Parent::attach(graph.notifier(Item())); 82 86 allocate_memory(); … … 92 96 // 93 97 // It constructs a map and initialize all of the the map. 94 ArrayMap(const Graph & graph, const Value& value) {98 ArrayMap(const GraphType& graph, const Value& value) { 95 99 Parent::attach(graph.notifier(Item())); 96 100 allocate_memory(); -
lemon/bits/base_extender.h
r440 r617 39 39 template <typename Base> 40 40 class UndirDigraphExtender : public Base { 41 typedef Base Parent; 41 42 42 43 public: 43 44 44 typedef Base Parent;45 45 typedef typename Parent::Arc Edge; 46 46 typedef typename Parent::Node Node; … … 281 281 template <typename Base> 282 282 class BidirBpGraphExtender : public Base { 283 typedef Base Parent; 284 283 285 public: 284 typedef Base Parent;285 286 typedef BidirBpGraphExtender Digraph; 286 287 -
lemon/bits/default_map.h
r535 r617 154 154 class DefaultMap 155 155 : public DefaultMapSelector<_Graph, _Item, _Value>::Map { 156 typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent; 157 156 158 public: 157 typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;158 159 typedef DefaultMap<_Graph, _Item, _Value> Map; 159 160 typedef typename Parent::Graph Graph;160 161 typedef typename Parent::GraphType GraphType; 161 162 typedef typename Parent::Value Value; 162 163 163 explicit DefaultMap(const Graph & graph) : Parent(graph) {}164 DefaultMap(const Graph & graph, const Value& value)164 explicit DefaultMap(const GraphType& graph) : Parent(graph) {} 165 DefaultMap(const GraphType& graph, const Value& value) 165 166 : Parent(graph, value) {} 166 167 -
lemon/bits/edge_set_extender.h
r559 r617 35 35 template <typename Base> 36 36 class ArcSetExtender : public Base { 37 typedef Base Parent; 38 37 39 public: 38 40 39 typedef Base Parent;40 41 typedef ArcSetExtender Digraph; 41 42 … … 219 220 class ArcMap 220 221 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 221 public:222 typedef ArcSetExtender Digraph;223 222 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 224 223 224 public: 225 225 explicit ArcMap(const Digraph& _g) 226 226 : Parent(_g) {} … … 275 275 template <typename Base> 276 276 class EdgeSetExtender : public Base { 277 typedef Base Parent; 277 278 278 279 public: 279 280 280 typedef Base Parent; 281 typedef EdgeSetExtender Digraph; 281 typedef EdgeSetExtender Graph; 282 282 283 283 typedef typename Parent::Node Node; 284 284 typedef typename Parent::Arc Arc; 285 285 typedef typename Parent::Edge Edge; 286 287 286 288 287 int maxId(Node) const { … … 351 350 352 351 class NodeIt : public Node { 353 const Digraph* digraph;352 const Graph* graph; 354 353 public: 355 354 … … 358 357 NodeIt(Invalid i) : Node(i) { } 359 358 360 explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {359 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 361 360 _graph.first(static_cast<Node&>(*this)); 362 361 } 363 362 364 NodeIt(const Digraph& _graph, const Node& node)365 : Node(node), digraph(&_graph) {}363 NodeIt(const Graph& _graph, const Node& node) 364 : Node(node), graph(&_graph) {} 366 365 367 366 NodeIt& operator++() { 368 digraph->next(*this);367 graph->next(*this); 369 368 return *this; 370 369 } … … 374 373 375 374 class ArcIt : public Arc { 376 const Digraph* digraph;375 const Graph* graph; 377 376 public: 378 377 … … 381 380 ArcIt(Invalid i) : Arc(i) { } 382 381 383 explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {382 explicit ArcIt(const Graph& _graph) : graph(&_graph) { 384 383 _graph.first(static_cast<Arc&>(*this)); 385 384 } 386 385 387 ArcIt(const Digraph& _graph, const Arc& e) :388 Arc(e), digraph(&_graph) { }386 ArcIt(const Graph& _graph, const Arc& e) : 387 Arc(e), graph(&_graph) { } 389 388 390 389 ArcIt& operator++() { 391 digraph->next(*this);390 graph->next(*this); 392 391 return *this; 393 392 } … … 397 396 398 397 class OutArcIt : public Arc { 399 const Digraph* digraph;398 const Graph* graph; 400 399 public: 401 400 … … 404 403 OutArcIt(Invalid i) : Arc(i) { } 405 404 406 OutArcIt(const Digraph& _graph, const Node& node)407 : digraph(&_graph) {405 OutArcIt(const Graph& _graph, const Node& node) 406 : graph(&_graph) { 408 407 _graph.firstOut(*this, node); 409 408 } 410 409 411 OutArcIt(const Digraph& _graph, const Arc& arc)412 : Arc(arc), digraph(&_graph) {}410 OutArcIt(const Graph& _graph, const Arc& arc) 411 : Arc(arc), graph(&_graph) {} 413 412 414 413 OutArcIt& operator++() { 415 digraph->nextOut(*this);414 graph->nextOut(*this); 416 415 return *this; 417 416 } … … 421 420 422 421 class InArcIt : public Arc { 423 const Digraph* digraph;422 const Graph* graph; 424 423 public: 425 424 … … 428 427 InArcIt(Invalid i) : Arc(i) { } 429 428 430 InArcIt(const Digraph& _graph, const Node& node)431 : digraph(&_graph) {429 InArcIt(const Graph& _graph, const Node& node) 430 : graph(&_graph) { 432 431 _graph.firstIn(*this, node); 433 432 } 434 433 435 InArcIt(const Digraph& _graph, const Arc& arc) :436 Arc(arc), digraph(&_graph) {}434 InArcIt(const Graph& _graph, const Arc& arc) : 435 Arc(arc), graph(&_graph) {} 437 436 438 437 InArcIt& operator++() { 439 digraph->nextIn(*this);438 graph->nextIn(*this); 440 439 return *this; 441 440 } … … 445 444 446 445 class EdgeIt : public Parent::Edge { 447 const Digraph* digraph;446 const Graph* graph; 448 447 public: 449 448 … … 452 451 EdgeIt(Invalid i) : Edge(i) { } 453 452 454 explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {453 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 455 454 _graph.first(static_cast<Edge&>(*this)); 456 455 } 457 456 458 EdgeIt(const Digraph& _graph, const Edge& e) :459 Edge(e), digraph(&_graph) { }457 EdgeIt(const Graph& _graph, const Edge& e) : 458 Edge(e), graph(&_graph) { } 460 459 461 460 EdgeIt& operator++() { 462 digraph->next(*this);461 graph->next(*this); 463 462 return *this; 464 463 } … … 468 467 class IncEdgeIt : public Parent::Edge { 469 468 friend class EdgeSetExtender; 470 const Digraph* digraph;469 const Graph* graph; 471 470 bool direction; 472 471 public: … … 476 475 IncEdgeIt(Invalid i) : Edge(i), direction(false) { } 477 476 478 IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {477 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 479 478 _graph.firstInc(*this, direction, n); 480 479 } 481 480 482 IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)483 : digraph(&_graph), Edge(ue) {481 IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) 482 : graph(&_graph), Edge(ue) { 484 483 direction = (_graph.source(ue) == n); 485 484 } 486 485 487 486 IncEdgeIt& operator++() { 488 digraph->nextInc(*this, direction);487 graph->nextInc(*this, direction); 489 488 return *this; 490 489 } … … 535 534 template <typename _Value> 536 535 class ArcMap 537 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 538 public: 539 typedef EdgeSetExtender Digraph; 540 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 541 542 ArcMap(const Digraph& _g) 536 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 537 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 538 539 public: 540 ArcMap(const Graph& _g) 543 541 : Parent(_g) {} 544 ArcMap(const Digraph& _g, const _Value& _v)542 ArcMap(const Graph& _g, const _Value& _v) 545 543 : Parent(_g, _v) {} 546 544 … … 560 558 template <typename _Value> 561 559 class EdgeMap 562 : public MapExtender<DefaultMap<Digraph, Edge, _Value> > { 563 public: 564 typedef EdgeSetExtender Digraph; 565 typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent; 566 567 EdgeMap(const Digraph& _g) 560 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 561 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 562 563 public: 564 EdgeMap(const Graph& _g) 568 565 : Parent(_g) {} 569 566 570 EdgeMap(const Digraph& _g, const _Value& _v)567 EdgeMap(const Graph& _g, const _Value& _v) 571 568 : Parent(_g, _v) {} 572 569 -
lemon/bits/graph_adaptor_extender.h
r580 r617 27 27 template <typename _Digraph> 28 28 class DigraphAdaptorExtender : public _Digraph { 29 typedef _Digraph Parent; 30 29 31 public: 30 32 31 typedef _Digraph Parent;32 33 typedef _Digraph Digraph; 33 34 typedef DigraphAdaptorExtender Adaptor; … … 174 175 template <typename _Graph> 175 176 class GraphAdaptorExtender : public _Graph { 177 typedef _Graph Parent; 178 176 179 public: 177 180 178 typedef _Graph Parent;179 181 typedef _Graph Graph; 180 182 typedef GraphAdaptorExtender Adaptor; -
lemon/bits/graph_extender.h
r440 r617 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { 40 typedef Base Parent; 41 40 42 public: 41 43 42 typedef Base Parent;43 44 typedef DigraphExtender Digraph; 44 45 … … 219 220 class NodeMap 220 221 : public MapExtender<DefaultMap<Digraph, Node, _Value> > { 221 public:222 typedef DigraphExtender Digraph;223 222 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent; 224 223 224 public: 225 225 explicit NodeMap(const Digraph& digraph) 226 226 : Parent(digraph) {} … … 244 244 class ArcMap 245 245 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 246 public:247 typedef DigraphExtender Digraph;248 246 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 249 247 248 public: 250 249 explicit ArcMap(const Digraph& digraph) 251 250 : Parent(digraph) {} … … 331 330 template <typename Base> 332 331 class GraphExtender : public Base { 332 typedef Base Parent; 333 333 334 public: 334 335 335 typedef Base Parent;336 336 typedef GraphExtender Graph; 337 337 … … 602 602 class NodeMap 603 603 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 604 public:605 typedef GraphExtender Graph;606 604 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 607 605 606 public: 608 607 NodeMap(const Graph& graph) 609 608 : Parent(graph) {} … … 627 626 class ArcMap 628 627 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 629 public:630 typedef GraphExtender Graph;631 628 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 632 629 630 public: 633 631 ArcMap(const Graph& graph) 634 632 : Parent(graph) {} … … 652 650 class EdgeMap 653 651 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 654 public:655 typedef GraphExtender Graph;656 652 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 657 653 654 public: 658 655 EdgeMap(const Graph& graph) 659 656 : Parent(graph) {} -
lemon/bits/map_extender.h
r580 r617 37 37 template <typename _Map> 38 38 class MapExtender : public _Map { 39 public:40 41 39 typedef _Map Parent; 40 typedef typename Parent::GraphType GraphType; 41 42 public: 43 42 44 typedef MapExtender Map; 43 44 45 typedef typename Parent::Graph Graph;46 45 typedef typename Parent::Key Item; 47 46 … … 59 58 public: 60 59 61 MapExtender(const Graph & graph)60 MapExtender(const GraphType& graph) 62 61 : Parent(graph) {} 63 62 64 MapExtender(const Graph & graph, const Value& value)63 MapExtender(const GraphType& graph, const Value& value) 65 64 : Parent(graph, value) {} 66 65 … … 78 77 public: 79 78 class MapIt : public Item { 80 public: 81 82 typedef Item Parent; 79 typedef Item Parent; 80 81 public: 82 83 83 typedef typename Map::Value Value; 84 84 … … 117 117 118 118 class ConstMapIt : public Item { 119 public:120 121 typedef Item Parent;119 typedef Item Parent; 120 121 public: 122 122 123 123 typedef typename Map::Value Value; … … 148 148 149 149 class ItemIt : public Item { 150 public:151 152 typedef Item Parent;150 typedef Item Parent; 151 152 public: 153 153 154 154 ItemIt() {} … … 179 179 template <typename _Graph, typename _Map> 180 180 class SubMapExtender : public _Map { 181 public:182 183 181 typedef _Map Parent; 182 typedef _Graph GraphType; 183 184 public: 185 184 186 typedef SubMapExtender Map; 185 186 typedef _Graph Graph;187 188 187 typedef typename Parent::Key Item; 189 188 … … 201 200 public: 202 201 203 SubMapExtender(const Graph & _graph)202 SubMapExtender(const GraphType& _graph) 204 203 : Parent(_graph), graph(_graph) {} 205 204 206 SubMapExtender(const Graph & _graph, const Value& _value)205 SubMapExtender(const GraphType& _graph, const Value& _value) 207 206 : Parent(_graph, _value), graph(_graph) {} 208 207 … … 224 223 public: 225 224 class MapIt : public Item { 226 public:227 228 typedef Item Parent;225 typedef Item Parent; 226 227 public: 229 228 typedef typename Map::Value Value; 230 229 … … 263 262 264 263 class ConstMapIt : public Item { 265 public:266 267 typedef Item Parent;264 typedef Item Parent; 265 266 public: 268 267 269 268 typedef typename Map::Value Value; … … 294 293 295 294 class ItemIt : public Item { 296 public:297 298 typedef Item Parent;295 typedef Item Parent; 296 297 public: 299 298 300 299 ItemIt() {} … … 321 320 private: 322 321 323 const Graph & graph;322 const GraphType& graph; 324 323 325 324 }; -
lemon/bits/traits.h
r440 r616 30 30 struct InvalidType {}; 31 31 32 template <typename _Graph, typename _Item>32 template <typename GR, typename _Item> 33 33 class ItemSetTraits {}; 34 34 35 35 36 template <typename G raph, typename Enable = void>36 template <typename GR, typename Enable = void> 37 37 struct NodeNotifierIndicator { 38 38 typedef InvalidType Type; 39 39 }; 40 template <typename G raph>40 template <typename GR> 41 41 struct NodeNotifierIndicator< 42 G raph,43 typename enable_if<typename G raph::NodeNotifier::Notifier, void>::type44 > { 45 typedef typename G raph::NodeNotifier Type;46 }; 47 48 template <typename _Graph>49 class ItemSetTraits< _Graph, typename _Graph::Node> {42 GR, 43 typename enable_if<typename GR::NodeNotifier::Notifier, void>::type 44 > { 45 typedef typename GR::NodeNotifier Type; 46 }; 47 48 template <typename GR> 49 class ItemSetTraits<GR, typename GR::Node> { 50 50 public: 51 51 52 typedef _Graph Graph; 53 54 typedef typename Graph::Node Item; 55 typedef typename Graph::NodeIt ItemIt; 56 57 typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier; 58 59 template <typename _Value> 60 class Map : public Graph::template NodeMap<_Value> { 52 typedef GR Graph; 53 typedef GR Digraph; 54 55 typedef typename GR::Node Item; 56 typedef typename GR::NodeIt ItemIt; 57 58 typedef typename NodeNotifierIndicator<GR>::Type ItemNotifier; 59 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 G raph& _digraph) : Parent(_digraph) {}67 Map(const G raph& _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 … … 72 74 }; 73 75 74 template <typename G raph, typename Enable = void>76 template <typename GR, typename Enable = void> 75 77 struct ArcNotifierIndicator { 76 78 typedef InvalidType Type; 77 79 }; 78 template <typename G raph>80 template <typename GR> 79 81 struct ArcNotifierIndicator< 80 G raph,81 typename enable_if<typename G raph::ArcNotifier::Notifier, void>::type82 > { 83 typedef typename G raph::ArcNotifier Type;84 }; 85 86 template <typename _Graph>87 class ItemSetTraits< _Graph, typename _Graph::Arc> {82 GR, 83 typename enable_if<typename GR::ArcNotifier::Notifier, void>::type 84 > { 85 typedef typename GR::ArcNotifier Type; 86 }; 87 88 template <typename GR> 89 class ItemSetTraits<GR, typename GR::Arc> { 88 90 public: 89 91 90 typedef _Graph Graph; 91 92 typedef typename Graph::Arc Item; 93 typedef typename Graph::ArcIt ItemIt; 94 95 typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier; 96 97 template <typename _Value> 98 class Map : public Graph::template ArcMap<_Value> { 92 typedef GR Graph; 93 typedef GR Digraph; 94 95 typedef typename GR::Arc Item; 96 typedef typename GR::ArcIt ItemIt; 97 98 typedef typename ArcNotifierIndicator<GR>::Type ItemNotifier; 99 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 G raph& _digraph) : Parent(_digraph) {}105 Map(const G raph& _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 }; … … 109 113 }; 110 114 111 template <typename G raph, typename Enable = void>115 template <typename GR, typename Enable = void> 112 116 struct EdgeNotifierIndicator { 113 117 typedef InvalidType Type; 114 118 }; 115 template <typename G raph>119 template <typename GR> 116 120 struct EdgeNotifierIndicator< 117 G raph,118 typename enable_if<typename G raph::EdgeNotifier::Notifier, void>::type119 > { 120 typedef typename G raph::EdgeNotifier Type;121 }; 122 123 template <typename _Graph>124 class ItemSetTraits< _Graph, typename _Graph::Edge> {121 GR, 122 typename enable_if<typename GR::EdgeNotifier::Notifier, void>::type 123 > { 124 typedef typename GR::EdgeNotifier Type; 125 }; 126 127 template <typename GR> 128 class ItemSetTraits<GR, typename GR::Edge> { 125 129 public: 126 130 127 typedef _Graph Graph; 128 129 typedef typename Graph::Edge Item; 130 typedef typename Graph::EdgeIt ItemIt; 131 132 typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier; 133 134 template <typename _Value> 135 class Map : public Graph::template EdgeMap<_Value> { 131 typedef GR Graph; 132 typedef GR Digraph; 133 134 typedef typename GR::Edge Item; 135 typedef typename GR::EdgeIt ItemIt; 136 137 typedef typename EdgeNotifierIndicator<GR>::Type ItemNotifier; 138 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 G raph& _digraph) : Parent(_digraph) {}142 Map(const G raph& _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 }; … … 205 211 // Indicators for the tags 206 212 207 template <typename G raph, typename Enable = void>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 G raph>218 template <typename GR> 213 219 struct NodeNumTagIndicator< 214 G raph,215 typename enable_if<typename G raph::NodeNumTag, void>::type216 > { 217 static const bool value = true; 218 }; 219 220 template <typename G raph, typename Enable = void>220 GR, 221 typename enable_if<typename GR::NodeNumTag, void>::type 222 > { 223 static const bool value = true; 224 }; 225 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 G raph>231 template <typename GR> 226 232 struct ArcNumTagIndicator< 227 G raph,228 typename enable_if<typename G raph::ArcNumTag, void>::type229 > { 230 static const bool value = true; 231 }; 232 233 template <typename G raph, typename Enable = void>233 GR, 234 typename enable_if<typename GR::ArcNumTag, void>::type 235 > { 236 static const bool value = true; 237 }; 238 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 G raph>244 template <typename GR> 239 245 struct EdgeNumTagIndicator< 240 G raph,241 typename enable_if<typename G raph::EdgeNumTag, void>::type242 > { 243 static const bool value = true; 244 }; 245 246 template <typename G raph, typename Enable = void>246 GR, 247 typename enable_if<typename GR::EdgeNumTag, void>::type 248 > { 249 static const bool value = true; 250 }; 251 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 G raph>257 template <typename GR> 252 258 struct FindArcTagIndicator< 253 G raph,254 typename enable_if<typename G raph::FindArcTag, void>::type255 > { 256 static const bool value = true; 257 }; 258 259 template <typename G raph, typename Enable = void>259 GR, 260 typename enable_if<typename GR::FindArcTag, void>::type 261 > { 262 static const bool value = true; 263 }; 264 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 G raph>270 template <typename GR> 265 271 struct FindEdgeTagIndicator< 266 G raph,267 typename enable_if<typename G raph::FindEdgeTag, void>::type268 > { 269 static const bool value = true; 270 }; 271 272 template <typename G raph, typename Enable = void>272 GR, 273 typename enable_if<typename GR::FindEdgeTag, void>::type 274 > { 275 static const bool value = true; 276 }; 277 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 G raph>283 template <typename GR> 278 284 struct UndirectedTagIndicator< 279 G raph,280 typename enable_if<typename G raph::UndirectedTag, void>::type281 > { 282 static const bool value = true; 283 }; 284 285 template <typename G raph, typename Enable = void>285 GR, 286 typename enable_if<typename GR::UndirectedTag, void>::type 287 > { 288 static const bool value = true; 289 }; 290 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 G raph>296 template <typename GR> 291 297 struct BuildTagIndicator< 292 G raph,293 typename enable_if<typename G raph::BuildTag, void>::type298 GR, 299 typename enable_if<typename GR::BuildTag, void>::type 294 300 > { 295 301 static const bool value = true; -
lemon/bits/vector_map.h
r503 r617 57 57 58 58 // The graph type of the map. 59 typedef _Graph Graph ;59 typedef _Graph GraphType; 60 60 // The item type of the map. 61 61 typedef _Item Item; … … 73 73 // The map type. 74 74 typedef VectorMap Map; 75 // The base class of the map.76 typedef typename Notifier::ObserverBase Parent;77 75 78 76 // The reference type of the map; … … 81 79 typedef typename Container::const_reference ConstReference; 82 80 81 private: 82 83 // The base class of the map. 84 typedef typename Notifier::ObserverBase Parent; 85 86 public: 83 87 84 88 // \brief Constructor to attach the new map into the notifier. … … 86 90 // It constructs a map and attachs it into the notifier. 87 91 // It adds all the items of the graph to the map. 88 VectorMap(const Graph & graph) {92 VectorMap(const GraphType& graph) { 89 93 Parent::attach(graph.notifier(Item())); 90 94 container.resize(Parent::notifier()->maxId() + 1); … … 95 99 // It constructs a map uses a given value to initialize the map. 96 100 // It adds all the items of the graph to the map. 97 VectorMap(const Graph & graph, const Value& value) {101 VectorMap(const GraphType& graph, const Value& value) { 98 102 Parent::attach(graph.notifier(Item())); 99 103 container.resize(Parent::notifier()->maxId() + 1, value); -
lemon/circulation.h
r611 r622 22 22 #include <lemon/tolerance.h> 23 23 #include <lemon/elevator.h> 24 #include <limits> 24 25 25 26 ///\ingroup max_flow … … 120 121 121 122 The exact formulation of this problem is the following. 122 Let \f$G=(V,A)\f$ be a digraph, 123 \f$ lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and124 upper bounds on the arcs, for which \f$ 0 \leqlower(uv) \leq upper(uv)\f$123 Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$ 124 \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and 125 upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$ 125 126 holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ 126 127 denotes the signed supply values of the nodes. … … 128 129 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 129 130 \f$-sup(u)\f$ demand. 130 A feasible circulation is an \f$f: A\rightarrow\mathbf{R} ^+_0\f$131 A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$ 131 132 solution of the following problem. 132 133 … … 151 152 the direction of the arcs and taking the negative of the supply values 152 153 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 154 155 This algorithm either calculates a feasible circulation, or provides 156 a \ref barrier() "barrier", which prooves that a feasible soultion 157 cannot exist. 153 158 154 159 Note that this algorithm also provides a feasible solution for the … … 338 343 private: 339 344 345 bool checkBoundMaps() { 346 for (ArcIt e(_g);e!=INVALID;++e) { 347 if (_tol.less((*_up)[e], (*_lo)[e])) return false; 348 } 349 return true; 350 } 351 340 352 void createStructures() { 341 353 _node_num = _el = countNodes(_g); … … 381 393 /// Sets the upper bound (capacity) map. 382 394 /// \return <tt>(*this)</tt> 383 Circulation& upperMap(const LowerMap& map) {395 Circulation& upperMap(const UpperMap& map) { 384 396 _up = ↦ 385 397 return *this; … … 468 480 void init() 469 481 { 482 LEMON_DEBUG(checkBoundMaps(), 483 "Upper bounds must be greater or equal to the lower bounds"); 484 470 485 createStructures(); 471 486 … … 497 512 void greedyInit() 498 513 { 514 LEMON_DEBUG(checkBoundMaps(), 515 "Upper bounds must be greater or equal to the lower bounds"); 516 499 517 createStructures(); 500 518 … … 504 522 505 523 for (ArcIt e(_g);e!=INVALID;++e) { 506 if (!_tol. positive((*_excess)[_g.target(e)] +(*_up)[e])) {524 if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) { 507 525 _flow->set(e, (*_up)[e]); 508 526 (*_excess)[_g.target(e)] += (*_up)[e]; 509 527 (*_excess)[_g.source(e)] -= (*_up)[e]; 510 } else if (_tol. positive((*_excess)[_g.target(e)] +(*_lo)[e])) {528 } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) { 511 529 _flow->set(e, (*_lo)[e]); 512 530 (*_excess)[_g.target(e)] += (*_lo)[e]; … … 749 767 { 750 768 Flow delta=0; 769 Flow inf_cap = std::numeric_limits<Flow>::has_infinity ? 770 std::numeric_limits<Flow>::infinity() : 771 std::numeric_limits<Flow>::max(); 751 772 for(NodeIt n(_g);n!=INVALID;++n) 752 773 if(barrier(n)) … … 756 777 Node s=_g.source(e); 757 778 Node t=_g.target(e); 758 if(barrier(s)&&!barrier(t)) delta+=(*_up)[e]; 779 if(barrier(s)&&!barrier(t)) { 780 if (_tol.less(inf_cap - (*_up)[e], delta)) return false; 781 delta+=(*_up)[e]; 782 } 759 783 else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e]; 760 784 } -
lemon/concepts/graph_components.h
r584 r617 181 181 class BaseGraphComponent : public BaseDigraphComponent { 182 182 public: 183 184 typedef BaseGraphComponent Graph; 185 183 186 typedef BaseDigraphComponent::Node Node; 184 187 typedef BaseDigraphComponent::Arc Arc; … … 190 193 /// represented by two opposite directed arcs. 191 194 class Edge : public GraphItem<'e'> { 195 typedef GraphItem<'e'> Parent; 196 192 197 public: 193 typedef GraphItem<'e'> Parent;194 195 198 /// \brief Default constructor. 196 199 /// … … 992 995 template <typename GR, typename K, typename V> 993 996 class GraphMap : public ReferenceMap<K, V, V&, const V&> { 994 public: 995 996 typedef ReadWriteMap<K, V> Parent; 997 998 /// The graph type of the map. 999 typedef GR Graph; 997 typedef ReferenceMap<K, V, V&, const V&> Parent; 998 999 public: 1000 1000 1001 /// The key type of the map. 1001 1002 typedef K Key; … … 1013 1014 /// 1014 1015 /// Construct a new map for the graph. 1015 explicit GraphMap(const G raph&) {}1016 explicit GraphMap(const GR&) {} 1016 1017 /// \brief Construct a new map with default value. 1017 1018 /// 1018 1019 /// Construct a new map for the graph and initalize the values. 1019 GraphMap(const G raph&, const Value&) {}1020 GraphMap(const GR&, const Value&) {} 1020 1021 1021 1022 private: … … 1058 1059 1059 1060 const _Map &m; 1060 const G raph&g;1061 const GR &g; 1061 1062 const typename GraphMap::Value &t; 1062 1063 }; … … 1086 1087 template <typename V> 1087 1088 class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> { 1089 typedef GraphMap<MappableDigraphComponent, Node, V> Parent; 1090 1088 1091 public: 1089 typedef GraphMap<MappableDigraphComponent, Node, V> Parent;1090 1091 1092 /// \brief Construct a new map. 1092 1093 /// … … 1124 1125 template <typename V> 1125 1126 class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> { 1127 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent; 1128 1126 1129 public: 1127 typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;1128 1129 1130 /// \brief Construct a new map. 1130 1131 /// … … 1222 1223 template <typename V> 1223 1224 class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> { 1225 typedef GraphMap<MappableGraphComponent, Edge, V> Parent; 1226 1224 1227 public: 1225 typedef GraphMap<MappableGraphComponent, Edge, V> Parent;1226 1227 1228 /// \brief Construct a new map. 1228 1229 /// -
lemon/core.h
r581 r617 1037 1037 template <typename GR> 1038 1038 class ConArcIt : public GR::Arc { 1039 typedef typename GR::Arc Parent; 1040 1039 1041 public: 1040 1042 1041 typedef GR Graph; 1042 typedef typename Graph::Arc Parent; 1043 1044 typedef typename Graph::Arc Arc; 1045 typedef typename Graph::Node Node; 1043 typedef typename GR::Arc Arc; 1044 typedef typename GR::Node Node; 1046 1045 1047 1046 /// \brief Constructor. … … 1049 1048 /// Construct a new ConArcIt iterating on the arcs that 1050 1049 /// connects nodes \c u and \c v. 1051 ConArcIt(const G raph& g, Node u, Node v) : _graph(g) {1050 ConArcIt(const GR& g, Node u, Node v) : _graph(g) { 1052 1051 Parent::operator=(findArc(_graph, u, v)); 1053 1052 } … … 1056 1055 /// 1057 1056 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1058 ConArcIt(const G raph& g, Arc a) : Parent(a), _graph(g) {}1057 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {} 1059 1058 1060 1059 /// \brief Increment operator. … … 1067 1066 } 1068 1067 private: 1069 const G raph& _graph;1068 const GR& _graph; 1070 1069 }; 1071 1070 … … 1160 1159 template <typename GR> 1161 1160 class ConEdgeIt : public GR::Edge { 1161 typedef typename GR::Edge Parent; 1162 1162 1163 public: 1163 1164 1164 typedef GR Graph; 1165 typedef typename Graph::Edge Parent; 1166 1167 typedef typename Graph::Edge Edge; 1168 typedef typename Graph::Node Node; 1165 typedef typename GR::Edge Edge; 1166 typedef typename GR::Node Node; 1169 1167 1170 1168 /// \brief Constructor. … … 1172 1170 /// Construct a new ConEdgeIt iterating on the edges that 1173 1171 /// connects nodes \c u and \c v. 1174 ConEdgeIt(const G raph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {1172 ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) { 1175 1173 Parent::operator=(findEdge(_graph, _u, _v)); 1176 1174 } … … 1179 1177 /// 1180 1178 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1181 ConEdgeIt(const G raph& g, Edge e) : Parent(e), _graph(g) {}1179 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {} 1182 1180 1183 1181 /// \brief Increment operator. … … 1189 1187 } 1190 1188 private: 1191 const G raph& _graph;1189 const GR& _graph; 1192 1190 Node _u, _v; 1193 1191 }; … … 1220 1218 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1221 1219 { 1222 public:1223 1220 typedef typename ItemSetTraits<GR, typename GR::Arc> 1224 1221 ::ItemNotifier::ObserverBase Parent; 1225 1222 1226 1223 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1224 1225 public: 1226 1227 /// The Digraph type 1227 1228 typedef GR Digraph; 1228 1229 … … 1230 1231 1231 1232 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1233 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1234 1232 1235 public: 1233 1234 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;1235 1236 1236 1237 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {} … … 1257 1258 } 1258 1259 }; 1259 1260 const Digraph &_g;1261 AutoNodeMap _head;1262 typename Digraph::template ArcMap<Arc> _parent;1263 typename Digraph::template ArcMap<Arc> _left;1264 typename Digraph::template ArcMap<Arc> _right;1265 1260 1266 1261 class ArcLess { … … 1273 1268 } 1274 1269 }; 1270 1271 protected: 1272 1273 const Digraph &_g; 1274 AutoNodeMap _head; 1275 typename Digraph::template ArcMap<Arc> _parent; 1276 typename Digraph::template ArcMap<Arc> _left; 1277 typename Digraph::template ArcMap<Arc> _right; 1275 1278 1276 1279 public: … … 1631 1634 class ArcLookUp 1632 1635 { 1636 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1637 1633 1638 public: 1634 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1639 1640 /// The Digraph type 1635 1641 typedef GR Digraph; 1636 1642 … … 1747 1753 1748 1754 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1749 typedef GR Digraph; 1750 1751 typename Digraph::template ArcMap<Arc> _next; 1755 1756 typename GR::template ArcMap<Arc> _next; 1752 1757 1753 1758 Arc refreshNext(Arc head,Arc next=INVALID) … … 1768 1773 1769 1774 public: 1775 1776 /// The Digraph type 1777 typedef GR Digraph; 1778 1770 1779 ///Constructor 1771 1780 -
lemon/edge_set.h
r559 r617 34 34 public: 35 35 36 typedef GR Graph;37 36 typedef typename GR::Node Node; 38 37 typedef typename GR::NodeIt NodeIt; … … 209 208 template <typename V> 210 209 class NodeMap : public GR::template NodeMap<V> { 210 typedef typename GR::template NodeMap<V> Parent; 211 211 212 public: 212 213 typedef typename GR::template NodeMap<V> Parent;214 213 215 214 explicit NodeMap(const ListArcSetBase<GR>& arcset) … … 260 259 template <typename GR> 261 260 class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > { 262 263 public:264 265 261 typedef ArcSetExtender<ListArcSetBase<GR> > Parent; 262 263 public: 266 264 267 265 typedef typename Parent::Node Node; 268 266 typedef typename Parent::Arc Arc; 269 270 typedef GR Graph;271 272 267 273 268 typedef typename Parent::NodesImplBase NodesImplBase; … … 293 288 294 289 class NodesImpl : public NodesImplBase { 290 typedef NodesImplBase Parent; 291 295 292 public: 296 typedef NodesImplBase Parent;297 298 293 NodesImpl(const GR& graph, ListArcSet& arcset) 299 294 : Parent(graph), _arcset(arcset) {} … … 355 350 public: 356 351 357 typedef GR Graph;358 352 typedef typename GR::Node Node; 359 353 typedef typename GR::NodeIt NodeIt; … … 638 632 template <typename V> 639 633 class NodeMap : public GR::template NodeMap<V> { 634 typedef typename GR::template NodeMap<V> Parent; 635 640 636 public: 641 642 typedef typename GR::template NodeMap<V> Parent;643 637 644 638 explicit NodeMap(const ListEdgeSetBase<GR>& arcset) … … 689 683 template <typename GR> 690 684 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > { 691 692 public:693 694 685 typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent; 686 687 public: 695 688 696 689 typedef typename Parent::Node Node; 697 690 typedef typename Parent::Arc Arc; 698 691 typedef typename Parent::Edge Edge; 699 700 typedef GR Graph;701 702 692 703 693 typedef typename Parent::NodesImplBase NodesImplBase; … … 718 708 719 709 class NodesImpl : public NodesImplBase { 710 typedef NodesImplBase Parent; 711 720 712 public: 721 typedef NodesImplBase Parent;722 723 713 NodesImpl(const GR& graph, ListEdgeSet& arcset) 724 714 : Parent(graph), _arcset(arcset) {} … … 780 770 public: 781 771 782 typedef GR Graph; 783 typedef typename Graph::Node Node; 784 typedef typename Graph::NodeIt NodeIt; 772 typedef typename GR::Node Node; 773 typedef typename GR::NodeIt NodeIt; 785 774 786 775 protected: … … 901 890 template <typename V> 902 891 class NodeMap : public GR::template NodeMap<V> { 892 typedef typename GR::template NodeMap<V> Parent; 893 903 894 public: 904 905 typedef typename GR::template NodeMap<V> Parent;906 895 907 896 explicit NodeMap(const SmartArcSetBase<GR>& arcset) … … 957 946 template <typename GR> 958 947 class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > { 959 960 public:961 962 948 typedef ArcSetExtender<SmartArcSetBase<GR> > Parent; 949 950 public: 963 951 964 952 typedef typename Parent::Node Node; 965 953 typedef typename Parent::Arc Arc; 966 967 typedef GR Graph;968 954 969 955 protected: … … 984 970 985 971 class NodesImpl : public NodesImplBase { 972 typedef NodesImplBase Parent; 973 986 974 public: 987 typedef NodesImplBase Parent;988 989 975 NodesImpl(const GR& graph, SmartArcSet& arcset) 990 976 : Parent(graph), _arcset(arcset) {} … … 1063 1049 public: 1064 1050 1065 typedef GR Graph;1066 1051 typedef typename GR::Node Node; 1067 1052 typedef typename GR::NodeIt NodeIt; … … 1250 1235 template <typename V> 1251 1236 class NodeMap : public GR::template NodeMap<V> { 1237 typedef typename GR::template NodeMap<V> Parent; 1238 1252 1239 public: 1253 1254 typedef typename GR::template NodeMap<V> Parent;1255 1240 1256 1241 explicit NodeMap(const SmartEdgeSetBase<GR>& arcset) … … 1305 1290 template <typename GR> 1306 1291 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > { 1307 1308 public:1309 1310 1292 typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent; 1293 1294 public: 1311 1295 1312 1296 typedef typename Parent::Node Node; … … 1314 1298 typedef typename Parent::Edge Edge; 1315 1299 1316 typedef GR Graph;1317 1318 1300 protected: 1319 1301 … … 1332 1314 1333 1315 class NodesImpl : public NodesImplBase { 1316 typedef NodesImplBase Parent; 1317 1334 1318 public: 1335 typedef NodesImplBase Parent;1336 1337 1319 NodesImpl(const GR& graph, SmartEdgeSet& arcset) 1338 1320 : Parent(graph), _arcset(arcset) {} -
lemon/full_graph.h
r582 r617 32 32 public: 33 33 34 typedef FullDigraphBase Graph;34 typedef FullDigraphBase Digraph; 35 35 36 36 class Node; … … 170 170 /// \sa FullGraph 171 171 class FullDigraph : public ExtendedFullDigraphBase { 172 typedef ExtendedFullDigraphBase Parent; 173 172 174 public: 173 174 typedef ExtendedFullDigraphBase Parent;175 175 176 176 /// \brief Constructor … … 227 227 228 228 class FullGraphBase { 229 int _node_num;230 int _edge_num;231 229 public: 232 230 … … 238 236 239 237 protected: 238 239 int _node_num; 240 int _edge_num; 240 241 241 242 FullGraphBase() {} … … 538 539 /// \sa FullDigraph 539 540 class FullGraph : public ExtendedFullGraphBase { 541 typedef ExtendedFullGraphBase Parent; 542 540 543 public: 541 542 typedef ExtendedFullGraphBase Parent;543 544 544 545 /// \brief Constructor -
lemon/graph_to_eps.h
r584 r617 70 70 { 71 71 typedef GR Graph; 72 typedef GR Digraph; 72 73 typedef typename Graph::Node Node; 73 74 typedef typename Graph::NodeIt NodeIt; … … 242 243 243 244 typedef typename T::Graph Graph; 245 typedef typename T::Digraph Digraph; 244 246 typedef typename Graph::Node Node; 245 247 typedef typename Graph::NodeIt NodeIt; -
lemon/grid_graph.h
r582 r617 500 500 /// "Graph concept". 501 501 class GridGraph : public ExtendedGridGraphBase { 502 typedef ExtendedGridGraphBase Parent; 503 502 504 public: 503 504 typedef ExtendedGridGraphBase Parent;505 505 506 506 /// \brief Map to get the indices of the nodes as dim2::Point<int>. -
lemon/hypercube_graph.h
r582 r617 295 295 /// "Graph concept". 296 296 class HypercubeGraph : public ExtendedHypercubeGraphBase { 297 typedef ExtendedHypercubeGraphBase Parent; 298 297 299 public: 298 299 typedef ExtendedHypercubeGraphBase Parent;300 300 301 301 /// \brief Constructs a hypercube graph with \c dim dimensions. -
lemon/list_graph.h
r582 r617 324 324 325 325 class ListDigraph : public ExtendedListDigraphBase { 326 typedef ExtendedListDigraphBase Parent; 327 326 328 private: 327 329 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. … … 337 339 void operator=(const ListDigraph &) {} 338 340 public: 339 340 typedef ExtendedListDigraphBase Parent;341 341 342 342 /// Constructor … … 794 794 public: 795 795 796 typedef ListGraphBase Digraph;796 typedef ListGraphBase Graph; 797 797 798 798 class Node; … … 1177 1177 1178 1178 class ListGraph : public ExtendedListGraphBase { 1179 typedef ExtendedListGraphBase Parent; 1180 1179 1181 private: 1180 1182 ///ListGraph is \e not copy constructible. Use copyGraph() instead. … … 1195 1197 /// 1196 1198 ListGraph() {} 1197 1198 typedef ExtendedListGraphBase Parent;1199 1199 1200 1200 typedef Parent::OutArcIt IncEdgeIt; -
lemon/maps.h
r584 r617 1839 1839 /// The graph type of IdMap. 1840 1840 typedef GR Graph; 1841 typedef GR Digraph; 1841 1842 /// The key type of IdMap (\c Node, \c Arc or \c Edge). 1842 1843 typedef K Item; … … 1930 1931 /// The graph type of CrossRefMap. 1931 1932 typedef GR Graph; 1933 typedef GR Digraph; 1932 1934 /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge). 1933 1935 typedef K Item; … … 2133 2135 /// The graph type of RangeIdMap. 2134 2136 typedef GR Graph; 2137 typedef GR Digraph; 2135 2138 /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge). 2136 2139 typedef K Item; … … 2495 2498 public: 2496 2499 2497 /// The digraph type 2500 /// The graph type of InDegMap 2501 typedef GR Graph; 2498 2502 typedef GR Digraph; 2499 2503 /// The key type … … 2624 2628 public: 2625 2629 2626 /// The digraph type 2630 /// The graph type of OutDegMap 2631 typedef GR Graph; 2627 2632 typedef GR Digraph; 2628 2633 /// The key type -
lemon/network_simplex.h
r609 r618 382 382 const int MIN_BLOCK_SIZE = 10; 383 383 384 _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)), 384 _block_size = std::max( int(BLOCK_SIZE_FACTOR * 385 std::sqrt(double(_arc_num))), 385 386 MIN_BLOCK_SIZE ); 386 387 } … … 458 459 const int MIN_MINOR_LIMIT = 3; 459 460 460 _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_arc_num)), 461 _list_length = std::max( int(LIST_LENGTH_FACTOR * 462 std::sqrt(double(_arc_num))), 461 463 MIN_LIST_LENGTH ); 462 464 _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length), … … 578 580 const int MIN_HEAD_LENGTH = 3; 579 581 580 _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)), 582 _block_size = std::max( int(BLOCK_SIZE_FACTOR * 583 std::sqrt(double(_arc_num))), 581 584 MIN_BLOCK_SIZE ); 582 585 _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size), … … 1145 1148 // Run Circulation to check if a feasible solution exists 1146 1149 typedef ConstMap<Arc, Flow> ConstArcMap; 1150 ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap); 1147 1151 FlowNodeMap *csup = NULL; 1148 1152 bool local_csup = false; … … 1165 1169 } else { 1166 1170 Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap> 1167 circ(_graph, *_plower, ConstArcMap(inf_cap), *csup);1171 circ(_graph, *_plower, inf_arc_map, *csup); 1168 1172 circ_result = circ.run(); 1169 1173 } … … 1171 1175 if (_pupper) { 1172 1176 Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap> 1173 circ(_graph, ConstArcMap(0), *_pupper, *csup);1177 circ(_graph, zero_arc_map, *_pupper, *csup); 1174 1178 circ_result = circ.run(); 1175 1179 } else { 1176 1180 Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap> 1177 circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup);1181 circ(_graph, zero_arc_map, inf_arc_map, *csup); 1178 1182 circ_result = circ.run(); 1179 1183 } … … 1192 1196 } else { 1193 1197 Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap> 1194 circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup);1198 circ(rgraph, *_plower, inf_arc_map, neg_csup); 1195 1199 circ_result = circ.run(); 1196 1200 } … … 1198 1202 if (_pupper) { 1199 1203 Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap> 1200 circ(rgraph, ConstArcMap(0), *_pupper, neg_csup);1204 circ(rgraph, zero_arc_map, *_pupper, neg_csup); 1201 1205 circ_result = circ.run(); 1202 1206 } else { 1203 1207 Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap> 1204 circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup);1208 circ(rgraph, zero_arc_map, inf_arc_map, neg_csup); 1205 1209 circ_result = circ.run(); 1206 1210 } … … 1226 1230 1227 1231 // Store the arcs in a mixed order 1228 int k = std::max(int(s qrt(_arc_num)), 10);1232 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 1229 1233 int i = 0; 1230 1234 for (ArcIt e(_graph); e != INVALID; ++e) { -
lemon/smart_graph.h
r582 r617 56 56 public: 57 57 58 typedef SmartDigraphBase Graph;58 typedef SmartDigraphBase Digraph; 59 59 60 60 class Node; … … 196 196 ///\sa concepts::Digraph. 197 197 class SmartDigraph : public ExtendedSmartDigraphBase { 198 public:199 200 198 typedef ExtendedSmartDigraphBase Parent; 201 199 … … 421 419 public: 422 420 423 typedef SmartGraphBase Digraph;421 typedef SmartGraphBase Graph; 424 422 425 423 class Node; … … 632 630 /// \sa concepts::Graph. 633 631 class SmartGraph : public ExtendedSmartGraphBase { 632 typedef ExtendedSmartGraphBase Parent; 633 634 634 private: 635 635 … … 648 648 649 649 public: 650 651 typedef ExtendedSmartGraphBase Parent;652 650 653 651 /// Constructor -
lemon/suurballe.h
r584 r623 26 26 27 27 #include <vector> 28 #include <limits> 28 29 #include <lemon/bin_heap.h> 29 30 #include <lemon/path.h> … … 43 44 /// from a given source node to a given target node in a digraph. 44 45 /// 45 /// In fact, this implementation is the specialization of the 46 /// \ref CapacityScaling "successive shortest path" algorithm. 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" algorithm directly for this problem. 50 /// Therefore this class provides query functions for flow values and 51 /// node potentials (the dual solution) just like the minimum cost flow 52 /// algorithms. 47 53 /// 48 54 /// \tparam GR The digraph type the algorithm runs on. 49 /// The default value is \c ListDigraph. 50 /// \tparam LEN The type of the length (cost) map. 51 /// The default value is <tt>Digraph::ArcMap<int></tt>. 55 /// \tparam LEN The type of the length map. 56 /// The default value is <tt>GR::ArcMap<int></tt>. 52 57 /// 53 58 /// \warning Length values should be \e non-negative \e integers. 54 59 /// 55 60 /// \note For finding node-disjoint paths this algorithm can be used 56 /// with \ref SplitNodes.61 /// along with the \ref SplitNodes adaptor. 57 62 #ifdef DOXYGEN 58 63 template <typename GR, typename LEN> 59 64 #else 60 template < typename GR = ListDigraph,65 template < typename GR, 61 66 typename LEN = typename GR::template ArcMap<int> > 62 67 #endif … … 76 81 /// The type of the lengths. 77 82 typedef typename LengthMap::Value Length; 83 #ifdef DOXYGEN 84 /// The type of the flow map. 85 typedef GR::ArcMap<int> FlowMap; 86 /// The type of the potential map. 87 typedef GR::NodeMap<Length> PotentialMap; 88 #else 78 89 /// The type of the flow map. 79 90 typedef typename Digraph::template ArcMap<int> FlowMap; 80 91 /// The type of the potential map. 81 92 typedef typename Digraph::template NodeMap<Length> PotentialMap; 93 #endif 94 82 95 /// The type of the path structures. 83 typedef SimplePath< Digraph> Path;96 typedef SimplePath<GR> Path; 84 97 85 98 private: 86 99 87 /// \brief Special implementation of the Dijkstra algorithm 88 /// for finding shortest paths in the residual network. 89 /// 90 /// \ref ResidualDijkstra is a special implementation of the 91 /// \ref Dijkstra algorithm for finding shortest paths in the 92 /// residual network of the digraph with respect to the reduced arc 93 /// lengths and modifying the node potentials according to the 94 /// distance of the nodes. 100 // ResidualDijkstra is a special implementation of the 101 // Dijkstra algorithm for finding shortest paths in the 102 // residual network with respect to the reduced arc lengths 103 // and modifying the node potentials according to the 104 // distance of the nodes. 95 105 class ResidualDijkstra 96 106 { … … 121 131 122 132 /// Constructor. 123 ResidualDijkstra( const Digraph & digraph,133 ResidualDijkstra( const Digraph &graph, 124 134 const FlowMap &flow, 125 135 const LengthMap &length, … … 127 137 PredMap &pred, 128 138 Node s, Node t ) : 129 _graph( digraph), _flow(flow), _length(length), _potential(potential),130 _dist( digraph), _pred(pred), _s(s), _t(t) {}139 _graph(graph), _flow(flow), _length(length), _potential(potential), 140 _dist(graph), _pred(pred), _s(s), _t(t) {} 131 141 132 142 /// \brief Run the algorithm. It returns \c true if a path is found … … 237 247 /// Constructor. 238 248 /// 239 /// \param digraph The digraph the algorithm runs on.249 /// \param graph The digraph the algorithm runs on. 240 250 /// \param length The length (cost) values of the arcs. 241 /// \param s The source node.242 /// \param t The target node.243 Suurballe( const Digraph &digraph,244 const LengthMap &length,245 Node s, Node t ) :246 _graph(digraph), _length(length), _flow(0), _local_flow(false),247 _potential(0), _local_potential(false), _source(s), _target(t),248 _pred(digraph) {}251 Suurballe( const Digraph &graph, 252 const LengthMap &length ) : 253 _graph(graph), _length(length), _flow(0), _local_flow(false), 254 _potential(0), _local_potential(false), _pred(graph) 255 { 256 LEMON_ASSERT(std::numeric_limits<Length>::is_integer, 257 "The length type of Suurballe must be integer"); 258 } 249 259 250 260 /// Destructor. … … 258 268 /// 259 269 /// This function sets the flow map. 260 /// 261 /// The found flow contains only 0 and 1 values. It is the union of 262 /// the found arc-disjoint paths. 270 /// If it is not used before calling \ref run() or \ref init(), 271 /// an instance will be allocated automatically. The destructor 272 /// deallocates this automatically allocated map, of course. 273 /// 274 /// The found flow contains only 0 and 1 values, since it is the 275 /// union of the found arc-disjoint paths. 263 276 /// 264 277 /// \return <tt>(*this)</tt> … … 275 288 /// 276 289 /// This function sets the potential map. 277 /// 278 /// The potentials provide the dual solution of the underlying 279 /// minimum cost flow problem. 290 /// If it is not used before calling \ref run() or \ref init(), 291 /// an instance will be allocated automatically. The destructor 292 /// deallocates this automatically allocated map, of course. 293 /// 294 /// The node potentials provide the dual solution of the underlying 295 /// \ref min_cost_flow "minimum cost flow problem". 280 296 /// 281 297 /// \return <tt>(*this)</tt> … … 302 318 /// This function runs the algorithm. 303 319 /// 320 /// \param s The source node. 321 /// \param t The target node. 304 322 /// \param k The number of paths to be found. 305 323 /// … … 308 326 /// arc-disjoint paths found. 309 327 /// 310 /// \note Apart from the return value, <tt>s.run( k)</tt> is just a311 /// shortcut of the following code.328 /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is 329 /// just a shortcut of the following code. 312 330 /// \code 313 /// s.init( );314 /// s.findFlow( k);331 /// s.init(s); 332 /// s.findFlow(t, k); 315 333 /// s.findPaths(); 316 334 /// \endcode 317 int run( int k = 2) {318 init( );319 findFlow( k);335 int run(const Node& s, const Node& t, int k = 2) { 336 init(s); 337 findFlow(t, k); 320 338 findPaths(); 321 339 return _path_num; … … 325 343 /// 326 344 /// This function initializes the algorithm. 327 void init() { 345 /// 346 /// \param s The source node. 347 void init(const Node& s) { 348 _source = s; 349 328 350 // Initialize maps 329 351 if (!_flow) { … … 337 359 for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 338 360 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 339 340 _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 341 *_potential, _pred, 342 _source, _target ); 343 } 344 345 /// \brief Execute the successive shortest path algorithm to find 346 /// an optimal flow. 361 } 362 363 /// \brief Execute the algorithm to find an optimal flow. 347 364 /// 348 365 /// This function executes the successive shortest path algorithm to 349 /// find a minimum cost flow, which is the union of \c k or less366 /// find a minimum cost flow, which is the union of \c k (or less) 350 367 /// arc-disjoint paths. 351 368 /// 369 /// \param t The target node. 370 /// \param k The number of paths to be found. 371 /// 352 372 /// \return \c k if there are at least \c k arc-disjoint paths from 353 /// \c s to \c t in the digraph. Otherwise it returns the number of354 /// arc-disjoint paths found.373 /// the source node to the given node \c t in the digraph. 374 /// Otherwise it returns the number of arc-disjoint paths found. 355 375 /// 356 376 /// \pre \ref init() must be called before using this function. 357 int findFlow(int k = 2) { 377 int findFlow(const Node& t, int k = 2) { 378 _target = t; 379 _dijkstra = 380 new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, 381 _source, _target ); 382 358 383 // Find shortest paths 359 384 _path_num = 0; … … 381 406 /// \brief Compute the paths from the flow. 382 407 /// 383 /// This function computes the paths from the flow. 408 /// This function computes the paths from the found minimum cost flow, 409 /// which is the union of some arc-disjoint paths. 384 410 /// 385 411 /// \pre \ref init() and \ref findFlow() must be called before using 386 412 /// this function. 387 413 void findPaths() { 388 // Create the residual flow map (the union of the paths not found389 // so far)390 414 FlowMap res_flow(_graph); 391 415 for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; … … 414 438 /// @{ 415 439 416 /// \brief Return a const reference to the arc map storing the 417 /// found flow. 418 /// 419 /// This function returns a const reference to the arc map storing 420 /// the flow that is the union of the found arc-disjoint paths. 421 /// 422 /// \pre \ref run() or \ref findFlow() must be called before using 423 /// this function. 424 const FlowMap& flowMap() const { 425 return *_flow; 426 } 427 428 /// \brief Return a const reference to the node map storing the 429 /// found potentials (the dual solution). 430 /// 431 /// This function returns a const reference to the node map storing 432 /// the found potentials that provide the dual solution of the 433 /// underlying minimum cost flow problem. 434 /// 435 /// \pre \ref run() or \ref findFlow() must be called before using 436 /// this function. 437 const PotentialMap& potentialMap() const { 438 return *_potential; 439 } 440 441 /// \brief Return the flow on the given arc. 442 /// 443 /// This function returns the flow on the given arc. 444 /// It is \c 1 if the arc is involved in one of the found paths, 445 /// otherwise it is \c 0. 446 /// 447 /// \pre \ref run() or \ref findFlow() must be called before using 448 /// this function. 449 int flow(const Arc& arc) const { 450 return (*_flow)[arc]; 451 } 452 453 /// \brief Return the potential of the given node. 454 /// 455 /// This function returns the potential of the given node. 456 /// 457 /// \pre \ref run() or \ref findFlow() must be called before using 458 /// this function. 459 Length potential(const Node& node) const { 460 return (*_potential)[node]; 461 } 462 463 /// \brief Return the total length (cost) of the found paths (flow). 464 /// 465 /// This function returns the total length (cost) of the found paths 466 /// (flow). The complexity of the function is O(e). 440 /// \brief Return the total length of the found paths. 441 /// 442 /// This function returns the total length of the found paths, i.e. 443 /// the total cost of the found flow. 444 /// The complexity of the function is O(e). 467 445 /// 468 446 /// \pre \ref run() or \ref findFlow() must be called before using … … 475 453 } 476 454 455 /// \brief Return the flow value on the given arc. 456 /// 457 /// This function returns the flow value on the given arc. 458 /// It is \c 1 if the arc is involved in one of the found arc-disjoint 459 /// paths, otherwise it is \c 0. 460 /// 461 /// \pre \ref run() or \ref findFlow() must be called before using 462 /// this function. 463 int flow(const Arc& arc) const { 464 return (*_flow)[arc]; 465 } 466 467 /// \brief Return a const reference to an arc map storing the 468 /// found flow. 469 /// 470 /// This function returns a const reference to an arc map storing 471 /// the flow that is the union of the found arc-disjoint paths. 472 /// 473 /// \pre \ref run() or \ref findFlow() must be called before using 474 /// this function. 475 const FlowMap& flowMap() const { 476 return *_flow; 477 } 478 479 /// \brief Return the potential of the given node. 480 /// 481 /// This function returns the potential of the given node. 482 /// The node potentials provide the dual solution of the 483 /// underlying \ref min_cost_flow "minimum cost flow problem". 484 /// 485 /// \pre \ref run() or \ref findFlow() must be called before using 486 /// this function. 487 Length potential(const Node& node) const { 488 return (*_potential)[node]; 489 } 490 491 /// \brief Return a const reference to a node map storing the 492 /// found potentials (the dual solution). 493 /// 494 /// This function returns a const reference to a node map storing 495 /// the found potentials that provide the dual solution of the 496 /// underlying \ref min_cost_flow "minimum cost flow problem". 497 /// 498 /// \pre \ref run() or \ref findFlow() must be called before using 499 /// this function. 500 const PotentialMap& potentialMap() const { 501 return *_potential; 502 } 503 477 504 /// \brief Return the number of the found paths. 478 505 /// … … 489 516 /// This function returns a const reference to the specified path. 490 517 /// 491 /// \param i The function returns the \c i-th path.518 /// \param i The function returns the <tt>i</tt>-th path. 492 519 /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>. 493 520 /// -
test/min_cost_flow_test.cc
r609 r615 234 234 typedef int Flow; 235 235 typedef int Cost; 236 // TODO: This typedef should be enabled if the standard maps are 237 // reference maps in the graph concepts (See #190). 238 /**/ 239 //typedef concepts::Digraph GR; 240 typedef ListDigraph GR; 241 /**/ 236 typedef concepts::Digraph GR; 242 237 checkConcept< McfClassConcept<GR, Flow, Cost>, 243 238 NetworkSimplex<GR, Flow, Cost> >(); -
test/suurballe_test.cc
r440 r623 23 23 #include <lemon/path.h> 24 24 #include <lemon/suurballe.h> 25 #include <lemon/concepts/digraph.h> 25 26 26 27 #include "test_tools.h" … … 30 31 char test_lgf[] = 31 32 "@nodes\n" 32 "label supply1 supply2 supply3\n"33 "1 0 20 27\n"34 "2 0 -4 0\n"35 "3 0 0 0\n"36 "4 0 0 0\n"37 "5 0 9 0\n"38 "6 0 -6 0\n"39 "7 0 0 0\n"40 "8 0 0 0\n"41 "9 0 3 0\n"42 "10 0 -2 0\n"43 "11 0 0 0\n"44 "12 0 -20 -27\n"33 "label\n" 34 "1\n" 35 "2\n" 36 "3\n" 37 "4\n" 38 "5\n" 39 "6\n" 40 "7\n" 41 "8\n" 42 "9\n" 43 "10\n" 44 "11\n" 45 "12\n" 45 46 "@arcs\n" 46 " cost capacity lower1 lower2\n"47 " 1 2 70 11 0 8\n"48 " 1 3 150 3 0 1\n"49 " 1 4 80 15 0 2\n"50 " 2 8 80 12 0 0\n"51 " 3 5 140 5 0 3\n"52 " 4 6 60 10 0 1\n"53 " 4 7 80 2 0 0\n"54 " 4 8 110 3 0 0\n"55 " 5 7 60 14 0 0\n"56 " 5 11 120 12 0 0\n"57 " 6 3 0 3 0 0\n"58 " 6 9 140 4 0 0\n"59 " 6 10 90 8 0 0\n"60 " 7 1 30 5 0 0\n"61 " 8 12 60 16 0 4\n"62 " 9 12 50 6 0 0\n"63 "10 12 70 13 0 5\n"64 "10 2 100 7 0 0\n"65 "10 7 60 10 0 0\n"66 "11 10 20 14 0 6\n"67 "12 11 30 10 0 0\n"47 " length\n" 48 " 1 2 70\n" 49 " 1 3 150\n" 50 " 1 4 80\n" 51 " 2 8 80\n" 52 " 3 5 140\n" 53 " 4 6 60\n" 54 " 4 7 80\n" 55 " 4 8 110\n" 56 " 5 7 60\n" 57 " 5 11 120\n" 58 " 6 3 0\n" 59 " 6 9 140\n" 60 " 6 10 90\n" 61 " 7 1 30\n" 62 " 8 12 60\n" 63 " 9 12 50\n" 64 "10 12 70\n" 65 "10 2 100\n" 66 "10 7 60\n" 67 "11 10 20\n" 68 "12 11 30\n" 68 69 "@attributes\n" 69 70 "source 1\n" 70 71 "target 12\n" 71 72 "@end\n"; 73 74 // Check the interface of Suurballe 75 void checkSuurballeCompile() 76 { 77 typedef int VType; 78 typedef concepts::Digraph Digraph; 79 80 typedef Digraph::Node Node; 81 typedef Digraph::Arc Arc; 82 typedef concepts::ReadMap<Arc, VType> LengthMap; 83 84 typedef Suurballe<Digraph, LengthMap> SuurballeType; 85 86 Digraph g; 87 Node n; 88 Arc e; 89 LengthMap len; 90 SuurballeType::FlowMap flow(g); 91 SuurballeType::PotentialMap pi(g); 92 93 SuurballeType suurb_test(g, len); 94 const SuurballeType& const_suurb_test = suurb_test; 95 96 suurb_test 97 .flowMap(flow) 98 .potentialMap(pi); 99 100 int k; 101 k = suurb_test.run(n, n); 102 k = suurb_test.run(n, n, k); 103 suurb_test.init(n); 104 k = suurb_test.findFlow(n); 105 k = suurb_test.findFlow(n, k); 106 suurb_test.findPaths(); 107 108 int f; 109 VType c; 110 c = const_suurb_test.totalLength(); 111 f = const_suurb_test.flow(e); 112 const SuurballeType::FlowMap& fm = 113 const_suurb_test.flowMap(); 114 c = const_suurb_test.potential(n); 115 const SuurballeType::PotentialMap& pm = 116 const_suurb_test.potentialMap(); 117 k = const_suurb_test.pathNum(); 118 Path<Digraph> p = const_suurb_test.path(k); 119 120 ignore_unused_variable_warning(fm); 121 ignore_unused_variable_warning(pm); 122 } 72 123 73 124 // Check the feasibility of the flow … … 119 170 typename Digraph::Node s, typename Digraph::Node t) 120 171 { 121 // Check the "Complementary Slackness" optimality condition122 172 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 123 173 Node n = s; … … 137 187 ListDigraph digraph; 138 188 ListDigraph::ArcMap<int> length(digraph); 139 Node s ource, target;189 Node s, t; 140 190 141 191 std::istringstream input(test_lgf); 142 192 DigraphReader<ListDigraph>(digraph, input). 143 arcMap(" cost", length).144 node("source", s ource).145 node("target", t arget).193 arcMap("length", length). 194 node("source", s). 195 node("target", t). 146 196 run(); 147 197 148 198 // Find 2 paths 149 199 { 150 Suurballe<ListDigraph> suurballe(digraph, length , source, target);151 check(suurballe.run( 2) == 2, "Wrong number of paths");152 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 2),200 Suurballe<ListDigraph> suurballe(digraph, length); 201 check(suurballe.run(s, t) == 2, "Wrong number of paths"); 202 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), 153 203 "The flow is not feasible"); 154 204 check(suurballe.totalLength() == 510, "The flow is not optimal"); … … 157 207 "Wrong potentials"); 158 208 for (int i = 0; i < suurballe.pathNum(); ++i) 159 check(checkPath(digraph, suurballe.path(i), source, target), 160 "Wrong path"); 209 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 161 210 } 162 211 163 212 // Find 3 paths 164 213 { 165 Suurballe<ListDigraph> suurballe(digraph, length , source, target);166 check(suurballe.run( 3) == 3, "Wrong number of paths");167 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),214 Suurballe<ListDigraph> suurballe(digraph, length); 215 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); 216 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 168 217 "The flow is not feasible"); 169 218 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 172 221 "Wrong potentials"); 173 222 for (int i = 0; i < suurballe.pathNum(); ++i) 174 check(checkPath(digraph, suurballe.path(i), source, target), 175 "Wrong path"); 223 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 176 224 } 177 225 178 226 // Find 5 paths (only 3 can be found) 179 227 { 180 Suurballe<ListDigraph> suurballe(digraph, length , source, target);181 check(suurballe.run( 5) == 3, "Wrong number of paths");182 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),228 Suurballe<ListDigraph> suurballe(digraph, length); 229 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); 230 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 183 231 "The flow is not feasible"); 184 232 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 187 235 "Wrong potentials"); 188 236 for (int i = 0; i < suurballe.pathNum(); ++i) 189 check(checkPath(digraph, suurballe.path(i), source, target), 190 "Wrong path"); 237 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 191 238 } 192 239 -
tools/dimacs-solver.cc
r611 r614 94 94 template<class Value> 95 95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, 96 DimacsDescriptor &desc)96 Value infty, DimacsDescriptor &desc) 97 97 { 98 98 bool report = !ap.given("q"); … … 101 101 Digraph::NodeMap<Value> sup(g); 102 102 Timer ti; 103 ti.restart(); 104 readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); 103 104 ti.restart(); 105 readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); 106 ti.stop(); 107 Value sum_sup = 0; 108 for (Digraph::NodeIt n(g); n != INVALID; ++n) { 109 sum_sup += sup[n]; 110 } 111 if (report) { 112 std::cerr << "Sum of supply values: " << sum_sup << "\n"; 113 if (sum_sup <= 0) 114 std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; 115 else 116 std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; 117 } 105 118 if (report) std::cerr << "Read the file: " << ti << '\n'; 119 106 120 ti.restart(); 107 121 NetworkSimplex<Digraph, Value> ns(g); 108 122 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); 123 if (sum_sup > 0) ns.problemType(ns.LEQ); 109 124 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; 110 125 ti.restart(); 111 ns.run(); 112 if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; 113 if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; 126 bool res = ns.run(); 127 if (report) { 128 std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; 129 std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; 130 if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n'; 131 } 114 132 } 115 133 … … 152 170 { 153 171 case DimacsDescriptor::MIN: 154 solve_min<Value>(ap,is,os, desc);172 solve_min<Value>(ap,is,os,infty,desc); 155 173 break; 156 174 case DimacsDescriptor::MAX: -
tools/lgf-gen.cc
r584 r623 66 66 double tlen=0; 67 67 for(EdgeIt e(g);e!=INVALID;++e) 68 tlen+=s qrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());68 tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); 69 69 return tlen; 70 70 } … … 189 189 (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y); 190 190 191 return d / (2 * a) + s qrt((d * d + e * e) / (4 * a * a) + f / a);191 return d / (2 * a) + std::sqrt((d * d + e * e) / (4 * a * a) + f / a); 192 192 } 193 193 … … 207 207 double b = (q.x - sx) * p.y - (p.x - sx) * q.y; 208 208 double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare(); 209 return (b - s qrt(d)) / a;209 return (b - std::sqrt(d)) / a; 210 210 } 211 211 … … 481 481 g.erase(*ei); 482 482 ConstMap<Arc,int> cegy(1); 483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy ,a,b);484 int k=sur.run( 2);483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 484 int k=sur.run(a,b,2); 485 485 if(k<2 || sur.totalLength()>d) 486 486 g.addEdge(a,b); … … 512 512 if(e==INVALID) { 513 513 ConstMap<Arc,int> cegy(1); 514 Suurballe<ListGraph,ConstMap<Arc,int> > 515 sur(g,cegy,pi->a,pi->b); 516 int k=sur.run(2); 514 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 515 int k=sur.run(pi->a,pi->b,2); 517 516 if(k<2 || sur.totalLength()>d) 518 517 { … … 721 720 722 721 if (ap["rand"]) { 723 int seed = time(0);722 int seed = int(time(0)); 724 723 std::cout << "Random number seed: " << seed << std::endl; 725 724 rnd = Random(seed); … … 814 813 double tlen=0; 815 814 for(EdgeIt e(g);e!=INVALID;++e) 816 tlen+=s qrt((coords[g.v(e)]-coords[g.u(e)]).normSquare());815 tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); 817 816 std::cout << "Total arc length : " << tlen << std::endl; 818 817
Note: See TracChangeset
for help on using the changeset viewer.