COIN-OR::LEMON - Graph Library

Changeset 2115:4cd528a30ec1 in lemon-0.x


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

Splitted graph files

Files:
6 added
15 edited
2 copied

Legend:

Unmodified
Added
Removed
  • demo/coloring.cc

    r2038 r2115  
    3030#include <iostream>
    3131
    32 #include <lemon/smart_graph.h>
     32#include <lemon/smart_ugraph.h>
    3333#include <lemon/bucket_heap.h>
    3434#include <lemon/graph_reader.h>
  • demo/strongly_connected_orientation.cc

    r2084 r2115  
    1919#include <iostream>
    2020
    21 #include <lemon/smart_graph.h>
     21#include <lemon/smart_ugraph.h>
    2222#include <lemon/graph_reader.h>
    2323#include <lemon/ugraph_adaptor.h>
  • demo/topology_demo.cc

    r1956 r2115  
    1818
    1919#include <lemon/list_graph.h>
     20#include <lemon/list_ugraph.h>
    2021#include <lemon/topology.h>
    2122#include <lemon/graph_to_eps.h>
  • doc/graphs.dox

    r2111 r2115  
    1010provide a node list - edge list interface, i.e. they have
    1111functionalities to list the nodes and the edges of the graph as well
    12 as  incoming and outgoing edges of a given node.
     12as  incoming and outgoing edges of a given node. This functionalities
     13are defined in the \ref lemon::concept::Graph "Graph" concept.
    1314
    14 Each graph should meet the \ref lemon::concept::Graph "Graph" concept.
    15 This concept does not make it possible to change the graph (i.e. it is
    16 not possible to add or delete edges or nodes). Most of the graph
    17 algorithms will run on these graphs.
     15The next important graph type concept is the undirected graph concept
     16what is defined in the \ref lemon::concept::UGraph "UGraph" concept class.
     17Each undirected graphs provide node - undirected edge list interfaces.
     18In addition the undirected graphs can be used as directed graphs so
     19they are also conform to the \ref lemon::concept::Graph "Graph" concept.
    1820
     21Usually the graphs can be sorted to two group, the first is the
     22general topology graph types which can store any graph and the second
     23are the special topology graphs like the \ref FullUGraph or the \ref
     24GridUGraph.
    1925
    20 In case of graphs meeting the full feature
    21 \ref lemon::concept::ErasableGraph "ErasableGraph"
    22 concept
    23 you can also erase individual edges and nodes in arbitrary order.
    24 
    25 The implemented graph structures are the following.
    2626\li \ref lemon::ListGraph "ListGraph" is the most versatile graph class. It meets
    2727the \ref lemon::concept::ErasableGraph "ErasableGraph" concept
  • 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
  • test/bipartite_matching_test.cc

    r2058 r2115  
    33#include <sstream>
    44
    5 #include <lemon/list_graph.h>
     5#include <lemon/list_bpugraph.h>
    66
    77#include <lemon/bpugraph_adaptor.h>
  • test/max_matching_test.cc

    r1993 r2115  
    2424
    2525#include "test_tools.h"
    26 #include <lemon/list_graph.h>
     26#include <lemon/list_ugraph.h>
    2727#include <lemon/max_matching.h>
    2828
  • test/ugraph_test.cc

    r2111 r2115  
    1919#include <lemon/bits/graph_extender.h>
    2020#include <lemon/concept/ugraph.h>
    21 #include <lemon/list_graph.h>
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/full_graph.h>
     21#include <lemon/list_ugraph.h>
     22#include <lemon/smart_ugraph.h>
     23#include <lemon/full_ugraph.h>
    2424#include <lemon/grid_ugraph.h>
    2525
Note: See TracChangeset for help on using the changeset viewer.