Changeset 1979:c2992fd74dad in lemon-0.x
- Timestamp:
- 02/22/06 19:26:56 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569
- Files:
-
- 6 added
- 7 deleted
- 25 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/Makefile.am
r1971 r1979 17 17 descriptor_map_demo \ 18 18 coloring \ 19 grid_ graph_demo \19 grid_ugraph_demo \ 20 20 topology_demo \ 21 21 simann_maxcut_demo … … 44 44 graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc 45 45 46 grid_ graph_demo_SOURCES = grid_graph_demo.cc46 grid_ugraph_demo_SOURCES = grid_ugraph_demo.cc 47 47 48 48 graph_orientation_SOURCES = graph_orientation.cc -
lemon/Makefile.am
r1977 r1979 41 41 fredman_tarjan.h \ 42 42 full_graph.h \ 43 grid_ graph.h \43 grid_ugraph.h \ 44 44 graph_adaptor.h \ 45 45 graph_utils.h \ … … 76 76 topology.h \ 77 77 traits.h \ 78 ugraph_adaptor.h \ 78 79 unionfind.h \ 79 80 xy.h \ … … 88 89 bits/array_map.h \ 89 90 bits/default_map.h \ 91 bits/static_map.h \ 90 92 bits/vector_map.h \ 91 bits/iterable_graph_extender.h \ 92 bits/extendable_graph_extender.h \ 93 bits/clearable_graph_extender.h \ 94 bits/erasable_graph_extender.h \ 93 bits/map_extender.h \ 95 94 bits/graph_extender.h \ 96 bits/ map_extender.h \97 bits/ static_map.h \95 bits/graph_adaptor_extender.h \ 96 bits/edge_set_extender.h \ 98 97 bits/item_reader.h \ 99 98 bits/item_writer.h \ -
lemon/bits/alteration_notifier.h
r1956 r1979 266 266 void add(const Item& item) { 267 267 typename Container::iterator it; 268 for (it = container.begin(); it != container.end(); ++it) { 269 (*it)->add(item); 268 try { 269 for (it = container.begin(); it != container.end(); ++it) { 270 (*it)->add(item); 271 } 272 } catch (...) { 273 typename Container::iterator jt; 274 for (jt = container.begin(); jt != it; ++it) { 275 (*it)->erase(item); 276 } 277 throw; 270 278 } 271 279 } … … 279 287 void add(const std::vector<Item>& items) { 280 288 typename Container::iterator it; 281 for (it = container.begin(); it != container.end(); ++it) { 282 (*it)->add(items); 289 try { 290 for (it = container.begin(); it != container.end(); ++it) { 291 (*it)->add(items); 292 } 293 } catch (...) { 294 typename Container::iterator jt; 295 for (jt = container.begin(); jt != it; ++it) { 296 (*it)->erase(items); 297 } 298 throw; 283 299 } 284 300 } … … 317 333 void build() { 318 334 typename Container::iterator it; 319 for (it = container.begin(); it != container.end(); ++it) { 320 (*it)->build(); 335 try { 336 for (it = container.begin(); it != container.end(); ++it) { 337 (*it)->build(); 338 } 339 } catch (...) { 340 typename Container::iterator jt; 341 for (jt = container.begin(); jt != it; ++it) { 342 (*it)->clear(); 343 } 344 throw; 321 345 } 322 346 } … … 336 360 }; 337 361 338 339 /// \brief Class to extend a graph with the functionality of alteration340 /// observing.341 ///342 /// AlterableGraphExtender extends the _Base graphs functionality with343 /// the possibility of alteration observing. It defines two observer344 /// registrys for the nodes and mapes.345 ///346 /// \todo Document what "alteration observing" is. And probably find a347 /// better (shorter) name.348 ///349 /// \param _Base is the base class to extend.350 ///351 /// \pre _Base is conform to the BaseGraphComponent concept.352 ///353 /// \post AlterableGraphExtender<_Base> is conform to the354 /// AlterableGraphComponent concept.355 ///356 /// \author Balazs Dezso357 358 template <typename _Base>359 class AlterableGraphExtender : public _Base {360 public:361 362 typedef AlterableGraphExtender Graph;363 typedef _Base Parent;364 365 typedef typename Parent::Node Node;366 typedef typename Parent::Edge Edge;367 368 /// The edge observer registry.369 typedef AlterationNotifier<Edge> EdgeNotifier;370 /// The node observer registry.371 typedef AlterationNotifier<Node> NodeNotifier;372 373 374 protected:375 376 mutable EdgeNotifier edge_notifier;377 378 mutable NodeNotifier node_notifier;379 380 public:381 382 /// \brief Gives back the edge alteration notifier.383 ///384 /// Gives back the edge alteration notifier.385 EdgeNotifier& getNotifier(Edge) const {386 return edge_notifier;387 }388 389 /// \brief Gives back the node alteration notifier.390 ///391 /// Gives back the node alteration notifier.392 NodeNotifier& getNotifier(Node) const {393 return node_notifier;394 }395 396 ~AlterableGraphExtender() {397 node_notifier.clear();398 edge_notifier.clear();399 }400 401 };402 403 404 template <typename _Base>405 class AlterableEdgeSetExtender : public _Base {406 public:407 408 typedef AlterableEdgeSetExtender Graph;409 typedef _Base Parent;410 411 typedef typename Parent::Edge Edge;412 413 /// The edge observer registry.414 typedef AlterationNotifier<Edge> EdgeNotifier;415 416 protected:417 418 mutable EdgeNotifier edge_notifier;419 420 public:421 422 /// \brief Gives back the edge alteration notifier.423 ///424 /// Gives back the edge alteration notifier.425 EdgeNotifier& getNotifier(Edge) const {426 return edge_notifier;427 }428 429 ~AlterableEdgeSetExtender() {430 edge_notifier.clear();431 }432 433 };434 435 /// \brief Class to extend an undirected graph with the functionality of436 /// alteration observing.437 ///438 /// \todo Document.439 ///440 /// \sa AlterableGraphExtender441 ///442 /// \bug This should be done some other way. Possibilities: template443 /// specialization (not very easy, if at all possible); some kind of444 /// enable_if boost technique?445 446 template <typename _Base>447 class AlterableUGraphExtender448 : public AlterableGraphExtender<_Base> {449 public:450 451 typedef AlterableUGraphExtender Graph;452 typedef AlterableGraphExtender<_Base> Parent;453 454 typedef typename Parent::UEdge UEdge;455 456 /// The edge observer registry.457 typedef AlterationNotifier<UEdge> UEdgeNotifier;458 459 protected:460 461 mutable UEdgeNotifier u_edge_notifier;462 463 public:464 465 using Parent::getNotifier;466 UEdgeNotifier& getNotifier(UEdge) const {467 return u_edge_notifier;468 }469 470 ~AlterableUGraphExtender() {471 u_edge_notifier.clear();472 }473 };474 475 template <typename _Base>476 class AlterableUEdgeSetExtender477 : public AlterableEdgeSetExtender<_Base> {478 public:479 480 typedef AlterableUEdgeSetExtender Graph;481 typedef AlterableEdgeSetExtender<_Base> Parent;482 483 typedef typename Parent::UEdge UEdge;484 485 typedef AlterationNotifier<UEdge> UEdgeNotifier;486 487 protected:488 489 mutable UEdgeNotifier u_edge_notifier;490 491 public:492 493 using Parent::getNotifier;494 UEdgeNotifier& getNotifier(UEdge) const {495 return u_edge_notifier;496 }497 498 ~AlterableUEdgeSetExtender() {499 u_edge_notifier.clear();500 }501 };502 503 504 505 template <typename _Base>506 class AlterableBpUGraphExtender : public _Base {507 public:508 509 typedef _Base Parent;510 typedef AlterableBpUGraphExtender Graph;511 512 typedef typename Parent::Node Node;513 typedef typename Parent::BNode BNode;514 typedef typename Parent::ANode ANode;515 typedef typename Parent::Edge Edge;516 typedef typename Parent::UEdge UEdge;517 518 519 typedef AlterationNotifier<Node> NodeNotifier;520 typedef AlterationNotifier<BNode> BNodeNotifier;521 typedef AlterationNotifier<ANode> ANodeNotifier;522 typedef AlterationNotifier<Edge> EdgeNotifier;523 typedef AlterationNotifier<UEdge> UEdgeNotifier;524 525 protected:526 527 mutable NodeNotifier nodeNotifier;528 mutable BNodeNotifier bNodeNotifier;529 mutable ANodeNotifier aNodeNotifier;530 mutable EdgeNotifier edgeNotifier;531 mutable UEdgeNotifier uEdgeNotifier;532 533 public:534 535 NodeNotifier& getNotifier(Node) const {536 return nodeNotifier;537 }538 539 BNodeNotifier& getNotifier(BNode) const {540 return bNodeNotifier;541 }542 543 ANodeNotifier& getNotifier(ANode) const {544 return aNodeNotifier;545 }546 547 EdgeNotifier& getNotifier(Edge) const {548 return edgeNotifier;549 }550 551 UEdgeNotifier& getNotifier(UEdge) const {552 return uEdgeNotifier;553 }554 555 ~AlterableBpUGraphExtender() {556 nodeNotifier.clear();557 bNodeNotifier.clear();558 aNodeNotifier.clear();559 edgeNotifier.clear();560 uEdgeNotifier.clear();561 }562 563 };564 362 565 363 /// @} -
lemon/bits/default_map.h
r1966 r1979 23 23 #include <lemon/bits/array_map.h> 24 24 #include <lemon/bits/vector_map.h> 25 #include <lemon/bits/static_map.h> 25 26 26 27 ///\ingroup graphmapfactory … … 31 32 namespace lemon { 32 33 33 #ifndef GLIBCXX_DEBUG 34 35 #ifndef _GLIBCXX_DEBUG 34 36 35 37 template <typename _Graph, typename _Item, typename _Value> … … 168 170 }; 169 171 170 171 /// \e172 template <typename _Base>173 class MappableGraphExtender : public _Base {174 public:175 176 typedef MappableGraphExtender<_Base> Graph;177 typedef _Base Parent;178 179 typedef typename Parent::Node Node;180 typedef typename Parent::NodeIt NodeIt;181 182 typedef typename Parent::Edge Edge;183 typedef typename Parent::EdgeIt EdgeIt;184 185 186 template <typename _Value>187 class NodeMap188 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {189 public:190 typedef MappableGraphExtender Graph;191 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;192 193 NodeMap(const Graph& _g)194 : Parent(_g) {}195 NodeMap(const Graph& _g, const _Value& _v)196 : Parent(_g, _v) {}197 198 NodeMap& operator=(const NodeMap& cmap) {199 return operator=<NodeMap>(cmap);200 }201 202 203 /// \brief Template assign operator.204 ///205 /// The given parameter should be conform to the ReadMap206 /// concecpt and could be indiced by the current item set of207 /// the NodeMap. In this case the value for each item208 /// is assigned by the value of the given ReadMap.209 template <typename CMap>210 NodeMap& operator=(const CMap& cmap) {211 checkConcept<concept::ReadMap<Node, _Value>, CMap>();212 const typename Parent::Graph* graph = Parent::getGraph();213 Node it;214 for (graph->first(it); it != INVALID; graph->next(it)) {215 Parent::set(it, cmap[it]);216 }217 return *this;218 }219 220 };221 222 template <typename _Value>223 class EdgeMap224 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {225 public:226 typedef MappableGraphExtender Graph;227 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;228 229 EdgeMap(const Graph& _g)230 : Parent(_g) {}231 EdgeMap(const Graph& _g, const _Value& _v)232 : Parent(_g, _v) {}233 234 EdgeMap& operator=(const EdgeMap& cmap) {235 return operator=<EdgeMap>(cmap);236 }237 238 template <typename CMap>239 EdgeMap& operator=(const CMap& cmap) {240 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();241 const typename Parent::Graph* graph = Parent::getGraph();242 Edge it;243 for (graph->first(it); it != INVALID; graph->next(it)) {244 Parent::set(it, cmap[it]);245 }246 return *this;247 }248 };249 250 };251 252 /// \e253 template <typename _Base>254 class MappableEdgeSetExtender : public _Base {255 public:256 257 typedef MappableEdgeSetExtender<_Base> Graph;258 typedef _Base Parent;259 260 typedef typename Parent::Edge Edge;261 typedef typename Parent::EdgeIt EdgeIt;262 263 template <typename _Value>264 class EdgeMap265 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {266 public:267 typedef MappableEdgeSetExtender Graph;268 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;269 270 EdgeMap(const Graph& _g)271 : Parent(_g) {}272 EdgeMap(const Graph& _g, const _Value& _v)273 : Parent(_g, _v) {}274 275 EdgeMap& operator=(const EdgeMap& cmap) {276 return operator=<EdgeMap>(cmap);277 }278 279 template <typename CMap>280 EdgeMap& operator=(const CMap& cmap) {281 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();282 const typename Parent::Graph* graph = Parent::getGraph();283 Edge it;284 for (graph->first(it); it != INVALID; graph->next(it)) {285 Parent::set(it, cmap[it]);286 }287 return *this;288 }289 };290 291 };292 293 /// \e294 template <typename _Base>295 class MappableUGraphExtender :296 public MappableGraphExtender<_Base> {297 public:298 299 typedef MappableUGraphExtender Graph;300 typedef MappableGraphExtender<_Base> Parent;301 302 typedef typename Parent::UEdge UEdge;303 304 template <typename _Value>305 class UEdgeMap306 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {307 public:308 typedef MappableUGraphExtender Graph;309 typedef IterableMapExtender<310 DefaultMap<Graph, UEdge, _Value> > Parent;311 312 UEdgeMap(const Graph& _g)313 : Parent(_g) {}314 UEdgeMap(const Graph& _g, const _Value& _v)315 : Parent(_g, _v) {}316 317 UEdgeMap& operator=(const UEdgeMap& cmap) {318 return operator=<UEdgeMap>(cmap);319 }320 321 template <typename CMap>322 UEdgeMap& operator=(const CMap& cmap) {323 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();324 const typename Parent::Graph* graph = Parent::getGraph();325 UEdge it;326 for (graph->first(it); it != INVALID; graph->next(it)) {327 Parent::set(it, cmap[it]);328 }329 return *this;330 }331 };332 333 334 };335 336 /// \e337 template <typename _Base>338 class MappableUEdgeSetExtender :339 public MappableEdgeSetExtender<_Base> {340 public:341 342 typedef MappableUEdgeSetExtender Graph;343 typedef MappableEdgeSetExtender<_Base> Parent;344 345 typedef typename Parent::UEdge UEdge;346 347 template <typename _Value>348 class UEdgeMap349 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {350 public:351 typedef MappableUEdgeSetExtender Graph;352 typedef IterableMapExtender<353 DefaultMap<Graph, UEdge, _Value> > Parent;354 355 UEdgeMap(const Graph& _g)356 : Parent(_g) {}357 UEdgeMap(const Graph& _g, const _Value& _v)358 : Parent(_g, _v) {}359 360 UEdgeMap& operator=(const UEdgeMap& cmap) {361 return operator=<UEdgeMap>(cmap);362 }363 364 template <typename CMap>365 UEdgeMap& operator=(const CMap& cmap) {366 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();367 const typename Parent::Graph* graph = Parent::getGraph();368 UEdge it;369 for (graph->first(it); it != INVALID; graph->next(it)) {370 Parent::set(it, cmap[it]);371 }372 return *this;373 }374 };375 376 377 };378 379 380 template <typename _Base>381 class MappableBpUGraphExtender : public _Base {382 public:383 384 typedef _Base Parent;385 typedef MappableBpUGraphExtender Graph;386 387 typedef typename Parent::Node Node;388 typedef typename Parent::ANode ANode;389 typedef typename Parent::BNode BNode;390 typedef typename Parent::Edge Edge;391 typedef typename Parent::UEdge UEdge;392 393 template <typename _Value>394 class ANodeMap395 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {396 public:397 typedef MappableBpUGraphExtender Graph;398 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >399 Parent;400 401 ANodeMap(const Graph& _g)402 : Parent(_g) {}403 ANodeMap(const Graph& _g, const _Value& _v)404 : Parent(_g, _v) {}405 406 ANodeMap& operator=(const ANodeMap& cmap) {407 return operator=<ANodeMap>(cmap);408 }409 410 411 /// \brief Template assign operator.412 ///413 /// The given parameter should be conform to the ReadMap414 /// concept and could be indiced by the current item set of415 /// the ANodeMap. In this case the value for each item416 /// is assigned by the value of the given ReadMap.417 template <typename CMap>418 ANodeMap& operator=(const CMap& cmap) {419 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();420 const typename Parent::Graph* graph = Parent::getGraph();421 ANode it;422 for (graph->first(it); it != INVALID; graph->next(it)) {423 Parent::set(it, cmap[it]);424 }425 return *this;426 }427 428 };429 430 template <typename _Value>431 class BNodeMap432 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {433 public:434 typedef MappableBpUGraphExtender Graph;435 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >436 Parent;437 438 BNodeMap(const Graph& _g)439 : Parent(_g) {}440 BNodeMap(const Graph& _g, const _Value& _v)441 : Parent(_g, _v) {}442 443 BNodeMap& operator=(const BNodeMap& cmap) {444 return operator=<BNodeMap>(cmap);445 }446 447 448 /// \brief Template assign operator.449 ///450 /// The given parameter should be conform to the ReadMap451 /// concept and could be indiced by the current item set of452 /// the BNodeMap. In this case the value for each item453 /// is assigned by the value of the given ReadMap.454 template <typename CMap>455 BNodeMap& operator=(const CMap& cmap) {456 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();457 const typename Parent::Graph* graph = Parent::getGraph();458 BNode it;459 for (graph->first(it); it != INVALID; graph->next(it)) {460 Parent::set(it, cmap[it]);461 }462 return *this;463 }464 465 };466 467 protected:468 469 template <typename _Value>470 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {471 public:472 typedef MappableBpUGraphExtender Graph;473 474 typedef Node Key;475 typedef _Value Value;476 477 /// The reference type of the map;478 typedef typename BNodeMap<_Value>::Reference Reference;479 /// The pointer type of the map;480 typedef typename BNodeMap<_Value>::Pointer Pointer;481 482 /// The const value type of the map.483 typedef const Value ConstValue;484 /// The const reference type of the map;485 typedef typename BNodeMap<_Value>::ConstReference ConstReference;486 /// The pointer type of the map;487 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;488 489 typedef True ReferenceMapTag;490 491 NodeMapBase(const Graph& _g)492 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {493 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));494 }495 NodeMapBase(const Graph& _g, const _Value& _v)496 : graph(&_g), bNodeMap(_g, _v),497 aNodeMap(_g, _v) {498 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));499 }500 501 virtual ~NodeMapBase() {502 if (Parent::NodeNotifier::ObserverBase::attached()) {503 Parent::NodeNotifier::ObserverBase::detach();504 }505 }506 507 ConstReference operator[](const Key& node) const {508 if (Parent::aNode(node)) {509 return aNodeMap[node];510 } else {511 return bNodeMap[node];512 }513 }514 515 Reference operator[](const Key& node) {516 if (Parent::aNode(node)) {517 return aNodeMap[node];518 } else {519 return bNodeMap[node];520 }521 }522 523 void set(const Key& node, const Value& value) {524 if (Parent::aNode(node)) {525 aNodeMap.set(node, value);526 } else {527 bNodeMap.set(node, value);528 }529 }530 531 protected:532 533 virtual void add(const Node&) {}534 virtual void add(const std::vector<Node>&) {}535 virtual void erase(const Node&) {}536 virtual void erase(const std::vector<Node>&) {}537 virtual void clear() {}538 virtual void build() {}539 540 const Graph* getGraph() const { return graph; }541 542 private:543 const Graph* graph;544 BNodeMap<_Value> bNodeMap;545 ANodeMap<_Value> aNodeMap;546 };547 548 public:549 550 template <typename _Value>551 class NodeMap552 : public IterableMapExtender<NodeMapBase<_Value> > {553 public:554 typedef MappableBpUGraphExtender Graph;555 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;556 557 NodeMap(const Graph& _g)558 : Parent(_g) {}559 NodeMap(const Graph& _g, const _Value& _v)560 : Parent(_g, _v) {}561 562 NodeMap& operator=(const NodeMap& cmap) {563 return operator=<NodeMap>(cmap);564 }565 566 567 /// \brief Template assign operator.568 ///569 /// The given parameter should be conform to the ReadMap570 /// concept and could be indiced by the current item set of571 /// the NodeMap. In this case the value for each item572 /// is assigned by the value of the given ReadMap.573 template <typename CMap>574 NodeMap& operator=(const CMap& cmap) {575 checkConcept<concept::ReadMap<Node, _Value>, CMap>();576 const typename Parent::Graph* graph = Parent::getGraph();577 Node it;578 for (graph->first(it); it != INVALID; graph->next(it)) {579 Parent::set(it, cmap[it]);580 }581 return *this;582 }583 584 };585 586 587 588 template <typename _Value>589 class EdgeMap590 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {591 public:592 typedef MappableBpUGraphExtender Graph;593 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;594 595 EdgeMap(const Graph& _g)596 : Parent(_g) {}597 EdgeMap(const Graph& _g, const _Value& _v)598 : Parent(_g, _v) {}599 600 EdgeMap& operator=(const EdgeMap& cmap) {601 return operator=<EdgeMap>(cmap);602 }603 604 template <typename CMap>605 EdgeMap& operator=(const CMap& cmap) {606 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();607 const typename Parent::Graph* graph = Parent::getGraph();608 Edge it;609 for (graph->first(it); it != INVALID; graph->next(it)) {610 Parent::set(it, cmap[it]);611 }612 return *this;613 }614 };615 616 template <typename _Value>617 class UEdgeMap618 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {619 public:620 typedef MappableBpUGraphExtender Graph;621 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >622 Parent;623 624 UEdgeMap(const Graph& _g)625 : Parent(_g) {}626 UEdgeMap(const Graph& _g, const _Value& _v)627 : Parent(_g, _v) {}628 629 UEdgeMap& operator=(const UEdgeMap& cmap) {630 return operator=<UEdgeMap>(cmap);631 }632 633 template <typename CMap>634 UEdgeMap& operator=(const CMap& cmap) {635 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();636 const typename Parent::Graph* graph = Parent::getGraph();637 UEdge it;638 for (graph->first(it); it != INVALID; graph->next(it)) {639 Parent::set(it, cmap[it]);640 }641 return *this;642 }643 };644 645 };646 647 172 } 648 173 -
lemon/bits/graph_extender.h
r1956 r1979 23 23 #include <lemon/error.h> 24 24 25 #include <lemon/bits/default_map.h> 26 25 27 namespace lemon { 26 28 27 template <typename _Base>28 class GraphExtender : public _Base {29 template <typename Base> 30 class GraphExtender : public Base { 29 31 public: 30 32 31 typedef _Base Parent;33 typedef Base Parent; 32 34 typedef GraphExtender Graph; 35 36 // Base extensions 33 37 34 38 typedef typename Parent::Node Node; … … 60 64 } 61 65 66 // Alterable extension 67 68 typedef AlterationNotifier<Node> NodeNotifier; 69 typedef AlterationNotifier<Edge> EdgeNotifier; 70 71 72 protected: 73 74 mutable NodeNotifier node_notifier; 75 mutable EdgeNotifier edge_notifier; 76 77 public: 78 79 NodeNotifier& getNotifier(Node) const { 80 return node_notifier; 81 } 82 83 EdgeNotifier& getNotifier(Edge) const { 84 return edge_notifier; 85 } 86 87 class NodeIt : public Node { 88 const Graph* graph; 89 public: 90 91 NodeIt() {} 92 93 NodeIt(Invalid i) : Node(i) { } 94 95 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 96 _graph.first(*static_cast<Node*>(this)); 97 } 98 99 NodeIt(const Graph& _graph, const Node& node) 100 : Node(node), graph(&_graph) {} 101 102 NodeIt& operator++() { 103 graph->next(*this); 104 return *this; 105 } 106 107 }; 108 109 110 class EdgeIt : public Edge { 111 const Graph* graph; 112 public: 113 114 EdgeIt() { } 115 116 EdgeIt(Invalid i) : Edge(i) { } 117 118 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 119 _graph.first(*static_cast<Edge*>(this)); 120 } 121 122 EdgeIt(const Graph& _graph, const Edge& e) : 123 Edge(e), graph(&_graph) { } 124 125 EdgeIt& operator++() { 126 graph->next(*this); 127 return *this; 128 } 129 130 }; 131 132 133 class OutEdgeIt : public Edge { 134 const Graph* graph; 135 public: 136 137 OutEdgeIt() { } 138 139 OutEdgeIt(Invalid i) : Edge(i) { } 140 141 OutEdgeIt(const Graph& _graph, const Node& node) 142 : graph(&_graph) { 143 _graph.firstOut(*this, node); 144 } 145 146 OutEdgeIt(const Graph& _graph, const Edge& edge) 147 : Edge(edge), graph(&_graph) {} 148 149 OutEdgeIt& operator++() { 150 graph->nextOut(*this); 151 return *this; 152 } 153 154 }; 155 156 157 class InEdgeIt : public Edge { 158 const Graph* graph; 159 public: 160 161 InEdgeIt() { } 162 163 InEdgeIt(Invalid i) : Edge(i) { } 164 165 InEdgeIt(const Graph& _graph, const Node& node) 166 : graph(&_graph) { 167 _graph.firstIn(*this, node); 168 } 169 170 InEdgeIt(const Graph& _graph, const Edge& edge) : 171 Edge(edge), graph(&_graph) {} 172 173 InEdgeIt& operator++() { 174 graph->nextIn(*this); 175 return *this; 176 } 177 178 }; 179 180 /// \brief Base node of the iterator 181 /// 182 /// Returns the base node (ie. the source in this case) of the iterator 183 Node baseNode(const OutEdgeIt &e) const { 184 return Parent::source(e); 185 } 186 /// \brief Running node of the iterator 187 /// 188 /// Returns the running node (ie. the target in this case) of the 189 /// iterator 190 Node runningNode(const OutEdgeIt &e) const { 191 return Parent::target(e); 192 } 193 194 /// \brief Base node of the iterator 195 /// 196 /// Returns the base node (ie. the target in this case) of the iterator 197 Node baseNode(const InEdgeIt &e) const { 198 return Parent::target(e); 199 } 200 /// \brief Running node of the iterator 201 /// 202 /// Returns the running node (ie. the source in this case) of the 203 /// iterator 204 Node runningNode(const InEdgeIt &e) const { 205 return Parent::source(e); 206 } 207 208 209 template <typename _Value> 210 class NodeMap 211 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > { 212 public: 213 typedef GraphExtender Graph; 214 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent; 215 216 NodeMap(const Graph& _g) 217 : Parent(_g) {} 218 NodeMap(const Graph& _g, const _Value& _v) 219 : Parent(_g, _v) {} 220 221 NodeMap& operator=(const NodeMap& cmap) { 222 return operator=<NodeMap>(cmap); 223 } 224 225 226 /// \brief Template assign operator. 227 /// 228 /// The given parameter should be conform to the ReadMap 229 /// concecpt and could be indiced by the current item set of 230 /// the NodeMap. In this case the value for each item 231 /// is assigned by the value of the given ReadMap. 232 template <typename CMap> 233 NodeMap& operator=(const CMap& cmap) { 234 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 235 const typename Parent::Graph* graph = Parent::getGraph(); 236 Node it; 237 for (graph->first(it); it != INVALID; graph->next(it)) { 238 Parent::set(it, cmap[it]); 239 } 240 return *this; 241 } 242 243 }; 244 245 template <typename _Value> 246 class EdgeMap 247 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 248 public: 249 typedef GraphExtender Graph; 250 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 251 252 EdgeMap(const Graph& _g) 253 : Parent(_g) {} 254 EdgeMap(const Graph& _g, const _Value& _v) 255 : Parent(_g, _v) {} 256 257 EdgeMap& operator=(const EdgeMap& cmap) { 258 return operator=<EdgeMap>(cmap); 259 } 260 261 template <typename CMap> 262 EdgeMap& operator=(const CMap& cmap) { 263 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 264 const typename Parent::Graph* graph = Parent::getGraph(); 265 Edge it; 266 for (graph->first(it); it != INVALID; graph->next(it)) { 267 Parent::set(it, cmap[it]); 268 } 269 return *this; 270 } 271 }; 272 273 274 Node addNode() { 275 Node node = Parent::addNode(); 276 getNotifier(Node()).add(node); 277 return node; 278 } 279 280 Edge addEdge(const Node& from, const Node& to) { 281 Edge edge = Parent::addEdge(from, to); 282 getNotifier(Edge()).add(edge); 283 return edge; 284 } 285 286 void clear() { 287 getNotifier(Edge()).clear(); 288 getNotifier(Node()).clear(); 289 Parent::clear(); 290 } 291 292 293 void erase(const Node& node) { 294 Edge edge; 295 Parent::firstOut(edge, node); 296 while (edge != INVALID ) { 297 erase(edge); 298 Parent::firstOut(edge, node); 299 } 300 301 Parent::firstIn(edge, node); 302 while (edge != INVALID ) { 303 erase(edge); 304 Parent::firstIn(edge, node); 305 } 306 307 getNotifier(Node()).erase(node); 308 Parent::erase(node); 309 } 310 311 void erase(const Edge& edge) { 312 getNotifier(Edge()).erase(edge); 313 Parent::erase(edge); 314 } 315 316 317 ~GraphExtender() { 318 getNotifier(Edge()).clear(); 319 getNotifier(Node()).clear(); 320 } 62 321 }; 63 322 64 template <typename _Base> 65 class UGraphExtender : public _Base { 66 typedef _Base Parent; 67 typedef UGraphExtender Graph; 323 template <typename Base> 324 class UGraphBaseExtender : public Base { 68 325 69 326 public: 70 327 328 typedef Base Parent; 71 329 typedef typename Parent::Edge UEdge; 72 330 typedef typename Parent::Node Node; 73 331 332 typedef True UndirectedTag; 333 74 334 class Edge : public UEdge { 75 friend class UGraph Extender;335 friend class UGraphBaseExtender; 76 336 77 337 protected: 78 // FIXME: Marci use opposite logic in his graph adaptors. It would79 // be reasonable to syncronize...80 338 bool forward; 81 339 … … 102 360 103 361 104 /// \brief Edge of opposite direction. 105 /// 106 /// Returns the Edge of opposite direction. 107 Edge oppositeEdge(const Edge &e) const { 108 return Edge(e,!e.forward); 109 } 110 111 public: 112 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" 113 /// or something??? 362 114 363 using Parent::source; 115 364 … … 119 368 } 120 369 121 /// \todo Shouldn't the "target" of an undirected edge be called "bNode"122 /// or something???123 370 using Parent::target; 124 371 … … 126 373 Node target(const Edge &e) const { 127 374 return e.forward ? Parent::target(e) : Parent::source(e); 128 }129 130 Node oppositeNode(const Node &n, const UEdge &e) const {131 if( n == Parent::source(e))132 return Parent::target(e);133 else if( n == Parent::target(e))134 return Parent::source(e);135 else136 return INVALID;137 }138 139 /// \brief Directed edge from an undirected edge and a source node.140 ///141 /// Returns a (directed) Edge corresponding to the specified UEdge142 /// and source Node.143 ///144 Edge direct(const UEdge &ue, const Node &s) const {145 return Edge(ue, s == source(ue));146 375 } 147 376 … … 164 393 165 394 using Parent::first; 395 using Parent::next; 396 166 397 void first(Edge &e) const { 167 398 Parent::first(e); … … 169 400 } 170 401 171 using Parent::next;172 402 void next(Edge &e) const { 173 403 if( e.forward ) { … … 179 409 } 180 410 } 181 182 public:183 411 184 412 void firstOut(Edge &e, const Node &n) const { … … 230 458 } 231 459 232 void firstInc(UEdge &e, const Node &n) const {233 Parent::firstOut(e, n);234 if (e != INVALID) return;235 Parent::firstIn(e, n);236 }237 void nextInc(UEdge &e, const Node &n) const {238 if (Parent::source(e) == n) {239 Parent::nextOut(e);240 if (e != INVALID) return;241 Parent::firstIn(e, n);242 } else {243 Parent::nextIn(e);244 }245 }246 247 460 void firstInc(UEdge &e, bool &d, const Node &n) const { 248 461 d = true; … … 252 465 Parent::firstIn(e, n); 253 466 } 467 254 468 void nextInc(UEdge &e, bool &d) const { 255 469 if (d) { … … 264 478 } 265 479 266 // Miscellaneous stuff: 267 268 /// \todo these methods (id, maxEdgeId) should be moved into separate 269 /// Extender 270 271 // using Parent::id; 272 // Using "using" is not a good idea, cause it could be that there is 273 // no "id" in Parent... 480 Node nodeFromId(int id) const { 481 return Parent::nodeFromId(id); 482 } 483 484 Edge edgeFromId(int id) const { 485 return direct(Parent::edgeFromId(id >> 1), bool(id & 1)); 486 } 487 488 UEdge uEdgeFromId(int id) const { 489 return Parent::edgeFromId(id >> 1); 490 } 274 491 275 492 int id(const Node &n) const { … … 297 514 } 298 515 299 int maxId(Node) const {300 return maxNodeId();301 }302 303 int maxId(Edge) const {304 return maxEdgeId();305 }306 int maxId(UEdge) const {307 return maxUEdgeId();308 }309 516 310 517 int edgeNum() const { … … 315 522 return Parent::edgeNum(); 316 523 } 317 318 Node nodeFromId(int id) const {319 return Parent::nodeFromId(id);320 }321 322 Edge edgeFromId(int id) const {323 return direct(Parent::edgeFromId(id >> 1), bool(id & 1));324 }325 326 UEdge uEdgeFromId(int id) const {327 return Parent::edgeFromId(id >> 1);328 }329 330 Node fromId(int id, Node) const {331 return nodeFromId(id);332 }333 334 Edge fromId(int id, Edge) const {335 return edgeFromId(id);336 }337 338 UEdge fromId(int id, UEdge) const {339 return uEdgeFromId(id);340 }341 342 524 343 525 Edge findEdge(Node source, Node target, Edge prev) const { … … 376 558 return INVALID; 377 559 } 378 379 560 }; 380 561 381 562 382 template <typename _Base>383 class BpUGraphExtender : public _Base {563 template <typename Base> 564 class UGraphExtender : public Base { 384 565 public: 385 typedef _Base Parent; 386 typedef BpUGraphExtender Graph; 566 567 typedef Base Parent; 568 typedef UGraphExtender Graph; 569 570 typedef typename Parent::Node Node; 571 typedef typename Parent::Edge Edge; 572 typedef typename Parent::UEdge UEdge; 573 574 // UGraph extension 575 576 int maxId(Node) const { 577 return Parent::maxNodeId(); 578 } 579 580 int maxId(Edge) const { 581 return Parent::maxEdgeId(); 582 } 583 584 int maxId(UEdge) const { 585 return Parent::maxUEdgeId(); 586 } 587 588 Node fromId(int id, Node) const { 589 return Parent::nodeFromId(id); 590 } 591 592 Edge fromId(int id, Edge) const { 593 return Parent::edgeFromId(id); 594 } 595 596 UEdge fromId(int id, UEdge) const { 597 return Parent::uEdgeFromId(id); 598 } 599 600 Node oppositeNode(const Node &n, const UEdge &e) const { 601 if( n == Parent::source(e)) 602 return Parent::target(e); 603 else if( n == Parent::target(e)) 604 return Parent::source(e); 605 else 606 return INVALID; 607 } 608 609 Edge oppositeEdge(const Edge &e) const { 610 return Parent::direct(e, !Parent::direction(e)); 611 } 612 613 using Parent::direct; 614 Edge direct(const UEdge &ue, const Node &s) const { 615 return Parent::direct(ue, Parent::source(ue) == s); 616 } 617 618 // Alterable extension 619 620 typedef AlterationNotifier<Node> NodeNotifier; 621 typedef AlterationNotifier<Edge> EdgeNotifier; 622 typedef AlterationNotifier<UEdge> UEdgeNotifier; 623 624 625 protected: 626 627 mutable NodeNotifier node_notifier; 628 mutable EdgeNotifier edge_notifier; 629 mutable UEdgeNotifier uedge_notifier; 630 631 public: 632 633 NodeNotifier& getNotifier(Node) const { 634 return node_notifier; 635 } 636 637 EdgeNotifier& getNotifier(Edge) const { 638 return edge_notifier; 639 } 640 641 UEdgeNotifier& getNotifier(UEdge) const { 642 return uedge_notifier; 643 } 644 645 646 647 class NodeIt : public Node { 648 const Graph* graph; 649 public: 650 651 NodeIt() {} 652 653 NodeIt(Invalid i) : Node(i) { } 654 655 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 656 _graph.first(*static_cast<Node*>(this)); 657 } 658 659 NodeIt(const Graph& _graph, const Node& node) 660 : Node(node), graph(&_graph) {} 661 662 NodeIt& operator++() { 663 graph->next(*this); 664 return *this; 665 } 666 667 }; 668 669 670 class EdgeIt : public Edge { 671 const Graph* graph; 672 public: 673 674 EdgeIt() { } 675 676 EdgeIt(Invalid i) : Edge(i) { } 677 678 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 679 _graph.first(*static_cast<Edge*>(this)); 680 } 681 682 EdgeIt(const Graph& _graph, const Edge& e) : 683 Edge(e), graph(&_graph) { } 684 685 EdgeIt& operator++() { 686 graph->next(*this); 687 return *this; 688 } 689 690 }; 691 692 693 class OutEdgeIt : public Edge { 694 const Graph* graph; 695 public: 696 697 OutEdgeIt() { } 698 699 OutEdgeIt(Invalid i) : Edge(i) { } 700 701 OutEdgeIt(const Graph& _graph, const Node& node) 702 : graph(&_graph) { 703 _graph.firstOut(*this, node); 704 } 705 706 OutEdgeIt(const Graph& _graph, const Edge& edge) 707 : Edge(edge), graph(&_graph) {} 708 709 OutEdgeIt& operator++() { 710 graph->nextOut(*this); 711 return *this; 712 } 713 714 }; 715 716 717 class InEdgeIt : public Edge { 718 const Graph* graph; 719 public: 720 721 InEdgeIt() { } 722 723 InEdgeIt(Invalid i) : Edge(i) { } 724 725 InEdgeIt(const Graph& _graph, const Node& node) 726 : graph(&_graph) { 727 _graph.firstIn(*this, node); 728 } 729 730 InEdgeIt(const Graph& _graph, const Edge& edge) : 731 Edge(edge), graph(&_graph) {} 732 733 InEdgeIt& operator++() { 734 graph->nextIn(*this); 735 return *this; 736 } 737 738 }; 739 740 741 class UEdgeIt : public Parent::UEdge { 742 const Graph* graph; 743 public: 744 745 UEdgeIt() { } 746 747 UEdgeIt(Invalid i) : UEdge(i) { } 748 749 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 750 _graph.first(*static_cast<UEdge*>(this)); 751 } 752 753 UEdgeIt(const Graph& _graph, const UEdge& e) : 754 UEdge(e), graph(&_graph) { } 755 756 UEdgeIt& operator++() { 757 graph->next(*this); 758 return *this; 759 } 760 761 }; 762 763 class IncEdgeIt : public Parent::UEdge { 764 friend class UGraphExtender; 765 const Graph* graph; 766 bool direction; 767 public: 768 769 IncEdgeIt() { } 770 771 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } 772 773 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 774 _graph.firstInc(*this, direction, n); 775 } 776 777 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 778 : graph(&_graph), UEdge(ue) { 779 direction = (_graph.source(ue) == n); 780 } 781 782 IncEdgeIt& operator++() { 783 graph->nextInc(*this, direction); 784 return *this; 785 } 786 }; 787 788 /// \brief Base node of the iterator 789 /// 790 /// Returns the base node (ie. the source in this case) of the iterator 791 Node baseNode(const OutEdgeIt &e) const { 792 return Parent::source((Edge)e); 793 } 794 /// \brief Running node of the iterator 795 /// 796 /// Returns the running node (ie. the target in this case) of the 797 /// iterator 798 Node runningNode(const OutEdgeIt &e) const { 799 return Parent::target((Edge)e); 800 } 801 802 /// \brief Base node of the iterator 803 /// 804 /// Returns the base node (ie. the target in this case) of the iterator 805 Node baseNode(const InEdgeIt &e) const { 806 return Parent::target((Edge)e); 807 } 808 /// \brief Running node of the iterator 809 /// 810 /// Returns the running node (ie. the source in this case) of the 811 /// iterator 812 Node runningNode(const InEdgeIt &e) const { 813 return Parent::source((Edge)e); 814 } 815 816 /// Base node of the iterator 817 /// 818 /// Returns the base node of the iterator 819 Node baseNode(const IncEdgeIt &e) const { 820 return e.direction ? source(e) : target(e); 821 } 822 /// Running node of the iterator 823 /// 824 /// Returns the running node of the iterator 825 Node runningNode(const IncEdgeIt &e) const { 826 return e.direction ? target(e) : source(e); 827 } 828 829 // Mappable extension 830 831 template <typename _Value> 832 class NodeMap 833 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > { 834 public: 835 typedef UGraphExtender Graph; 836 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent; 837 838 NodeMap(const Graph& _g) 839 : Parent(_g) {} 840 NodeMap(const Graph& _g, const _Value& _v) 841 : Parent(_g, _v) {} 842 843 NodeMap& operator=(const NodeMap& cmap) { 844 return operator=<NodeMap>(cmap); 845 } 846 847 848 /// \brief Template assign operator. 849 /// 850 /// The given parameter should be conform to the ReadMap 851 /// concecpt and could be indiced by the current item set of 852 /// the NodeMap. In this case the value for each item 853 /// is assigned by the value of the given ReadMap. 854 template <typename CMap> 855 NodeMap& operator=(const CMap& cmap) { 856 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 857 const typename Parent::Graph* graph = Parent::getGraph(); 858 Node it; 859 for (graph->first(it); it != INVALID; graph->next(it)) { 860 Parent::set(it, cmap[it]); 861 } 862 return *this; 863 } 864 865 }; 866 867 template <typename _Value> 868 class EdgeMap 869 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 870 public: 871 typedef UGraphExtender Graph; 872 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 873 874 EdgeMap(const Graph& _g) 875 : Parent(_g) {} 876 EdgeMap(const Graph& _g, const _Value& _v) 877 : Parent(_g, _v) {} 878 879 EdgeMap& operator=(const EdgeMap& cmap) { 880 return operator=<EdgeMap>(cmap); 881 } 882 883 template <typename CMap> 884 EdgeMap& operator=(const CMap& cmap) { 885 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 886 const typename Parent::Graph* graph = Parent::getGraph(); 887 Edge it; 888 for (graph->first(it); it != INVALID; graph->next(it)) { 889 Parent::set(it, cmap[it]); 890 } 891 return *this; 892 } 893 }; 894 895 896 template <typename _Value> 897 class UEdgeMap 898 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { 899 public: 900 typedef UGraphExtender Graph; 901 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 902 903 UEdgeMap(const Graph& _g) 904 : Parent(_g) {} 905 UEdgeMap(const Graph& _g, const _Value& _v) 906 : Parent(_g, _v) {} 907 908 UEdgeMap& operator=(const UEdgeMap& cmap) { 909 return operator=<UEdgeMap>(cmap); 910 } 911 912 template <typename CMap> 913 UEdgeMap& operator=(const CMap& cmap) { 914 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); 915 const typename Parent::Graph* graph = Parent::getGraph(); 916 UEdge it; 917 for (graph->first(it); it != INVALID; graph->next(it)) { 918 Parent::set(it, cmap[it]); 919 } 920 return *this; 921 } 922 }; 923 924 // Alteration extension 925 926 Node addNode() { 927 Node node = Parent::addNode(); 928 getNotifier(Node()).add(node); 929 return node; 930 } 931 932 UEdge addEdge(const Node& from, const Node& to) { 933 UEdge uedge = Parent::addEdge(from, to); 934 getNotifier(UEdge()).add(uedge); 935 getNotifier(Edge()).add(Parent::direct(uedge, true)); 936 getNotifier(Edge()).add(Parent::direct(uedge, false)); 937 return uedge; 938 } 939 940 void clear() { 941 getNotifier(Edge()).clear(); 942 getNotifier(UEdge()).clear(); 943 getNotifier(Node()).clear(); 944 Parent::clear(); 945 } 946 947 void erase(const Node& node) { 948 Edge edge; 949 Parent::firstOut(edge, node); 950 while (edge != INVALID ) { 951 erase(edge); 952 Parent::firstOut(edge, node); 953 } 954 955 Parent::firstIn(edge, node); 956 while (edge != INVALID ) { 957 erase(edge); 958 Parent::firstIn(edge, node); 959 } 960 961 getNotifier(Node()).erase(node); 962 Parent::erase(node); 963 } 964 965 void erase(const UEdge& uedge) { 966 getNotifier(Edge()).erase(Parent::direct(uedge, true)); 967 getNotifier(Edge()).erase(Parent::direct(uedge, false)); 968 getNotifier(UEdge()).erase(uedge); 969 Parent::erase(uedge); 970 } 971 972 ~UGraphExtender() { 973 getNotifier(Edge()).clear(); 974 getNotifier(UEdge()).clear(); 975 getNotifier(Node()).clear(); 976 } 977 978 }; 979 980 981 template <typename Base> 982 class BpUGraphBaseExtender : public Base { 983 public: 984 typedef Base Parent; 985 typedef BpUGraphBaseExtender Graph; 387 986 388 987 typedef typename Parent::Node Node; 389 988 typedef typename Parent::Edge UEdge; 390 989 990 391 991 using Parent::first; 392 992 using Parent::next; 393 993 394 994 using Parent::id; 995 996 class ANode : public Node { 997 friend class BpUGraphBaseExtender; 998 public: 999 ANode() {} 1000 ANode(const Node& node) : Node(node) { 1001 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 1002 typename Parent::NodeSetError()); 1003 } 1004 ANode(Invalid) : Node(INVALID) {} 1005 }; 1006 1007 void first(ANode& node) const { 1008 Parent::firstANode(static_cast<Node&>(node)); 1009 } 1010 void next(ANode& node) const { 1011 Parent::nextANode(static_cast<Node&>(node)); 1012 } 1013 1014 int id(const ANode& node) const { 1015 return Parent::aNodeId(node); 1016 } 1017 1018 class BNode : public Node { 1019 friend class BpUGraphBaseExtender; 1020 public: 1021 BNode() {} 1022 BNode(const Node& node) : Node(node) { 1023 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 1024 typename Parent::NodeSetError()); 1025 } 1026 BNode(Invalid) : Node(INVALID) {} 1027 }; 1028 1029 void first(BNode& node) const { 1030 Parent::firstBNode(static_cast<Node&>(node)); 1031 } 1032 void next(BNode& node) const { 1033 Parent::nextBNode(static_cast<Node&>(node)); 1034 } 1035 1036 int id(const BNode& node) const { 1037 return Parent::aNodeId(node); 1038 } 395 1039 396 1040 Node source(const UEdge& edge) const { … … 428 1072 429 1073 class Edge : public UEdge { 430 friend class BpUGraph Extender;1074 friend class BpUGraphBaseExtender; 431 1075 protected: 432 1076 bool forward; … … 505 1149 } 506 1150 1151 int id(const Edge& edge) const { 1152 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); 1153 } 1154 Edge edgeFromId(int id) const { 1155 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); 1156 } 1157 int maxEdgeId() const { 1158 return (Parent::maxId(UEdge()) << 1) + 1; 1159 } 1160 507 1161 bool direction(const Edge& edge) const { 508 1162 return edge.forward; 509 1163 } 510 1164 511 Edge direct(const UEdge& edge, const Node& node) const {512 return Edge(edge, node == Parent::source(edge));513 }514 515 1165 Edge direct(const UEdge& edge, bool direction) const { 516 1166 return Edge(edge, direction); 517 1167 } 1168 }; 1169 1170 template <typename Base> 1171 class BpUGraphExtender : public Base { 1172 public: 1173 typedef Base Parent; 1174 typedef BpUGraphExtender Graph; 1175 1176 typedef typename Parent::Node Node; 1177 typedef typename Parent::BNode BNode; 1178 typedef typename Parent::ANode ANode; 1179 typedef typename Parent::Edge Edge; 1180 typedef typename Parent::UEdge UEdge; 518 1181 519 1182 Node oppositeNode(const UEdge& edge, const Node& node) const { … … 522 1185 } 523 1186 1187 using Parent::direct; 1188 Edge direct(const UEdge& edge, const Node& node) const { 1189 return Edge(edge, node == Parent::source(edge)); 1190 } 1191 524 1192 Edge oppositeEdge(const Edge& edge) const { 525 return Edge(edge, !edge.forward); 526 } 527 528 int id(const Edge& edge) const { 529 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); 530 } 531 Edge edgeFromId(int id) const { 532 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); 533 } 534 int maxEdgeId() const { 535 return (Parent::maxId(UEdge()) << 1) + 1; 536 } 537 538 class ANode : public Node { 539 friend class BpUGraphExtender; 540 public: 541 ANode() {} 542 ANode(const Node& node) : Node(node) { 543 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 544 typename Parent::NodeSetError()); 545 } 546 ANode(Invalid) : Node(INVALID) {} 547 }; 548 549 void first(ANode& node) const { 550 Parent::firstANode(static_cast<Node&>(node)); 551 } 552 void next(ANode& node) const { 553 Parent::nextANode(static_cast<Node&>(node)); 554 } 555 556 int id(const ANode& node) const { 557 return Parent::aNodeId(node); 558 } 559 560 class BNode : public Node { 561 friend class BpUGraphExtender; 562 public: 563 BNode() {} 564 BNode(const Node& node) : Node(node) { 565 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 566 typename Parent::NodeSetError()); 567 } 568 BNode(Invalid) : Node(INVALID) {} 569 }; 570 571 void first(BNode& node) const { 572 Parent::firstBNode(static_cast<Node&>(node)); 573 } 574 void next(BNode& node) const { 575 Parent::nextBNode(static_cast<Node&>(node)); 576 } 577 578 int id(const BNode& node) const { 579 return Parent::aNodeId(node); 580 } 581 1193 return Parent::direct(edge, !Parent::direction(edge)); 1194 } 582 1195 583 1196 … … 592 1205 } 593 1206 int maxId(Edge) const { 594 return maxEdgeId();1207 return Parent::maxEdgeId(); 595 1208 } 596 1209 int maxId(UEdge) const { 597 return maxUEdgeId();1210 return Parent::maxUEdgeId(); 598 1211 } 599 1212 … … 609 1222 } 610 1223 Edge fromId(int id, Edge) const { 611 return edgeFromId(id);1224 return Parent::edgeFromId(id); 612 1225 } 613 1226 UEdge fromId(int id, UEdge) const { 614 return uEdgeFromId(id); 615 } 1227 return Parent::uEdgeFromId(id); 1228 } 1229 1230 typedef AlterationNotifier<Node> NodeNotifier; 1231 typedef AlterationNotifier<BNode> BNodeNotifier; 1232 typedef AlterationNotifier<ANode> ANodeNotifier; 1233 typedef AlterationNotifier<Edge> EdgeNotifier; 1234 typedef AlterationNotifier<UEdge> UEdgeNotifier; 1235 1236 protected: 1237 1238 mutable NodeNotifier nodeNotifier; 1239 mutable BNodeNotifier bNodeNotifier; 1240 mutable ANodeNotifier aNodeNotifier; 1241 mutable EdgeNotifier edgeNotifier; 1242 mutable UEdgeNotifier uEdgeNotifier; 1243 1244 public: 1245 1246 NodeNotifier& getNotifier(Node) const { 1247 return nodeNotifier; 1248 } 1249 1250 BNodeNotifier& getNotifier(BNode) const { 1251 return bNodeNotifier; 1252 } 1253 1254 ANodeNotifier& getNotifier(ANode) const { 1255 return aNodeNotifier; 1256 } 1257 1258 EdgeNotifier& getNotifier(Edge) const { 1259 return edgeNotifier; 1260 } 1261 1262 UEdgeNotifier& getNotifier(UEdge) const { 1263 return uEdgeNotifier; 1264 } 1265 1266 ~BpUGraphExtender() { 1267 getNotifier(UEdge()).clear(); 1268 getNotifier(Edge()).clear(); 1269 getNotifier(ANode()).clear(); 1270 getNotifier(BNode()).clear(); 1271 getNotifier(Node()).clear(); 1272 } 1273 1274 1275 class NodeIt : public Node { 1276 const Graph* graph; 1277 public: 1278 1279 NodeIt() { } 1280 1281 NodeIt(Invalid i) : Node(INVALID) { } 1282 1283 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 1284 graph->first(static_cast<Node&>(*this)); 1285 } 1286 1287 NodeIt(const Graph& _graph, const Node& node) 1288 : Node(node), graph(&_graph) { } 1289 1290 NodeIt& operator++() { 1291 graph->next(*this); 1292 return *this; 1293 } 1294 1295 }; 1296 1297 class ANodeIt : public Node { 1298 friend class BpUGraphExtender; 1299 const Graph* graph; 1300 public: 1301 1302 ANodeIt() { } 1303 1304 ANodeIt(Invalid i) : Node(INVALID) { } 1305 1306 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 1307 graph->firstANode(static_cast<Node&>(*this)); 1308 } 1309 1310 ANodeIt(const Graph& _graph, const Node& node) 1311 : Node(node), graph(&_graph) {} 1312 1313 ANodeIt& operator++() { 1314 graph->nextANode(*this); 1315 return *this; 1316 } 1317 }; 1318 1319 class BNodeIt : public Node { 1320 friend class BpUGraphExtender; 1321 const Graph* graph; 1322 public: 1323 1324 BNodeIt() { } 1325 1326 BNodeIt(Invalid i) : Node(INVALID) { } 1327 1328 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 1329 graph->firstBNode(static_cast<Node&>(*this)); 1330 } 1331 1332 BNodeIt(const Graph& _graph, const Node& node) 1333 : Node(node), graph(&_graph) {} 1334 1335 BNodeIt& operator++() { 1336 graph->nextBNode(*this); 1337 return *this; 1338 } 1339 }; 1340 1341 class EdgeIt : public Edge { 1342 friend class BpUGraphExtender; 1343 const Graph* graph; 1344 public: 1345 1346 EdgeIt() { } 1347 1348 EdgeIt(Invalid i) : Edge(INVALID) { } 1349 1350 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 1351 graph->first(static_cast<Edge&>(*this)); 1352 } 1353 1354 EdgeIt(const Graph& _graph, const Edge& edge) 1355 : Edge(edge), graph(&_graph) { } 1356 1357 EdgeIt& operator++() { 1358 graph->next(*this); 1359 return *this; 1360 } 1361 1362 }; 1363 1364 class UEdgeIt : public UEdge { 1365 friend class BpUGraphExtender; 1366 const Graph* graph; 1367 public: 1368 1369 UEdgeIt() { } 1370 1371 UEdgeIt(Invalid i) : UEdge(INVALID) { } 1372 1373 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 1374 graph->first(static_cast<UEdge&>(*this)); 1375 } 1376 1377 UEdgeIt(const Graph& _graph, const UEdge& edge) 1378 : UEdge(edge), graph(&_graph) { } 1379 1380 UEdgeIt& operator++() { 1381 graph->next(*this); 1382 return *this; 1383 } 1384 }; 1385 1386 class OutEdgeIt : public Edge { 1387 friend class BpUGraphExtender; 1388 const Graph* graph; 1389 public: 1390 1391 OutEdgeIt() { } 1392 1393 OutEdgeIt(Invalid i) : Edge(i) { } 1394 1395 OutEdgeIt(const Graph& _graph, const Node& node) 1396 : graph(&_graph) { 1397 graph->firstOut(*this, node); 1398 } 1399 1400 OutEdgeIt(const Graph& _graph, const Edge& edge) 1401 : Edge(edge), graph(&_graph) {} 1402 1403 OutEdgeIt& operator++() { 1404 graph->nextOut(*this); 1405 return *this; 1406 } 1407 1408 }; 1409 1410 1411 class InEdgeIt : public Edge { 1412 friend class BpUGraphExtender; 1413 const Graph* graph; 1414 public: 1415 1416 InEdgeIt() { } 1417 1418 InEdgeIt(Invalid i) : Edge(i) { } 1419 1420 InEdgeIt(const Graph& _graph, const Node& node) 1421 : graph(&_graph) { 1422 graph->firstIn(*this, node); 1423 } 1424 1425 InEdgeIt(const Graph& _graph, const Edge& edge) : 1426 Edge(edge), graph(&_graph) {} 1427 1428 InEdgeIt& operator++() { 1429 graph->nextIn(*this); 1430 return *this; 1431 } 1432 1433 }; 1434 1435 /// \brief Base node of the iterator 1436 /// 1437 /// Returns the base node (ie. the source in this case) of the iterator 1438 Node baseNode(const OutEdgeIt &e) const { 1439 return Parent::source((Edge&)e); 1440 } 1441 /// \brief Running node of the iterator 1442 /// 1443 /// Returns the running node (ie. the target in this case) of the 1444 /// iterator 1445 Node runningNode(const OutEdgeIt &e) const { 1446 return Parent::target((Edge&)e); 1447 } 1448 1449 /// \brief Base node of the iterator 1450 /// 1451 /// Returns the base node (ie. the target in this case) of the iterator 1452 Node baseNode(const InEdgeIt &e) const { 1453 return Parent::target((Edge&)e); 1454 } 1455 /// \brief Running node of the iterator 1456 /// 1457 /// Returns the running node (ie. the source in this case) of the 1458 /// iterator 1459 Node runningNode(const InEdgeIt &e) const { 1460 return Parent::source((Edge&)e); 1461 } 1462 1463 class IncEdgeIt : public Parent::UEdge { 1464 friend class BpUGraphExtender; 1465 const Graph* graph; 1466 bool direction; 1467 public: 1468 1469 IncEdgeIt() { } 1470 1471 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } 1472 1473 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 1474 graph->firstInc(*this, direction, n); 1475 } 1476 1477 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 1478 : graph(&_graph), UEdge(ue) { 1479 direction = (graph->source(ue) == n); 1480 } 1481 1482 IncEdgeIt& operator++() { 1483 graph->nextInc(*this, direction); 1484 return *this; 1485 } 1486 }; 1487 1488 1489 /// Base node of the iterator 1490 /// 1491 /// Returns the base node of the iterator 1492 Node baseNode(const IncEdgeIt &e) const { 1493 return e.direction ? source(e) : target(e); 1494 } 1495 1496 /// Running node of the iterator 1497 /// 1498 /// Returns the running node of the iterator 1499 Node runningNode(const IncEdgeIt &e) const { 1500 return e.direction ? target(e) : source(e); 1501 } 1502 1503 template <typename _Value> 1504 class ANodeMap 1505 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > { 1506 public: 1507 typedef BpUGraphExtender Graph; 1508 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> > 1509 Parent; 1510 1511 ANodeMap(const Graph& _g) 1512 : Parent(_g) {} 1513 ANodeMap(const Graph& _g, const _Value& _v) 1514 : Parent(_g, _v) {} 1515 1516 ANodeMap& operator=(const ANodeMap& cmap) { 1517 return operator=<ANodeMap>(cmap); 1518 } 1519 1520 1521 /// \brief Template assign operator. 1522 /// 1523 /// The given parameter should be conform to the ReadMap 1524 /// concept and could be indiced by the current item set of 1525 /// the ANodeMap. In this case the value for each item 1526 /// is assigned by the value of the given ReadMap. 1527 template <typename CMap> 1528 ANodeMap& operator=(const CMap& cmap) { 1529 checkConcept<concept::ReadMap<ANode, _Value>, CMap>(); 1530 const typename Parent::Graph* graph = Parent::getGraph(); 1531 ANode it; 1532 for (graph->first(it); it != INVALID; graph->next(it)) { 1533 Parent::set(it, cmap[it]); 1534 } 1535 return *this; 1536 } 1537 1538 }; 1539 1540 template <typename _Value> 1541 class BNodeMap 1542 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > { 1543 public: 1544 typedef BpUGraphExtender Graph; 1545 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> > 1546 Parent; 1547 1548 BNodeMap(const Graph& _g) 1549 : Parent(_g) {} 1550 BNodeMap(const Graph& _g, const _Value& _v) 1551 : Parent(_g, _v) {} 1552 1553 BNodeMap& operator=(const BNodeMap& cmap) { 1554 return operator=<BNodeMap>(cmap); 1555 } 1556 1557 1558 /// \brief Template assign operator. 1559 /// 1560 /// The given parameter should be conform to the ReadMap 1561 /// concept and could be indiced by the current item set of 1562 /// the BNodeMap. In this case the value for each item 1563 /// is assigned by the value of the given ReadMap. 1564 template <typename CMap> 1565 BNodeMap& operator=(const CMap& cmap) { 1566 checkConcept<concept::ReadMap<BNode, _Value>, CMap>(); 1567 const typename Parent::Graph* graph = Parent::getGraph(); 1568 BNode it; 1569 for (graph->first(it); it != INVALID; graph->next(it)) { 1570 Parent::set(it, cmap[it]); 1571 } 1572 return *this; 1573 } 1574 1575 }; 1576 1577 protected: 1578 1579 template <typename _Value> 1580 class NodeMapBase : public NodeNotifier::ObserverBase { 1581 public: 1582 typedef BpUGraphExtender Graph; 1583 1584 typedef Node Key; 1585 typedef _Value Value; 1586 1587 /// The reference type of the map; 1588 typedef typename BNodeMap<_Value>::Reference Reference; 1589 /// The pointer type of the map; 1590 typedef typename BNodeMap<_Value>::Pointer Pointer; 1591 1592 /// The const value type of the map. 1593 typedef const Value ConstValue; 1594 /// The const reference type of the map; 1595 typedef typename BNodeMap<_Value>::ConstReference ConstReference; 1596 /// The pointer type of the map; 1597 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer; 1598 1599 typedef True ReferenceMapTag; 1600 1601 NodeMapBase(const Graph& _g) 1602 : graph(&_g), bNodeMap(_g), aNodeMap(_g) { 1603 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1604 } 1605 NodeMapBase(const Graph& _g, const _Value& _v) 1606 : graph(&_g), bNodeMap(_g, _v), 1607 aNodeMap(_g, _v) { 1608 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1609 } 1610 1611 virtual ~NodeMapBase() { 1612 if (NodeNotifier::ObserverBase::attached()) { 1613 NodeNotifier::ObserverBase::detach(); 1614 } 1615 } 1616 1617 ConstReference operator[](const Key& node) const { 1618 if (Parent::aNode(node)) { 1619 return aNodeMap[node]; 1620 } else { 1621 return bNodeMap[node]; 1622 } 1623 } 1624 1625 Reference operator[](const Key& node) { 1626 if (Parent::aNode(node)) { 1627 return aNodeMap[node]; 1628 } else { 1629 return bNodeMap[node]; 1630 } 1631 } 1632 1633 void set(const Key& node, const Value& value) { 1634 if (Parent::aNode(node)) { 1635 aNodeMap.set(node, value); 1636 } else { 1637 bNodeMap.set(node, value); 1638 } 1639 } 1640 1641 protected: 1642 1643 virtual void add(const Node&) {} 1644 virtual void add(const std::vector<Node>&) {} 1645 virtual void erase(const Node&) {} 1646 virtual void erase(const std::vector<Node>&) {} 1647 virtual void clear() {} 1648 virtual void build() {} 1649 1650 const Graph* getGraph() const { return graph; } 1651 1652 private: 1653 const Graph* graph; 1654 BNodeMap<_Value> bNodeMap; 1655 ANodeMap<_Value> aNodeMap; 1656 }; 1657 1658 public: 1659 1660 template <typename _Value> 1661 class NodeMap 1662 : public IterableMapExtender<NodeMapBase<_Value> > { 1663 public: 1664 typedef BpUGraphExtender Graph; 1665 typedef IterableMapExtender< NodeMapBase<_Value> > Parent; 1666 1667 NodeMap(const Graph& _g) 1668 : Parent(_g) {} 1669 NodeMap(const Graph& _g, const _Value& _v) 1670 : Parent(_g, _v) {} 1671 1672 NodeMap& operator=(const NodeMap& cmap) { 1673 return operator=<NodeMap>(cmap); 1674 } 1675 1676 1677 /// \brief Template assign operator. 1678 /// 1679 /// The given parameter should be conform to the ReadMap 1680 /// concept and could be indiced by the current item set of 1681 /// the NodeMap. In this case the value for each item 1682 /// is assigned by the value of the given ReadMap. 1683 template <typename CMap> 1684 NodeMap& operator=(const CMap& cmap) { 1685 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 1686 const typename Parent::Graph* graph = Parent::getGraph(); 1687 Node it; 1688 for (graph->first(it); it != INVALID; graph->next(it)) { 1689 Parent::set(it, cmap[it]); 1690 } 1691 return *this; 1692 } 1693 1694 }; 1695 1696 1697 1698 template <typename _Value> 1699 class EdgeMap 1700 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 1701 public: 1702 typedef BpUGraphExtender Graph; 1703 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 1704 1705 EdgeMap(const Graph& _g) 1706 : Parent(_g) {} 1707 EdgeMap(const Graph& _g, const _Value& _v) 1708 : Parent(_g, _v) {} 1709 1710 EdgeMap& operator=(const EdgeMap& cmap) { 1711 return operator=<EdgeMap>(cmap); 1712 } 1713 1714 template <typename CMap> 1715 EdgeMap& operator=(const CMap& cmap) { 1716 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 1717 const typename Parent::Graph* graph = Parent::getGraph(); 1718 Edge it; 1719 for (graph->first(it); it != INVALID; graph->next(it)) { 1720 Parent::set(it, cmap[it]); 1721 } 1722 return *this; 1723 } 1724 }; 1725 1726 template <typename _Value> 1727 class UEdgeMap 1728 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { 1729 public: 1730 typedef BpUGraphExtender Graph; 1731 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > 1732 Parent; 1733 1734 UEdgeMap(const Graph& _g) 1735 : Parent(_g) {} 1736 UEdgeMap(const Graph& _g, const _Value& _v) 1737 : Parent(_g, _v) {} 1738 1739 UEdgeMap& operator=(const UEdgeMap& cmap) { 1740 return operator=<UEdgeMap>(cmap); 1741 } 1742 1743 template <typename CMap> 1744 UEdgeMap& operator=(const CMap& cmap) { 1745 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); 1746 const typename Parent::Graph* graph = Parent::getGraph(); 1747 UEdge it; 1748 for (graph->first(it); it != INVALID; graph->next(it)) { 1749 Parent::set(it, cmap[it]); 1750 } 1751 return *this; 1752 } 1753 }; 1754 1755 1756 Node addANode() { 1757 Node node = Parent::addANode(); 1758 getNotifier(ANode()).add(node); 1759 getNotifier(Node()).add(node); 1760 return node; 1761 } 1762 1763 Node addBNode() { 1764 Node node = Parent::addBNode(); 1765 getNotifier(BNode()).add(node); 1766 getNotifier(Node()).add(node); 1767 return node; 1768 } 1769 1770 UEdge addEdge(const Node& source, const Node& target) { 1771 UEdge uedge = Parent::addEdge(source, target); 1772 getNotifier(UEdge()).add(uedge); 1773 1774 std::vector<Edge> edges; 1775 edges.push_back(direct(uedge, true)); 1776 edges.push_back(direct(uedge, false)); 1777 getNotifier(Edge()).add(edges); 1778 1779 return uedge; 1780 } 1781 1782 void clear() { 1783 getNotifier(Edge()).clear(); 1784 getNotifier(UEdge()).clear(); 1785 getNotifier(Node()).clear(); 1786 getNotifier(BNode()).clear(); 1787 getNotifier(ANode()).clear(); 1788 Parent::clear(); 1789 } 1790 1791 void erase(const Node& node) { 1792 UEdge uedge; 1793 bool dir; 1794 Parent::firstInc(uedge, dir, node); 1795 while (uedge != INVALID ) { 1796 erase(uedge); 1797 Parent::firstInc(uedge, dir, node); 1798 } 1799 1800 getNotifier(Node()).erase(node); 1801 Parent::erase(node); 1802 } 1803 1804 void erase(const UEdge& uedge) { 1805 std::vector<Edge> edges; 1806 edges.push_back(direct(uedge, true)); 1807 edges.push_back(direct(uedge, false)); 1808 getNotifier(Edge()).erase(edges); 1809 getNotifier(UEdge()).erase(uedge); 1810 Parent::erase(uedge); 1811 } 1812 1813 1814 ~BpUGraphExtender() { 1815 getNotifier(Edge()).clear(); 1816 getNotifier(UEdge()).clear(); 1817 getNotifier(Node()).clear(); 1818 getNotifier(BNode()).clear(); 1819 getNotifier(ANode()).clear(); 1820 } 1821 616 1822 617 1823 }; -
lemon/bits/static_map.h
r1961 r1979 57 57 public: 58 58 59 /// \brief Exception class for uns inported exceptions.60 class Uns inportedOperation : public lemon::LogicError {59 /// \brief Exception class for unsupported exceptions. 60 class UnsupportedOperation : public lemon::LogicError { 61 61 public: 62 62 virtual const char* exceptionName() const { 63 return "lemon::StaticMap::Uns inportedOperation";63 return "lemon::StaticMap::UnsupportedOperation"; 64 64 } 65 65 }; … … 188 188 189 189 void add(const Key&) { 190 throw Uns inportedOperation();190 throw UnsupportedOperation(); 191 191 } 192 192 … … 196 196 /// and it overrides the erase() member function of the observer base. 197 197 void erase(const Key&) { 198 throw Uns inportedOperation();198 throw UnsupportedOperation(); 199 199 } 200 200 … … 225 225 }; 226 226 227 /// \e228 template <typename _Base>229 class StaticMappableGraphExtender : public _Base {230 public:231 232 typedef StaticMappableGraphExtender<_Base> Graph;233 typedef _Base Parent;234 235 typedef typename Parent::Node Node;236 typedef typename Parent::NodeIt NodeIt;237 238 typedef typename Parent::Edge Edge;239 typedef typename Parent::EdgeIt EdgeIt;240 241 242 template <typename _Value>243 class NodeMap244 : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {245 public:246 typedef StaticMappableGraphExtender Graph;247 typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;248 249 NodeMap(const Graph& _g)250 : Parent(_g) {}251 NodeMap(const Graph& _g, const _Value& _v)252 : Parent(_g, _v) {}253 254 NodeMap& operator=(const NodeMap& cmap) {255 return operator=<NodeMap>(cmap);256 }257 258 259 /// \brief Template assign operator.260 ///261 /// The given parameter should be conform to the ReadMap262 /// concecpt and could be indiced by the current item set of263 /// the NodeMap. In this case the value for each item264 /// is assigned by the value of the given ReadMap.265 template <typename CMap>266 NodeMap& operator=(const CMap& cmap) {267 checkConcept<concept::ReadMap<Node, _Value>, CMap>();268 const typename Parent::Graph* graph = Parent::getGraph();269 Node it;270 for (graph->first(it); it != INVALID; graph->next(it)) {271 Parent::set(it, cmap[it]);272 }273 return *this;274 }275 276 };277 278 template <typename _Value>279 class EdgeMap280 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {281 public:282 typedef StaticMappableGraphExtender Graph;283 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;284 285 EdgeMap(const Graph& _g)286 : Parent(_g) {}287 EdgeMap(const Graph& _g, const _Value& _v)288 : Parent(_g, _v) {}289 290 EdgeMap& operator=(const EdgeMap& cmap) {291 return operator=<EdgeMap>(cmap);292 }293 294 template <typename CMap>295 EdgeMap& operator=(const CMap& cmap) {296 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();297 const typename Parent::Graph* graph = Parent::getGraph();298 Edge it;299 for (graph->first(it); it != INVALID; graph->next(it)) {300 Parent::set(it, cmap[it]);301 }302 return *this;303 }304 };305 306 };307 308 /// \e309 template <typename _Base>310 class StaticMappableUGraphExtender :311 public StaticMappableGraphExtender<_Base> {312 public:313 314 typedef StaticMappableUGraphExtender Graph;315 typedef StaticMappableGraphExtender<_Base> Parent;316 317 typedef typename Parent::UEdge UEdge;318 319 template <typename _Value>320 class UEdgeMap321 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {322 public:323 typedef StaticMappableUGraphExtender Graph;324 typedef IterableMapExtender<325 StaticMap<Graph, UEdge, _Value> > Parent;326 327 UEdgeMap(const Graph& _g)328 : Parent(_g) {}329 UEdgeMap(const Graph& _g, const _Value& _v)330 : Parent(_g, _v) {}331 332 UEdgeMap& operator=(const UEdgeMap& cmap) {333 return operator=<UEdgeMap>(cmap);334 }335 336 template <typename CMap>337 UEdgeMap& operator=(const CMap& cmap) {338 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();339 const typename Parent::Graph* graph = Parent::getGraph();340 UEdge it;341 for (graph->first(it); it != INVALID; graph->next(it)) {342 Parent::set(it, cmap[it]);343 }344 return *this;345 }346 };347 348 };349 350 template <typename _Base>351 class StaticMappableBpUGraphExtender : public _Base {352 public:353 354 typedef _Base Parent;355 typedef StaticMappableBpUGraphExtender Graph;356 357 typedef typename Parent::Node Node;358 typedef typename Parent::ANode ANode;359 typedef typename Parent::BNode BNode;360 typedef typename Parent::Edge Edge;361 typedef typename Parent::UEdge UEdge;362 363 template <typename _Value>364 class ANodeMap365 : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {366 public:367 typedef StaticMappableBpUGraphExtender Graph;368 typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >369 Parent;370 371 ANodeMap(const Graph& _g)372 : Parent(_g) {}373 ANodeMap(const Graph& _g, const _Value& _v)374 : Parent(_g, _v) {}375 376 ANodeMap& operator=(const ANodeMap& cmap) {377 return operator=<ANodeMap>(cmap);378 }379 380 381 /// \brief Template assign operator.382 ///383 /// The given parameter should be conform to the ReadMap384 /// concept and could be indiced by the current item set of385 /// the ANodeMap. In this case the value for each item386 /// is assigned by the value of the given ReadMap.387 template <typename CMap>388 ANodeMap& operator=(const CMap& cmap) {389 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();390 const typename Parent::Graph* graph = Parent::getGraph();391 ANode it;392 for (graph->first(it); it != INVALID; graph->next(it)) {393 Parent::set(it, cmap[it]);394 }395 return *this;396 }397 398 };399 400 template <typename _Value>401 class BNodeMap402 : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {403 public:404 typedef StaticMappableBpUGraphExtender Graph;405 typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >406 Parent;407 408 BNodeMap(const Graph& _g)409 : Parent(_g) {}410 BNodeMap(const Graph& _g, const _Value& _v)411 : Parent(_g, _v) {}412 413 BNodeMap& operator=(const BNodeMap& cmap) {414 return operator=<BNodeMap>(cmap);415 }416 417 418 /// \brief Template assign operator.419 ///420 /// The given parameter should be conform to the ReadMap421 /// concept and could be indiced by the current item set of422 /// the BNodeMap. In this case the value for each item423 /// is assigned by the value of the given ReadMap.424 template <typename CMap>425 BNodeMap& operator=(const CMap& cmap) {426 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();427 const typename Parent::Graph* graph = Parent::getGraph();428 BNode it;429 for (graph->first(it); it != INVALID; graph->next(it)) {430 Parent::set(it, cmap[it]);431 }432 return *this;433 }434 435 };436 437 protected:438 439 template <typename _Value>440 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {441 public:442 typedef StaticMappableBpUGraphExtender Graph;443 444 typedef Node Key;445 typedef _Value Value;446 447 /// The reference type of the map;448 typedef typename BNodeMap<_Value>::Reference Reference;449 /// The pointer type of the map;450 typedef typename BNodeMap<_Value>::Pointer Pointer;451 452 /// The const value type of the map.453 typedef const Value ConstValue;454 /// The const reference type of the map;455 typedef typename BNodeMap<_Value>::ConstReference ConstReference;456 /// The pointer type of the map;457 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;458 459 typedef True ReferenceMapTag;460 461 NodeMapBase(const Graph& _g)462 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {463 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));464 }465 NodeMapBase(const Graph& _g, const _Value& _v)466 : graph(&_g), bNodeMap(_g, _v),467 aNodeMap(_g, _v) {468 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));469 }470 471 virtual ~NodeMapBase() {472 if (Parent::NodeNotifier::ObserverBase::attached()) {473 Parent::NodeNotifier::ObserverBase::detach();474 }475 }476 477 ConstReference operator[](const Key& node) const {478 if (Parent::aNode(node)) {479 return aNodeMap[node];480 } else {481 return bNodeMap[node];482 }483 }484 485 Reference operator[](const Key& node) {486 if (Parent::aNode(node)) {487 return aNodeMap[node];488 } else {489 return bNodeMap[node];490 }491 }492 493 void set(const Key& node, const Value& value) {494 if (Parent::aNode(node)) {495 aNodeMap.set(node, value);496 } else {497 bNodeMap.set(node, value);498 }499 }500 501 protected:502 503 virtual void add(const Node&) {}504 virtual void add(const std::vector<Node>&) {}505 virtual void erase(const Node&) {}506 virtual void erase(const std::vector<Node>&) {}507 virtual void clear() {}508 virtual void build() {}509 510 const Graph* getGraph() const { return graph; }511 512 private:513 const Graph* graph;514 BNodeMap<_Value> bNodeMap;515 ANodeMap<_Value> aNodeMap;516 };517 518 public:519 520 template <typename _Value>521 class NodeMap522 : public IterableMapExtender<NodeMapBase<_Value> > {523 public:524 typedef StaticMappableBpUGraphExtender Graph;525 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;526 527 NodeMap(const Graph& _g)528 : Parent(_g) {}529 NodeMap(const Graph& _g, const _Value& _v)530 : Parent(_g, _v) {}531 532 NodeMap& operator=(const NodeMap& cmap) {533 return operator=<NodeMap>(cmap);534 }535 536 537 /// \brief Template assign operator.538 ///539 /// The given parameter should be conform to the ReadMap540 /// concept and could be indiced by the current item set of541 /// the NodeMap. In this case the value for each item542 /// is assigned by the value of the given ReadMap.543 template <typename CMap>544 NodeMap& operator=(const CMap& cmap) {545 checkConcept<concept::ReadMap<Node, _Value>, CMap>();546 const typename Parent::Graph* graph = Parent::getGraph();547 Node it;548 for (graph->first(it); it != INVALID; graph->next(it)) {549 Parent::set(it, cmap[it]);550 }551 return *this;552 }553 554 };555 556 557 558 template <typename _Value>559 class EdgeMap560 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {561 public:562 typedef StaticMappableBpUGraphExtender Graph;563 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;564 565 EdgeMap(const Graph& _g)566 : Parent(_g) {}567 EdgeMap(const Graph& _g, const _Value& _v)568 : Parent(_g, _v) {}569 570 EdgeMap& operator=(const EdgeMap& cmap) {571 return operator=<EdgeMap>(cmap);572 }573 574 template <typename CMap>575 EdgeMap& operator=(const CMap& cmap) {576 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();577 const typename Parent::Graph* graph = Parent::getGraph();578 Edge it;579 for (graph->first(it); it != INVALID; graph->next(it)) {580 Parent::set(it, cmap[it]);581 }582 return *this;583 }584 };585 586 template <typename _Value>587 class UEdgeMap588 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {589 public:590 typedef StaticMappableBpUGraphExtender Graph;591 typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >592 Parent;593 594 UEdgeMap(const Graph& _g)595 : Parent(_g) {}596 UEdgeMap(const Graph& _g, const _Value& _v)597 : Parent(_g, _v) {}598 599 UEdgeMap& operator=(const UEdgeMap& cmap) {600 return operator=<UEdgeMap>(cmap);601 }602 603 template <typename CMap>604 UEdgeMap& operator=(const CMap& cmap) {605 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();606 const typename Parent::Graph* graph = Parent::getGraph();607 UEdge it;608 for (graph->first(it); it != INVALID; graph->next(it)) {609 Parent::set(it, cmap[it]);610 }611 return *this;612 }613 };614 615 };616 617 227 } 618 228 -
lemon/concept/bpugraph.h
r1956 r1979 71 71 /// \todo undocumented 72 72 /// 73 typedef True U Tag;73 typedef True UndirectedTag; 74 74 75 75 /// \brief The base type of node iterators, -
lemon/concept/graph.h
r1956 r1979 45 45 public: 46 46 47 typedef False UTag;48 49 47 typedef BaseGraphComponent::Node Node; 50 48 typedef BaseGraphComponent::Edge Edge; … … 124 122 ///\e 125 123 126 ///\todo undocumented127 ///128 typedef False UTag;129 130 124 /// Defalult constructor. 131 125 -
lemon/concept/ugraph.h
r1956 r1979 246 246 ///\todo undocumented 247 247 /// 248 typedef True U Tag;248 typedef True UndirectedTag; 249 249 250 250 /// \brief The base type of node iterators, -
lemon/edge_set.h
r1962 r1979 20 20 #define LEMON_EDGE_SET_H 21 21 22 #include <lemon/bits/erasable_graph_extender.h> 23 #include <lemon/bits/clearable_graph_extender.h> 24 #include <lemon/bits/extendable_graph_extender.h> 25 #include <lemon/bits/iterable_graph_extender.h> 26 #include <lemon/bits/alteration_notifier.h> 27 #include <lemon/bits/default_map.h> 28 #include <lemon/bits/graph_extender.h> 22 23 #include <lemon/bits/edge_set_extender.h> 29 24 30 25 /// \ingroup graphs … … 230 225 /// \ref concept::ErasableGraph "ErasableGraph" concept. 231 226 template <typename _Graph> 232 class ListEdgeSet : 233 public ErasableEdgeSetExtender< 234 ClearableEdgeSetExtender< 235 ExtendableEdgeSetExtender< 236 MappableEdgeSetExtender< 237 IterableGraphExtender< 238 AlterableEdgeSetExtender< 239 GraphExtender< 240 ListEdgeSetBase<_Graph> > > > > > > > { 241 242 public: 243 244 typedef ErasableEdgeSetExtender< 245 ClearableEdgeSetExtender< 246 ExtendableEdgeSetExtender< 247 MappableEdgeSetExtender< 248 IterableGraphExtender< 249 AlterableEdgeSetExtender< 250 GraphExtender< 251 ListEdgeSetBase<_Graph> > > > > > > > Parent; 227 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > { 228 229 public: 230 231 typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent; 252 232 253 233 typedef typename Parent::Node Node; … … 337 317 /// \ref concept::ErasableUGraph "ErasableUGraph" concept. 338 318 template <typename _Graph> 339 class ListUEdgeSet : 340 public ErasableUEdgeSetExtender< 341 ClearableUEdgeSetExtender< 342 ExtendableUEdgeSetExtender< 343 MappableUEdgeSetExtender< 344 IterableUGraphExtender< 345 AlterableUEdgeSetExtender< 346 UGraphExtender< 347 ListEdgeSetBase<_Graph> > > > > > > > { 348 349 public: 350 351 typedef ErasableUEdgeSetExtender< 352 ClearableUEdgeSetExtender< 353 ExtendableUEdgeSetExtender< 354 MappableUEdgeSetExtender< 355 IterableUGraphExtender< 356 AlterableUEdgeSetExtender< 357 UGraphExtender< 358 ListEdgeSetBase<_Graph> > > > > > > > Parent; 319 class ListUEdgeSet 320 : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > { 321 322 public: 323 324 typedef UEdgeSetExtender<UGraphBaseExtender< 325 ListEdgeSetBase<_Graph> > > Parent; 359 326 360 327 typedef typename Parent::Node Node; … … 568 535 /// \ref concept::ExtendableGraph "ExtendableGraph" concept. 569 536 template <typename _Graph> 570 class SmartEdgeSet : 571 public ClearableEdgeSetExtender< 572 ExtendableEdgeSetExtender< 573 MappableEdgeSetExtender< 574 IterableGraphExtender< 575 AlterableEdgeSetExtender< 576 GraphExtender< 577 SmartEdgeSetBase<_Graph> > > > > > > { 578 579 public: 580 581 typedef ClearableEdgeSetExtender< 582 ExtendableEdgeSetExtender< 583 MappableEdgeSetExtender< 584 IterableGraphExtender< 585 AlterableEdgeSetExtender< 586 GraphExtender< 587 SmartEdgeSetBase<_Graph> > > > > > > Parent; 537 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > { 538 539 public: 540 541 typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent; 588 542 589 543 typedef typename Parent::Node Node; … … 672 626 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept. 673 627 template <typename _Graph> 674 class SmartUEdgeSet : 675 public ClearableUEdgeSetExtender< 676 ExtendableUEdgeSetExtender< 677 MappableUEdgeSetExtender< 678 IterableUGraphExtender< 679 AlterableUEdgeSetExtender< 680 UGraphExtender< 681 SmartEdgeSetBase<_Graph> > > > > > > { 682 683 public: 684 685 typedef ClearableUEdgeSetExtender< 686 ExtendableUEdgeSetExtender< 687 MappableUEdgeSetExtender< 688 IterableUGraphExtender< 689 AlterableUEdgeSetExtender< 690 UGraphExtender< 691 SmartEdgeSetBase<_Graph> > > > > > > Parent; 628 class SmartUEdgeSet 629 : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > { 630 631 public: 632 633 typedef UEdgeSetExtender<UGraphBaseExtender< 634 SmartEdgeSetBase<_Graph> > > Parent; 692 635 693 636 typedef typename Parent::Node Node; -
lemon/euler.h
r1970 r1979 234 234 bool 235 235 #else 236 typename enable_if< typename Graph::UTag,bool>::type236 typename enable_if<UndirectedTagIndicator<Graph>,bool>::type 237 237 euler(const Graph &g) 238 238 { … … 242 242 } 243 243 template<class Graph> 244 typename disable_if< typename Graph::UTag,bool>::type244 typename disable_if<UndirectedTagIndicator<Graph>,bool>::type 245 245 #endif 246 246 euler(const Graph &g) -
lemon/fredman_tarjan.h
r1956 r1979 505 505 ft.treeMap(tree); 506 506 ft.run(); 507 } ;507 } 508 508 509 509 } //END OF NAMESPACE LEMON -
lemon/full_graph.h
r1956 r1979 23 23 24 24 25 #include <lemon/bits/iterable_graph_extender.h>26 #include <lemon/bits/alteration_notifier.h>27 #include <lemon/bits/static_map.h>28 25 #include <lemon/bits/graph_extender.h> 26 29 27 30 28 #include <lemon/invalid.h> … … 192 190 }; 193 191 194 typedef StaticMappableGraphExtender< 195 IterableGraphExtender< 196 AlterableGraphExtender< 197 GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase; 192 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase; 198 193 199 194 /// \ingroup graphs … … 212 207 public: 213 208 209 typedef ExtendedFullGraphBase Parent; 210 211 /// \brief Constructor 212 /// 214 213 FullGraph(int n) { construct(n); } 214 215 /// \brief Resize the graph 216 /// 217 void resize(int n) { 218 Parent::getNotifier(Edge()).clear(); 219 Parent::getNotifier(Node()).clear(); 220 construct(n); 221 Parent::getNotifier(Node()).build(); 222 Parent::getNotifier(Edge()).build(); 223 } 215 224 }; 216 225 … … 380 389 }; 381 390 382 typedef StaticMappableUGraphExtender< 383 IterableUGraphExtender< 384 AlterableUGraphExtender< 385 UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase; 391 typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> > 392 ExtendedFullUGraphBase; 386 393 387 394 /// \ingroup graphs … … 402 409 class FullUGraph : public ExtendedFullUGraphBase { 403 410 public: 411 412 typedef ExtendedFullUGraphBase Parent; 413 414 /// \brief Constructor 404 415 FullUGraph(int n) { construct(n); } 416 417 /// \brief Resize the graph 418 /// 419 void resize(int n) { 420 Parent::getNotifier(Edge()).clear(); 421 Parent::getNotifier(UEdge()).clear(); 422 Parent::getNotifier(Node()).clear(); 423 construct(n); 424 Parent::getNotifier(Node()).build(); 425 Parent::getNotifier(UEdge()).build(); 426 Parent::getNotifier(Edge()).build(); 427 } 405 428 }; 406 429 … … 578 601 579 602 580 typedef StaticMappableBpUGraphExtender< 581 IterableBpUGraphExtender< 582 AlterableBpUGraphExtender< 583 BpUGraphExtender < 584 FullBpUGraphBase> > > > 585 ExtendedFullBpUGraphBase; 603 typedef BpUGraphExtender< BpUGraphBaseExtender< 604 FullBpUGraphBase> > ExtendedFullBpUGraphBase; 586 605 587 606 … … 600 619 public ExtendedFullBpUGraphBase { 601 620 public: 621 602 622 typedef ExtendedFullBpUGraphBase Parent; 623 603 624 FullBpUGraph(int aNodeNum, int bNodeNum) { 604 625 Parent::construct(aNodeNum, bNodeNum); 605 626 } 627 /// \brief Resize the graph 628 /// 629 void resize(int n, int m) { 630 Parent::getNotifier(Edge()).clear(); 631 Parent::getNotifier(UEdge()).clear(); 632 Parent::getNotifier(Node()).clear(); 633 construct(n, m); 634 Parent::getNotifier(Node()).build(); 635 Parent::getNotifier(UEdge()).build(); 636 Parent::getNotifier(Edge()).build(); 637 } 606 638 }; 607 639 -
lemon/graph_adaptor.h
r1957 r1979 30 30 #include <lemon/invalid.h> 31 31 #include <lemon/maps.h> 32 #include <lemon/bits/erasable_graph_extender.h> 33 #include <lemon/bits/clearable_graph_extender.h> 34 #include <lemon/bits/extendable_graph_extender.h> 35 #include <lemon/bits/iterable_graph_extender.h> 36 #include <lemon/bits/alteration_notifier.h> 37 #include <lemon/bits/default_map.h> 32 33 #include <lemon/bits/graph_adaptor_extender.h> 38 34 #include <lemon/bits/graph_extender.h> 35 39 36 #include <iostream> 40 37 … … 118 115 int id(const Edge& e) const { return graph->id(e); } 119 116 120 Edge oppositeNode(const Edge& e) const {121 return Edge(graph->opposite(e));122 }123 124 117 template <typename _Value> 125 118 class NodeMap : public _Graph::template NodeMap<_Value> { … … 146 139 template <typename _Graph> 147 140 class GraphAdaptor : 148 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {141 public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > { 149 142 public: 150 143 typedef _Graph Graph; 151 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;144 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent; 152 145 protected: 153 146 GraphAdaptor() : Parent() { } … … 199 192 template<typename _Graph> 200 193 class RevGraphAdaptor : 201 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {194 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > { 202 195 public: 203 196 typedef _Graph Graph; 204 typedef IterableGraphExtender<197 typedef GraphAdaptorExtender< 205 198 RevGraphAdaptorBase<_Graph> > Parent; 206 199 protected: … … 323 316 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 324 317 318 typedef False FindEdgeTag; 325 319 typedef False NodeNumTag; 326 320 typedef False EdgeNumTag; … … 429 423 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } 430 424 425 typedef False FindEdgeTag; 431 426 typedef False NodeNumTag; 432 427 typedef False EdgeNumTag; … … 497 492 typename EdgeFilterMap, bool checked = true> 498 493 class SubGraphAdaptor : 499 public IterableGraphExtender<494 public GraphAdaptorExtender< 500 495 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { 501 496 public: 502 497 typedef _Graph Graph; 503 typedef IterableGraphExtender<498 typedef GraphAdaptorExtender< 504 499 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 505 500 protected: … … 704 699 705 700 template <typename _Graph> 706 class U GraphAdaptorBase :707 public UGraph Extender<GraphAdaptorBase<_Graph> > {701 class UndirectGraphAdaptorBase : 702 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > { 708 703 public: 709 704 typedef _Graph Graph; 710 typedef UGraph Extender<GraphAdaptorBase<_Graph> > Parent;705 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent; 711 706 protected: 712 U GraphAdaptorBase() : Parent() { }707 UndirectGraphAdaptorBase() : Parent() { } 713 708 public: 714 709 typedef typename Parent::UEdge UEdge; … … 718 713 class EdgeMap { 719 714 protected: 720 const U GraphAdaptorBase<_Graph>* g;715 const UndirectGraphAdaptorBase<_Graph>* g; 721 716 template <typename TT> friend class EdgeMap; 722 717 typename _Graph::template EdgeMap<T> forward_map, backward_map; … … 725 720 typedef Edge Key; 726 721 727 EdgeMap(const U GraphAdaptorBase<_Graph>& _g) : g(&_g),722 EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g), 728 723 forward_map(*(g->graph)), backward_map(*(g->graph)) { } 729 724 730 EdgeMap(const U GraphAdaptorBase<_Graph>& _g, T a) : g(&_g),725 EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g), 731 726 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } 732 727 … … 754 749 typedef UEdge Key; 755 750 756 UEdgeMap(const U GraphAdaptorBase<_Graph>& g) :751 UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) : 757 752 map(*(g.graph)) { } 758 753 759 UEdgeMap(const U GraphAdaptorBase<_Graph>& g, T a) :754 UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) : 760 755 map(*(g.graph), a) { } 761 756 … … 779 774 /// \author Marton Makai 780 775 template<typename _Graph> 781 class U GraphAdaptor :782 public IterableUGraphExtender<783 U GraphAdaptorBase<_Graph> > {776 class UndirectGraphAdaptor : 777 public UGraphAdaptorExtender< 778 UndirectGraphAdaptorBase<_Graph> > { 784 779 public: 785 780 typedef _Graph Graph; 786 typedef IterableUGraphExtender<787 U GraphAdaptorBase<_Graph> > Parent;781 typedef UGraphAdaptorExtender< 782 UndirectGraphAdaptorBase<_Graph> > Parent; 788 783 protected: 789 U GraphAdaptor() { }790 public: 791 U GraphAdaptor(_Graph& _graph) {784 UndirectGraphAdaptor() { } 785 public: 786 UndirectGraphAdaptor(_Graph& _graph) { 792 787 setGraph(_graph); 793 788 } … … 1084 1079 typename ForwardFilterMap, typename BackwardFilterMap> 1085 1080 class SubBidirGraphAdaptor : 1086 public IterableGraphExtender<1081 public GraphAdaptorExtender< 1087 1082 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { 1088 1083 public: 1089 1084 typedef _Graph Graph; 1090 typedef IterableGraphExtender<1085 typedef GraphAdaptorExtender< 1091 1086 SubBidirGraphAdaptorBase< 1092 1087 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; … … 1342 1337 template <typename _Graph, typename FirstOutEdgesMap> 1343 1338 class ErasingFirstGraphAdaptor : 1344 public IterableGraphExtender<1339 public GraphAdaptorExtender< 1345 1340 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > { 1346 1341 public: 1347 1342 typedef _Graph Graph; 1348 typedef IterableGraphExtender<1343 typedef GraphAdaptorExtender< 1349 1344 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent; 1350 1345 ErasingFirstGraphAdaptor(Graph& _graph, … … 1712 1707 template <typename _Graph> 1713 1708 class SplitGraphAdaptor 1714 : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {1715 public: 1716 typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;1709 : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > { 1710 public: 1711 typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent; 1717 1712 1718 1713 SplitGraphAdaptor(_Graph& graph) { -
lemon/hypercube_graph.h
r1963 r1979 26 26 #include <lemon/error.h> 27 27 28 #include <lemon/bits/iterable_graph_extender.h>29 #include <lemon/bits/alteration_notifier.h>30 #include <lemon/bits/static_map.h>31 28 #include <lemon/bits/graph_extender.h> 32 29 … … 237 234 238 235 239 typedef StaticMappableGraphExtender< 240 IterableGraphExtender< 241 AlterableGraphExtender< 242 GraphExtender< 243 HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase; 236 typedef GraphExtender<HyperCubeGraphBase> ExtendedHyperCubeGraphBase; 244 237 245 238 /// \ingroup graphs -
lemon/kruskal.h
r1956 r1979 24 24 #include <lemon/unionfind.h> 25 25 #include <lemon/utility.h> 26 #include <lemon/traits.h> 26 27 27 28 /** … … 229 230 230 231 template<class _GR> 231 typename enable_if< typename _GR::UTag,void>::type232 typename enable_if<UndirectedTagIndicator<_GR>,void>::type 232 233 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 233 234 { … … 237 238 238 239 template<class _GR> 239 typename disable_if< typename _GR::UTag,void>::type240 typename disable_if<UndirectedTagIndicator<_GR>,void>::type 240 241 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 241 242 { -
lemon/list_graph.h
r1956 r1979 24 24 ///\brief ListGraph, ListUGraph classes. 25 25 26 #include <lemon/bits/erasable_graph_extender.h>27 #include <lemon/bits/clearable_graph_extender.h>28 #include <lemon/bits/extendable_graph_extender.h>29 #include <lemon/bits/iterable_graph_extender.h>30 #include <lemon/bits/alteration_notifier.h>31 #include <lemon/bits/default_map.h>32 26 #include <lemon/bits/graph_extender.h> 33 27 34 28 #include <lemon/error.h> 35 29 30 #include <vector> 36 31 #include <list> 37 32 … … 312 307 }; 313 308 314 typedef ErasableGraphExtender< 315 ClearableGraphExtender< 316 ExtendableGraphExtender< 317 MappableGraphExtender< 318 IterableGraphExtender< 319 AlterableGraphExtender< 320 GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase; 309 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 321 310 322 311 /// \addtogroup graphs … … 579 568 /**************** Undirected List Graph ****************/ 580 569 581 typedef ErasableUGraphExtender< 582 ClearableUGraphExtender< 583 ExtendableUGraphExtender< 584 MappableUGraphExtender< 585 IterableUGraphExtender< 586 AlterableUGraphExtender< 587 UGraphExtender<ListGraphBase> > > > > > > ExtendedListUGraphBase; 570 typedef UGraphExtender<UGraphBaseExtender< 571 ListGraphBase> > ExtendedListUGraphBase; 588 572 589 573 /// \addtogroup graphs -
lemon/prim.h
r1956 r1979 789 789 prm.treeMap(tree); 790 790 prm.run(); 791 } ;791 } 792 792 793 793 } //END OF NAMESPACE LEMON -
lemon/radix_sort.h
r1956 r1979 265 265 const int size = 266 266 (unsigned int)std::numeric_limits<unsigned char>::max() + 1; 267 int counter[size];267 std::vector<int> counter(size); 268 268 for (int i = 0; i < size; ++i) { 269 269 counter[i] = 0; … … 291 291 const int size = 292 292 (unsigned int)std::numeric_limits<unsigned char>::max() + 1; 293 int counter[size];293 std::vector<int> counter(size); 294 294 for (int i = 0; i < size; ++i) { 295 295 counter[i] = 0; -
lemon/smart_graph.h
r1956 r1979 28 28 #include <lemon/invalid.h> 29 29 30 #include <lemon/bits/clearable_graph_extender.h>31 #include <lemon/bits/extendable_graph_extender.h>32 #include <lemon/bits/iterable_graph_extender.h>33 #include <lemon/bits/alteration_notifier.h>34 #include <lemon/bits/default_map.h>35 30 #include <lemon/bits/graph_extender.h> 36 31 37 32 #include <lemon/utility.h> 38 33 #include <lemon/error.h> 34 35 #include <lemon/bits/graph_extender.h> 39 36 40 37 namespace lemon { … … 223 220 }; 224 221 225 typedef ClearableGraphExtender< 226 ExtendableGraphExtender< 227 MappableGraphExtender< 228 IterableGraphExtender< 229 AlterableGraphExtender< 230 GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase; 222 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase; 231 223 232 224 /// \ingroup graphs … … 245 237 class SmartGraph : public ExtendedSmartGraphBase { 246 238 public: 247 239 240 typedef ExtendedSmartGraphBase Parent; 241 248 242 class Snapshot; 249 243 friend class Snapshot; … … 356 350 /**************** Undirected List Graph ****************/ 357 351 358 typedef ClearableUGraphExtender< 359 ExtendableUGraphExtender< 360 MappableUGraphExtender< 361 IterableUGraphExtender< 362 AlterableUGraphExtender< 363 UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase; 352 typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> > 353 ExtendedSmartUGraphBase; 364 354 365 355 /// \ingroup graphs … … 588 578 589 579 590 typedef ClearableBpUGraphExtender< 591 ExtendableBpUGraphExtender< 592 MappableBpUGraphExtender< 593 IterableBpUGraphExtender< 594 AlterableBpUGraphExtender< 595 BpUGraphExtender < 596 SmartBpUGraphBase> > > > > > 597 ExtendedSmartBpUGraphBase; 580 typedef BpUGraphExtender< BpUGraphBaseExtender< 581 SmartBpUGraphBase> > ExtendedSmartBpUGraphBase; 598 582 599 583 /// \ingroup graphs -
lemon/sub_graph.h
r1964 r1979 387 387 template <typename Graph> 388 388 class SubGraph 389 : public IterableGraphExtender< SubGraphBase<Graph> > {389 : public GraphAdaptorExtender< SubGraphBase<Graph> > { 390 390 public: 391 typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;391 typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent; 392 392 public: 393 393 /// \brief Constructor for sub-graph. … … 684 684 template <typename Graph> 685 685 class EdgeSubGraph 686 : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {686 : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > { 687 687 public: 688 typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;688 typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent; 689 689 public: 690 690 /// \brief Constructor for sub-graph. -
lemon/topology.h
r1956 r1979 1418 1418 } 1419 1419 return true; 1420 } ;1420 } 1421 1421 1422 1422 /// \ingroup topology … … 1460 1460 } 1461 1461 return true; 1462 } ;1462 } 1463 1463 1464 1464 } //namespace lemon -
lemon/traits.h
r1956 r1979 210 210 }; 211 211 212 template <typename Graph, typename Enable = void> 213 struct UndirectedTagIndicator { 214 static const bool value = false; 215 }; 216 217 template <typename Graph> 218 struct UndirectedTagIndicator< 219 Graph, 220 typename enable_if<typename Graph::UndirectedTag, void>::type 221 > { 222 static const bool value = true; 223 }; 224 212 225 213 226 -
test/graph_adaptor_test.cc
r1956 r1979 68 68 69 69 /// \bug why does not compile with StaticGraph 70 checkConcept<BaseIterableUGraphConcept, UGraphAdaptor<ListGraph> >(); 71 checkConcept<IterableUGraphConcept, UGraphAdaptor<ListGraph> >(); 72 checkConcept<MappableUGraphConcept, UGraphAdaptor<ListGraph> >(); 70 checkConcept<UGraph, UndirectGraphAdaptor<ListGraph> >(); 73 71 } 74 72 std::cout << __FILE__ ": All tests passed.\n"; -
test/ugraph_test.cc
r1956 r1979 22 22 #include <lemon/smart_graph.h> 23 23 #include <lemon/full_graph.h> 24 #include <lemon/grid_ graph.h>24 #include <lemon/grid_ugraph.h> 25 25 26 26 #include <lemon/graph_utils.h> … … 33 33 34 34 void check_concepts() { 35 typedef UGraphExtender<ListGraphBase> ListUGraphBase;36 37 typedef IterableUGraphExtender<38 AlterableUGraphExtender<ListUGraphBase> > IterableListUGraph;39 40 typedef MappableUGraphExtender<IterableListUGraph>41 MappableListUGraph;42 43 typedef ErasableUGraphExtender<44 ClearableUGraphExtender<45 ExtendableUGraphExtender<MappableListUGraph> > > Graph;46 47 checkConcept<BaseIterableUGraphConcept, Graph>();48 checkConcept<IterableUGraphConcept, Graph>();49 checkConcept<MappableUGraphConcept, Graph>();50 51 checkConcept<UGraph, Graph>();52 checkConcept<ErasableUGraph, Graph>();53 54 35 checkConcept<UGraph, ListUGraph>(); 55 36 checkConcept<ErasableUGraph, ListUGraph>(); … … 62 43 checkConcept<UGraph, UGraph>(); 63 44 64 checkConcept<UGraph, Grid Graph>();45 checkConcept<UGraph, GridUGraph>(); 65 46 } 66 47 … … 151 132 } 152 133 153 void checkGrid Graph(const GridGraph& g, int w, int h) {134 void checkGridUGraph(const GridUGraph& g, int w, int h) { 154 135 check(g.width() == w, "Wrong width"); 155 136 check(g.height() == h, "Wrong height"); … … 207 188 208 189 { 209 Grid Graph g(5, 6);190 GridUGraph g(5, 6); 210 191 check_item_counts(g, 30, 49); 211 checkGrid Graph(g, 5, 6);192 checkGridUGraph(g, 5, 6); 212 193 } 213 194
Note: See TracChangeset
for help on using the changeset viewer.