COIN-OR::LEMON - Graph Library

Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon


Ignore:
Timestamp:
06/30/06 14:14:36 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2821
Message:

Splitted graph files

Location:
lemon
Files:
6 added
8 edited
2 copied

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r2108 r2115  
    4444        lemon/floyd_warshall.h \
    4545        lemon/fredman_tarjan.h \
     46        lemon/full_bpugraph.h \
    4647        lemon/full_graph.h \
     48        lemon/full_ugraph.h \
    4749        lemon/graph_adaptor.h \
    4850        lemon/graph_reader.h \
     
    5759        lemon/lemon_reader.h \
    5860        lemon/lemon_writer.h \
     61        lemon/list_bpugraph.h \
    5962        lemon/list_graph.h \
     63        lemon/list_ugraph.h \
    6064        lemon/lp.h \
    6165        lemon/lp_base.h \
     
    7882        lemon/refptr.h \
    7983        lemon/simann.h \
     84        lemon/smart_bpugraph.h \
    8085        lemon/smart_graph.h \
     86        lemon/smart_ugraph.h \
    8187        lemon/sub_graph.h \
    8288        lemon/suurballe.h \
     
    9399        lemon/bits/array_map.h \
    94100        lemon/bits/base_extender.h \
     101        lemon/bits/bpugraph_extender.h \
    95102        lemon/bits/default_map.h \
    96103        lemon/bits/edge_set_extender.h \
     
    104111        lemon/bits/mingw32_time.h \
    105112        lemon/bits/traits.h \
     113        lemon/bits/ugraph_extender.h \
    106114        lemon/bits/utility.h \
    107115        lemon/bits/vector_map.h
  • lemon/bits/graph_extender.h

    r2102 r2115  
    2121
    2222#include <lemon/bits/invalid.h>
    23 #include <lemon/error.h>
    2423
    2524#include <lemon/bits/map_extender.h>
    2625#include <lemon/bits/default_map.h>
    27 
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concept/maps.h>
    3026
    3127///\ingroup graphbits
     
    319315  };
    320316
    321   /// \ingroup graphbits
    322   ///
    323   /// \brief Extender for the UGraphs
    324   template <typename Base>
    325   class UGraphExtender : public Base {
    326   public:
    327    
    328     typedef Base Parent;
    329     typedef UGraphExtender Graph;
    330 
    331     typedef typename Parent::Node Node;
    332     typedef typename Parent::Edge Edge;
    333     typedef typename Parent::UEdge UEdge;
    334 
    335     // UGraph extension   
    336 
    337     int maxId(Node) const {
    338       return Parent::maxNodeId();
    339     }
    340 
    341     int maxId(Edge) const {
    342       return Parent::maxEdgeId();
    343     }
    344 
    345     int maxId(UEdge) const {
    346       return Parent::maxUEdgeId();
    347     }
    348 
    349     Node fromId(int id, Node) const {
    350       return Parent::nodeFromId(id);
    351     }
    352 
    353     Edge fromId(int id, Edge) const {
    354       return Parent::edgeFromId(id);
    355     }
    356 
    357     UEdge fromId(int id, UEdge) const {
    358       return Parent::uEdgeFromId(id);
    359     }
    360 
    361     Node oppositeNode(const Node &n, const UEdge &e) const {
    362       if( n == Parent::source(e))
    363         return Parent::target(e);
    364       else if( n == Parent::target(e))
    365         return Parent::source(e);
    366       else
    367         return INVALID;
    368     }
    369 
    370     Edge oppositeEdge(const Edge &e) const {
    371       return Parent::direct(e, !Parent::direction(e));
    372     }
    373 
    374     using Parent::direct;
    375     Edge direct(const UEdge &ue, const Node &s) const {
    376       return Parent::direct(ue, Parent::source(ue) == s);
    377     }
    378 
    379     // Alterable extension
    380 
    381     typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
    382     typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
    383     typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
    384 
    385 
    386   protected:
    387 
    388     mutable NodeNotifier node_notifier;
    389     mutable EdgeNotifier edge_notifier;
    390     mutable UEdgeNotifier uedge_notifier;
    391 
    392   public:
    393 
    394     NodeNotifier& getNotifier(Node) const {
    395       return node_notifier;
    396     }
    397    
    398     EdgeNotifier& getNotifier(Edge) const {
    399       return edge_notifier;
    400     }
    401 
    402     UEdgeNotifier& getNotifier(UEdge) const {
    403       return uedge_notifier;
    404     }
    405 
    406 
    407 
    408     class NodeIt : public Node {
    409       const Graph* graph;
    410     public:
    411 
    412       NodeIt() {}
    413 
    414       NodeIt(Invalid i) : Node(i) { }
    415 
    416       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    417         _graph.first(static_cast<Node&>(*this));
    418       }
    419 
    420       NodeIt(const Graph& _graph, const Node& node)
    421         : Node(node), graph(&_graph) {}
    422 
    423       NodeIt& operator++() {
    424         graph->next(*this);
    425         return *this;
    426       }
    427 
    428     };
    429 
    430 
    431     class EdgeIt : public Edge {
    432       const Graph* graph;
    433     public:
    434 
    435       EdgeIt() { }
    436 
    437       EdgeIt(Invalid i) : Edge(i) { }
    438 
    439       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    440         _graph.first(static_cast<Edge&>(*this));
    441       }
    442 
    443       EdgeIt(const Graph& _graph, const Edge& e) :
    444         Edge(e), graph(&_graph) { }
    445 
    446       EdgeIt& operator++() {
    447         graph->next(*this);
    448         return *this;
    449       }
    450 
    451     };
    452 
    453 
    454     class OutEdgeIt : public Edge {
    455       const Graph* graph;
    456     public:
    457 
    458       OutEdgeIt() { }
    459 
    460       OutEdgeIt(Invalid i) : Edge(i) { }
    461 
    462       OutEdgeIt(const Graph& _graph, const Node& node)
    463         : graph(&_graph) {
    464         _graph.firstOut(*this, node);
    465       }
    466 
    467       OutEdgeIt(const Graph& _graph, const Edge& edge)
    468         : Edge(edge), graph(&_graph) {}
    469 
    470       OutEdgeIt& operator++() {
    471         graph->nextOut(*this);
    472         return *this;
    473       }
    474 
    475     };
    476 
    477 
    478     class InEdgeIt : public Edge {
    479       const Graph* graph;
    480     public:
    481 
    482       InEdgeIt() { }
    483 
    484       InEdgeIt(Invalid i) : Edge(i) { }
    485 
    486       InEdgeIt(const Graph& _graph, const Node& node)
    487         : graph(&_graph) {
    488         _graph.firstIn(*this, node);
    489       }
    490 
    491       InEdgeIt(const Graph& _graph, const Edge& edge) :
    492         Edge(edge), graph(&_graph) {}
    493 
    494       InEdgeIt& operator++() {
    495         graph->nextIn(*this);
    496         return *this;
    497       }
    498 
    499     };
    500 
    501 
    502     class UEdgeIt : public Parent::UEdge {
    503       const Graph* graph;
    504     public:
    505 
    506       UEdgeIt() { }
    507 
    508       UEdgeIt(Invalid i) : UEdge(i) { }
    509 
    510       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
    511         _graph.first(static_cast<UEdge&>(*this));
    512       }
    513 
    514       UEdgeIt(const Graph& _graph, const UEdge& e) :
    515         UEdge(e), graph(&_graph) { }
    516 
    517       UEdgeIt& operator++() {
    518         graph->next(*this);
    519         return *this;
    520       }
    521 
    522     };
    523 
    524     class IncEdgeIt : public Parent::UEdge {
    525       friend class UGraphExtender;
    526       const Graph* graph;
    527       bool direction;
    528     public:
    529 
    530       IncEdgeIt() { }
    531 
    532       IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
    533 
    534       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    535         _graph.firstInc(*this, direction, n);
    536       }
    537 
    538       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
    539         : graph(&_graph), UEdge(ue) {
    540         direction = (_graph.source(ue) == n);
    541       }
    542 
    543       IncEdgeIt& operator++() {
    544         graph->nextInc(*this, direction);
    545         return *this;
    546       }
    547     };
    548 
    549     /// \brief Base node of the iterator
    550     ///
    551     /// Returns the base node (ie. the source in this case) of the iterator
    552     Node baseNode(const OutEdgeIt &e) const {
    553       return Parent::source((Edge)e);
    554     }
    555     /// \brief Running node of the iterator
    556     ///
    557     /// Returns the running node (ie. the target in this case) of the
    558     /// iterator
    559     Node runningNode(const OutEdgeIt &e) const {
    560       return Parent::target((Edge)e);
    561     }
    562 
    563     /// \brief Base node of the iterator
    564     ///
    565     /// Returns the base node (ie. the target in this case) of the iterator
    566     Node baseNode(const InEdgeIt &e) const {
    567       return Parent::target((Edge)e);
    568     }
    569     /// \brief Running node of the iterator
    570     ///
    571     /// Returns the running node (ie. the source in this case) of the
    572     /// iterator
    573     Node runningNode(const InEdgeIt &e) const {
    574       return Parent::source((Edge)e);
    575     }
    576 
    577     /// Base node of the iterator
    578     ///
    579     /// Returns the base node of the iterator
    580     Node baseNode(const IncEdgeIt &e) const {
    581       return e.direction ? source(e) : target(e);
    582     }
    583     /// Running node of the iterator
    584     ///
    585     /// Returns the running node of the iterator
    586     Node runningNode(const IncEdgeIt &e) const {
    587       return e.direction ? target(e) : source(e);
    588     }
    589 
    590     // Mappable extension
    591 
    592     template <typename _Value>
    593     class NodeMap
    594       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    595     public:
    596       typedef UGraphExtender Graph;
    597       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    598 
    599       NodeMap(const Graph& graph)
    600         : Parent(graph) {}
    601       NodeMap(const Graph& graph, const _Value& value)
    602         : Parent(graph, value) {}
    603 
    604       NodeMap& operator=(const NodeMap& cmap) {
    605         return operator=<NodeMap>(cmap);
    606       }
    607 
    608       template <typename CMap>
    609       NodeMap& operator=(const CMap& cmap) {
    610         Parent::operator=(cmap);
    611         return *this;
    612       }
    613 
    614     };
    615 
    616     template <typename _Value>
    617     class EdgeMap
    618       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    619     public:
    620       typedef UGraphExtender Graph;
    621       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    622 
    623       EdgeMap(const Graph& graph)
    624         : Parent(graph) {}
    625       EdgeMap(const Graph& graph, const _Value& value)
    626         : Parent(graph, value) {}
    627 
    628       EdgeMap& operator=(const EdgeMap& cmap) {
    629         return operator=<EdgeMap>(cmap);
    630       }
    631 
    632       template <typename CMap>
    633       EdgeMap& operator=(const CMap& cmap) {
    634         Parent::operator=(cmap);
    635         return *this;
    636       }
    637     };
    638 
    639 
    640     template <typename _Value>
    641     class UEdgeMap
    642       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
    643     public:
    644       typedef UGraphExtender Graph;
    645       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
    646 
    647       UEdgeMap(const Graph& graph)
    648         : Parent(graph) {}
    649 
    650       UEdgeMap(const Graph& graph, const _Value& value)
    651         : Parent(graph, value) {}
    652 
    653       UEdgeMap& operator=(const UEdgeMap& cmap) {
    654         return operator=<UEdgeMap>(cmap);
    655       }
    656 
    657       template <typename CMap>
    658       UEdgeMap& operator=(const CMap& cmap) {
    659         Parent::operator=(cmap);
    660         return *this;
    661       }
    662 
    663     };
    664 
    665     // Alteration extension
    666 
    667     Node addNode() {
    668       Node node = Parent::addNode();
    669       getNotifier(Node()).add(node);
    670       return node;
    671     }
    672 
    673     UEdge addEdge(const Node& from, const Node& to) {
    674       UEdge uedge = Parent::addEdge(from, to);
    675       getNotifier(UEdge()).add(uedge);
    676       getNotifier(Edge()).add(Parent::direct(uedge, true));
    677       getNotifier(Edge()).add(Parent::direct(uedge, false));
    678       return uedge;
    679     }
    680    
    681     void clear() {
    682       getNotifier(Edge()).clear();
    683       getNotifier(UEdge()).clear();
    684       getNotifier(Node()).clear();
    685       Parent::clear();
    686     }
    687 
    688     void erase(const Node& node) {
    689       Edge edge;
    690       Parent::firstOut(edge, node);
    691       while (edge != INVALID ) {
    692         erase(edge);
    693         Parent::firstOut(edge, node);
    694       }
    695 
    696       Parent::firstIn(edge, node);
    697       while (edge != INVALID ) {
    698         erase(edge);
    699         Parent::firstIn(edge, node);
    700       }
    701 
    702       getNotifier(Node()).erase(node);
    703       Parent::erase(node);
    704     }
    705 
    706     void erase(const UEdge& uedge) {
    707       getNotifier(Edge()).erase(Parent::direct(uedge, true));
    708       getNotifier(Edge()).erase(Parent::direct(uedge, false));
    709       getNotifier(UEdge()).erase(uedge);
    710       Parent::erase(uedge);
    711     }
    712 
    713     UGraphExtender() {
    714       node_notifier.setContainer(*this);
    715       edge_notifier.setContainer(*this);
    716       uedge_notifier.setContainer(*this);
    717     }
    718 
    719     ~UGraphExtender() {
    720       uedge_notifier.clear();
    721       edge_notifier.clear();
    722       node_notifier.clear();
    723     }
    724 
    725   };
    726 
    727   /// \ingroup graphbits
    728   ///
    729   /// \brief Extender for the BpUGraphs
    730   template <typename Base>
    731   class BpUGraphExtender : public Base {
    732   public:
    733     typedef Base Parent;
    734     typedef BpUGraphExtender Graph;
    735 
    736     typedef typename Parent::Node Node;
    737     typedef typename Parent::UEdge UEdge;
    738 
    739 
    740     using Parent::first;
    741     using Parent::next;
    742 
    743     using Parent::id;
    744 
    745     class ANode : public Node {
    746       friend class BpUGraphExtender;
    747     public:
    748       ANode() {}
    749       ANode(const Node& node) : Node(node) {
    750         LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    751                      typename Parent::NodeSetError());
    752       }
    753       ANode(Invalid) : Node(INVALID) {}
    754     };
    755 
    756     void first(ANode& node) const {
    757       Parent::firstANode(static_cast<Node&>(node));
    758     }
    759     void next(ANode& node) const {
    760       Parent::nextANode(static_cast<Node&>(node));
    761     }
    762 
    763     int id(const ANode& node) const {
    764       return Parent::aNodeId(node);
    765     }
    766 
    767     class BNode : public Node {
    768       friend class BpUGraphExtender;
    769     public:
    770       BNode() {}
    771       BNode(const Node& node) : Node(node) {
    772         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    773                      typename Parent::NodeSetError());
    774       }
    775       BNode(Invalid) : Node(INVALID) {}
    776     };
    777 
    778     void first(BNode& node) const {
    779       Parent::firstBNode(static_cast<Node&>(node));
    780     }
    781     void next(BNode& node) const {
    782       Parent::nextBNode(static_cast<Node&>(node));
    783     }
    784  
    785     int id(const BNode& node) const {
    786       return Parent::aNodeId(node);
    787     }
    788 
    789     Node source(const UEdge& edge) const {
    790       return aNode(edge);
    791     }
    792     Node target(const UEdge& edge) const {
    793       return bNode(edge);
    794     }
    795 
    796     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
    797       if (Parent::aNode(node)) {
    798         Parent::firstFromANode(edge, node);
    799         direction = true;
    800       } else {
    801         Parent::firstFromBNode(edge, node);
    802         direction = static_cast<UEdge&>(edge) == INVALID;
    803       }
    804     }
    805     void nextInc(UEdge& edge, bool& direction) const {
    806       if (direction) {
    807         Parent::nextFromANode(edge);
    808       } else {
    809         Parent::nextFromBNode(edge);
    810         if (edge == INVALID) direction = true;
    811       }
    812     }
    813 
    814     class Edge : public UEdge {
    815       friend class BpUGraphExtender;
    816     protected:
    817       bool forward;
    818 
    819       Edge(const UEdge& edge, bool _forward)
    820         : UEdge(edge), forward(_forward) {}
    821 
    822     public:
    823       Edge() {}
    824       Edge (Invalid) : UEdge(INVALID), forward(true) {}
    825       bool operator==(const Edge& i) const {
    826         return UEdge::operator==(i) && forward == i.forward;
    827       }
    828       bool operator!=(const Edge& i) const {
    829         return UEdge::operator!=(i) || forward != i.forward;
    830       }
    831       bool operator<(const Edge& i) const {
    832         return UEdge::operator<(i) ||
    833           (!(i.forward<forward) && UEdge(*this)<UEdge(i));
    834       }
    835     };
    836 
    837     void first(Edge& edge) const {
    838       Parent::first(static_cast<UEdge&>(edge));
    839       edge.forward = true;
    840     }
    841 
    842     void next(Edge& edge) const {
    843       if (!edge.forward) {
    844         Parent::next(static_cast<UEdge&>(edge));
    845       }
    846       edge.forward = !edge.forward;
    847     }
    848 
    849     void firstOut(Edge& edge, const Node& node) const {
    850       if (Parent::aNode(node)) {
    851         Parent::firstFromANode(edge, node);
    852         edge.forward = true;
    853       } else {
    854         Parent::firstFromBNode(edge, node);
    855         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    856       }
    857     }
    858     void nextOut(Edge& edge) const {
    859       if (edge.forward) {
    860         Parent::nextFromANode(edge);
    861       } else {
    862         Parent::nextFromBNode(edge);
    863         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    864       }
    865     }
    866 
    867     void firstIn(Edge& edge, const Node& node) const {
    868       if (Parent::bNode(node)) {
    869         Parent::firstFromBNode(edge, node);
    870         edge.forward = true;   
    871       } else {
    872         Parent::firstFromANode(edge, node);
    873         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    874       }
    875     }
    876     void nextIn(Edge& edge) const {
    877       if (edge.forward) {
    878         Parent::nextFromBNode(edge);
    879       } else {
    880         Parent::nextFromANode(edge);
    881         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    882       }
    883     }
    884 
    885     Node source(const Edge& edge) const {
    886       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
    887     }
    888     Node target(const Edge& edge) const {
    889       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
    890     }
    891 
    892     int id(const Edge& edge) const {
    893       return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
    894         (edge.forward ? 0 : 1);
    895     }
    896     Edge edgeFromId(int id) const {
    897       return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
    898     }
    899     int maxEdgeId() const {
    900       return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
    901     }
    902 
    903     bool direction(const Edge& edge) const {
    904       return edge.forward;
    905     }
    906 
    907     Edge direct(const UEdge& edge, bool direction) const {
    908       return Edge(edge, direction);
    909     }
    910 
    911     int edgeNum() const {
    912       return 2 * Parent::uEdgeNum();
    913     }
    914 
    915     int uEdgeNum() const {
    916       return Parent::uEdgeNum();
    917     }
    918 
    919     Node oppositeNode(const UEdge& edge, const Node& node) const {
    920       return source(edge) == node ?
    921         target(edge) : source(edge);
    922     }
    923 
    924     Edge direct(const UEdge& edge, const Node& node) const {
    925       return Edge(edge, node == Parent::source(edge));
    926     }
    927 
    928     Edge oppositeEdge(const Edge& edge) const {
    929       return Parent::direct(edge, !Parent::direction(edge));
    930     }
    931 
    932 
    933     int maxId(Node) const {
    934       return Parent::maxNodeId();
    935     }
    936     int maxId(BNode) const {
    937       return Parent::maxBNodeId();
    938     }
    939     int maxId(ANode) const {
    940       return Parent::maxANodeId();
    941     }
    942     int maxId(Edge) const {
    943       return maxEdgeId();
    944     }
    945     int maxId(UEdge) const {
    946       return Parent::maxUEdgeId();
    947     }
    948 
    949 
    950     Node fromId(int id, Node) const {
    951       return Parent::nodeFromId(id);
    952     }
    953     ANode fromId(int id, ANode) const {
    954       return Parent::fromANodeId(id);
    955     }
    956     BNode fromId(int id, BNode) const {
    957       return Parent::fromBNodeId(id);
    958     }
    959     Edge fromId(int id, Edge) const {
    960       return Parent::edgeFromId(id);
    961     }
    962     UEdge fromId(int id, UEdge) const {
    963       return Parent::uEdgeFromId(id);
    964     } 
    965  
    966     typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
    967     typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
    968     typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
    969     typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
    970     typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
    971 
    972   protected:
    973 
    974     mutable ANodeNotifier anode_notifier;
    975     mutable BNodeNotifier bnode_notifier;
    976     mutable NodeNotifier node_notifier;
    977     mutable EdgeNotifier edge_notifier;
    978     mutable UEdgeNotifier uedge_notifier;
    979 
    980   public:
    981 
    982     NodeNotifier& getNotifier(Node) const {
    983       return node_notifier;
    984     }
    985 
    986     ANodeNotifier& getNotifier(ANode) const {
    987       return anode_notifier;
    988     }
    989 
    990     BNodeNotifier& getNotifier(BNode) const {
    991       return bnode_notifier;
    992     }
    993 
    994     EdgeNotifier& getNotifier(Edge) const {
    995       return edge_notifier;
    996     }
    997 
    998     UEdgeNotifier& getNotifier(UEdge) const {
    999       return uedge_notifier;
    1000     }
    1001 
    1002     class NodeIt : public Node {
    1003       const Graph* graph;
    1004     public:
    1005    
    1006       NodeIt() { }
    1007    
    1008       NodeIt(Invalid i) : Node(INVALID) { }
    1009    
    1010       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    1011         graph->first(static_cast<Node&>(*this));
    1012       }
    1013 
    1014       NodeIt(const Graph& _graph, const Node& node)
    1015         : Node(node), graph(&_graph) { }
    1016    
    1017       NodeIt& operator++() {
    1018         graph->next(*this);
    1019         return *this;
    1020       }
    1021 
    1022     };
    1023 
    1024     class ANodeIt : public Node {
    1025       friend class BpUGraphExtender;
    1026       const Graph* graph;
    1027     public:
    1028    
    1029       ANodeIt() { }
    1030    
    1031       ANodeIt(Invalid i) : Node(INVALID) { }
    1032    
    1033       explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
    1034         graph->firstANode(static_cast<Node&>(*this));
    1035       }
    1036 
    1037       ANodeIt(const Graph& _graph, const Node& node)
    1038         : Node(node), graph(&_graph) {}
    1039    
    1040       ANodeIt& operator++() {
    1041         graph->nextANode(*this);
    1042         return *this;
    1043       }
    1044     };
    1045 
    1046     class BNodeIt : public Node {
    1047       friend class BpUGraphExtender;
    1048       const Graph* graph;
    1049     public:
    1050    
    1051       BNodeIt() { }
    1052    
    1053       BNodeIt(Invalid i) : Node(INVALID) { }
    1054    
    1055       explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
    1056         graph->firstBNode(static_cast<Node&>(*this));
    1057       }
    1058 
    1059       BNodeIt(const Graph& _graph, const Node& node)
    1060         : Node(node), graph(&_graph) {}
    1061    
    1062       BNodeIt& operator++() {
    1063         graph->nextBNode(*this);
    1064         return *this;
    1065       }
    1066     };
    1067 
    1068     class EdgeIt : public Edge {
    1069       friend class BpUGraphExtender;
    1070       const Graph* graph;
    1071     public:
    1072    
    1073       EdgeIt() { }
    1074    
    1075       EdgeIt(Invalid i) : Edge(INVALID) { }
    1076    
    1077       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    1078         graph->first(static_cast<Edge&>(*this));
    1079       }
    1080 
    1081       EdgeIt(const Graph& _graph, const Edge& edge)
    1082         : Edge(edge), graph(&_graph) { }
    1083    
    1084       EdgeIt& operator++() {
    1085         graph->next(*this);
    1086         return *this;
    1087       }
    1088 
    1089     };
    1090 
    1091     class UEdgeIt : public UEdge {
    1092       friend class BpUGraphExtender;
    1093       const Graph* graph;
    1094     public:
    1095    
    1096       UEdgeIt() { }
    1097    
    1098       UEdgeIt(Invalid i) : UEdge(INVALID) { }
    1099    
    1100       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
    1101         graph->first(static_cast<UEdge&>(*this));
    1102       }
    1103 
    1104       UEdgeIt(const Graph& _graph, const UEdge& edge)
    1105         : UEdge(edge), graph(&_graph) { }
    1106    
    1107       UEdgeIt& operator++() {
    1108         graph->next(*this);
    1109         return *this;
    1110       }
    1111     };
    1112 
    1113     class OutEdgeIt : public Edge {
    1114       friend class BpUGraphExtender;
    1115       const Graph* graph;
    1116     public:
    1117    
    1118       OutEdgeIt() { }
    1119    
    1120       OutEdgeIt(Invalid i) : Edge(i) { }
    1121    
    1122       OutEdgeIt(const Graph& _graph, const Node& node)
    1123         : graph(&_graph) {
    1124         graph->firstOut(*this, node);
    1125       }
    1126    
    1127       OutEdgeIt(const Graph& _graph, const Edge& edge)
    1128         : Edge(edge), graph(&_graph) {}
    1129    
    1130       OutEdgeIt& operator++() {
    1131         graph->nextOut(*this);
    1132         return *this;
    1133       }
    1134 
    1135     };
    1136 
    1137 
    1138     class InEdgeIt : public Edge {
    1139       friend class BpUGraphExtender;
    1140       const Graph* graph;
    1141     public:
    1142    
    1143       InEdgeIt() { }
    1144    
    1145       InEdgeIt(Invalid i) : Edge(i) { }
    1146    
    1147       InEdgeIt(const Graph& _graph, const Node& node)
    1148         : graph(&_graph) {
    1149         graph->firstIn(*this, node);
    1150       }
    1151    
    1152       InEdgeIt(const Graph& _graph, const Edge& edge) :
    1153         Edge(edge), graph(&_graph) {}
    1154    
    1155       InEdgeIt& operator++() {
    1156         graph->nextIn(*this);
    1157         return *this;
    1158       }
    1159 
    1160     };
    1161  
    1162     /// \brief Base node of the iterator
    1163     ///
    1164     /// Returns the base node (ie. the source in this case) of the iterator
    1165     Node baseNode(const OutEdgeIt &e) const {
    1166       return Parent::source((Edge&)e);
    1167     }
    1168     /// \brief Running node of the iterator
    1169     ///
    1170     /// Returns the running node (ie. the target in this case) of the
    1171     /// iterator
    1172     Node runningNode(const OutEdgeIt &e) const {
    1173       return Parent::target((Edge&)e);
    1174     }
    1175  
    1176     /// \brief Base node of the iterator
    1177     ///
    1178     /// Returns the base node (ie. the target in this case) of the iterator
    1179     Node baseNode(const InEdgeIt &e) const {
    1180       return Parent::target((Edge&)e);
    1181     }
    1182     /// \brief Running node of the iterator
    1183     ///
    1184     /// Returns the running node (ie. the source in this case) of the
    1185     /// iterator
    1186     Node runningNode(const InEdgeIt &e) const {
    1187       return Parent::source((Edge&)e);
    1188     }
    1189  
    1190     class IncEdgeIt : public Parent::UEdge {
    1191       friend class BpUGraphExtender;
    1192       const Graph* graph;
    1193       bool direction;
    1194     public:
    1195    
    1196       IncEdgeIt() { }
    1197    
    1198       IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
    1199    
    1200       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    1201         graph->firstInc(*this, direction, n);
    1202       }
    1203 
    1204       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
    1205         : graph(&_graph), UEdge(ue) {
    1206         direction = (graph->source(ue) == n);
    1207       }
    1208 
    1209       IncEdgeIt& operator++() {
    1210         graph->nextInc(*this, direction);
    1211         return *this;
    1212       }
    1213     };
    1214  
    1215 
    1216     /// Base node of the iterator
    1217     ///
    1218     /// Returns the base node of the iterator
    1219     Node baseNode(const IncEdgeIt &e) const {
    1220       return e.direction ? source(e) : target(e);
    1221     }
    1222 
    1223     /// Running node of the iterator
    1224     ///
    1225     /// Returns the running node of the iterator
    1226     Node runningNode(const IncEdgeIt &e) const {
    1227       return e.direction ? target(e) : source(e);
    1228     }
    1229 
    1230     template <typename _Value>
    1231     class ANodeMap
    1232       : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
    1233     public:
    1234       typedef BpUGraphExtender Graph;
    1235       typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
    1236    
    1237       ANodeMap(const Graph& graph)
    1238         : Parent(graph) {}
    1239       ANodeMap(const Graph& graph, const _Value& value)
    1240         : Parent(graph, value) {}
    1241    
    1242       ANodeMap& operator=(const ANodeMap& cmap) {
    1243         return operator=<ANodeMap>(cmap);
    1244       }
    1245    
    1246       template <typename CMap>
    1247       ANodeMap& operator=(const CMap& cmap) {
    1248         Parent::operator=(cmap);
    1249         return *this;
    1250       }
    1251    
    1252     };
    1253 
    1254     template <typename _Value>
    1255     class BNodeMap
    1256       : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
    1257     public:
    1258       typedef BpUGraphExtender Graph;
    1259       typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
    1260    
    1261       BNodeMap(const Graph& graph)
    1262         : Parent(graph) {}
    1263       BNodeMap(const Graph& graph, const _Value& value)
    1264         : Parent(graph, value) {}
    1265    
    1266       BNodeMap& operator=(const BNodeMap& cmap) {
    1267         return operator=<BNodeMap>(cmap);
    1268       }
    1269    
    1270       template <typename CMap>
    1271       BNodeMap& operator=(const CMap& cmap) {
    1272         Parent::operator=(cmap);
    1273         return *this;
    1274       }
    1275    
    1276     };
    1277 
    1278   public:
    1279 
    1280     template <typename _Value>
    1281     class NodeMap {
    1282     public:
    1283       typedef BpUGraphExtender Graph;
    1284 
    1285       typedef Node Key;
    1286       typedef _Value Value;
    1287 
    1288       /// The reference type of the map;
    1289       typedef typename ANodeMap<_Value>::Reference Reference;
    1290       /// The const reference type of the map;
    1291       typedef typename ANodeMap<_Value>::ConstReference ConstReference;
    1292 
    1293       typedef True ReferenceMapTag;
    1294 
    1295       NodeMap(const Graph& _graph)
    1296         : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
    1297       NodeMap(const Graph& _graph, const _Value& _value)
    1298         : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
    1299 
    1300       NodeMap& operator=(const NodeMap& cmap) {
    1301         return operator=<NodeMap>(cmap);
    1302       }
    1303    
    1304       template <typename CMap>
    1305       NodeMap& operator=(const CMap& cmap) {
    1306         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    1307         const typename Parent::Notifier* notifier = Parent::getNotifier();
    1308         Edge it;
    1309         for (graph.first(it); it != INVALID; graph.next(it)) {
    1310           Parent::set(it, cmap[it]);
    1311         }
    1312         return *this;
    1313       }
    1314 
    1315       ConstReference operator[](const Key& node) const {
    1316         if (Parent::aNode(node)) {
    1317           return aNodeMap[node];
    1318         } else {
    1319           return bNodeMap[node];
    1320         }
    1321       }
    1322 
    1323       Reference operator[](const Key& node) {
    1324         if (Parent::aNode(node)) {
    1325           return aNodeMap[node];
    1326         } else {
    1327           return bNodeMap[node];
    1328         }
    1329       }
    1330 
    1331       void set(const Key& node, const Value& value) {
    1332         if (Parent::aNode(node)) {
    1333           aNodeMap.set(node, value);
    1334         } else {
    1335           bNodeMap.set(node, value);
    1336         }
    1337       }
    1338 
    1339       class MapIt : public NodeIt {
    1340       public:
    1341 
    1342         typedef NodeIt Parent;
    1343        
    1344         explicit MapIt(NodeMap& _map)
    1345           : Parent(_map.graph), map(_map) {}
    1346        
    1347         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
    1348           return map[*this];
    1349         }
    1350        
    1351         typename MapTraits<NodeMap>::ReturnValue operator*() {
    1352           return map[*this];
    1353         }
    1354        
    1355         void set(const Value& value) {
    1356           map.set(*this, value);
    1357         }
    1358 
    1359       private:
    1360         NodeMap& map;
    1361       };
    1362 
    1363       class ConstMapIt : public NodeIt {
    1364       public:
    1365 
    1366         typedef NodeIt Parent;
    1367        
    1368         explicit ConstMapIt(const NodeMap& _map)
    1369           : Parent(_map.graph), map(_map) {}
    1370        
    1371         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
    1372           return map[*this];
    1373         }
    1374        
    1375       private:
    1376         const NodeMap& map;
    1377       };
    1378 
    1379       class ItemIt : public NodeIt {
    1380       public:
    1381 
    1382         typedef NodeIt Parent;
    1383 
    1384         explicit ItemIt(const NodeMap& _map)
    1385           : Parent(_map.graph) {}
    1386        
    1387       };
    1388      
    1389     private:
    1390       const Graph& graph;
    1391       ANodeMap<_Value> aNodeMap;
    1392       BNodeMap<_Value> bNodeMap;
    1393     };
    1394    
    1395 
    1396     template <typename _Value>
    1397     class EdgeMap
    1398       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    1399     public:
    1400       typedef BpUGraphExtender Graph;
    1401       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    1402    
    1403       EdgeMap(const Graph& graph)
    1404         : Parent(graph) {}
    1405       EdgeMap(const Graph& graph, const _Value& value)
    1406         : Parent(graph, value) {}
    1407    
    1408       EdgeMap& operator=(const EdgeMap& cmap) {
    1409         return operator=<EdgeMap>(cmap);
    1410       }
    1411    
    1412       template <typename CMap>
    1413       EdgeMap& operator=(const CMap& cmap) {
    1414         Parent::operator=(cmap);
    1415         return *this;
    1416       }
    1417     };
    1418 
    1419     template <typename _Value>
    1420     class UEdgeMap
    1421       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
    1422     public:
    1423       typedef BpUGraphExtender Graph;
    1424       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
    1425    
    1426       UEdgeMap(const Graph& graph)
    1427         : Parent(graph) {}
    1428       UEdgeMap(const Graph& graph, const _Value& value)
    1429         : Parent(graph, value) {}
    1430    
    1431       UEdgeMap& operator=(const UEdgeMap& cmap) {
    1432         return operator=<UEdgeMap>(cmap);
    1433       }
    1434    
    1435       template <typename CMap>
    1436       UEdgeMap& operator=(const CMap& cmap) {
    1437         Parent::operator=(cmap);
    1438         return *this;
    1439       }
    1440     };
    1441 
    1442  
    1443     Node addANode() {
    1444       Node node = Parent::addANode();
    1445       getNotifier(ANode()).add(node);
    1446       getNotifier(Node()).add(node);
    1447       return node;
    1448     }
    1449 
    1450     Node addBNode() {
    1451       Node node = Parent::addBNode();
    1452       getNotifier(BNode()).add(node);
    1453       getNotifier(Node()).add(node);
    1454       return node;
    1455     }
    1456  
    1457     UEdge addEdge(const Node& source, const Node& target) {
    1458       UEdge uedge = Parent::addEdge(source, target);
    1459       getNotifier(UEdge()).add(uedge);
    1460    
    1461       std::vector<Edge> edges;
    1462       edges.push_back(direct(uedge, true));
    1463       edges.push_back(direct(uedge, false));
    1464       getNotifier(Edge()).add(edges);
    1465    
    1466       return uedge;
    1467     }
    1468 
    1469     void clear() {
    1470       getNotifier(Edge()).clear();
    1471       getNotifier(UEdge()).clear();
    1472       getNotifier(Node()).clear();
    1473       getNotifier(BNode()).clear();
    1474       getNotifier(ANode()).clear();
    1475       Parent::clear();
    1476     }
    1477 
    1478     void erase(const Node& node) {
    1479       UEdge uedge;
    1480       if (Parent::aNode(node)) {
    1481         Parent::firstFromANode(uedge, node);
    1482         while (uedge != INVALID) {
    1483           erase(uedge);
    1484           Parent::firstFromANode(uedge, node);
    1485         }
    1486       } else {
    1487         Parent::firstFromBNode(uedge, node);
    1488         while (uedge != INVALID) {
    1489           erase(uedge);
    1490           Parent::firstFromBNode(uedge, node);
    1491         }
    1492       }
    1493 
    1494       getNotifier(Node()).erase(node);
    1495       Parent::erase(node);
    1496     }
    1497    
    1498     void erase(const UEdge& uedge) {
    1499       std::vector<Edge> edges;
    1500       edges.push_back(direct(uedge, true));
    1501       edges.push_back(direct(uedge, false));
    1502       getNotifier(Edge()).erase(edges);
    1503       getNotifier(UEdge()).erase(uedge);
    1504       Parent::erase(uedge);
    1505     }
    1506 
    1507 
    1508     BpUGraphExtender() {
    1509       anode_notifier.setContainer(*this);
    1510       bnode_notifier.setContainer(*this);
    1511       node_notifier.setContainer(*this);
    1512       edge_notifier.setContainer(*this);
    1513       uedge_notifier.setContainer(*this);
    1514     }
    1515 
    1516     ~BpUGraphExtender() {
    1517       uedge_notifier.clear();
    1518       edge_notifier.clear();
    1519       node_notifier.clear();
    1520       anode_notifier.clear();
    1521       bnode_notifier.clear();
    1522     }
    1523 
    1524 
    1525   };
    1526 
    1527317}
    1528318
  • lemon/edge_set.h

    r2111 r2115  
    2323#include <lemon/bits/default_map.h>
    2424#include <lemon/bits/edge_set_extender.h>
     25#include <lemon/bits/base_extender.h>
    2526
    2627/// \ingroup graphs
  • lemon/full_graph.h

    r2111 r2115  
    2222#include <cmath>
    2323
    24 #include <lemon/bits/base_extender.h>
    2524#include <lemon/bits/graph_extender.h>
    2625
     
    3130///\ingroup graphs
    3231///\file
    33 ///\brief FullGraph and FullUGraph classes.
     32///\brief FullGraph class.
    3433
    3534
     
    248247  };
    249248
    250 
    251   /// \brief Base of the FullUGrpah.
    252   ///
    253   /// Base of the FullUGrpah.
    254   class FullUGraphBase {
    255     int _nodeNum;
    256     int _edgeNum;
    257   public:
    258 
    259     typedef FullUGraphBase Graph;
    260 
    261     class Node;
    262     class Edge;
    263 
    264   public:
    265 
    266     FullUGraphBase() {}
    267 
    268 
    269     ///Creates a full graph with \c n nodes.
    270     void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
    271 
    272     /// \brief Returns the node with the given index.
    273     ///
    274     /// Returns the node with the given index. Because it is a
    275     /// static size graph the node's of the graph can be indiced
    276     /// by the range from 0 to \e nodeNum()-1 and the index of
    277     /// the node can accessed by the \e index() member.
    278     Node operator()(int index) const { return Node(index); }
    279 
    280     /// \brief Returns the index of the node.
    281     ///
    282     /// Returns the index of the node. Because it is a
    283     /// static size graph the node's of the graph can be indiced
    284     /// by the range from 0 to \e nodeNum()-1 and the index of
    285     /// the node can accessed by the \e index() member.
    286     int index(const Node& node) const { return node.id; }
    287 
    288     typedef True NodeNumTag;
    289     typedef True EdgeNumTag;
    290 
    291     ///Number of nodes.
    292     int nodeNum() const { return _nodeNum; }
    293     ///Number of edges.
    294     int edgeNum() const { return _edgeNum; }
    295 
    296     /// Maximum node ID.
    297    
    298     /// Maximum node ID.
    299     ///\sa id(Node)
    300     int maxNodeId() const { return _nodeNum-1; }
    301     /// Maximum edge ID.
    302    
    303     /// Maximum edge ID.
    304     ///\sa id(Edge)
    305     int maxEdgeId() const { return _edgeNum-1; }
    306 
    307     /// \brief Returns the node from its \c id.
    308     ///
    309     /// Returns the node from its \c id. If there is not node
    310     /// with the given id the effect of the function is undefinied.
    311     static Node nodeFromId(int id) { return Node(id);}
    312 
    313     /// \brief Returns the edge from its \c id.
    314     ///
    315     /// Returns the edge from its \c id. If there is not edge
    316     /// with the given id the effect of the function is undefinied.
    317     static Edge edgeFromId(int id) { return Edge(id);}
    318 
    319     Node source(Edge e) const {
    320       /// \todo we may do it faster
    321       return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
    322     }
    323 
    324     Node target(Edge e) const {
    325       int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    326       return Node(e.id - (source) * (source - 1) / 2);
    327     }
    328 
    329 
    330     /// \brief Node ID.
    331     ///
    332     /// The ID of a valid Node is a nonnegative integer not greater than
    333     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    334     /// and the greatest node ID can be actually less then \ref maxNodeId().
    335     ///
    336     /// The ID of the \ref INVALID node is -1.
    337     /// \return The ID of the node \c v.
    338 
    339     static int id(Node v) { return v.id; }
    340 
    341     /// \brief Edge ID.
    342     ///
    343     /// The ID of a valid Edge is a nonnegative integer not greater than
    344     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    345     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    346     ///
    347     /// The ID of the \ref INVALID edge is -1.
    348     ///\return The ID of the edge \c e.
    349     static int id(Edge e) { return e.id; }
    350 
    351     /// \brief Finds an edge between two nodes.
    352     ///
    353     /// Finds an edge from node \c u to node \c v.
    354     ///
    355     /// If \c prev is \ref INVALID (this is the default value), then
    356     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    357     /// the next edge from \c u to \c v after \c prev.
    358     /// \return The found edge or INVALID if there is no such an edge.
    359     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
    360       if (prev.id != -1 || u.id <= v.id) return Edge(-1);
    361       return Edge(u.id * (u.id - 1) / 2 + v.id);
    362     }
    363 
    364     typedef True FindEdgeTag;
    365    
    366      
    367     class Node {
    368       friend class FullUGraphBase;
    369 
    370     protected:
    371       int id;
    372       Node(int _id) { id = _id;}
    373     public:
    374       Node() {}
    375       Node (Invalid) { id = -1; }
    376       bool operator==(const Node node) const {return id == node.id;}
    377       bool operator!=(const Node node) const {return id != node.id;}
    378       bool operator<(const Node node) const {return id < node.id;}
    379     };
    380    
    381 
    382 
    383     class Edge {
    384       friend class FullUGraphBase;
    385      
    386     protected:
    387       int id;  // _nodeNum * target + source;
    388 
    389       Edge(int _id) : id(_id) {}
    390 
    391     public:
    392       Edge() { }
    393       Edge (Invalid) { id = -1; }
    394       bool operator==(const Edge edge) const {return id == edge.id;}
    395       bool operator!=(const Edge edge) const {return id != edge.id;}
    396       bool operator<(const Edge edge) const {return id < edge.id;}
    397     };
    398 
    399     void first(Node& node) const {
    400       node.id = _nodeNum - 1;
    401     }
    402 
    403     static void next(Node& node) {
    404       --node.id;
    405     }
    406 
    407     void first(Edge& edge) const {
    408       edge.id = _edgeNum - 1;
    409     }
    410 
    411     static void next(Edge& edge) {
    412       --edge.id;
    413     }
    414 
    415     void firstOut(Edge& edge, const Node& node) const {     
    416       int src = node.id;
    417       int trg = 0;
    418       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    419     }
    420 
    421     /// \todo with specialized iterators we can make faster iterating
    422     void nextOut(Edge& edge) const {
    423       int src = source(edge).id;
    424       int trg = target(edge).id;
    425       ++trg;
    426       edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
    427     }
    428 
    429     void firstIn(Edge& edge, const Node& node) const {
    430       int src = node.id + 1;
    431       int trg = node.id;
    432       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    433     }
    434    
    435     void nextIn(Edge& edge) const {
    436       int src = source(edge).id;
    437       int trg = target(edge).id;
    438       ++src;
    439       edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
    440     }
    441 
    442   };
    443 
    444   typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
    445   ExtendedFullUGraphBase;
    446 
    447   /// \ingroup graphs
    448   ///
    449   /// \brief An undirected full graph class.
    450   ///
    451   /// This is a simple and fast undirected full graph implementation.
    452   /// It is completely static, so you can neither add nor delete either
    453   /// edges or nodes.
    454   ///
    455   /// The main difference beetween the \e FullGraph and \e FullUGraph class
    456   /// is that this class conforms to the undirected graph concept and
    457   /// it does not contain the loop edges.
    458   ///
    459   /// \sa FullUGraphBase
    460   /// \sa FullGraph
    461   ///
    462   /// \author Balazs Dezso
    463   class FullUGraph : public ExtendedFullUGraphBase {
    464   public:
    465 
    466     typedef ExtendedFullUGraphBase Parent;
    467 
    468     /// \brief Constructor
    469     FullUGraph() { construct(0); }
    470 
    471     /// \brief Constructor
    472     FullUGraph(int n) { construct(n); }
    473 
    474     /// \brief Resize the graph
    475     ///
    476     /// Resize the graph. The function will fully destroy and build the graph.
    477     /// This cause that the maps of the graph will reallocated
    478     /// automatically and the previous values will be lost.
    479     void resize(int n) {
    480       Parent::getNotifier(Edge()).clear();
    481       Parent::getNotifier(UEdge()).clear();
    482       Parent::getNotifier(Node()).clear();
    483       construct(n);
    484       Parent::getNotifier(Node()).build();
    485       Parent::getNotifier(UEdge()).build();
    486       Parent::getNotifier(Edge()).build();
    487     }
    488   };
    489 
    490 
    491   class FullBpUGraphBase {
    492   protected:
    493 
    494     int _aNodeNum;
    495     int _bNodeNum;
    496 
    497     int _edgeNum;
    498 
    499   public:
    500 
    501     class NodeSetError : public LogicError {
    502       virtual const char* exceptionName() const {
    503         return "lemon::FullBpUGraph::NodeSetError";
    504       }
    505     };
    506  
    507     class Node {
    508       friend class FullBpUGraphBase;
    509     protected:
    510       int id;
    511 
    512       Node(int _id) : id(_id) {}
    513     public:
    514       Node() {}
    515       Node(Invalid) { id = -1; }
    516       bool operator==(const Node i) const {return id==i.id;}
    517       bool operator!=(const Node i) const {return id!=i.id;}
    518       bool operator<(const Node i) const {return id<i.id;}
    519     };
    520 
    521     class UEdge {
    522       friend class FullBpUGraphBase;
    523     protected:
    524       int id;
    525 
    526       UEdge(int _id) { id = _id;}
    527     public:
    528       UEdge() {}
    529       UEdge (Invalid) { id = -1; }
    530       bool operator==(const UEdge i) const {return id==i.id;}
    531       bool operator!=(const UEdge i) const {return id!=i.id;}
    532       bool operator<(const UEdge i) const {return id<i.id;}
    533     };
    534 
    535     void construct(int aNodeNum, int bNodeNum) {
    536       _aNodeNum = aNodeNum;
    537       _bNodeNum = bNodeNum;
    538       _edgeNum = aNodeNum * bNodeNum;
    539     }
    540 
    541     void firstANode(Node& node) const {
    542       node.id = 2 * _aNodeNum - 2;
    543       if (node.id < 0) node.id = -1;
    544     }
    545     void nextANode(Node& node) const {
    546       node.id -= 2;
    547       if (node.id < 0) node.id = -1;
    548     }
    549 
    550     void firstBNode(Node& node) const {
    551       node.id = 2 * _bNodeNum - 1;
    552     }
    553     void nextBNode(Node& node) const {
    554       node.id -= 2;
    555     }
    556 
    557     void first(Node& node) const {
    558       if (_aNodeNum > 0) {
    559         node.id = 2 * _aNodeNum - 2;
    560       } else {
    561         node.id = 2 * _bNodeNum - 1;
    562       }
    563     }
    564     void next(Node& node) const {
    565       node.id -= 2;
    566       if (node.id == -2) {
    567         node.id = 2 * _bNodeNum - 1;
    568       }
    569     }
    570  
    571     void first(UEdge& edge) const {
    572       edge.id = _edgeNum - 1;
    573     }
    574     void next(UEdge& edge) const {
    575       --edge.id;
    576     }
    577 
    578     void firstFromANode(UEdge& edge, const Node& node) const {
    579       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    580       edge.id = (node.id >> 1) * _bNodeNum;
    581     }
    582     void nextFromANode(UEdge& edge) const {
    583       ++(edge.id);
    584       if (edge.id % _bNodeNum == 0) edge.id = -1;
    585     }
    586 
    587     void firstFromBNode(UEdge& edge, const Node& node) const {
    588       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    589       edge.id = (node.id >> 1);
    590     }
    591     void nextFromBNode(UEdge& edge) const {
    592       edge.id += _bNodeNum;
    593       if (edge.id >= _edgeNum) edge.id = -1;
    594     }
    595 
    596     static int id(const Node& node) {
    597       return node.id;
    598     }
    599     static Node nodeFromId(int id) {
    600       return Node(id);
    601     }
    602     int maxNodeId() const {
    603       return _aNodeNum > _bNodeNum ?
    604         _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
    605     }
    606  
    607     static int id(const UEdge& edge) {
    608       return edge.id;
    609     }
    610     static UEdge uEdgeFromId(int id) {
    611       return UEdge(id);
    612     }
    613     int maxUEdgeId() const {
    614       return _edgeNum - 1;
    615     }
    616  
    617     static int aNodeId(const Node& node) {
    618       return node.id >> 1;
    619     }
    620     static Node fromANodeId(int id) {
    621       return Node(id << 1);
    622     }
    623     int maxANodeId() const {
    624       return _aNodeNum;
    625     }
    626 
    627     static int bNodeId(const Node& node) {
    628       return node.id >> 1;
    629     }
    630     static Node fromBNodeId(int id) {
    631       return Node((id << 1) + 1);
    632     }
    633     int maxBNodeId() const {
    634       return _bNodeNum;
    635     }
    636 
    637     Node aNode(const UEdge& edge) const {
    638       return Node((edge.id / _bNodeNum) << 1);
    639     }
    640     Node bNode(const UEdge& edge) const {
    641       return Node(((edge.id % _bNodeNum) << 1) + 1);
    642     }
    643 
    644     static bool aNode(const Node& node) {
    645       return (node.id & 1) == 0;
    646     }
    647 
    648     static bool bNode(const Node& node) {
    649       return (node.id & 1) == 1;
    650     }
    651 
    652     static Node aNode(int index) {
    653       return Node(index << 1);
    654     }
    655 
    656     static Node bNode(int index) {
    657       return Node((index << 1) + 1);
    658     }
    659 
    660     typedef True NodeNumTag;
    661     int nodeNum() const { return _aNodeNum + _bNodeNum; }
    662     int aNodeNum() const { return _aNodeNum; }
    663     int bNodeNum() const { return _bNodeNum; }
    664 
    665     typedef True EdgeNumTag;
    666     int uEdgeNum() const { return _edgeNum; }
    667 
    668   };
    669 
    670 
    671   typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
    672 
    673 
    674   /// \ingroup graphs
    675   ///
    676   /// \brief An undirected full bipartite graph class.
    677   ///
    678   /// This is a simple and fast bipartite undirected full graph implementation.
    679   /// It is completely static, so you can neither add nor delete either
    680   /// edges or nodes.
    681   ///
    682   /// \sa FullUGraphBase
    683   /// \sa FullGraph
    684   ///
    685   /// \author Balazs Dezso
    686   class FullBpUGraph :
    687     public ExtendedFullBpUGraphBase {
    688   public:
    689 
    690     typedef ExtendedFullBpUGraphBase Parent;
    691 
    692     FullBpUGraph() {
    693       Parent::construct(0, 0);
    694     }
    695 
    696     FullBpUGraph(int aNodeNum, int bNodeNum) {
    697       Parent::construct(aNodeNum, bNodeNum);
    698     }
    699 
    700     /// \brief Resize the graph
    701     ///
    702     void resize(int n, int m) {
    703       Parent::getNotifier(Edge()).clear();
    704       Parent::getNotifier(UEdge()).clear();
    705       Parent::getNotifier(Node()).clear();
    706       Parent::getNotifier(ANode()).clear();
    707       Parent::getNotifier(BNode()).clear();
    708       construct(n, m);
    709       Parent::getNotifier(ANode()).build();
    710       Parent::getNotifier(BNode()).build();
    711       Parent::getNotifier(Node()).build();
    712       Parent::getNotifier(UEdge()).build();
    713       Parent::getNotifier(Edge()).build();
    714     }
    715   };
    716 
    717249} //namespace lemon
    718250
  • lemon/grid_ugraph.h

    r2076 r2115  
    2525
    2626#include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
     27#include <lemon/bits/ugraph_extender.h>
    2828
    2929#include <lemon/xy.h>
  • lemon/list_bpugraph.h

    r2114 r2115  
    1717 */
    1818
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
     19#ifndef LEMON_LIST_BPUGRAPH_H
     20#define LEMON_LIST_BPUGRAPH_H
    2121
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
     24///\brief ListBpUGraph classes.
     25
     26#include <lemon/bits/bpugraph_extender.h>
    2827
    2928#include <lemon/error.h>
     
    3332
    3433namespace lemon {
    35 
    36   class ListGraphBase {
    37 
    38   protected:
    39     struct NodeT {
    40       int first_in, first_out;
    41       int prev, next;
    42     };
    43  
    44     struct EdgeT {
    45       int target, source;
    46       int prev_in, prev_out;
    47       int next_in, next_out;
    48     };
    49 
    50     std::vector<NodeT> nodes;
    51 
    52     int first_node;
    53 
    54     int first_free_node;
    55 
    56     std::vector<EdgeT> edges;
    57 
    58     int first_free_edge;
    59    
    60   public:
    61    
    62     typedef ListGraphBase Graph;
    63    
    64     class Node {
    65       friend class ListGraphBase;
    66     protected:
    67 
    68       int id;
    69       explicit Node(int pid) { id = pid;}
    70 
    71     public:
    72       Node() {}
    73       Node (Invalid) { id = -1; }
    74       bool operator==(const Node& node) const {return id == node.id;}
    75       bool operator!=(const Node& node) const {return id != node.id;}
    76       bool operator<(const Node& node) const {return id < node.id;}
    77     };
    78 
    79     class Edge {
    80       friend class ListGraphBase;
    81     protected:
    82 
    83       int id;
    84       explicit Edge(int pid) { id = pid;}
    85 
    86     public:
    87       Edge() {}
    88       Edge (Invalid) { id = -1; }
    89       bool operator==(const Edge& edge) const {return id == edge.id;}
    90       bool operator!=(const Edge& edge) const {return id != edge.id;}
    91       bool operator<(const Edge& edge) const {return id < edge.id;}
    92     };
    93 
    94 
    95 
    96     ListGraphBase()
    97       : nodes(), first_node(-1),
    98         first_free_node(-1), edges(), first_free_edge(-1) {}
    99 
    100    
    101     /// Maximum node ID.
    102    
    103     /// Maximum node ID.
    104     ///\sa id(Node)
    105     int maxNodeId() const { return nodes.size()-1; }
    106 
    107     /// Maximum edge ID.
    108    
    109     /// Maximum edge ID.
    110     ///\sa id(Edge)
    111     int maxEdgeId() const { return edges.size()-1; }
    112 
    113     Node source(Edge e) const { return Node(edges[e.id].source); }
    114     Node target(Edge e) const { return Node(edges[e.id].target); }
    115 
    116 
    117     void first(Node& node) const {
    118       node.id = first_node;
    119     }
    120 
    121     void next(Node& node) const {
    122       node.id = nodes[node.id].next;
    123     }
    124 
    125 
    126     void first(Edge& e) const {
    127       int n;
    128       for(n = first_node;
    129           n!=-1 && nodes[n].first_in == -1;
    130           n = nodes[n].next);
    131       e.id = (n == -1) ? -1 : nodes[n].first_in;
    132     }
    133 
    134     void next(Edge& edge) const {
    135       if (edges[edge.id].next_in != -1) {
    136         edge.id = edges[edge.id].next_in;
    137       } else {
    138         int n;
    139         for(n = nodes[edges[edge.id].target].next;
    140           n!=-1 && nodes[n].first_in == -1;
    141           n = nodes[n].next);
    142         edge.id = (n == -1) ? -1 : nodes[n].first_in;
    143       }     
    144     }
    145 
    146     void firstOut(Edge &e, const Node& v) const {
    147       e.id = nodes[v.id].first_out;
    148     }
    149     void nextOut(Edge &e) const {
    150       e.id=edges[e.id].next_out;
    151     }
    152 
    153     void firstIn(Edge &e, const Node& v) const {
    154       e.id = nodes[v.id].first_in;
    155     }
    156     void nextIn(Edge &e) const {
    157       e.id=edges[e.id].next_in;
    158     }
    159 
    160    
    161     static int id(Node v) { return v.id; }
    162     static int id(Edge e) { return e.id; }
    163 
    164     static Node nodeFromId(int id) { return Node(id);}
    165     static Edge edgeFromId(int id) { return Edge(id);}
    166 
    167     /// Adds a new node to the graph.
    168 
    169     /// \warning It adds the new node to the front of the list.
    170     /// (i.e. the lastly added node becomes the first.)
    171     Node addNode() {     
    172       int n;
    173      
    174       if(first_free_node==-1) {
    175         n = nodes.size();
    176         nodes.push_back(NodeT());
    177       } else {
    178         n = first_free_node;
    179         first_free_node = nodes[n].next;
    180       }
    181      
    182       nodes[n].next = first_node;
    183       if(first_node != -1) nodes[first_node].prev = n;
    184       first_node = n;
    185       nodes[n].prev = -1;
    186      
    187       nodes[n].first_in = nodes[n].first_out = -1;
    188      
    189       return Node(n);
    190     }
    191    
    192     Edge addEdge(Node u, Node v) {
    193       int n;     
    194 
    195       if (first_free_edge == -1) {
    196         n = edges.size();
    197         edges.push_back(EdgeT());
    198       } else {
    199         n = first_free_edge;
    200         first_free_edge = edges[n].next_in;
    201       }
    202      
    203       edges[n].source = u.id;
    204       edges[n].target = v.id;
    205 
    206       edges[n].next_out = nodes[u.id].first_out;
    207       if(nodes[u.id].first_out != -1) {
    208         edges[nodes[u.id].first_out].prev_out = n;
    209       }
    210      
    211       edges[n].next_in = nodes[v.id].first_in;
    212       if(nodes[v.id].first_in != -1) {
    213         edges[nodes[v.id].first_in].prev_in = n;
    214       }
    215      
    216       edges[n].prev_in = edges[n].prev_out = -1;
    217        
    218       nodes[u.id].first_out = nodes[v.id].first_in = n;
    219 
    220       return Edge(n);
    221     }
    222    
    223     void erase(const Node& node) {
    224       int n = node.id;
    225      
    226       if(nodes[n].next != -1) {
    227         nodes[nodes[n].next].prev = nodes[n].prev;
    228       }
    229      
    230       if(nodes[n].prev != -1) {
    231         nodes[nodes[n].prev].next = nodes[n].next;
    232       } else {
    233         first_node = nodes[n].next;
    234       }
    235      
    236       nodes[n].next = first_free_node;
    237       first_free_node = n;
    238 
    239     }
    240    
    241     void erase(const Edge& edge) {
    242       int n = edge.id;
    243      
    244       if(edges[n].next_in!=-1) {
    245         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    246       }
    247 
    248       if(edges[n].prev_in!=-1) {
    249         edges[edges[n].prev_in].next_in = edges[n].next_in;
    250       } else {
    251         nodes[edges[n].target].first_in = edges[n].next_in;
    252       }
    253 
    254      
    255       if(edges[n].next_out!=-1) {
    256         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    257       }
    258 
    259       if(edges[n].prev_out!=-1) {
    260         edges[edges[n].prev_out].next_out = edges[n].next_out;
    261       } else {
    262         nodes[edges[n].source].first_out = edges[n].next_out;
    263       }
    264      
    265       edges[n].next_in = first_free_edge;
    266       first_free_edge = n;     
    267 
    268     }
    269 
    270     void clear() {
    271       edges.clear();
    272       nodes.clear();
    273       first_node = first_free_node = first_free_edge = -1;
    274     }
    275 
    276   protected:
    277     void changeTarget(Edge e, Node n)
    278     {
    279       if(edges[e.id].next_in != -1)
    280         edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
    281       if(edges[e.id].prev_in != -1)
    282         edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
    283       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
    284       if (nodes[n.id].first_in != -1) {
    285         edges[nodes[n.id].first_in].prev_in = e.id;
    286       }
    287       edges[e.id].target = n.id;
    288       edges[e.id].prev_in = -1;
    289       edges[e.id].next_in = nodes[n.id].first_in;
    290       nodes[n.id].first_in = e.id;
    291     }
    292     void changeSource(Edge e, Node n)
    293     {
    294       if(edges[e.id].next_out != -1)
    295         edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
    296       if(edges[e.id].prev_out != -1)
    297         edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
    298       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
    299       if (nodes[n.id].first_out != -1) {
    300         edges[nodes[n.id].first_out].prev_out = e.id;
    301       }
    302       edges[e.id].source = n.id;
    303       edges[e.id].prev_out = -1;
    304       edges[e.id].next_out = nodes[n.id].first_out;
    305       nodes[n.id].first_out = e.id;
    306     }
    307 
    308   };
    309 
    310   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    311 
    312   /// \addtogroup graphs
    313   /// @{
    314 
    315   ///A list graph class.
    316 
    317   ///This is a simple and fast erasable graph implementation.
    318   ///
    319   ///It conforms to the \ref concept::Graph "Graph" concept and it
    320   ///also provides several additional useful extra functionalities.
    321   ///The most of the member functions and nested classes are
    322   ///documented only in the concept class.
    323   ///\sa concept::Graph.
    324 
    325   class ListGraph : public ExtendedListGraphBase {
    326   public:
    327 
    328     typedef ExtendedListGraphBase Parent;
    329 
    330     ///Add a new node to the graph.
    331    
    332     /// \return the new node.
    333     ///
    334     Node addNode() { return Parent::addNode(); }
    335 
    336     ///Add a new edge to the graph.
    337    
    338     ///Add a new edge to the graph with source node \c s
    339     ///and target node \c t.
    340     ///\return the new edge.
    341     Edge addEdge(const Node& s, const Node& t) {
    342       return Parent::addEdge(s, t);
    343     }
    344 
    345     /// Changes the target of \c e to \c n
    346 
    347     /// Changes the target of \c e to \c n
    348     ///
    349     ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
    350     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
    351     ///invalidated.
    352     void changeTarget(Edge e, Node n) {
    353       Parent::changeTarget(e,n);
    354     }
    355     /// Changes the source of \c e to \c n
    356 
    357     /// Changes the source of \c e to \c n
    358     ///
    359     ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
    360     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
    361     ///invalidated.
    362     void changeSource(Edge e, Node n) {
    363       Parent::changeSource(e,n);
    364     }
    365 
    366     /// Invert the direction of an edge.
    367 
    368     ///\note The <tt>Edge</tt>s referencing the changed edge remain
    369     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
    370     ///invalidated.
    371     void reverseEdge(Edge e) {
    372       Node t=target(e);
    373       changeTarget(e,source(e));
    374       changeSource(e,t);
    375     }
    376 
    377     /// \brief Using this it is possible to avoid the superfluous memory
    378     /// allocation.
    379 
    380     ///Using this it is possible to avoid the superfluous memory
    381     ///allocation: if you know that the graph you want to build will
    382     ///contain at least 10 million nodes then it is worth to reserve
    383     ///space for this amount before starting to build the graph.
    384     void reserveNode(int n) { nodes.reserve(n); };
    385 
    386     /// \brief Using this it is possible to avoid the superfluous memory
    387     /// allocation.
    388 
    389     ///Using this it is possible to avoid the superfluous memory
    390     ///allocation: see the \ref reserveNode function.
    391     void reserveEdge(int n) { edges.reserve(n); };
    392 
    393 
    394     ///Contract two nodes.
    395 
    396     ///This function contracts two nodes.
    397     ///
    398     ///Node \p b will be removed but instead of deleting
    399     ///incident edges, they will be joined to \p a.
    400     ///The last parameter \p r controls whether to remove loops. \c true
    401     ///means that loops will be removed.
    402     ///
    403     ///\note The <tt>Edge</tt>s
    404     ///referencing a moved edge remain
    405     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    406     ///may be invalidated.
    407     void contract(Node a, Node b, bool r = true)
    408     {
    409       for(OutEdgeIt e(*this,b);e!=INVALID;) {
    410         OutEdgeIt f=e;
    411         ++f;
    412         if(r && target(e)==a) erase(e);
    413         else changeSource(e,a);
    414         e=f;
    415       }
    416       for(InEdgeIt e(*this,b);e!=INVALID;) {
    417         InEdgeIt f=e;
    418         ++f;
    419         if(r && source(e)==a) erase(e);
    420         else changeTarget(e,a);
    421         e=f;
    422       }
    423       erase(b);
    424     }
    425 
    426     ///Split a node.
    427 
    428     ///This function splits a node. First a new node is added to the graph,
    429     ///then the source of each outgoing edge of \c n is moved to this new node.
    430     ///If \c connect is \c true (this is the default value), then a new edge
    431     ///from \c n to the newly created node is also added.
    432     ///\return The newly created node.
    433     ///
    434     ///\note The <tt>Edge</tt>s
    435     ///referencing a moved edge remain
    436     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    437     ///may be invalidated.
    438     ///\warning This functionality cannot be used together with the Snapshot
    439     ///feature.
    440     ///\todo It could be implemented in a bit faster way.
    441     Node split(Node n, bool connect = true) {
    442       Node b = addNode();
    443       for(OutEdgeIt e(*this,n);e!=INVALID;) {
    444         OutEdgeIt f=e;
    445         ++f;
    446         changeSource(e,b);
    447         e=f;
    448       }
    449       if (connect) addEdge(n,b);
    450       return b;
    451     }
    452      
    453     ///Split an edge.
    454 
    455     ///This function splits an edge. First a new node \c b is added to
    456     ///the graph, then the original edge is re-targeted to \c
    457     ///b. Finally an edge from \c b to the original target is added.
    458     ///\return The newly created node. 
    459     ///\warning This functionality
    460     ///cannot be used together with the Snapshot feature.
    461     Node split(Edge e) {
    462       Node b = addNode();
    463       addEdge(b,target(e));
    464       changeTarget(e,b);
    465       return b;
    466     }
    467      
    468     /// \brief Class to make a snapshot of the graph and restore
    469     /// to it later.
    470     ///
    471     /// Class to make a snapshot of the graph and to restore it
    472     /// later.
    473     ///
    474     /// The newly added nodes and edges can be removed using the
    475     /// restore() function.
    476     ///
    477     /// \warning Edge and node deletions cannot be restored.
    478     class Snapshot {
    479     public:
    480      
    481       class UnsupportedOperation : public LogicError {
    482       public:
    483         virtual const char* exceptionName() const {
    484           return "lemon::ListGraph::Snapshot::UnsupportedOperation";
    485         }
    486       };
    487            
    488 
    489     protected:
    490 
    491       typedef Parent::NodeNotifier NodeNotifier;
    492 
    493       class NodeObserverProxy : public NodeNotifier::ObserverBase {
    494       public:
    495 
    496         NodeObserverProxy(Snapshot& _snapshot)
    497           : snapshot(_snapshot) {}
    498 
    499         using NodeNotifier::ObserverBase::attach;
    500         using NodeNotifier::ObserverBase::detach;
    501         using NodeNotifier::ObserverBase::attached;
    502        
    503       protected:
    504        
    505         virtual void add(const Node& node) {
    506           snapshot.addNode(node);
    507         }
    508         virtual void add(const std::vector<Node>& nodes) {
    509           for (int i = nodes.size() - 1; i >= 0; ++i) {
    510             snapshot.addNode(nodes[i]);
    511           }
    512         }
    513         virtual void erase(const Node& node) {
    514           snapshot.eraseNode(node);
    515         }
    516         virtual void erase(const std::vector<Node>& nodes) {
    517           for (int i = 0; i < (int)nodes.size(); ++i) {
    518             if (!snapshot.eraseNode(nodes[i])) break;
    519           }
    520         }
    521         virtual void build() {
    522           NodeNotifier* notifier = getNotifier();
    523           Node node;
    524           std::vector<Node> nodes;
    525           for (notifier->first(node); node != INVALID; notifier->next(node)) {
    526             nodes.push_back(node);
    527           }
    528           for (int i = nodes.size() - 1; i >= 0; --i) {
    529             snapshot.addNode(nodes[i]);
    530           }
    531         }
    532         virtual void clear() {
    533           NodeNotifier* notifier = getNotifier();
    534           Node node;
    535           for (notifier->first(node); node != INVALID; notifier->next(node)) {
    536             if (!snapshot.eraseNode(node)) break;
    537           }
    538         }
    539 
    540         Snapshot& snapshot;
    541       };
    542 
    543       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
    544       public:
    545 
    546         EdgeObserverProxy(Snapshot& _snapshot)
    547           : snapshot(_snapshot) {}
    548 
    549         using EdgeNotifier::ObserverBase::attach;
    550         using EdgeNotifier::ObserverBase::detach;
    551         using EdgeNotifier::ObserverBase::attached;
    552        
    553       protected:
    554 
    555         virtual void add(const Edge& edge) {
    556           snapshot.addEdge(edge);
    557         }
    558         virtual void add(const std::vector<Edge>& edges) {
    559           for (int i = edges.size() - 1; i >= 0; ++i) {
    560             snapshot.addEdge(edges[i]);
    561           }
    562         }
    563         virtual void erase(const Edge& edge) {
    564           snapshot.eraseEdge(edge);
    565         }
    566         virtual void erase(const std::vector<Edge>& edges) {
    567           for (int i = 0; i < (int)edges.size(); ++i) {
    568             if (!snapshot.eraseEdge(edges[i])) break;
    569           }
    570         }
    571         virtual void build() {
    572           EdgeNotifier* notifier = getNotifier();
    573           Edge edge;
    574           std::vector<Edge> edges;
    575           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
    576             edges.push_back(edge);
    577           }
    578           for (int i = edges.size() - 1; i >= 0; --i) {
    579             snapshot.addEdge(edges[i]);
    580           }
    581         }
    582         virtual void clear() {
    583           EdgeNotifier* notifier = getNotifier();
    584           Edge edge;
    585           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
    586             if (!snapshot.eraseEdge(edge)) break;
    587           }
    588         }
    589 
    590         Snapshot& snapshot;
    591       };
    592      
    593       ListGraph *graph;
    594 
    595       NodeObserverProxy node_observer_proxy;
    596       EdgeObserverProxy edge_observer_proxy;
    597 
    598       std::list<Node> added_nodes;
    599       std::list<Edge> added_edges;
    600 
    601 
    602       void addNode(const Node& node) {
    603         added_nodes.push_front(node);       
    604       }
    605       bool eraseNode(const Node& node) {
    606         std::list<Node>::iterator it =
    607           std::find(added_nodes.begin(), added_nodes.end(), node);
    608         if (it == added_nodes.end()) {
    609           clear();
    610           return false;
    611         } else {
    612           added_nodes.erase(it);
    613           return true;
    614         }
    615       }
    616 
    617       void addEdge(const Edge& edge) {
    618         added_edges.push_front(edge);       
    619       }
    620       bool eraseEdge(const Edge& edge) {
    621         std::list<Edge>::iterator it =
    622           std::find(added_edges.begin(), added_edges.end(), edge);
    623         if (it == added_edges.end()) {
    624           clear();
    625           return false;
    626         } else {
    627           added_edges.erase(it);
    628           return true;
    629         }       
    630       }
    631 
    632       void attach(ListGraph &_graph) {
    633         graph = &_graph;
    634         node_observer_proxy.attach(graph->getNotifier(Node()));
    635         edge_observer_proxy.attach(graph->getNotifier(Edge()));
    636       }
    637            
    638       void detach() {
    639         node_observer_proxy.detach();
    640         edge_observer_proxy.detach();
    641       }
    642 
    643       void clear() {
    644         detach();
    645         added_nodes.clear();
    646         added_edges.clear();       
    647       }
    648 
    649     public:
    650 
    651       /// \brief Default constructur.
    652       ///
    653       /// Default constructor.
    654       /// To actually make a snapshot you must call save().
    655       Snapshot()
    656         : graph(0), node_observer_proxy(*this),
    657           edge_observer_proxy(*this) {}
    658      
    659       /// \brief Constructor that immediately makes a snapshot.
    660       ///     
    661       /// This constructor immediately makes a snapshot of the graph.
    662       /// \param _graph The graph we make a snapshot of.
    663       Snapshot(ListGraph &_graph)
    664         : node_observer_proxy(*this),
    665           edge_observer_proxy(*this) {
    666         attach(_graph);
    667       }
    668      
    669       /// \brief Make a snapshot.
    670       ///
    671       /// Make a snapshot of the graph.
    672       ///
    673       /// This function can be called more than once. In case of a repeated
    674       /// call, the previous snapshot gets lost.
    675       /// \param _graph The graph we make the snapshot of.
    676       void save(ListGraph &_graph) {
    677         clear();
    678         attach(_graph);
    679       }
    680      
    681       /// \brief Undo the changes until the last snapshot.
    682       //
    683       /// Undo the changes until last snapshot created by save().
    684       ///
    685       /// \todo This function might be called undo().
    686       void restore() {
    687         detach();
    688         while(!added_edges.empty()) {
    689           graph->erase(added_edges.front());
    690           added_edges.pop_front();
    691         }
    692         while(!added_nodes.empty()) {
    693           graph->erase(added_nodes.front());
    694           added_nodes.pop_front();
    695         }
    696       }
    697 
    698       /// \brief Gives back true when the snapshot is valid.
    699       ///
    700       /// Gives back true when the snapshot is valid.
    701       bool valid() const {
    702         return node_observer_proxy.attached();
    703       }
    704     };
    705    
    706   };
    707 
    708   ///@}
    709 
    710   /**************** Undirected List Graph ****************/
    711 
    712   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    713   ExtendedListUGraphBase;
    714 
    715   /// \addtogroup graphs
    716   /// @{
    717 
    718   ///An undirected list graph class.
    719 
    720   ///This is a simple and fast erasable undirected graph implementation.
    721   ///
    722   ///It conforms to the
    723   ///\ref concept::UGraph "UGraph" concept.
    724   ///
    725   ///\sa concept::UGraph.
    726   ///
    727   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
    728   ///haven't been implemented yet.
    729   ///
    730   class ListUGraph : public ExtendedListUGraphBase {
    731   public:
    732     typedef ExtendedListUGraphBase Parent;
    733     /// \brief Add a new node to the graph.
    734     ///
    735     /// \return the new node.
    736     ///
    737     Node addNode() { return Parent::addNode(); }
    738 
    739     /// \brief Add a new edge to the graph.
    740     ///
    741     /// Add a new edge to the graph with source node \c s
    742     /// and target node \c t.
    743     /// \return the new undirected edge.
    744     UEdge addEdge(const Node& s, const Node& t) {
    745       return Parent::addEdge(s, t);
    746     }
    747     /// \brief Changes the target of \c e to \c n
    748     ///
    749     /// Changes the target of \c e to \c n
    750     ///
    751     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
    752     /// referencing the changed edge remain
    753     /// valid. However <tt>InEdge</tt>'s are invalidated.
    754     void changeTarget(UEdge e, Node n) {
    755       Parent::changeTarget(e,n);
    756     }
    757     /// Changes the source of \c e to \c n
    758     ///
    759     /// Changes the source of \c e to \c n
    760     ///
    761     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
    762     ///referencing the changed edge remain
    763     ///valid. However <tt>OutEdge</tt>'s are invalidated.
    764     void changeSource(UEdge e, Node n) {
    765       Parent::changeSource(e,n);
    766     }
    767     /// \brief Contract two nodes.
    768     ///
    769     /// This function contracts two nodes.
    770     ///
    771     /// Node \p b will be removed but instead of deleting
    772     /// its neighboring edges, they will be joined to \p a.
    773     /// The last parameter \p r controls whether to remove loops. \c true
    774     /// means that loops will be removed.
    775     ///
    776     /// \note The <tt>Edge</tt>s
    777     /// referencing a moved edge remain
    778     /// valid.
    779     void contract(Node a, Node b, bool r = true) {
    780       for(IncEdgeIt e(*this, b); e!=INVALID;) {
    781         IncEdgeIt f = e; ++f;
    782         if (r && runningNode(e) == a) {
    783           erase(e);
    784         } else if (source(e) == b) {
    785           changeSource(e, a);
    786         } else {
    787           changeTarget(e, a);
    788         }
    789         e = f;
    790       }
    791       erase(b);
    792     }
    793   };
    794 
    79534
    79635  class ListBpUGraphBase {
  • lemon/list_graph.h

    r2114 r2115  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph, ListUGraph classes.
    25 
    26 #include <lemon/bits/base_extender.h>
     24///\brief ListGraph class.
     25
    2726#include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/error.h>
    3027
    3128#include <vector>
     
    310307  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    311308
    312   /// \addtogroup graphs
    313   /// @{
     309  /// \ingroup graphs
    314310
    315311  ///A list graph class.
     
    706702  };
    707703
    708   ///@}
    709 
    710   /**************** Undirected List Graph ****************/
    711 
    712   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    713   ExtendedListUGraphBase;
    714 
    715   /// \addtogroup graphs
    716   /// @{
    717 
    718   ///An undirected list graph class.
    719 
    720   ///This is a simple and fast erasable undirected graph implementation.
    721   ///
    722   ///It conforms to the
    723   ///\ref concept::UGraph "UGraph" concept.
    724   ///
    725   ///\sa concept::UGraph.
    726   ///
    727   ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
    728   ///haven't been implemented yet.
    729   ///
    730   class ListUGraph : public ExtendedListUGraphBase {
    731   public:
    732     typedef ExtendedListUGraphBase Parent;
    733     /// \brief Add a new node to the graph.
    734     ///
    735     /// \return the new node.
    736     ///
    737     Node addNode() { return Parent::addNode(); }
    738 
    739     /// \brief Add a new edge to the graph.
    740     ///
    741     /// Add a new edge to the graph with source node \c s
    742     /// and target node \c t.
    743     /// \return the new undirected edge.
    744     UEdge addEdge(const Node& s, const Node& t) {
    745       return Parent::addEdge(s, t);
    746     }
    747     /// \brief Changes the target of \c e to \c n
    748     ///
    749     /// Changes the target of \c e to \c n
    750     ///
    751     /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
    752     /// referencing the changed edge remain
    753     /// valid. However <tt>InEdge</tt>'s are invalidated.
    754     void changeTarget(UEdge e, Node n) {
    755       Parent::changeTarget(e,n);
    756     }
    757     /// Changes the source of \c e to \c n
    758     ///
    759     /// Changes the source of \c e to \c n
    760     ///
    761     ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
    762     ///referencing the changed edge remain
    763     ///valid. However <tt>OutEdge</tt>'s are invalidated.
    764     void changeSource(UEdge e, Node n) {
    765       Parent::changeSource(e,n);
    766     }
    767     /// \brief Contract two nodes.
    768     ///
    769     /// This function contracts two nodes.
    770     ///
    771     /// Node \p b will be removed but instead of deleting
    772     /// its neighboring edges, they will be joined to \p a.
    773     /// The last parameter \p r controls whether to remove loops. \c true
    774     /// means that loops will be removed.
    775     ///
    776     /// \note The <tt>Edge</tt>s
    777     /// referencing a moved edge remain
    778     /// valid.
    779     void contract(Node a, Node b, bool r = true) {
    780       for(IncEdgeIt e(*this, b); e!=INVALID;) {
    781         IncEdgeIt f = e; ++f;
    782         if (r && runningNode(e) == a) {
    783           erase(e);
    784         } else if (source(e) == b) {
    785           changeSource(e, a);
    786         } else {
    787           changeTarget(e, a);
    788         }
    789         e = f;
    790       }
    791       erase(b);
    792     }
    793   };
    794 
    795 
    796   class ListBpUGraphBase {
    797   public:
    798 
    799     class NodeSetError : public LogicError {
    800       virtual const char* exceptionName() const {
    801         return "lemon::ListBpUGraph::NodeSetError";
    802       }
    803     };
    804 
    805   protected:
    806 
    807     struct NodeT {
    808       int first_edge, prev, next;
    809     };
    810 
    811     struct UEdgeT {
    812       int aNode, prev_out, next_out;
    813       int bNode, prev_in, next_in;
    814     };
    815 
    816     std::vector<NodeT> aNodes;
    817     std::vector<NodeT> bNodes;
    818 
    819     std::vector<UEdgeT> edges;
    820 
    821     int first_anode;
    822     int first_free_anode;
    823 
    824     int first_bnode;
    825     int first_free_bnode;
    826 
    827     int first_free_edge;
    828 
    829   public:
    830  
    831     class Node {
    832       friend class ListBpUGraphBase;
    833     protected:
    834       int id;
    835 
    836       explicit Node(int _id) : id(_id) {}
    837     public:
    838       Node() {}
    839       Node(Invalid) { id = -1; }
    840       bool operator==(const Node i) const {return id==i.id;}
    841       bool operator!=(const Node i) const {return id!=i.id;}
    842       bool operator<(const Node i) const {return id<i.id;}
    843     };
    844 
    845     class UEdge {
    846       friend class ListBpUGraphBase;
    847     protected:
    848       int id;
    849 
    850       explicit UEdge(int _id) { id = _id;}
    851     public:
    852       UEdge() {}
    853       UEdge (Invalid) { id = -1; }
    854       bool operator==(const UEdge i) const {return id==i.id;}
    855       bool operator!=(const UEdge i) const {return id!=i.id;}
    856       bool operator<(const UEdge i) const {return id<i.id;}
    857     };
    858 
    859     ListBpUGraphBase()
    860       : first_anode(-1), first_free_anode(-1),
    861         first_bnode(-1), first_free_bnode(-1),
    862         first_free_edge(-1) {}
    863 
    864     void firstANode(Node& node) const {
    865       node.id = first_anode != -1 ? (first_anode << 1) : -1;
    866     }
    867     void nextANode(Node& node) const {
    868       node.id = aNodes[node.id >> 1].next;
    869     }
    870 
    871     void firstBNode(Node& node) const {
    872       node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    873     }
    874     void nextBNode(Node& node) const {
    875       node.id = bNodes[node.id >> 1].next;
    876     }
    877 
    878     void first(Node& node) const {
    879       if (first_anode != -1) {
    880         node.id = (first_anode << 1);
    881       } else if (first_bnode != -1) {
    882         node.id = (first_bnode << 1) + 1;
    883       } else {
    884         node.id = -1;
    885       }
    886     }
    887     void next(Node& node) const {
    888       if (aNode(node)) {
    889         node.id = aNodes[node.id >> 1].next;
    890         if (node.id == -1) {
    891           if (first_bnode != -1) {
    892             node.id = (first_bnode << 1) + 1;
    893           }
    894         }
    895       } else {
    896         node.id = bNodes[node.id >> 1].next;
    897       }
    898     }
    899  
    900     void first(UEdge& edge) const {
    901       int aNodeId = first_anode;
    902       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    903         aNodeId = aNodes[aNodeId].next != -1 ?
    904           aNodes[aNodeId].next >> 1 : -1;
    905       }
    906       if (aNodeId != -1) {
    907         edge.id = aNodes[aNodeId].first_edge;
    908       } else {
    909         edge.id = -1;
    910       }
    911     }
    912     void next(UEdge& edge) const {
    913       int aNodeId = edges[edge.id].aNode >> 1;
    914       edge.id = edges[edge.id].next_out;
    915       if (edge.id == -1) {
    916         aNodeId = aNodes[aNodeId].next != -1 ?
    917           aNodes[aNodeId].next >> 1 : -1;
    918         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    919           aNodeId = aNodes[aNodeId].next != -1 ?
    920           aNodes[aNodeId].next >> 1 : -1;
    921         }
    922         if (aNodeId != -1) {
    923           edge.id = aNodes[aNodeId].first_edge;
    924         } else {
    925           edge.id = -1;
    926         }
    927       }
    928     }
    929 
    930     void firstFromANode(UEdge& edge, const Node& node) const {
    931       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    932       edge.id = aNodes[node.id >> 1].first_edge;
    933     }
    934     void nextFromANode(UEdge& edge) const {
    935       edge.id = edges[edge.id].next_out;
    936     }
    937 
    938     void firstFromBNode(UEdge& edge, const Node& node) const {
    939       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    940       edge.id = bNodes[node.id >> 1].first_edge;
    941     }
    942     void nextFromBNode(UEdge& edge) const {
    943       edge.id = edges[edge.id].next_in;
    944     }
    945 
    946     static int id(const Node& node) {
    947       return node.id;
    948     }
    949     static Node nodeFromId(int id) {
    950       return Node(id);
    951     }
    952     int maxNodeId() const {
    953       return aNodes.size() > bNodes.size() ?
    954         aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    955     }
    956  
    957     static int id(const UEdge& edge) {
    958       return edge.id;
    959     }
    960     static UEdge uEdgeFromId(int id) {
    961       return UEdge(id);
    962     }
    963     int maxUEdgeId() const {
    964       return edges.size();
    965     }
    966  
    967     static int aNodeId(const Node& node) {
    968       return node.id >> 1;
    969     }
    970     static Node fromANodeId(int id) {
    971       return Node(id << 1);
    972     }
    973     int maxANodeId() const {
    974       return aNodes.size();
    975     }
    976 
    977     static int bNodeId(const Node& node) {
    978       return node.id >> 1;
    979     }
    980     static Node fromBNodeId(int id) {
    981       return Node((id << 1) + 1);
    982     }
    983     int maxBNodeId() const {
    984       return bNodes.size();
    985     }
    986 
    987     Node aNode(const UEdge& edge) const {
    988       return Node(edges[edge.id].aNode);
    989     }
    990     Node bNode(const UEdge& edge) const {
    991       return Node(edges[edge.id].bNode);
    992     }
    993 
    994     static bool aNode(const Node& node) {
    995       return (node.id & 1) == 0;
    996     }
    997 
    998     static bool bNode(const Node& node) {
    999       return (node.id & 1) == 1;
    1000     }
    1001 
    1002     Node addANode() {
    1003       int aNodeId;
    1004       if (first_free_anode == -1) {
    1005         aNodeId = aNodes.size();
    1006         aNodes.push_back(NodeT());
    1007       } else {
    1008         aNodeId = first_free_anode;
    1009         first_free_anode = aNodes[first_free_anode].next;
    1010       }
    1011       if (first_anode != -1) {
    1012         aNodes[aNodeId].next = first_anode << 1;
    1013         aNodes[first_anode].prev = aNodeId << 1;
    1014       } else {
    1015         aNodes[aNodeId].next = -1;
    1016       }
    1017       aNodes[aNodeId].prev = -1;
    1018       first_anode = aNodeId;
    1019       aNodes[aNodeId].first_edge = -1;
    1020       return Node(aNodeId << 1);
    1021     }
    1022 
    1023     Node addBNode() {
    1024       int bNodeId;
    1025       if (first_free_bnode == -1) {
    1026         bNodeId = bNodes.size();
    1027         bNodes.push_back(NodeT());
    1028       } else {
    1029         bNodeId = first_free_bnode;
    1030         first_free_bnode = bNodes[first_free_bnode].next;
    1031       }
    1032       if (first_bnode != -1) {
    1033         bNodes[bNodeId].next = (first_bnode << 1) + 1;
    1034         bNodes[first_bnode].prev = (bNodeId << 1) + 1;
    1035       } else {
    1036         bNodes[bNodeId].next = -1;
    1037       }
    1038       first_bnode = bNodeId;
    1039       bNodes[bNodeId].first_edge = -1;
    1040       return Node((bNodeId << 1) + 1);
    1041     }
    1042 
    1043     UEdge addEdge(const Node& source, const Node& target) {
    1044       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    1045       int edgeId;
    1046       if (first_free_edge != -1) {
    1047         edgeId = first_free_edge;
    1048         first_free_edge = edges[edgeId].next_out;
    1049       } else {
    1050         edgeId = edges.size();
    1051         edges.push_back(UEdgeT());
    1052       }
    1053       if ((source.id & 1) == 0) {
    1054         edges[edgeId].aNode = source.id;
    1055         edges[edgeId].bNode = target.id;
    1056       } else {
    1057         edges[edgeId].aNode = target.id;
    1058         edges[edgeId].bNode = source.id;
    1059       }
    1060       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
    1061       edges[edgeId].prev_out = -1;
    1062       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
    1063         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
    1064       }
    1065       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
    1066       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
    1067       edges[edgeId].prev_in = -1;
    1068       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
    1069         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
    1070       }
    1071       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
    1072       return UEdge(edgeId);
    1073     }
    1074 
    1075     void erase(const Node& node) {
    1076       if (aNode(node)) {
    1077         int aNodeId = node.id >> 1;
    1078         if (aNodes[aNodeId].prev != -1) {
    1079           aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
    1080         } else {
    1081           first_anode = aNodes[aNodeId].next >> 1;
    1082         }
    1083         if (aNodes[aNodeId].next != -1) {
    1084           aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
    1085         }
    1086         aNodes[aNodeId].next = first_free_anode;
    1087         first_free_anode = aNodeId;
    1088       } else {
    1089         int bNodeId = node.id >> 1;
    1090         if (bNodes[bNodeId].prev != -1) {
    1091           bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
    1092         } else {
    1093           first_bnode = bNodes[bNodeId].next >> 1;
    1094         }
    1095         if (bNodes[bNodeId].next != -1) {
    1096           bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
    1097         }
    1098         bNodes[bNodeId].next = first_free_bnode;
    1099         first_free_bnode = bNodeId;
    1100       }
    1101     }
    1102 
    1103     void erase(const UEdge& edge) {
    1104 
    1105       if (edges[edge.id].prev_out != -1) {
    1106         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
    1107       } else {
    1108         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
    1109       }
    1110       if (edges[edge.id].next_out != -1) {
    1111         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
    1112       }
    1113 
    1114       if (edges[edge.id].prev_in != -1) {
    1115         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
    1116       } else {
    1117         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
    1118       }
    1119       if (edges[edge.id].next_in != -1) {
    1120         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
    1121       }
    1122 
    1123       edges[edge.id].next_out = first_free_edge;
    1124       first_free_edge = edge.id;
    1125     }
    1126 
    1127     void clear() {
    1128       aNodes.clear();
    1129       bNodes.clear();
    1130       edges.clear();
    1131       first_anode = -1;
    1132       first_free_anode = -1;
    1133       first_bnode = -1;
    1134       first_free_bnode = -1;
    1135       first_free_edge = -1;
    1136     }
    1137 
    1138   };
    1139 
    1140 
    1141   typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
    1142 
    1143   /// \ingroup graphs
    1144   ///
    1145   /// \brief A smart bipartite undirected graph class.
    1146   ///
    1147   /// This is a bipartite undirected graph implementation.
    1148   /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
    1149   /// concept.
    1150   /// \sa concept::BpUGraph.
    1151   ///
    1152   class ListBpUGraph : public ExtendedListBpUGraphBase {};
    1153 
    1154  
    1155   /// @} 
    1156704} //namespace lemon
    1157705 
  • lemon/list_ugraph.h

    r2114 r2115  
    1717 */
    1818
    19 #ifndef LEMON_LIST_GRAPH_H
    20 #define LEMON_LIST_GRAPH_H
     19#ifndef LEMON_LIST_UGRAPH_H
     20#define LEMON_LIST_UGRAPH_H
    2121
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph, ListUGraph classes.
     24///\brief ListUGraph classes.
    2525
     26#include <lemon/list_graph.h>
    2627#include <lemon/bits/base_extender.h>
    27 #include <lemon/bits/graph_extender.h>
    28 
    29 #include <lemon/error.h>
     28#include <lemon/bits/ugraph_extender.h>
    3029
    3130#include <vector>
     
    3433namespace lemon {
    3534
    36   class ListGraphBase {
    37 
    38   protected:
    39     struct NodeT {
    40       int first_in, first_out;
    41       int prev, next;
    42     };
    43  
    44     struct EdgeT {
    45       int target, source;
    46       int prev_in, prev_out;
    47       int next_in, next_out;
    48     };
    49 
    50     std::vector<NodeT> nodes;
    51 
    52     int first_node;
    53 
    54     int first_free_node;
    55 
    56     std::vector<EdgeT> edges;
    57 
    58     int first_free_edge;
    59    
    60   public:
    61    
    62     typedef ListGraphBase Graph;
    63    
    64     class Node {
    65       friend class ListGraphBase;
    66     protected:
    67 
    68       int id;
    69       explicit Node(int pid) { id = pid;}
    70 
    71     public:
    72       Node() {}
    73       Node (Invalid) { id = -1; }
    74       bool operator==(const Node& node) const {return id == node.id;}
    75       bool operator!=(const Node& node) const {return id != node.id;}
    76       bool operator<(const Node& node) const {return id < node.id;}
    77     };
    78 
    79     class Edge {
    80       friend class ListGraphBase;
    81     protected:
    82 
    83       int id;
    84       explicit Edge(int pid) { id = pid;}
    85 
    86     public:
    87       Edge() {}
    88       Edge (Invalid) { id = -1; }
    89       bool operator==(const Edge& edge) const {return id == edge.id;}
    90       bool operator!=(const Edge& edge) const {return id != edge.id;}
    91       bool operator<(const Edge& edge) const {return id < edge.id;}
    92     };
    93 
    94 
    95 
    96     ListGraphBase()
    97       : nodes(), first_node(-1),
    98         first_free_node(-1), edges(), first_free_edge(-1) {}
    99 
    100    
    101     /// Maximum node ID.
    102    
    103     /// Maximum node ID.
    104     ///\sa id(Node)
    105     int maxNodeId() const { return nodes.size()-1; }
    106 
    107     /// Maximum edge ID.
    108    
    109     /// Maximum edge ID.
    110     ///\sa id(Edge)
    111     int maxEdgeId() const { return edges.size()-1; }
    112 
    113     Node source(Edge e) const { return Node(edges[e.id].source); }
    114     Node target(Edge e) const { return Node(edges[e.id].target); }
    115 
    116 
    117     void first(Node& node) const {
    118       node.id = first_node;
    119     }
    120 
    121     void next(Node& node) const {
    122       node.id = nodes[node.id].next;
    123     }
    124 
    125 
    126     void first(Edge& e) const {
    127       int n;
    128       for(n = first_node;
    129           n!=-1 && nodes[n].first_in == -1;
    130           n = nodes[n].next);
    131       e.id = (n == -1) ? -1 : nodes[n].first_in;
    132     }
    133 
    134     void next(Edge& edge) const {
    135       if (edges[edge.id].next_in != -1) {
    136         edge.id = edges[edge.id].next_in;
    137       } else {
    138         int n;
    139         for(n = nodes[edges[edge.id].target].next;
    140           n!=-1 && nodes[n].first_in == -1;
    141           n = nodes[n].next);
    142         edge.id = (n == -1) ? -1 : nodes[n].first_in;
    143       }     
    144     }
    145 
    146     void firstOut(Edge &e, const Node& v) const {
    147       e.id = nodes[v.id].first_out;
    148     }
    149     void nextOut(Edge &e) const {
    150       e.id=edges[e.id].next_out;
    151     }
    152 
    153     void firstIn(Edge &e, const Node& v) const {
    154       e.id = nodes[v.id].first_in;
    155     }
    156     void nextIn(Edge &e) const {
    157       e.id=edges[e.id].next_in;
    158     }
    159 
    160    
    161     static int id(Node v) { return v.id; }
    162     static int id(Edge e) { return e.id; }
    163 
    164     static Node nodeFromId(int id) { return Node(id);}
    165     static Edge edgeFromId(int id) { return Edge(id);}
    166 
    167     /// Adds a new node to the graph.
    168 
    169     /// \warning It adds the new node to the front of the list.
    170     /// (i.e. the lastly added node becomes the first.)
    171     Node addNode() {     
    172       int n;
    173      
    174       if(first_free_node==-1) {
    175         n = nodes.size();
    176         nodes.push_back(NodeT());
    177       } else {
    178         n = first_free_node;
    179         first_free_node = nodes[n].next;
    180       }
    181      
    182       nodes[n].next = first_node;
    183       if(first_node != -1) nodes[first_node].prev = n;
    184       first_node = n;
    185       nodes[n].prev = -1;
    186      
    187       nodes[n].first_in = nodes[n].first_out = -1;
    188      
    189       return Node(n);
    190     }
    191    
    192     Edge addEdge(Node u, Node v) {
    193       int n;     
    194 
    195       if (first_free_edge == -1) {
    196         n = edges.size();
    197         edges.push_back(EdgeT());
    198       } else {
    199         n = first_free_edge;
    200         first_free_edge = edges[n].next_in;
    201       }
    202      
    203       edges[n].source = u.id;
    204       edges[n].target = v.id;
    205 
    206       edges[n].next_out = nodes[u.id].first_out;
    207       if(nodes[u.id].first_out != -1) {
    208         edges[nodes[u.id].first_out].prev_out = n;
    209       }
    210      
    211       edges[n].next_in = nodes[v.id].first_in;
    212       if(nodes[v.id].first_in != -1) {
    213         edges[nodes[v.id].first_in].prev_in = n;
    214       }
    215      
    216       edges[n].prev_in = edges[n].prev_out = -1;
    217        
    218       nodes[u.id].first_out = nodes[v.id].first_in = n;
    219 
    220       return Edge(n);
    221     }
    222    
    223     void erase(const Node& node) {
    224       int n = node.id;
    225      
    226       if(nodes[n].next != -1) {
    227         nodes[nodes[n].next].prev = nodes[n].prev;
    228       }
    229      
    230       if(nodes[n].prev != -1) {
    231         nodes[nodes[n].prev].next = nodes[n].next;
    232       } else {
    233         first_node = nodes[n].next;
    234       }
    235      
    236       nodes[n].next = first_free_node;
    237       first_free_node = n;
    238 
    239     }
    240    
    241     void erase(const Edge& edge) {
    242       int n = edge.id;
    243      
    244       if(edges[n].next_in!=-1) {
    245         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    246       }
    247 
    248       if(edges[n].prev_in!=-1) {
    249         edges[edges[n].prev_in].next_in = edges[n].next_in;
    250       } else {
    251         nodes[edges[n].target].first_in = edges[n].next_in;
    252       }
    253 
    254      
    255       if(edges[n].next_out!=-1) {
    256         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    257       }
    258 
    259       if(edges[n].prev_out!=-1) {
    260         edges[edges[n].prev_out].next_out = edges[n].next_out;
    261       } else {
    262         nodes[edges[n].source].first_out = edges[n].next_out;
    263       }
    264      
    265       edges[n].next_in = first_free_edge;
    266       first_free_edge = n;     
    267 
    268     }
    269 
    270     void clear() {
    271       edges.clear();
    272       nodes.clear();
    273       first_node = first_free_node = first_free_edge = -1;
    274     }
    275 
    276   protected:
    277     void changeTarget(Edge e, Node n)
    278     {
    279       if(edges[e.id].next_in != -1)
    280         edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
    281       if(edges[e.id].prev_in != -1)
    282         edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
    283       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
    284       if (nodes[n.id].first_in != -1) {
    285         edges[nodes[n.id].first_in].prev_in = e.id;
    286       }
    287       edges[e.id].target = n.id;
    288       edges[e.id].prev_in = -1;
    289       edges[e.id].next_in = nodes[n.id].first_in;
    290       nodes[n.id].first_in = e.id;
    291     }
    292     void changeSource(Edge e, Node n)
    293     {
    294       if(edges[e.id].next_out != -1)
    295         edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
    296       if(edges[e.id].prev_out != -1)
    297         edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
    298       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
    299       if (nodes[n.id].first_out != -1) {
    300         edges[nodes[n.id].first_out].prev_out = e.id;
    301       }
    302       edges[e.id].source = n.id;
    303       edges[e.id].prev_out = -1;
    304       edges[e.id].next_out = nodes[n.id].first_out;
    305       nodes[n.id].first_out = e.id;
    306     }
    307 
    308   };
    309 
    310   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    311 
    312   /// \addtogroup graphs
    313   /// @{
    314 
    315   ///A list graph class.
    316 
    317   ///This is a simple and fast erasable graph implementation.
    318   ///
    319   ///It conforms to the \ref concept::Graph "Graph" concept and it
    320   ///also provides several additional useful extra functionalities.
    321   ///The most of the member functions and nested classes are
    322   ///documented only in the concept class.
    323   ///\sa concept::Graph.
    324 
    325   class ListGraph : public ExtendedListGraphBase {
    326   public:
    327 
    328     typedef ExtendedListGraphBase Parent;
    329 
    330     ///Add a new node to the graph.
    331    
    332     /// \return the new node.
    333     ///
    334     Node addNode() { return Parent::addNode(); }
    335 
    336     ///Add a new edge to the graph.
    337    
    338     ///Add a new edge to the graph with source node \c s
    339     ///and target node \c t.
    340     ///\return the new edge.
    341     Edge addEdge(const Node& s, const Node& t) {
    342       return Parent::addEdge(s, t);
    343     }
    344 
    345     /// Changes the target of \c e to \c n
    346 
    347     /// Changes the target of \c e to \c n
    348     ///
    349     ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
    350     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
    351     ///invalidated.
    352     void changeTarget(Edge e, Node n) {
    353       Parent::changeTarget(e,n);
    354     }
    355     /// Changes the source of \c e to \c n
    356 
    357     /// Changes the source of \c e to \c n
    358     ///
    359     ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
    360     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
    361     ///invalidated.
    362     void changeSource(Edge e, Node n) {
    363       Parent::changeSource(e,n);
    364     }
    365 
    366     /// Invert the direction of an edge.
    367 
    368     ///\note The <tt>Edge</tt>s referencing the changed edge remain
    369     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
    370     ///invalidated.
    371     void reverseEdge(Edge e) {
    372       Node t=target(e);
    373       changeTarget(e,source(e));
    374       changeSource(e,t);
    375     }
    376 
    377     /// \brief Using this it is possible to avoid the superfluous memory
    378     /// allocation.
    379 
    380     ///Using this it is possible to avoid the superfluous memory
    381     ///allocation: if you know that the graph you want to build will
    382     ///contain at least 10 million nodes then it is worth to reserve
    383     ///space for this amount before starting to build the graph.
    384     void reserveNode(int n) { nodes.reserve(n); };
    385 
    386     /// \brief Using this it is possible to avoid the superfluous memory
    387     /// allocation.
    388 
    389     ///Using this it is possible to avoid the superfluous memory
    390     ///allocation: see the \ref reserveNode function.
    391     void reserveEdge(int n) { edges.reserve(n); };
    392 
    393 
    394     ///Contract two nodes.
    395 
    396     ///This function contracts two nodes.
    397     ///
    398     ///Node \p b will be removed but instead of deleting
    399     ///incident edges, they will be joined to \p a.
    400     ///The last parameter \p r controls whether to remove loops. \c true
    401     ///means that loops will be removed.
    402     ///
    403     ///\note The <tt>Edge</tt>s
    404     ///referencing a moved edge remain
    405     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    406     ///may be invalidated.
    407     void contract(Node a, Node b, bool r = true)
    408     {
    409       for(OutEdgeIt e(*this,b);e!=INVALID;) {
    410         OutEdgeIt f=e;
    411         ++f;
    412         if(r && target(e)==a) erase(e);
    413         else changeSource(e,a);
    414         e=f;
    415       }
    416       for(InEdgeIt e(*this,b);e!=INVALID;) {
    417         InEdgeIt f=e;
    418         ++f;
    419         if(r && source(e)==a) erase(e);
    420         else changeTarget(e,a);
    421         e=f;
    422       }
    423       erase(b);
    424     }
    425 
    426     ///Split a node.
    427 
    428     ///This function splits a node. First a new node is added to the graph,
    429     ///then the source of each outgoing edge of \c n is moved to this new node.
    430     ///If \c connect is \c true (this is the default value), then a new edge
    431     ///from \c n to the newly created node is also added.
    432     ///\return The newly created node.
    433     ///
    434     ///\note The <tt>Edge</tt>s
    435     ///referencing a moved edge remain
    436     ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s
    437     ///may be invalidated.
    438     ///\warning This functionality cannot be used together with the Snapshot
    439     ///feature.
    440     ///\todo It could be implemented in a bit faster way.
    441     Node split(Node n, bool connect = true) {
    442       Node b = addNode();
    443       for(OutEdgeIt e(*this,n);e!=INVALID;) {
    444         OutEdgeIt f=e;
    445         ++f;
    446         changeSource(e,b);
    447         e=f;
    448       }
    449       if (connect) addEdge(n,b);
    450       return b;
    451     }
    452      
    453     ///Split an edge.
    454 
    455     ///This function splits an edge. First a new node \c b is added to
    456     ///the graph, then the original edge is re-targeted to \c
    457     ///b. Finally an edge from \c b to the original target is added.
    458     ///\return The newly created node. 
    459     ///\warning This functionality
    460     ///cannot be used together with the Snapshot feature.
    461     Node split(Edge e) {
    462       Node b = addNode();
    463       addEdge(b,target(e));
    464       changeTarget(e,b);
    465       return b;
    466     }
    467      
    468     /// \brief Class to make a snapshot of the graph and restore
    469     /// to it later.
    470     ///
    471     /// Class to make a snapshot of the graph and to restore it
    472     /// later.
    473     ///
    474     /// The newly added nodes and edges can be removed using the
    475     /// restore() function.
    476     ///
    477     /// \warning Edge and node deletions cannot be restored.
    478     class Snapshot {
    479     public:
    480      
    481       class UnsupportedOperation : public LogicError {
    482       public:
    483         virtual const char* exceptionName() const {
    484           return "lemon::ListGraph::Snapshot::UnsupportedOperation";
    485         }
    486       };
    487            
    488 
    489     protected:
    490 
    491       typedef Parent::NodeNotifier NodeNotifier;
    492 
    493       class NodeObserverProxy : public NodeNotifier::ObserverBase {
    494       public:
    495 
    496         NodeObserverProxy(Snapshot& _snapshot)
    497           : snapshot(_snapshot) {}
    498 
    499         using NodeNotifier::ObserverBase::attach;
    500         using NodeNotifier::ObserverBase::detach;
    501         using NodeNotifier::ObserverBase::attached;
    502        
    503       protected:
    504        
    505         virtual void add(const Node& node) {
    506           snapshot.addNode(node);
    507         }
    508         virtual void add(const std::vector<Node>& nodes) {
    509           for (int i = nodes.size() - 1; i >= 0; ++i) {
    510             snapshot.addNode(nodes[i]);
    511           }
    512         }
    513         virtual void erase(const Node& node) {
    514           snapshot.eraseNode(node);
    515         }
    516         virtual void erase(const std::vector<Node>& nodes) {
    517           for (int i = 0; i < (int)nodes.size(); ++i) {
    518             if (!snapshot.eraseNode(nodes[i])) break;
    519           }
    520         }
    521         virtual void build() {
    522           NodeNotifier* notifier = getNotifier();
    523           Node node;
    524           std::vector<Node> nodes;
    525           for (notifier->first(node); node != INVALID; notifier->next(node)) {
    526             nodes.push_back(node);
    527           }
    528           for (int i = nodes.size() - 1; i >= 0; --i) {
    529             snapshot.addNode(nodes[i]);
    530           }
    531         }
    532         virtual void clear() {
    533           NodeNotifier* notifier = getNotifier();
    534           Node node;
    535           for (notifier->first(node); node != INVALID; notifier->next(node)) {
    536             if (!snapshot.eraseNode(node)) break;
    537           }
    538         }
    539 
    540         Snapshot& snapshot;
    541       };
    542 
    543       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
    544       public:
    545 
    546         EdgeObserverProxy(Snapshot& _snapshot)
    547           : snapshot(_snapshot) {}
    548 
    549         using EdgeNotifier::ObserverBase::attach;
    550         using EdgeNotifier::ObserverBase::detach;
    551         using EdgeNotifier::ObserverBase::attached;
    552        
    553       protected:
    554 
    555         virtual void add(const Edge& edge) {
    556           snapshot.addEdge(edge);
    557         }
    558         virtual void add(const std::vector<Edge>& edges) {
    559           for (int i = edges.size() - 1; i >= 0; ++i) {
    560             snapshot.addEdge(edges[i]);
    561           }
    562         }
    563         virtual void erase(const Edge& edge) {
    564           snapshot.eraseEdge(edge);
    565         }
    566         virtual void erase(const std::vector<Edge>& edges) {
    567           for (int i = 0; i < (int)edges.size(); ++i) {
    568             if (!snapshot.eraseEdge(edges[i])) break;
    569           }
    570         }
    571         virtual void build() {
    572           EdgeNotifier* notifier = getNotifier();
    573           Edge edge;
    574           std::vector<Edge> edges;
    575           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
    576             edges.push_back(edge);
    577           }
    578           for (int i = edges.size() - 1; i >= 0; --i) {
    579             snapshot.addEdge(edges[i]);
    580           }
    581         }
    582         virtual void clear() {
    583           EdgeNotifier* notifier = getNotifier();
    584           Edge edge;
    585           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
    586             if (!snapshot.eraseEdge(edge)) break;
    587           }
    588         }
    589 
    590         Snapshot& snapshot;
    591       };
    592      
    593       ListGraph *graph;
    594 
    595       NodeObserverProxy node_observer_proxy;
    596       EdgeObserverProxy edge_observer_proxy;
    597 
    598       std::list<Node> added_nodes;
    599       std::list<Edge> added_edges;
    600 
    601 
    602       void addNode(const Node& node) {
    603         added_nodes.push_front(node);       
    604       }
    605       bool eraseNode(const Node& node) {
    606         std::list<Node>::iterator it =
    607           std::find(added_nodes.begin(), added_nodes.end(), node);
    608         if (it == added_nodes.end()) {
    609           clear();
    610           return false;
    611         } else {
    612           added_nodes.erase(it);
    613           return true;
    614         }
    615       }
    616 
    617       void addEdge(const Edge& edge) {
    618         added_edges.push_front(edge);       
    619       }
    620       bool eraseEdge(const Edge& edge) {
    621         std::list<Edge>::iterator it =
    622           std::find(added_edges.begin(), added_edges.end(), edge);
    623         if (it == added_edges.end()) {
    624           clear();
    625           return false;
    626         } else {
    627           added_edges.erase(it);
    628           return true;
    629         }       
    630       }
    631 
    632       void attach(ListGraph &_graph) {
    633         graph = &_graph;
    634         node_observer_proxy.attach(graph->getNotifier(Node()));
    635         edge_observer_proxy.attach(graph->getNotifier(Edge()));
    636       }
    637            
    638       void detach() {
    639         node_observer_proxy.detach();
    640         edge_observer_proxy.detach();
    641       }
    642 
    643       void clear() {
    644         detach();
    645         added_nodes.clear();
    646         added_edges.clear();       
    647       }
    648 
    649     public:
    650 
    651       /// \brief Default constructur.
    652       ///
    653       /// Default constructor.
    654       /// To actually make a snapshot you must call save().
    655       Snapshot()
    656         : graph(0), node_observer_proxy(*this),
    657           edge_observer_proxy(*this) {}
    658      
    659       /// \brief Constructor that immediately makes a snapshot.
    660       ///     
    661       /// This constructor immediately makes a snapshot of the graph.
    662       /// \param _graph The graph we make a snapshot of.
    663       Snapshot(ListGraph &_graph)
    664         : node_observer_proxy(*this),
    665           edge_observer_proxy(*this) {
    666         attach(_graph);
    667       }
    668      
    669       /// \brief Make a snapshot.
    670       ///
    671       /// Make a snapshot of the graph.
    672       ///
    673       /// This function can be called more than once. In case of a repeated
    674       /// call, the previous snapshot gets lost.
    675       /// \param _graph The graph we make the snapshot of.
    676       void save(ListGraph &_graph) {
    677         clear();
    678         attach(_graph);
    679       }
    680      
    681       /// \brief Undo the changes until the last snapshot.
    682       //
    683       /// Undo the changes until last snapshot created by save().
    684       ///
    685       /// \todo This function might be called undo().
    686       void restore() {
    687         detach();
    688         while(!added_edges.empty()) {
    689           graph->erase(added_edges.front());
    690           added_edges.pop_front();
    691         }
    692         while(!added_nodes.empty()) {
    693           graph->erase(added_nodes.front());
    694           added_nodes.pop_front();
    695         }
    696       }
    697 
    698       /// \brief Gives back true when the snapshot is valid.
    699       ///
    700       /// Gives back true when the snapshot is valid.
    701       bool valid() const {
    702         return node_observer_proxy.attached();
    703       }
    704     };
    705    
    706   };
    707 
    708   ///@}
    709 
    710   /**************** Undirected List Graph ****************/
    711 
    71235  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
    71336  ExtendedListUGraphBase;
    71437
    715   /// \addtogroup graphs
    716   /// @{
     38  /// \ingroup graphs
    71739
    71840  ///An undirected list graph class.
     
    793115  };
    794116
    795 
    796   class ListBpUGraphBase {
    797   public:
    798 
    799     class NodeSetError : public LogicError {
    800       virtual const char* exceptionName() const {
    801         return "lemon::ListBpUGraph::NodeSetError";
    802       }
    803     };
    804 
    805   protected:
    806 
    807     struct NodeT {
    808       int first_edge, prev, next;
    809     };
    810 
    811     struct UEdgeT {
    812       int aNode, prev_out, next_out;
    813       int bNode, prev_in, next_in;
    814     };
    815 
    816     std::vector<NodeT> aNodes;
    817     std::vector<NodeT> bNodes;
    818 
    819     std::vector<UEdgeT> edges;
    820 
    821     int first_anode;
    822     int first_free_anode;
    823 
    824     int first_bnode;
    825     int first_free_bnode;
    826 
    827     int first_free_edge;
    828 
    829   public:
    830  
    831     class Node {
    832       friend class ListBpUGraphBase;
    833     protected:
    834       int id;
    835 
    836       explicit Node(int _id) : id(_id) {}
    837     public:
    838       Node() {}
    839       Node(Invalid) { id = -1; }
    840       bool operator==(const Node i) const {return id==i.id;}
    841       bool operator!=(const Node i) const {return id!=i.id;}
    842       bool operator<(const Node i) const {return id<i.id;}
    843     };
    844 
    845     class UEdge {
    846       friend class ListBpUGraphBase;
    847     protected:
    848       int id;
    849 
    850       explicit UEdge(int _id) { id = _id;}
    851     public:
    852       UEdge() {}
    853       UEdge (Invalid) { id = -1; }
    854       bool operator==(const UEdge i) const {return id==i.id;}
    855       bool operator!=(const UEdge i) const {return id!=i.id;}
    856       bool operator<(const UEdge i) const {return id<i.id;}
    857     };
    858 
    859     ListBpUGraphBase()
    860       : first_anode(-1), first_free_anode(-1),
    861         first_bnode(-1), first_free_bnode(-1),
    862         first_free_edge(-1) {}
    863 
    864     void firstANode(Node& node) const {
    865       node.id = first_anode != -1 ? (first_anode << 1) : -1;
    866     }
    867     void nextANode(Node& node) const {
    868       node.id = aNodes[node.id >> 1].next;
    869     }
    870 
    871     void firstBNode(Node& node) const {
    872       node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
    873     }
    874     void nextBNode(Node& node) const {
    875       node.id = bNodes[node.id >> 1].next;
    876     }
    877 
    878     void first(Node& node) const {
    879       if (first_anode != -1) {
    880         node.id = (first_anode << 1);
    881       } else if (first_bnode != -1) {
    882         node.id = (first_bnode << 1) + 1;
    883       } else {
    884         node.id = -1;
    885       }
    886     }
    887     void next(Node& node) const {
    888       if (aNode(node)) {
    889         node.id = aNodes[node.id >> 1].next;
    890         if (node.id == -1) {
    891           if (first_bnode != -1) {
    892             node.id = (first_bnode << 1) + 1;
    893           }
    894         }
    895       } else {
    896         node.id = bNodes[node.id >> 1].next;
    897       }
    898     }
    899  
    900     void first(UEdge& edge) const {
    901       int aNodeId = first_anode;
    902       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    903         aNodeId = aNodes[aNodeId].next != -1 ?
    904           aNodes[aNodeId].next >> 1 : -1;
    905       }
    906       if (aNodeId != -1) {
    907         edge.id = aNodes[aNodeId].first_edge;
    908       } else {
    909         edge.id = -1;
    910       }
    911     }
    912     void next(UEdge& edge) const {
    913       int aNodeId = edges[edge.id].aNode >> 1;
    914       edge.id = edges[edge.id].next_out;
    915       if (edge.id == -1) {
    916         aNodeId = aNodes[aNodeId].next != -1 ?
    917           aNodes[aNodeId].next >> 1 : -1;
    918         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
    919           aNodeId = aNodes[aNodeId].next != -1 ?
    920           aNodes[aNodeId].next >> 1 : -1;
    921         }
    922         if (aNodeId != -1) {
    923           edge.id = aNodes[aNodeId].first_edge;
    924         } else {
    925           edge.id = -1;
    926         }
    927       }
    928     }
    929 
    930     void firstFromANode(UEdge& edge, const Node& node) const {
    931       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    932       edge.id = aNodes[node.id >> 1].first_edge;
    933     }
    934     void nextFromANode(UEdge& edge) const {
    935       edge.id = edges[edge.id].next_out;
    936     }
    937 
    938     void firstFromBNode(UEdge& edge, const Node& node) const {
    939       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    940       edge.id = bNodes[node.id >> 1].first_edge;
    941     }
    942     void nextFromBNode(UEdge& edge) const {
    943       edge.id = edges[edge.id].next_in;
    944     }
    945 
    946     static int id(const Node& node) {
    947       return node.id;
    948     }
    949     static Node nodeFromId(int id) {
    950       return Node(id);
    951     }
    952     int maxNodeId() const {
    953       return aNodes.size() > bNodes.size() ?
    954         aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    955     }
    956  
    957     static int id(const UEdge& edge) {
    958       return edge.id;
    959     }
    960     static UEdge uEdgeFromId(int id) {
    961       return UEdge(id);
    962     }
    963     int maxUEdgeId() const {
    964       return edges.size();
    965     }
    966  
    967     static int aNodeId(const Node& node) {
    968       return node.id >> 1;
    969     }
    970     static Node fromANodeId(int id) {
    971       return Node(id << 1);
    972     }
    973     int maxANodeId() const {
    974       return aNodes.size();
    975     }
    976 
    977     static int bNodeId(const Node& node) {
    978       return node.id >> 1;
    979     }
    980     static Node fromBNodeId(int id) {
    981       return Node((id << 1) + 1);
    982     }
    983     int maxBNodeId() const {
    984       return bNodes.size();
    985     }
    986 
    987     Node aNode(const UEdge& edge) const {
    988       return Node(edges[edge.id].aNode);
    989     }
    990     Node bNode(const UEdge& edge) const {
    991       return Node(edges[edge.id].bNode);
    992     }
    993 
    994     static bool aNode(const Node& node) {
    995       return (node.id & 1) == 0;
    996     }
    997 
    998     static bool bNode(const Node& node) {
    999       return (node.id & 1) == 1;
    1000     }
    1001 
    1002     Node addANode() {
    1003       int aNodeId;
    1004       if (first_free_anode == -1) {
    1005         aNodeId = aNodes.size();
    1006         aNodes.push_back(NodeT());
    1007       } else {
    1008         aNodeId = first_free_anode;
    1009         first_free_anode = aNodes[first_free_anode].next;
    1010       }
    1011       if (first_anode != -1) {
    1012         aNodes[aNodeId].next = first_anode << 1;
    1013         aNodes[first_anode].prev = aNodeId << 1;
    1014       } else {
    1015         aNodes[aNodeId].next = -1;
    1016       }
    1017       aNodes[aNodeId].prev = -1;
    1018       first_anode = aNodeId;
    1019       aNodes[aNodeId].first_edge = -1;
    1020       return Node(aNodeId << 1);
    1021     }
    1022 
    1023     Node addBNode() {
    1024       int bNodeId;
    1025       if (first_free_bnode == -1) {
    1026         bNodeId = bNodes.size();
    1027         bNodes.push_back(NodeT());
    1028       } else {
    1029         bNodeId = first_free_bnode;
    1030         first_free_bnode = bNodes[first_free_bnode].next;
    1031       }
    1032       if (first_bnode != -1) {
    1033         bNodes[bNodeId].next = (first_bnode << 1) + 1;
    1034         bNodes[first_bnode].prev = (bNodeId << 1) + 1;
    1035       } else {
    1036         bNodes[bNodeId].next = -1;
    1037       }
    1038       first_bnode = bNodeId;
    1039       bNodes[bNodeId].first_edge = -1;
    1040       return Node((bNodeId << 1) + 1);
    1041     }
    1042 
    1043     UEdge addEdge(const Node& source, const Node& target) {
    1044       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    1045       int edgeId;
    1046       if (first_free_edge != -1) {
    1047         edgeId = first_free_edge;
    1048         first_free_edge = edges[edgeId].next_out;
    1049       } else {
    1050         edgeId = edges.size();
    1051         edges.push_back(UEdgeT());
    1052       }
    1053       if ((source.id & 1) == 0) {
    1054         edges[edgeId].aNode = source.id;
    1055         edges[edgeId].bNode = target.id;
    1056       } else {
    1057         edges[edgeId].aNode = target.id;
    1058         edges[edgeId].bNode = source.id;
    1059       }
    1060       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
    1061       edges[edgeId].prev_out = -1;
    1062       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
    1063         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
    1064       }
    1065       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
    1066       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
    1067       edges[edgeId].prev_in = -1;
    1068       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
    1069         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
    1070       }
    1071       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
    1072       return UEdge(edgeId);
    1073     }
    1074 
    1075     void erase(const Node& node) {
    1076       if (aNode(node)) {
    1077         int aNodeId = node.id >> 1;
    1078         if (aNodes[aNodeId].prev != -1) {
    1079           aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
    1080         } else {
    1081           first_anode = aNodes[aNodeId].next >> 1;
    1082         }
    1083         if (aNodes[aNodeId].next != -1) {
    1084           aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
    1085         }
    1086         aNodes[aNodeId].next = first_free_anode;
    1087         first_free_anode = aNodeId;
    1088       } else {
    1089         int bNodeId = node.id >> 1;
    1090         if (bNodes[bNodeId].prev != -1) {
    1091           bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
    1092         } else {
    1093           first_bnode = bNodes[bNodeId].next >> 1;
    1094         }
    1095         if (bNodes[bNodeId].next != -1) {
    1096           bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
    1097         }
    1098         bNodes[bNodeId].next = first_free_bnode;
    1099         first_free_bnode = bNodeId;
    1100       }
    1101     }
    1102 
    1103     void erase(const UEdge& edge) {
    1104 
    1105       if (edges[edge.id].prev_out != -1) {
    1106         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
    1107       } else {
    1108         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
    1109       }
    1110       if (edges[edge.id].next_out != -1) {
    1111         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
    1112       }
    1113 
    1114       if (edges[edge.id].prev_in != -1) {
    1115         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
    1116       } else {
    1117         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
    1118       }
    1119       if (edges[edge.id].next_in != -1) {
    1120         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
    1121       }
    1122 
    1123       edges[edge.id].next_out = first_free_edge;
    1124       first_free_edge = edge.id;
    1125     }
    1126 
    1127     void clear() {
    1128       aNodes.clear();
    1129       bNodes.clear();
    1130       edges.clear();
    1131       first_anode = -1;
    1132       first_free_anode = -1;
    1133       first_bnode = -1;
    1134       first_free_bnode = -1;
    1135       first_free_edge = -1;
    1136     }
    1137 
    1138   };
    1139 
    1140 
    1141   typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
    1142 
    1143   /// \ingroup graphs
    1144   ///
    1145   /// \brief A smart bipartite undirected graph class.
    1146   ///
    1147   /// This is a bipartite undirected graph implementation.
    1148   /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
    1149   /// concept.
    1150   /// \sa concept::BpUGraph.
    1151   ///
    1152   class ListBpUGraph : public ExtendedListBpUGraphBase {};
    1153 
    1154  
    1155   /// @} 
    1156117} //namespace lemon
    1157118 
  • lemon/min_cut.h

    r2111 r2115  
    2424
    2525#include <lemon/list_graph.h>
     26#include <lemon/list_ugraph.h>
    2627#include <lemon/bin_heap.h>
    2728#include <lemon/bucket_heap.h>
     
    195196  template <typename _Graph, typename _CapacityMap, typename _Traits>
    196197#else
    197   template <typename _Graph = ListUGraph,
     198  template <typename _Graph = ListGraph,
    198199            typename _CapacityMap = typename _Graph::template EdgeMap<int>,
    199200            typename _Traits =
  • lemon/smart_graph.h

    r2111 r2115  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief SmartGraph and SmartUGraph classes.
     24///\brief SmartGraph class.
    2525
    2626#include <vector>
     
    2828#include <lemon/bits/invalid.h>
    2929
    30 #include <lemon/bits/base_extender.h>
    3130#include <lemon/bits/graph_extender.h>
    3231
    3332#include <lemon/bits/utility.h>
    34 #include <lemon/error.h>
    3533
    3634#include <lemon/bits/graph_extender.h>
     
    357355
    358356
    359   /**************** Undirected List Graph ****************/
    360 
    361   typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
    362   ExtendedSmartUGraphBase;
    363 
    364   /// \ingroup graphs
    365   ///
    366   /// \brief A smart undirected graph class.
    367   ///
    368   /// This is a simple and fast undirected graph implementation.
    369   /// It is also quite memory efficient, but at the price
    370   /// that <b> it does support only limited (only stack-like)
    371   /// node and edge deletions</b>.
    372   /// Except from this it conforms to
    373   /// the \ref concept::UGraph "UGraph" concept.
    374   /// \sa concept::UGraph.
    375   ///
    376   /// \todo Snapshot hasn't been implemented yet.
    377   ///
    378   class SmartUGraph : public ExtendedSmartUGraphBase {
    379   };
    380 
    381 
    382   class SmartBpUGraphBase {
    383   public:
    384 
    385     class NodeSetError : public LogicError {
    386       virtual const char* exceptionName() const {
    387         return "lemon::SmartBpUGraph::NodeSetError";
    388       }
    389     };
    390 
    391   protected:
    392 
    393     struct NodeT {
    394       int first;
    395       NodeT() {}
    396       NodeT(int _first) : first(_first) {}
    397     };
    398 
    399     struct UEdgeT {
    400       int aNode, next_out;
    401       int bNode, next_in;
    402     };
    403 
    404     std::vector<NodeT> aNodes;
    405     std::vector<NodeT> bNodes;
    406 
    407     std::vector<UEdgeT> edges;
    408 
    409   public:
    410  
    411     class Node {
    412       friend class SmartBpUGraphBase;
    413     protected:
    414       int id;
    415 
    416       Node(int _id) : id(_id) {}
    417     public:
    418       Node() {}
    419       Node(Invalid) { id = -1; }
    420       bool operator==(const Node i) const {return id==i.id;}
    421       bool operator!=(const Node i) const {return id!=i.id;}
    422       bool operator<(const Node i) const {return id<i.id;}
    423     };
    424 
    425     class UEdge {
    426       friend class SmartBpUGraphBase;
    427     protected:
    428       int id;
    429 
    430       UEdge(int _id) { id = _id;}
    431     public:
    432       UEdge() {}
    433       UEdge (Invalid) { id = -1; }
    434       bool operator==(const UEdge i) const {return id==i.id;}
    435       bool operator!=(const UEdge i) const {return id!=i.id;}
    436       bool operator<(const UEdge i) const {return id<i.id;}
    437     };
    438 
    439     void firstANode(Node& node) const {
    440       node.id = 2 * aNodes.size() - 2;
    441       if (node.id < 0) node.id = -1;
    442     }
    443     void nextANode(Node& node) const {
    444       node.id -= 2;
    445       if (node.id < 0) node.id = -1;
    446     }
    447 
    448     void firstBNode(Node& node) const {
    449       node.id = 2 * bNodes.size() - 1;
    450     }
    451     void nextBNode(Node& node) const {
    452       node.id -= 2;
    453     }
    454 
    455     void first(Node& node) const {
    456       if (aNodes.size() > 0) {
    457         node.id = 2 * aNodes.size() - 2;
    458       } else {
    459         node.id = 2 * bNodes.size() - 1;
    460       }
    461     }
    462     void next(Node& node) const {
    463       node.id -= 2;
    464       if (node.id == -2) {
    465         node.id = 2 * bNodes.size() - 1;
    466       }
    467     }
    468  
    469     void first(UEdge& edge) const {
    470       edge.id = edges.size() - 1;
    471     }
    472     void next(UEdge& edge) const {
    473       --edge.id;
    474     }
    475 
    476     void firstFromANode(UEdge& edge, const Node& node) const {
    477       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    478       edge.id = aNodes[node.id >> 1].first;
    479     }
    480     void nextFromANode(UEdge& edge) const {
    481       edge.id = edges[edge.id].next_out;
    482     }
    483 
    484     void firstFromBNode(UEdge& edge, const Node& node) const {
    485       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    486       edge.id = bNodes[node.id >> 1].first;
    487     }
    488     void nextFromBNode(UEdge& edge) const {
    489       edge.id = edges[edge.id].next_in;
    490     }
    491 
    492     static int id(const Node& node) {
    493       return node.id;
    494     }
    495     static Node nodeFromId(int id) {
    496       return Node(id);
    497     }
    498     int maxNodeId() const {
    499       return aNodes.size() > bNodes.size() ?
    500         aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    501     }
    502  
    503     static int id(const UEdge& edge) {
    504       return edge.id;
    505     }
    506     static UEdge uEdgeFromId(int id) {
    507       return UEdge(id);
    508     }
    509     int maxUEdgeId() const {
    510       return edges.size();
    511     }
    512  
    513     static int aNodeId(const Node& node) {
    514       return node.id >> 1;
    515     }
    516     static Node fromANodeId(int id) {
    517       return Node(id << 1);
    518     }
    519     int maxANodeId() const {
    520       return aNodes.size();
    521     }
    522 
    523     static int bNodeId(const Node& node) {
    524       return node.id >> 1;
    525     }
    526     static Node fromBNodeId(int id) {
    527       return Node((id << 1) + 1);
    528     }
    529     int maxBNodeId() const {
    530       return bNodes.size();
    531     }
    532 
    533     Node aNode(const UEdge& edge) const {
    534       return Node(edges[edge.id].aNode);
    535     }
    536     Node bNode(const UEdge& edge) const {
    537       return Node(edges[edge.id].bNode);
    538     }
    539 
    540     static bool aNode(const Node& node) {
    541       return (node.id & 1) == 0;
    542     }
    543 
    544     static bool bNode(const Node& node) {
    545       return (node.id & 1) == 1;
    546     }
    547 
    548     Node addANode() {
    549       NodeT nodeT;
    550       nodeT.first = -1;
    551       aNodes.push_back(nodeT);
    552       return Node(aNodes.size() * 2 - 2);
    553     }
    554 
    555     Node addBNode() {
    556       NodeT nodeT;
    557       nodeT.first = -1;
    558       bNodes.push_back(nodeT);
    559       return Node(bNodes.size() * 2 - 1);
    560     }
    561 
    562     UEdge addEdge(const Node& source, const Node& target) {
    563       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    564       UEdgeT edgeT;
    565       if ((source.id & 1) == 0) {
    566         edgeT.aNode = source.id;
    567         edgeT.bNode = target.id;
    568       } else {
    569         edgeT.aNode = target.id;
    570         edgeT.bNode = source.id;
    571       }
    572       edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
    573       aNodes[edgeT.aNode >> 1].first = edges.size();
    574       edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
    575       bNodes[edgeT.bNode >> 1].first = edges.size();
    576       edges.push_back(edgeT);
    577       return UEdge(edges.size() - 1);
    578     }
    579 
    580     void clear() {
    581       aNodes.clear();
    582       bNodes.clear();
    583       edges.clear();
    584     }
    585 
    586     typedef True NodeNumTag;
    587     int nodeNum() const { return aNodes.size() + bNodes.size(); }
    588     int aNodeNum() const { return aNodes.size(); }
    589     int bNodeNum() const { return bNodes.size(); }
    590 
    591     typedef True EdgeNumTag;
    592     int uEdgeNum() const { return edges.size(); }
    593 
    594   };
    595 
    596 
    597   typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
    598 
    599   /// \ingroup graphs
    600   ///
    601   /// \brief A smart bipartite undirected graph class.
    602   ///
    603   /// This is a simple and fast bipartite undirected graph implementation.
    604   /// It is also quite memory efficient, but at the price
    605   /// that <b> it does not support node and edge deletions</b>.
    606   /// Except from this it conforms to
    607   /// the \ref concept::BpUGraph "BpUGraph" concept.
    608   /// \sa concept::BpUGraph.
    609   ///
    610   class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
    611 
    612  
    613   /// @} 
    614357} //namespace lemon
    615358
Note: See TracChangeset for help on using the changeset viewer.