Changeset 1910:f95eea8c34b0 in lemon-0.x
- Timestamp:
- 01/26/06 17:24:40 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2485
- Files:
-
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
demo/topology_demo.cc
r1909 r1910 60 60 connectedComponents(graph, compMap); 61 61 62 graphToEps(graph, "connected_components.eps").u ().62 graphToEps(graph, "connected_components.eps").undirected(). 63 63 coords(coords).scaleToA4().enableParallel(). 64 64 parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). … … 116 116 biNodeConnectedComponents(graph, compMap); 117 117 biNodeConnectedCutNodes(graph, cutMap); 118 graphToEps(graph, "bi_node_connected_components.eps").u(). 118 119 graphToEps(graph, "bi_node_connected_components.eps").undirected(). 119 120 coords(coords).scaleToA4().enableParallel(). 120 121 parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0). … … 146 147 biEdgeConnectedCutEdges(graph, cutMap); 147 148 148 graphToEps(graph, "bi_edge_connected_components.eps").u ().149 graphToEps(graph, "bi_edge_connected_components.eps").undirected(). 149 150 coords(coords).scaleToA4().enableParallel(). 150 151 parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). … … 173 174 bipartitePartitions(graph, partMap); 174 175 175 graphToEps(graph, "bipartite_partitions.eps").u ().176 graphToEps(graph, "bipartite_partitions.eps").undirected(). 176 177 coords(coords).scaleToA4().enableParallel(). 177 178 parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0). -
lemon/Makefile.am
r1909 r1910 89 89 bits/item_reader.h \ 90 90 bits/item_writer.h \ 91 concept/bpugraph.h \ 91 92 concept/graph.h \ 92 93 concept/graph_component.h \ -
lemon/bits/alteration_notifier.h
r1909 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 21 21 #include <algorithm> 22 22 23 ///\ingro upgraphmapfactory23 ///\ingroin graphmapfactory 24 24 ///\file 25 25 ///\brief Observer registry for graph alteration observers. … … 27 27 namespace lemon { 28 28 29 /// \addtogro upgraphmapfactory29 /// \addtogroin graphmapfactory 30 30 /// @{ 31 31 … … 502 502 503 503 template <typename _Base> 504 class Alterable UBipartiteGraphExtender : public _Base {504 class AlterableBpUGraphExtender : public _Base { 505 505 public: 506 506 507 507 typedef _Base Parent; 508 typedef Alterable UBipartiteGraphExtender Graph;508 typedef AlterableBpUGraphExtender Graph; 509 509 510 510 typedef typename Parent::Node Node; 511 typedef typename Parent:: LowerNode LowerNode;512 typedef typename Parent:: UpperNode UpperNode;511 typedef typename Parent::BNode BNode; 512 typedef typename Parent::ANode ANode; 513 513 typedef typename Parent::Edge Edge; 514 514 typedef typename Parent::UEdge UEdge; … … 516 516 517 517 typedef AlterationNotifier<Node> NodeNotifier; 518 typedef AlterationNotifier< LowerNode> LowerNodeNotifier;519 typedef AlterationNotifier< UpperNode> UpperNodeNotifier;518 typedef AlterationNotifier<BNode> BNodeNotifier; 519 typedef AlterationNotifier<ANode> ANodeNotifier; 520 520 typedef AlterationNotifier<Edge> EdgeNotifier; 521 521 typedef AlterationNotifier<UEdge> UEdgeNotifier; … … 524 524 525 525 mutable NodeNotifier nodeNotifier; 526 mutable LowerNodeNotifier lowerNodeNotifier;527 mutable UpperNodeNotifier upperNodeNotifier;526 mutable BNodeNotifier bNodeNotifier; 527 mutable ANodeNotifier aNodeNotifier; 528 528 mutable EdgeNotifier edgeNotifier; 529 529 mutable UEdgeNotifier uEdgeNotifier; … … 535 535 } 536 536 537 LowerNodeNotifier& getNotifier(LowerNode) const {538 return lowerNodeNotifier;539 } 540 541 UpperNodeNotifier& getNotifier(UpperNode) const {542 return upperNodeNotifier;537 BNodeNotifier& getNotifier(BNode) const { 538 return bNodeNotifier; 539 } 540 541 ANodeNotifier& getNotifier(ANode) const { 542 return aNodeNotifier; 543 543 } 544 544 … … 551 551 } 552 552 553 ~Alterable UBipartiteGraphExtender() {553 ~AlterableBpUGraphExtender() { 554 554 nodeNotifier.clear(); 555 lowerNodeNotifier.clear();556 upperNodeNotifier.clear();555 bNodeNotifier.clear(); 556 aNodeNotifier.clear(); 557 557 edgeNotifier.clear(); 558 558 uEdgeNotifier.clear(); -
lemon/bits/array_map.h
r1875 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 24 24 #include <lemon/concept/maps.h> 25 25 26 /// \ingro upgraphmapfactory26 /// \ingroin graphmapfactory 27 27 /// \file 28 28 /// \brief Graph maps that construct and destruct … … 31 31 namespace lemon { 32 32 33 /// \ingro upgraphmapfactory33 /// \ingroin graphmapfactory 34 34 /// 35 35 /// \brief Graph map based on the array storage. 36 36 /// 37 37 /// The ArrayMap template class is graph map structure what 38 /// automatically updates the map when a key is added to or erased from38 /// automatically indates the map when a key is added to or erased from 39 39 /// the map. This map uses the allocators to implement 40 40 /// the container functionality. -
lemon/bits/clearable_graph_extender.h
r1909 r1910 80 80 81 81 template <typename _Base> 82 class Clearable UBipartiteGraphExtender : public _Base {82 class ClearableBpUGraphExtender : public _Base { 83 83 public: 84 84 85 85 typedef _Base Parent; 86 typedef Clearable UBipartiteGraphExtender Graph;86 typedef ClearableBpUGraphExtender Graph; 87 87 88 88 typedef typename Parent::Node Node; 89 typedef typename Parent:: LowerNode LowerNode;90 typedef typename Parent:: UpperNode UpperNode;89 typedef typename Parent::BNode BNode; 90 typedef typename Parent::ANode ANode; 91 91 typedef typename Parent::Edge Edge; 92 92 typedef typename Parent::UEdge UEdge; … … 96 96 Parent::getNotifier(UEdge()).clear(); 97 97 Parent::getNotifier(Node()).clear(); 98 Parent::getNotifier( LowerNode()).clear();99 Parent::getNotifier( UpperNode()).clear();98 Parent::getNotifier(BNode()).clear(); 99 Parent::getNotifier(ANode()).clear(); 100 100 Parent::clear(); 101 101 } -
lemon/bits/default_map.h
r1909 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 22 22 #include <lemon/bits/vector_map.h> 23 23 24 ///\ingro upgraphmapfactory24 ///\ingroin graphmapfactory 25 25 ///\file 26 26 ///\brief Graph maps that construct and destruct … … 353 353 354 354 template <typename _Base> 355 class Mappable UBipartiteGraphExtender : public _Base {355 class MappableBpUGraphExtender : public _Base { 356 356 public: 357 357 358 358 typedef _Base Parent; 359 typedef Mappable UBipartiteGraphExtender Graph;359 typedef MappableBpUGraphExtender Graph; 360 360 361 361 typedef typename Parent::Node Node; 362 typedef typename Parent:: UpperNode UpperNode;363 typedef typename Parent:: LowerNode LowerNode;362 typedef typename Parent::ANode ANode; 363 typedef typename Parent::BNode BNode; 364 364 typedef typename Parent::Edge Edge; 365 365 typedef typename Parent::UEdge UEdge; 366 366 367 367 template <typename _Value> 368 class UpperNodeMap369 : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {370 public: 371 typedef Mappable UBipartiteGraphExtender Graph;372 typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> >368 class ANodeMap 369 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > { 370 public: 371 typedef MappableBpUGraphExtender Graph; 372 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> > 373 373 Parent; 374 374 375 UpperNodeMap(const Graph& _g)376 : Parent(_g) {} 377 UpperNodeMap(const Graph& _g, const _Value& _v)378 : Parent(_g, _v) {} 379 380 UpperNodeMap& operator=(const UpperNodeMap& cmap) {381 return operator=< UpperNodeMap>(cmap);375 ANodeMap(const Graph& _g) 376 : Parent(_g) {} 377 ANodeMap(const Graph& _g, const _Value& _v) 378 : Parent(_g, _v) {} 379 380 ANodeMap& operator=(const ANodeMap& cmap) { 381 return operator=<ANodeMap>(cmap); 382 382 } 383 383 … … 387 387 /// The given parameter should be conform to the ReadMap 388 388 /// concept and could be indiced by the current item set of 389 /// the UpperNodeMap. In this case the value for each item389 /// the ANodeMap. In this case the value for each item 390 390 /// is assigned by the value of the given ReadMap. 391 391 template <typename CMap> 392 UpperNodeMap& operator=(const CMap& cmap) {393 checkConcept<concept::ReadMap< UpperNode, _Value>, CMap>();394 const typename Parent::Graph* graph = Parent::getGraph(); 395 UpperNode it;396 for (graph->first(it); it != INVALID; graph->next(it)) { 397 Parent::set(it, cmap[it]); 398 } 399 return *this; 400 } 401 402 }; 403 404 template <typename _Value> 405 class LowerNodeMap406 : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {407 public: 408 typedef Mappable UBipartiteGraphExtender Graph;409 typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> >392 ANodeMap& operator=(const CMap& cmap) { 393 checkConcept<concept::ReadMap<ANode, _Value>, CMap>(); 394 const typename Parent::Graph* graph = Parent::getGraph(); 395 ANode it; 396 for (graph->first(it); it != INVALID; graph->next(it)) { 397 Parent::set(it, cmap[it]); 398 } 399 return *this; 400 } 401 402 }; 403 404 template <typename _Value> 405 class BNodeMap 406 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > { 407 public: 408 typedef MappableBpUGraphExtender Graph; 409 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> > 410 410 Parent; 411 411 412 LowerNodeMap(const Graph& _g)413 : Parent(_g) {} 414 LowerNodeMap(const Graph& _g, const _Value& _v)415 : Parent(_g, _v) {} 416 417 LowerNodeMap& operator=(const LowerNodeMap& cmap) {418 return operator=< LowerNodeMap>(cmap);412 BNodeMap(const Graph& _g) 413 : Parent(_g) {} 414 BNodeMap(const Graph& _g, const _Value& _v) 415 : Parent(_g, _v) {} 416 417 BNodeMap& operator=(const BNodeMap& cmap) { 418 return operator=<BNodeMap>(cmap); 419 419 } 420 420 … … 424 424 /// The given parameter should be conform to the ReadMap 425 425 /// concept and could be indiced by the current item set of 426 /// the LowerNodeMap. In this case the value for each item426 /// the BNodeMap. In this case the value for each item 427 427 /// is assigned by the value of the given ReadMap. 428 428 template <typename CMap> 429 LowerNodeMap& operator=(const CMap& cmap) {430 checkConcept<concept::ReadMap< LowerNode, _Value>, CMap>();431 const typename Parent::Graph* graph = Parent::getGraph(); 432 LowerNode it;429 BNodeMap& operator=(const CMap& cmap) { 430 checkConcept<concept::ReadMap<BNode, _Value>, CMap>(); 431 const typename Parent::Graph* graph = Parent::getGraph(); 432 BNode it; 433 433 for (graph->first(it); it != INVALID; graph->next(it)) { 434 434 Parent::set(it, cmap[it]); … … 444 444 class NodeMapBase : public Parent::NodeNotifier::ObserverBase { 445 445 public: 446 typedef Mappable UBipartiteGraphExtender Graph;446 typedef MappableBpUGraphExtender Graph; 447 447 448 448 typedef Node Key; … … 450 450 451 451 /// The reference type of the map; 452 typedef typename LowerNodeMap<_Value>::Reference Reference;452 typedef typename BNodeMap<_Value>::Reference Reference; 453 453 /// The pointer type of the map; 454 typedef typename LowerNodeMap<_Value>::Pointer Pointer;454 typedef typename BNodeMap<_Value>::Pointer Pointer; 455 455 456 456 /// The const value type of the map. 457 457 typedef const Value ConstValue; 458 458 /// The const reference type of the map; 459 typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;459 typedef typename BNodeMap<_Value>::ConstReference ConstReference; 460 460 /// The pointer type of the map; 461 typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;461 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer; 462 462 463 463 typedef True ReferenceMapTag; 464 464 465 465 NodeMapBase(const Graph& _g) 466 : graph(&_g), lowerMap(_g), upperMap(_g) {466 : graph(&_g), bNodeMap(_g), aNodeMap(_g) { 467 467 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 468 468 } 469 469 NodeMapBase(const Graph& _g, const _Value& _v) 470 : graph(&_g), lowerMap(_g, _v),471 upperMap(_g, _v) {470 : graph(&_g), bNodeMap(_g, _v), 471 aNodeMap(_g, _v) { 472 472 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 473 473 } … … 480 480 481 481 ConstReference operator[](const Key& node) const { 482 if (Parent:: upper(node)) {483 return upperMap[node];482 if (Parent::aNode(node)) { 483 return aNodeMap[node]; 484 484 } else { 485 return lowerMap[node];485 return bNodeMap[node]; 486 486 } 487 487 } 488 488 489 489 Reference operator[](const Key& node) { 490 if (Parent:: upper(node)) {491 return upperMap[node];490 if (Parent::aNode(node)) { 491 return aNodeMap[node]; 492 492 } else { 493 return lowerMap[node];493 return bNodeMap[node]; 494 494 } 495 495 } 496 496 497 497 void set(const Key& node, const Value& value) { 498 if (Parent:: upper(node)) {499 upperMap.set(node, value);498 if (Parent::aNode(node)) { 499 aNodeMap.set(node, value); 500 500 } else { 501 lowerMap.set(node, value);501 bNodeMap.set(node, value); 502 502 } 503 503 } … … 514 514 private: 515 515 const Graph* graph; 516 LowerNodeMap<_Value> lowerMap;517 UpperNodeMap<_Value> upperMap;516 BNodeMap<_Value> bNodeMap; 517 ANodeMap<_Value> aNodeMap; 518 518 }; 519 519 … … 524 524 : public IterableMapExtender<NodeMapBase<_Value> > { 525 525 public: 526 typedef Mappable UBipartiteGraphExtender Graph;526 typedef MappableBpUGraphExtender Graph; 527 527 typedef IterableMapExtender< NodeMapBase<_Value> > Parent; 528 528 … … 562 562 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 563 563 public: 564 typedef Mappable UBipartiteGraphExtender Graph;564 typedef MappableBpUGraphExtender Graph; 565 565 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 566 566 … … 590 590 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { 591 591 public: 592 typedef Mappable UBipartiteGraphExtender Graph;592 typedef MappableBpUGraphExtender Graph; 593 593 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > 594 594 Parent; -
lemon/bits/extendable_graph_extender.h
r1909 r1910 106 106 107 107 template <typename _Base> 108 class Extendable UBipartiteGraphExtender : public _Base {108 class ExtendableBpUGraphExtender : public _Base { 109 109 public: 110 110 111 111 typedef _Base Parent; 112 typedef Extendable UBipartiteGraphExtender Graph;112 typedef ExtendableBpUGraphExtender Graph; 113 113 114 114 typedef typename Parent::Node Node; 115 typedef typename Parent:: LowerNode LowerNode;116 typedef typename Parent:: UpperNode UpperNode;115 typedef typename Parent::BNode BNode; 116 typedef typename Parent::ANode ANode; 117 117 typedef typename Parent::Edge Edge; 118 118 typedef typename Parent::UEdge UEdge; 119 119 120 Node add UpperNode() {121 Node node = Parent::add UpperNode();122 Parent::getNotifier( UpperNode()).add(node);120 Node addANode() { 121 Node node = Parent::addANode(); 122 Parent::getNotifier(ANode()).add(node); 123 123 Parent::getNotifier(Node()).add(node); 124 124 return node; 125 125 } 126 126 127 Node add LowerNode() {128 Node node = Parent::add LowerNode();129 Parent::getNotifier( LowerNode()).add(node);127 Node addBNode() { 128 Node node = Parent::addBNode(); 129 Parent::getNotifier(BNode()).add(node); 130 130 Parent::getNotifier(Node()).add(node); 131 131 return node; -
lemon/bits/graph_extender.h
r1909 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi 5 * Kutatocsoport (Egervary Research Gro upon Combinatorial Optimization,5 * Kutatocsoport (Egervary Research Groin on Combinatorial Optimization, 6 6 * EGRES). 7 7 * … … 380 380 381 381 template <typename _Base> 382 class UBipartiteGraphExtender : public _Base {382 class BpUGraphExtender : public _Base { 383 383 public: 384 384 typedef _Base Parent; 385 typedef UBipartiteGraphExtender Graph;385 typedef BpUGraphExtender Graph; 386 386 387 387 typedef typename Parent::Node Node; … … 394 394 395 395 Node source(const UEdge& edge) const { 396 return upperNode(edge);396 return aNode(edge); 397 397 } 398 398 Node target(const UEdge& edge) const { 399 return lowerNode(edge);399 return bNode(edge); 400 400 } 401 401 402 402 void firstInc(UEdge& edge, bool& direction, const Node& node) const { 403 if (Parent:: upper(node)) {404 Parent::first Down(edge, node);403 if (Parent::aNode(node)) { 404 Parent::firstOut(edge, node); 405 405 direction = true; 406 406 } else { 407 Parent::first Up(edge, node);407 Parent::firstIn(edge, node); 408 408 direction = static_cast<UEdge&>(edge) == INVALID; 409 409 } … … 411 411 void nextInc(UEdge& edge, bool& direction) const { 412 412 if (direction) { 413 Parent::next Down(edge);414 } else { 415 Parent::next Up(edge);413 Parent::nextOut(edge); 414 } else { 415 Parent::nextIn(edge); 416 416 if (edge == INVALID) direction = true; 417 417 } … … 427 427 428 428 class Edge : public UEdge { 429 friend class UBipartiteGraphExtender;429 friend class BpUGraphExtender; 430 430 protected: 431 431 bool forward; … … 462 462 463 463 void firstOut(Edge& edge, const Node& node) const { 464 if (Parent:: upper(node)) {465 Parent::first Down(edge, node);464 if (Parent::aNode(node)) { 465 Parent::firstOut(edge, node); 466 466 edge.forward = true; 467 467 } else { 468 Parent::first Up(edge, node);468 Parent::firstIn(edge, node); 469 469 edge.forward = static_cast<UEdge&>(edge) == INVALID; 470 470 } … … 472 472 void nextOut(Edge& edge) const { 473 473 if (edge.forward) { 474 Parent::next Down(edge);475 } else { 476 Parent::next Up(edge);474 Parent::nextOut(edge); 475 } else { 476 Parent::nextIn(edge); 477 477 edge.forward = static_cast<UEdge&>(edge) == INVALID; 478 478 } … … 480 480 481 481 void firstIn(Edge& edge, const Node& node) const { 482 if (Parent:: lower(node)) {483 Parent::first Up(edge, node);482 if (Parent::bNode(node)) { 483 Parent::firstIn(edge, node); 484 484 edge.forward = true; 485 485 } else { 486 Parent::first Down(edge, node);486 Parent::firstOut(edge, node); 487 487 edge.forward = static_cast<UEdge&>(edge) == INVALID; 488 488 } … … 490 490 void nextIn(Edge& edge) const { 491 491 if (edge.forward) { 492 Parent::next Up(edge);493 } else { 494 Parent::next Down(edge);492 Parent::nextIn(edge); 493 } else { 494 Parent::nextOut(edge); 495 495 edge.forward = static_cast<UEdge&>(edge) == INVALID; 496 496 } … … 498 498 499 499 Node source(const Edge& edge) const { 500 return edge.forward ? Parent:: upperNode(edge) : Parent::lowerNode(edge);500 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); 501 501 } 502 502 Node target(const Edge& edge) const { 503 return edge.forward ? Parent:: lowerNode(edge) : Parent::upperNode(edge);503 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); 504 504 } 505 505 … … 535 535 } 536 536 537 class UpperNode : public Node {538 friend class UBipartiteGraphExtender;537 class ANode : public Node { 538 friend class BpUGraphExtender; 539 539 public: 540 UpperNode() {}541 UpperNode(const Node& node) : Node(node) {542 LEMON_ASSERT(Parent:: upper(node) || node == INVALID,540 ANode() {} 541 ANode(const Node& node) : Node(node) { 542 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 543 543 typename Parent::NodeSetError()); 544 544 } 545 UpperNode(Invalid) : Node(INVALID) {}545 ANode(Invalid) : Node(INVALID) {} 546 546 }; 547 547 548 void first( UpperNode& node) const {549 Parent::first Upper(static_cast<Node&>(node));550 } 551 void next( UpperNode& node) const {552 Parent::next Upper(static_cast<Node&>(node));553 } 554 555 int id(const UpperNode& node) const {556 return Parent:: upperId(node);557 } 558 559 class LowerNode : public Node {560 friend class UBipartiteGraphExtender;548 void first(ANode& node) const { 549 Parent::firstANode(static_cast<Node&>(node)); 550 } 551 void next(ANode& node) const { 552 Parent::nextANode(static_cast<Node&>(node)); 553 } 554 555 int id(const ANode& node) const { 556 return Parent::aNodeId(node); 557 } 558 559 class BNode : public Node { 560 friend class BpUGraphExtender; 561 561 public: 562 LowerNode() {}563 LowerNode(const Node& node) : Node(node) {564 LEMON_ASSERT(Parent:: lower(node) || node == INVALID,562 BNode() {} 563 BNode(const Node& node) : Node(node) { 564 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 565 565 typename Parent::NodeSetError()); 566 566 } 567 LowerNode(Invalid) : Node(INVALID) {}567 BNode(Invalid) : Node(INVALID) {} 568 568 }; 569 569 570 void first( LowerNode& node) const {571 Parent::first Lower(static_cast<Node&>(node));572 } 573 void next( LowerNode& node) const {574 Parent::next Lower(static_cast<Node&>(node));570 void first(BNode& node) const { 571 Parent::firstBNode(static_cast<Node&>(node)); 572 } 573 void next(BNode& node) const { 574 Parent::nextBNode(static_cast<Node&>(node)); 575 575 } 576 576 577 int id(const LowerNode& node) const {578 return Parent:: upperId(node);577 int id(const BNode& node) const { 578 return Parent::aNodeId(node); 579 579 } 580 580 … … 584 584 return Parent::maxNodeId(); 585 585 } 586 int maxId( LowerNode) const {587 return Parent::max LowerId();588 } 589 int maxId( UpperNode) const {590 return Parent::max UpperId();586 int maxId(BNode) const { 587 return Parent::maxBNodeId(); 588 } 589 int maxId(ANode) const { 590 return Parent::maxANodeId(); 591 591 } 592 592 int maxId(Edge) const { … … 601 601 return Parent::nodeFromId(id); 602 602 } 603 UpperNode fromId(int id, UpperNode) const {604 return Parent::from UpperId(id);605 } 606 LowerNode fromId(int id, LowerNode) const {607 return Parent::from LowerId(id);603 ANode fromId(int id, ANode) const { 604 return Parent::fromANodeId(id); 605 } 606 BNode fromId(int id, BNode) const { 607 return Parent::fromBNodeId(id); 608 608 } 609 609 Edge fromId(int id, Edge) const { -
lemon/bits/item_reader.h
r1875 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 15 15 */ 16 16 17 /// @defgro upitem_io Item Readers and Writers18 /// @ingro up io_group17 /// @defgroin item_io Item Readers and Writers 18 /// @ingroin io_groin 19 19 /// \brief Item Readers and Writers 20 20 /// … … 23 23 /// read some way. The module make possible to do this. 24 24 25 /// \ingro upitem_io25 /// \ingroin item_io 26 26 /// \file 27 27 /// \brief Item reader bits for lemon input. … … 43 43 class DefaultReader; 44 44 45 /// \ingro upitem_io45 /// \ingroin item_io 46 46 /// 47 47 /// \brief Reader class for quoted strings. … … 158 158 }; 159 159 160 /// \ingro upitem_io160 /// \ingroin item_io 161 161 /// \brief Reader for standard containers. 162 162 /// … … 205 205 }; 206 206 207 /// \ingro upitem_io207 /// \ingroin item_io 208 208 /// 209 209 /// \brief Reader for standard containers. … … 253 253 }; 254 254 255 /// \ingro upitem_io255 /// \ingroin item_io 256 256 /// \brief Reader for parsed string. 257 257 /// … … 301 301 }; 302 302 303 /// \ingro upitem_io303 /// \ingroin item_io 304 304 /// \brief Reader for read the whole line. 305 305 /// … … 331 331 }; 332 332 333 /// \ingro upitem_io333 /// \ingroin item_io 334 334 /// \brief Reader for std::pair. 335 335 /// … … 385 385 }; 386 386 387 /// \ingro upitem_io387 /// \ingroin item_io 388 388 /// 389 389 /// \brief The default item reader template class. … … 472 472 : public PairReader<std::pair<First, Second> > {}; 473 473 474 /// \ingro upitem_io474 /// \ingroin item_io 475 475 /// 476 476 /// \brief The default item reader for skipping a value in the stream. … … 481 481 class DefaultSkipper : public DefaultReader<std::string> {}; 482 482 483 /// \ingro upitem_io483 /// \ingroin item_io 484 484 /// \brief Standard ReaderTraits for the GraphReader class. 485 485 /// -
lemon/bits/item_writer.h
r1875 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 15 15 */ 16 16 17 /// \ingro upitem_io17 /// \ingroin item_io 18 18 /// \file 19 19 /// \brief Item writer bits for lemon output. … … 35 35 class DefaultWriter; 36 36 37 /// \ingro upitem_io37 /// \ingroin item_io 38 38 /// \brief Writer class for quoted strings. 39 39 /// … … 118 118 }; 119 119 120 /// \ingro upitem_io120 /// \ingroin item_io 121 121 /// \brief Writer class for quoted char array. 122 122 /// … … 146 146 147 147 148 /// \ingro upitem_io148 /// \ingroin item_io 149 149 /// 150 150 /// \brief Writer for standard containers. … … 188 188 }; 189 189 190 /// \ingro upitem_io190 /// \ingroin item_io 191 191 /// 192 192 /// \brief Writer for standard pairs. … … 235 235 }; 236 236 237 /// \ingro upitem_io237 /// \ingroin item_io 238 238 /// 239 239 /// \brief The default item writer template class. … … 308 308 : public PairWriter<std::pair<First, Second> > {}; 309 309 310 /// \ingro upitem_io310 /// \ingroin item_io 311 311 /// \brief Standard WriterTraits for the section writers. 312 312 /// -
lemon/bits/iterable_graph_extender.h
r1909 r1910 271 271 272 272 template <typename _Base> 273 class Iterable UBipartiteGraphExtender : public _Base {273 class IterableBpUGraphExtender : public _Base { 274 274 public: 275 275 typedef _Base Parent; 276 typedef Iterable UBipartiteGraphExtender Graph;276 typedef IterableBpUGraphExtender Graph; 277 277 278 278 typedef typename Parent::Node Node; 279 typedef typename Parent:: UpperNode UpperNode;280 typedef typename Parent:: LowerNode LowerNode;279 typedef typename Parent::ANode ANode; 280 typedef typename Parent::BNode BNode; 281 281 typedef typename Parent::Edge Edge; 282 282 typedef typename Parent::UEdge UEdge; … … 304 304 }; 305 305 306 class UpperNodeIt : public Node {307 friend class Iterable UBipartiteGraphExtender;308 const Graph* graph; 309 public: 310 311 UpperNodeIt() { }312 313 UpperNodeIt(Invalid i) : Node(INVALID) { }314 315 explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {316 graph->first Upper(static_cast<Node&>(*this));317 } 318 319 UpperNodeIt(const Graph& _graph, const Node& node)306 class ANodeIt : public Node { 307 friend class IterableBpUGraphExtender; 308 const Graph* graph; 309 public: 310 311 ANodeIt() { } 312 313 ANodeIt(Invalid i) : Node(INVALID) { } 314 315 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 316 graph->firstANode(static_cast<Node&>(*this)); 317 } 318 319 ANodeIt(const Graph& _graph, const Node& node) 320 320 : Node(node), graph(&_graph) {} 321 321 322 UpperNodeIt& operator++() {323 graph->next Upper(*this);324 return *this; 325 } 326 }; 327 328 class LowerNodeIt : public Node {329 friend class Iterable UBipartiteGraphExtender;330 const Graph* graph; 331 public: 332 333 LowerNodeIt() { }334 335 LowerNodeIt(Invalid i) : Node(INVALID) { }336 337 explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {338 graph->first Lower(static_cast<Node&>(*this));339 } 340 341 LowerNodeIt(const Graph& _graph, const Node& node)322 ANodeIt& operator++() { 323 graph->nextANode(*this); 324 return *this; 325 } 326 }; 327 328 class BNodeIt : public Node { 329 friend class IterableBpUGraphExtender; 330 const Graph* graph; 331 public: 332 333 BNodeIt() { } 334 335 BNodeIt(Invalid i) : Node(INVALID) { } 336 337 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 338 graph->firstBNode(static_cast<Node&>(*this)); 339 } 340 341 BNodeIt(const Graph& _graph, const Node& node) 342 342 : Node(node), graph(&_graph) {} 343 343 344 LowerNodeIt& operator++() {345 graph->next Lower(*this);344 BNodeIt& operator++() { 345 graph->nextBNode(*this); 346 346 return *this; 347 347 } … … 349 349 350 350 class EdgeIt : public Edge { 351 friend class Iterable UBipartiteGraphExtender;351 friend class IterableBpUGraphExtender; 352 352 const Graph* graph; 353 353 public: … … 372 372 373 373 class UEdgeIt : public UEdge { 374 friend class Iterable UBipartiteGraphExtender;374 friend class IterableBpUGraphExtender; 375 375 const Graph* graph; 376 376 public: … … 394 394 395 395 class OutEdgeIt : public Edge { 396 friend class Iterable UBipartiteGraphExtender;396 friend class IterableBpUGraphExtender; 397 397 const Graph* graph; 398 398 public: … … 419 419 420 420 class InEdgeIt : public Edge { 421 friend class Iterable UBipartiteGraphExtender;421 friend class IterableBpUGraphExtender; 422 422 const Graph* graph; 423 423 public: … … 471 471 472 472 class IncEdgeIt : public Parent::UEdge { 473 friend class Iterable UBipartiteGraphExtender;473 friend class IterableBpUGraphExtender; 474 474 const Graph* graph; 475 475 bool direction; -
lemon/bits/map_extender.h
r1875 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted -
lemon/bits/static_map.h
r1909 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 28 28 #include <lemon/concept/maps.h> 29 29 30 /// \ingro upgraphmaps30 /// \ingroin graphmaps 31 31 /// 32 32 ///\file … … 35 35 namespace lemon { 36 36 37 /// \ingro upgraphmaps37 /// \ingroin graphmaps 38 38 /// 39 39 /// \brief Graph map with static sized storage. 40 40 /// 41 41 /// The StaticMap template class is graph map structure what 42 /// does not update automatically the map when a key is added to or42 /// does not indate automatically the map when a key is added to or 43 43 /// erased from the map rather it throws an exception. This map factory 44 44 /// uses the allocators to implement the container functionality. … … 55 55 public: 56 56 57 /// \brief Exception class for uns upported exceptions.58 class Uns upportedOperation : public lemon::LogicError {57 /// \brief Exception class for unsinported exceptions. 58 class UnsinportedOperation : public lemon::LogicError { 59 59 public: 60 60 virtual const char* exceptionName() const { 61 return "lemon::StaticMap::Uns upportedOperation";61 return "lemon::StaticMap::UnsinportedOperation"; 62 62 } 63 63 }; … … 186 186 187 187 void add(const Key&) { 188 throw Uns upportedOperation();188 throw UnsinportedOperation(); 189 189 } 190 190 … … 194 194 /// and it overrides the erase() member function of the observer base. 195 195 void erase(const Key&) { 196 throw Uns upportedOperation();196 throw UnsinportedOperation(); 197 197 } 198 198 … … 347 347 348 348 template <typename _Base> 349 class StaticMappable UBipartiteGraphExtender : public _Base {349 class StaticMappableBpUGraphExtender : public _Base { 350 350 public: 351 351 352 352 typedef _Base Parent; 353 typedef StaticMappable UBipartiteGraphExtender Graph;353 typedef StaticMappableBpUGraphExtender Graph; 354 354 355 355 typedef typename Parent::Node Node; 356 typedef typename Parent:: UpperNode UpperNode;357 typedef typename Parent:: LowerNode LowerNode;356 typedef typename Parent::ANode ANode; 357 typedef typename Parent::BNode BNode; 358 358 typedef typename Parent::Edge Edge; 359 359 typedef typename Parent::UEdge UEdge; 360 360 361 361 template <typename _Value> 362 class UpperNodeMap363 : public IterableMapExtender<StaticMap<Graph, UpperNode, _Value> > {364 public: 365 typedef StaticMappable UBipartiteGraphExtender Graph;366 typedef IterableMapExtender<StaticMap<Graph, UpperNode, _Value> >362 class ANodeMap 363 : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > { 364 public: 365 typedef StaticMappableBpUGraphExtender Graph; 366 typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> > 367 367 Parent; 368 368 369 UpperNodeMap(const Graph& _g)370 : Parent(_g) {} 371 UpperNodeMap(const Graph& _g, const _Value& _v)372 : Parent(_g, _v) {} 373 374 UpperNodeMap& operator=(const UpperNodeMap& cmap) {375 return operator=< UpperNodeMap>(cmap);369 ANodeMap(const Graph& _g) 370 : Parent(_g) {} 371 ANodeMap(const Graph& _g, const _Value& _v) 372 : Parent(_g, _v) {} 373 374 ANodeMap& operator=(const ANodeMap& cmap) { 375 return operator=<ANodeMap>(cmap); 376 376 } 377 377 … … 381 381 /// The given parameter should be conform to the ReadMap 382 382 /// concept and could be indiced by the current item set of 383 /// the UpperNodeMap. In this case the value for each item383 /// the ANodeMap. In this case the value for each item 384 384 /// is assigned by the value of the given ReadMap. 385 385 template <typename CMap> 386 UpperNodeMap& operator=(const CMap& cmap) {387 checkConcept<concept::ReadMap< UpperNode, _Value>, CMap>();388 const typename Parent::Graph* graph = Parent::getGraph(); 389 UpperNode it;390 for (graph->first(it); it != INVALID; graph->next(it)) { 391 Parent::set(it, cmap[it]); 392 } 393 return *this; 394 } 395 396 }; 397 398 template <typename _Value> 399 class LowerNodeMap400 : public IterableMapExtender<StaticMap<Graph, LowerNode, _Value> > {401 public: 402 typedef StaticMappable UBipartiteGraphExtender Graph;403 typedef IterableMapExtender<StaticMap<Graph, LowerNode, _Value> >386 ANodeMap& operator=(const CMap& cmap) { 387 checkConcept<concept::ReadMap<ANode, _Value>, CMap>(); 388 const typename Parent::Graph* graph = Parent::getGraph(); 389 ANode it; 390 for (graph->first(it); it != INVALID; graph->next(it)) { 391 Parent::set(it, cmap[it]); 392 } 393 return *this; 394 } 395 396 }; 397 398 template <typename _Value> 399 class BNodeMap 400 : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > { 401 public: 402 typedef StaticMappableBpUGraphExtender Graph; 403 typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> > 404 404 Parent; 405 405 406 LowerNodeMap(const Graph& _g)407 : Parent(_g) {} 408 LowerNodeMap(const Graph& _g, const _Value& _v)409 : Parent(_g, _v) {} 410 411 LowerNodeMap& operator=(const LowerNodeMap& cmap) {412 return operator=< LowerNodeMap>(cmap);406 BNodeMap(const Graph& _g) 407 : Parent(_g) {} 408 BNodeMap(const Graph& _g, const _Value& _v) 409 : Parent(_g, _v) {} 410 411 BNodeMap& operator=(const BNodeMap& cmap) { 412 return operator=<BNodeMap>(cmap); 413 413 } 414 414 … … 418 418 /// The given parameter should be conform to the ReadMap 419 419 /// concept and could be indiced by the current item set of 420 /// the LowerNodeMap. In this case the value for each item420 /// the BNodeMap. In this case the value for each item 421 421 /// is assigned by the value of the given ReadMap. 422 422 template <typename CMap> 423 LowerNodeMap& operator=(const CMap& cmap) {424 checkConcept<concept::ReadMap< LowerNode, _Value>, CMap>();425 const typename Parent::Graph* graph = Parent::getGraph(); 426 LowerNode it;423 BNodeMap& operator=(const CMap& cmap) { 424 checkConcept<concept::ReadMap<BNode, _Value>, CMap>(); 425 const typename Parent::Graph* graph = Parent::getGraph(); 426 BNode it; 427 427 for (graph->first(it); it != INVALID; graph->next(it)) { 428 428 Parent::set(it, cmap[it]); … … 438 438 class NodeMapBase : public Parent::NodeNotifier::ObserverBase { 439 439 public: 440 typedef StaticMappable UBipartiteGraphExtender Graph;440 typedef StaticMappableBpUGraphExtender Graph; 441 441 442 442 typedef Node Key; … … 444 444 445 445 /// The reference type of the map; 446 typedef typename LowerNodeMap<_Value>::Reference Reference;446 typedef typename BNodeMap<_Value>::Reference Reference; 447 447 /// The pointer type of the map; 448 typedef typename LowerNodeMap<_Value>::Pointer Pointer;448 typedef typename BNodeMap<_Value>::Pointer Pointer; 449 449 450 450 /// The const value type of the map. 451 451 typedef const Value ConstValue; 452 452 /// The const reference type of the map; 453 typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;453 typedef typename BNodeMap<_Value>::ConstReference ConstReference; 454 454 /// The pointer type of the map; 455 typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;455 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer; 456 456 457 457 typedef True ReferenceMapTag; 458 458 459 459 NodeMapBase(const Graph& _g) 460 : graph(&_g), lowerMap(_g), upperMap(_g) {460 : graph(&_g), bNodeMap(_g), aNodeMap(_g) { 461 461 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 462 462 } 463 463 NodeMapBase(const Graph& _g, const _Value& _v) 464 : graph(&_g), lowerMap(_g, _v),465 upperMap(_g, _v) {464 : graph(&_g), bNodeMap(_g, _v), 465 aNodeMap(_g, _v) { 466 466 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 467 467 } … … 474 474 475 475 ConstReference operator[](const Key& node) const { 476 if (Parent:: upper(node)) {477 return upperMap[node];476 if (Parent::aNode(node)) { 477 return aNodeMap[node]; 478 478 } else { 479 return lowerMap[node];479 return bNodeMap[node]; 480 480 } 481 481 } 482 482 483 483 Reference operator[](const Key& node) { 484 if (Parent:: upper(node)) {485 return upperMap[node];484 if (Parent::aNode(node)) { 485 return aNodeMap[node]; 486 486 } else { 487 return lowerMap[node];487 return bNodeMap[node]; 488 488 } 489 489 } 490 490 491 491 void set(const Key& node, const Value& value) { 492 if (Parent:: upper(node)) {493 upperMap.set(node, value);492 if (Parent::aNode(node)) { 493 aNodeMap.set(node, value); 494 494 } else { 495 lowerMap.set(node, value);495 bNodeMap.set(node, value); 496 496 } 497 497 } … … 508 508 private: 509 509 const Graph* graph; 510 LowerNodeMap<_Value> lowerMap;511 UpperNodeMap<_Value> upperMap;510 BNodeMap<_Value> bNodeMap; 511 ANodeMap<_Value> aNodeMap; 512 512 }; 513 513 … … 518 518 : public IterableMapExtender<NodeMapBase<_Value> > { 519 519 public: 520 typedef StaticMappable UBipartiteGraphExtender Graph;520 typedef StaticMappableBpUGraphExtender Graph; 521 521 typedef IterableMapExtender< NodeMapBase<_Value> > Parent; 522 522 … … 556 556 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > { 557 557 public: 558 typedef StaticMappable UBipartiteGraphExtender Graph;558 typedef StaticMappableBpUGraphExtender Graph; 559 559 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent; 560 560 … … 584 584 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > { 585 585 public: 586 typedef StaticMappable UBipartiteGraphExtender Graph;586 typedef StaticMappableBpUGraphExtender Graph; 587 587 typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> > 588 588 Parent; -
lemon/bits/vector_map.h
r1875 r1910 3 3 * 4 4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 5 * (Egervary Research Gro upon Combinatorial Optimization, EGRES).5 * (Egervary Research Groin on Combinatorial Optimization, EGRES). 6 6 * 7 7 * Permission to use, modify and distribute this software is granted … … 27 27 #include <lemon/concept/maps.h> 28 28 29 /// \ingro upgraphmapfactory29 /// \ingroin graphmapfactory 30 30 /// 31 31 ///\file … … 34 34 namespace lemon { 35 35 36 /// \ingro upgraphmapfactory36 /// \ingroin graphmapfactory 37 37 /// 38 38 /// \brief Graph map based on the std::vector storage. 39 39 /// 40 40 /// The VectorMap template class is graph map structure what 41 /// automatically updates the map when a key is added to or erased from41 /// automatically indates the map when a key is added to or erased from 42 42 /// the map. This map factory uses the allocators to implement 43 43 /// the container functionality. This map factory -
lemon/concept/ugraph.h
r1909 r1910 23 23 24 24 25 #ifndef LEMON_CONCEPT_U NDIR_GRAPH_H26 #define LEMON_CONCEPT_U NDIR_GRAPH_H25 #ifndef LEMON_CONCEPT_UGRAPH_H 26 #define LEMON_CONCEPT_UGRAPH_H 27 27 28 28 #include <lemon/concept/graph_component.h> -
lemon/full_graph.h
r1909 r1910 404 404 405 405 406 class Full UBipartiteGraphBase {406 class FullBpUGraphBase { 407 407 protected: 408 408 409 int _ upperNodeNum;410 int _ lowerNodeNum;409 int _aNodeNum; 410 int _bNodeNum; 411 411 412 412 int _edgeNum; … … 416 416 class NodeSetError : public LogicError { 417 417 virtual const char* exceptionName() const { 418 return "lemon::Full UBipartiteGraph::NodeSetError";418 return "lemon::FullBpUGraph::NodeSetError"; 419 419 } 420 420 }; 421 421 422 422 class Node { 423 friend class Full UBipartiteGraphBase;423 friend class FullBpUGraphBase; 424 424 protected: 425 425 int id; … … 435 435 436 436 class Edge { 437 friend class Full UBipartiteGraphBase;437 friend class FullBpUGraphBase; 438 438 protected: 439 439 int id; … … 448 448 }; 449 449 450 void construct(int upperNodeNum, int lowerNodeNum) {451 _ upperNodeNum = upperNodeNum;452 _ lowerNodeNum = lowerNodeNum;453 _edgeNum = upperNodeNum * lowerNodeNum;454 } 455 456 void first Upper(Node& node) const {457 node.id = 2 * _ upperNodeNum - 2;450 void construct(int aNodeNum, int bNodeNum) { 451 _aNodeNum = aNodeNum; 452 _bNodeNum = bNodeNum; 453 _edgeNum = aNodeNum * bNodeNum; 454 } 455 456 void firstANode(Node& node) const { 457 node.id = 2 * _aNodeNum - 2; 458 458 if (node.id < 0) node.id = -1; 459 459 } 460 void next Upper(Node& node) const {460 void nextANode(Node& node) const { 461 461 node.id -= 2; 462 462 if (node.id < 0) node.id = -1; 463 463 } 464 464 465 void first Lower(Node& node) const {466 node.id = 2 * _ lowerNodeNum - 1;467 } 468 void next Lower(Node& node) const {465 void firstBNode(Node& node) const { 466 node.id = 2 * _bNodeNum - 1; 467 } 468 void nextBNode(Node& node) const { 469 469 node.id -= 2; 470 470 } 471 471 472 472 void first(Node& node) const { 473 if (_ upperNodeNum > 0) {474 node.id = 2 * _ upperNodeNum - 2;473 if (_aNodeNum > 0) { 474 node.id = 2 * _aNodeNum - 2; 475 475 } else { 476 node.id = 2 * _ lowerNodeNum - 1;476 node.id = 2 * _bNodeNum - 1; 477 477 } 478 478 } … … 480 480 node.id -= 2; 481 481 if (node.id == -2) { 482 node.id = 2 * _ lowerNodeNum - 1;482 node.id = 2 * _bNodeNum - 1; 483 483 } 484 484 } … … 491 491 } 492 492 493 void first Down(Edge& edge, const Node& node) const {493 void firstOut(Edge& edge, const Node& node) const { 494 494 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 495 edge.id = (node.id >> 1) * _ lowerNodeNum;496 } 497 void next Down(Edge& edge) const {495 edge.id = (node.id >> 1) * _bNodeNum; 496 } 497 void nextOut(Edge& edge) const { 498 498 ++(edge.id); 499 if (edge.id % _ lowerNodeNum == 0) edge.id = -1;500 } 501 502 void first Up(Edge& edge, const Node& node) const {499 if (edge.id % _bNodeNum == 0) edge.id = -1; 500 } 501 502 void firstIn(Edge& edge, const Node& node) const { 503 503 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 504 504 edge.id = (node.id >> 1); 505 505 } 506 void next Up(Edge& edge) const {507 edge.id += _ lowerNodeNum;506 void nextIn(Edge& edge) const { 507 edge.id += _bNodeNum; 508 508 if (edge.id >= _edgeNum) edge.id = -1; 509 509 } … … 516 516 } 517 517 int maxNodeId() const { 518 return _ upperNodeNum > _lowerNodeNum ?519 _ upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;518 return _aNodeNum > _bNodeNum ? 519 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1; 520 520 } 521 521 … … 530 530 } 531 531 532 static int upperId(const Node& node) {532 static int aNodeId(const Node& node) { 533 533 return node.id >> 1; 534 534 } 535 static Node from UpperId(int id, Node) {535 static Node fromANodeId(int id, Node) { 536 536 return Node(id << 1); 537 537 } 538 int max UpperId() const {539 return _ upperNodeNum;540 } 541 542 static int lowerId(const Node& node) {538 int maxANodeId() const { 539 return _aNodeNum; 540 } 541 542 static int bNodeId(const Node& node) { 543 543 return node.id >> 1; 544 544 } 545 static Node from LowerId(int id) {545 static Node fromBNodeId(int id) { 546 546 return Node((id << 1) + 1); 547 547 } 548 int max LowerId() const {549 return _ lowerNodeNum;550 } 551 552 Node upperNode(const Edge& edge) const {553 return Node((edge.id / _ lowerNodeNum) << 1);554 } 555 Node lowerNode(const Edge& edge) const {556 return Node(((edge.id % _ lowerNodeNum) << 1) + 1);557 } 558 559 static bool upper(const Node& node) {548 int maxBNodeId() const { 549 return _bNodeNum; 550 } 551 552 Node aNode(const Edge& edge) const { 553 return Node((edge.id / _bNodeNum) << 1); 554 } 555 Node bNode(const Edge& edge) const { 556 return Node(((edge.id % _bNodeNum) << 1) + 1); 557 } 558 559 static bool aNode(const Node& node) { 560 560 return (node.id & 1) == 0; 561 561 } 562 562 563 static bool lower(const Node& node) {563 static bool bNode(const Node& node) { 564 564 return (node.id & 1) == 1; 565 565 } 566 566 567 static Node upperNode(int index) {567 static Node aNode(int index) { 568 568 return Node(index << 1); 569 569 } 570 570 571 static Node lowerNode(int index) {571 static Node bNode(int index) { 572 572 return Node((index << 1) + 1); 573 573 } … … 576 576 577 577 578 typedef StaticMappableUBipartiteGraphExtender< 579 IterableUBipartiteGraphExtender< 580 AlterableUBipartiteGraphExtender< 581 UBipartiteGraphExtender < 582 FullUBipartiteGraphBase> > > > 583 ExtendedFullUBipartiteGraphBase; 584 585 586 class FullUBipartiteGraph : 587 public ExtendedFullUBipartiteGraphBase { 588 public: 589 typedef ExtendedFullUBipartiteGraphBase Parent; 590 FullUBipartiteGraph(int upperNodeNum, int lowerNodeNum) { 591 Parent::construct(upperNodeNum, lowerNodeNum); 578 typedef StaticMappableBpUGraphExtender< 579 IterableBpUGraphExtender< 580 AlterableBpUGraphExtender< 581 BpUGraphExtender < 582 FullBpUGraphBase> > > > 583 ExtendedFullBpUGraphBase; 584 585 586 /// \ingroup graphs 587 /// 588 /// \brief An undirected full bipartite graph class. 589 /// 590 /// This is a simple and fast bipartite undirected full graph implementation. 591 /// It is completely static, so you can neither add nor delete either 592 /// edges or nodes. 593 /// 594 /// \sa FullGraph 595 /// 596 /// \author Balazs Dezso 597 class FullBpUGraph : 598 public ExtendedFullBpUGraphBase { 599 public: 600 typedef ExtendedFullBpUGraphBase Parent; 601 FullBpUGraph(int aNodeNum, int bNodeNum) { 602 Parent::construct(aNodeNum, bNodeNum); 592 603 } 593 604 }; -
lemon/graph_to_eps.h
r1909 r1910 235 235 char *_nodePsTextsPreamble; 236 236 237 bool _u; 237 bool _undirected; 238 238 239 bool _pleaseRemoveOsStream; 239 240 … … 273 274 _showNodeText(false), _nodeTexts(false), _nodeTextSize(1), 274 275 _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0), 275 _u (false),276 _undirected(false), 276 277 _pleaseRemoveOsStream(_pros), _scaleToA4(false), 277 278 _nodeTextColorType(SAME_COL), _nodeTextColors(Color(0,0,0)), … … 330 331 using T::_nodePsTextsPreamble; 331 332 332 using T::_u; 333 using T::_undirected; 334 333 335 using T::_pleaseRemoveOsStream; 334 336 … … 735 737 ///Sets whether the the graph is undirected 736 738 /// 737 GraphToEps<T> &u(bool b=true) {_u=b;return *this;} 739 GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;} 740 738 741 ///Sets whether the the graph is directed 739 742 740 743 ///Sets whether the the graph is directed. 741 744 ///Use it to show the undirected edges as a pair of directed ones. 742 GraphToEps<T> &bidir(bool b=true) {_u =!b;return *this;}745 GraphToEps<T> &bidir(bool b=true) {_undirected=!b;return *this;} 743 746 744 747 ///Sets the title. … … 959 962 std::vector<Edge> el; 960 963 for(EdgeIt e(g);e!=INVALID;++e) 961 if((!_u ||g.source(e)<g.target(e))&&_edgeWidths[e]>0)964 if((!_undirected||g.source(e)<g.target(e))&&_edgeWidths[e]>0) 962 965 el.push_back(e); 963 966 std::sort(el.begin(),el.end(),edgeLess(g)); … … 1047 1050 } 1048 1051 else for(EdgeIt e(g);e!=INVALID;++e) 1049 if((!_u ||g.source(e)<g.target(e))&&_edgeWidths[e]>0)1052 if((!_undirected||g.source(e)<g.target(e))&&_edgeWidths[e]>0) 1050 1053 if(_drawArrows) { 1051 1054 xy<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]); -
lemon/smart_graph.h
r1909 r1910 379 379 380 380 381 class Smart UBipartiteGraphBase {381 class SmartBpUGraphBase { 382 382 public: 383 383 384 384 class NodeSetError : public LogicError { 385 385 virtual const char* exceptionName() const { 386 return "lemon:: FullUBipartiteGraph::NodeSetError";386 return "lemon::SmartBpUGraph::NodeSetError"; 387 387 } 388 388 }; … … 397 397 398 398 struct EdgeT { 399 int upper, next_down;400 int lower, next_up;401 }; 402 403 std::vector<NodeT> upperNodes;404 std::vector<NodeT> lowerNodes;399 int aNode, next_out; 400 int bNode, next_in; 401 }; 402 403 std::vector<NodeT> aNodes; 404 std::vector<NodeT> bNodes; 405 405 406 406 std::vector<EdgeT> edges; … … 409 409 410 410 class Node { 411 friend class Smart UBipartiteGraphBase;411 friend class SmartBpUGraphBase; 412 412 protected: 413 413 int id; … … 423 423 424 424 class Edge { 425 friend class Smart UBipartiteGraphBase;425 friend class SmartBpUGraphBase; 426 426 protected: 427 427 int id; … … 436 436 }; 437 437 438 void first Upper(Node& node) const {439 node.id = 2 * upperNodes.size() - 2;438 void firstANode(Node& node) const { 439 node.id = 2 * aNodes.size() - 2; 440 440 if (node.id < 0) node.id = -1; 441 441 } 442 void next Upper(Node& node) const {442 void nextANode(Node& node) const { 443 443 node.id -= 2; 444 444 if (node.id < 0) node.id = -1; 445 445 } 446 446 447 void first Lower(Node& node) const {448 node.id = 2 * lowerNodes.size() - 1;449 } 450 void next Lower(Node& node) const {447 void firstBNode(Node& node) const { 448 node.id = 2 * bNodes.size() - 1; 449 } 450 void nextBNode(Node& node) const { 451 451 node.id -= 2; 452 452 } 453 453 454 454 void first(Node& node) const { 455 if ( upperNodes.size() > 0) {456 node.id = 2 * upperNodes.size() - 2;455 if (aNodes.size() > 0) { 456 node.id = 2 * aNodes.size() - 2; 457 457 } else { 458 node.id = 2 * lowerNodes.size() - 1;458 node.id = 2 * bNodes.size() - 1; 459 459 } 460 460 } … … 462 462 node.id -= 2; 463 463 if (node.id == -2) { 464 node.id = 2 * lowerNodes.size() - 1;464 node.id = 2 * bNodes.size() - 1; 465 465 } 466 466 } … … 473 473 } 474 474 475 void first Down(Edge& edge, const Node& node) const {475 void firstOut(Edge& edge, const Node& node) const { 476 476 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 477 edge.id = upperNodes[node.id >> 1].first;478 } 479 void next Down(Edge& edge) const {480 edge.id = edges[edge.id].next_ down;481 } 482 483 void first Up(Edge& edge, const Node& node) const {477 edge.id = aNodes[node.id >> 1].first; 478 } 479 void nextOut(Edge& edge) const { 480 edge.id = edges[edge.id].next_out; 481 } 482 483 void firstIn(Edge& edge, const Node& node) const { 484 484 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 485 edge.id = lowerNodes[node.id >> 1].first;486 } 487 void next Up(Edge& edge) const {488 edge.id = edges[edge.id].next_ up;485 edge.id = bNodes[node.id >> 1].first; 486 } 487 void nextIn(Edge& edge) const { 488 edge.id = edges[edge.id].next_in; 489 489 } 490 490 … … 496 496 } 497 497 int maxNodeId() const { 498 return upperNodes.size() > lowerNodes.size() ?499 upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;498 return aNodes.size() > bNodes.size() ? 499 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 500 500 } 501 501 … … 510 510 } 511 511 512 static int upperId(const Node& node) {512 static int aNodeId(const Node& node) { 513 513 return node.id >> 1; 514 514 } 515 static Node from UpperId(int id, Node) {515 static Node fromANodeId(int id, Node) { 516 516 return Node(id << 1); 517 517 } 518 int max UpperId() const {519 return upperNodes.size();520 } 521 522 static int lowerId(const Node& node) {518 int maxANodeId() const { 519 return aNodes.size(); 520 } 521 522 static int bNodeId(const Node& node) { 523 523 return node.id >> 1; 524 524 } 525 static Node from LowerId(int id) {525 static Node fromBNodeId(int id) { 526 526 return Node((id << 1) + 1); 527 527 } 528 int max LowerId() const {529 return lowerNodes.size();530 } 531 532 Node upperNode(const Edge& edge) const {533 return Node(edges[edge.id]. upper);534 } 535 Node lowerNode(const Edge& edge) const {536 return Node(edges[edge.id]. lower);537 } 538 539 static bool upper(const Node& node) {528 int maxBNodeId() const { 529 return bNodes.size(); 530 } 531 532 Node aNode(const Edge& edge) const { 533 return Node(edges[edge.id].aNode); 534 } 535 Node bNode(const Edge& edge) const { 536 return Node(edges[edge.id].bNode); 537 } 538 539 static bool aNode(const Node& node) { 540 540 return (node.id & 1) == 0; 541 541 } 542 542 543 static bool lower(const Node& node) {543 static bool bNode(const Node& node) { 544 544 return (node.id & 1) == 1; 545 545 } 546 546 547 Node add UpperNode() {547 Node addANode() { 548 548 NodeT nodeT; 549 549 nodeT.first = -1; 550 upperNodes.push_back(nodeT);551 return Node( upperNodes.size() * 2 - 2);552 } 553 554 Node add LowerNode() {550 aNodes.push_back(nodeT); 551 return Node(aNodes.size() * 2 - 2); 552 } 553 554 Node addBNode() { 555 555 NodeT nodeT; 556 556 nodeT.first = -1; 557 lowerNodes.push_back(nodeT);558 return Node( lowerNodes.size() * 2 - 1);557 bNodes.push_back(nodeT); 558 return Node(bNodes.size() * 2 - 1); 559 559 } 560 560 … … 563 563 EdgeT edgeT; 564 564 if ((source.id & 1) == 0) { 565 edgeT. upper= source.id;566 edgeT. lower= target.id;565 edgeT.aNode = source.id; 566 edgeT.bNode = target.id; 567 567 } else { 568 edgeT. upper= target.id;569 edgeT. lower= source.id;570 } 571 edgeT.next_ down = upperNodes[edgeT.upper>> 1].first;572 upperNodes[edgeT.upper>> 1].first = edges.size();573 edgeT.next_ up = lowerNodes[edgeT.lower>> 1].first;574 lowerNodes[edgeT.lower>> 1].first = edges.size();568 edgeT.aNode = target.id; 569 edgeT.bNode = source.id; 570 } 571 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; 572 aNodes[edgeT.aNode >> 1].first = edges.size(); 573 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; 574 bNodes[edgeT.bNode >> 1].first = edges.size(); 575 575 edges.push_back(edgeT); 576 576 return Edge(edges.size() - 1); … … 578 578 579 579 void clear() { 580 upperNodes.clear();581 lowerNodes.clear();580 aNodes.clear(); 581 bNodes.clear(); 582 582 edges.clear(); 583 583 } … … 586 586 587 587 588 typedef ClearableUBipartiteGraphExtender< 589 ExtendableUBipartiteGraphExtender< 590 MappableUBipartiteGraphExtender< 591 IterableUBipartiteGraphExtender< 592 AlterableUBipartiteGraphExtender< 593 UBipartiteGraphExtender < 594 SmartUBipartiteGraphBase> > > > > > 595 ExtendedSmartUBipartiteGraphBase; 596 597 598 class SmartUBipartiteGraph : 599 public ExtendedSmartUBipartiteGraphBase { 600 }; 588 typedef ClearableBpUGraphExtender< 589 ExtendableBpUGraphExtender< 590 MappableBpUGraphExtender< 591 IterableBpUGraphExtender< 592 AlterableBpUGraphExtender< 593 BpUGraphExtender < 594 SmartBpUGraphBase> > > > > > 595 ExtendedSmartBpUGraphBase; 596 597 /// \ingroup graphs 598 /// 599 /// \brief A smart bipartite undirected graph class. 600 /// 601 /// This is a simple and fast bipartite undirected graph implementation. 602 /// It is also quite memory efficient, but at the price 603 /// that <b> it does not support node and edge deletions</b>. 604 /// Except from this it conforms to 605 /// the \ref concept::BpUGraph "BpUGraph" concept. 606 /// \sa concept::BpUGraph. 607 /// 608 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; 601 609 602 610
Note: See TracChangeset
for help on using the changeset viewer.