COIN-OR::LEMON - Graph Library

Changeset 2116:b6a68c15a6a3 in lemon-0.x


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

Revert splitted files

Files:
8 deleted
15 edited

Legend:

Unmodified
Added
Removed
  • demo/coloring.cc

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

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

    r2115 r2116  
    1818
    1919#include <lemon/list_graph.h>
    20 #include <lemon/list_ugraph.h>
    2120#include <lemon/topology.h>
    2221#include <lemon/graph_to_eps.h>
  • doc/graphs.dox

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

    r2115 r2116  
    4444        lemon/floyd_warshall.h \
    4545        lemon/fredman_tarjan.h \
    46         lemon/full_bpugraph.h \
    4746        lemon/full_graph.h \
    48         lemon/full_ugraph.h \
    4947        lemon/graph_adaptor.h \
    5048        lemon/graph_reader.h \
     
    5957        lemon/lemon_reader.h \
    6058        lemon/lemon_writer.h \
    61         lemon/list_bpugraph.h \
    6259        lemon/list_graph.h \
    63         lemon/list_ugraph.h \
    6460        lemon/lp.h \
    6561        lemon/lp_base.h \
     
    8278        lemon/refptr.h \
    8379        lemon/simann.h \
    84         lemon/smart_bpugraph.h \
    8580        lemon/smart_graph.h \
    86         lemon/smart_ugraph.h \
    8781        lemon/sub_graph.h \
    8882        lemon/suurballe.h \
     
    9993        lemon/bits/array_map.h \
    10094        lemon/bits/base_extender.h \
    101         lemon/bits/bpugraph_extender.h \
    10295        lemon/bits/default_map.h \
    10396        lemon/bits/edge_set_extender.h \
     
    111104        lemon/bits/mingw32_time.h \
    112105        lemon/bits/traits.h \
    113         lemon/bits/ugraph_extender.h \
    114106        lemon/bits/utility.h \
    115107        lemon/bits/vector_map.h
  • lemon/bits/graph_extender.h

    r2115 r2116  
    2121
    2222#include <lemon/bits/invalid.h>
     23#include <lemon/error.h>
    2324
    2425#include <lemon/bits/map_extender.h>
    2526#include <lemon/bits/default_map.h>
     27
     28#include <lemon/concept_check.h>
     29#include <lemon/concept/maps.h>
    2630
    2731///\ingroup graphbits
     
    315319  };
    316320
     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
    3171527}
    3181528
  • lemon/edge_set.h

    r2115 r2116  
    2323#include <lemon/bits/default_map.h>
    2424#include <lemon/bits/edge_set_extender.h>
    25 #include <lemon/bits/base_extender.h>
    2625
    2726/// \ingroup graphs
  • lemon/full_graph.h

    r2115 r2116  
    2222#include <cmath>
    2323
     24#include <lemon/bits/base_extender.h>
    2425#include <lemon/bits/graph_extender.h>
    2526
     
    3031///\ingroup graphs
    3132///\file
    32 ///\brief FullGraph class.
     33///\brief FullGraph and FullUGraph classes.
    3334
    3435
     
    247248  };
    248249
     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
    249717} //namespace lemon
    250718
  • lemon/grid_ugraph.h

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

    r2115 r2116  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief ListGraph class.
    25 
     24///\brief ListGraph, ListUGraph classes.
     25
     26#include <lemon/bits/base_extender.h>
    2627#include <lemon/bits/graph_extender.h>
     28
     29#include <lemon/error.h>
    2730
    2831#include <vector>
     
    307310  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    308311
    309   /// \ingroup graphs
     312  /// \addtogroup graphs
     313  /// @{
    310314
    311315  ///A list graph class.
     
    702706  };
    703707
     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  /// @} 
    7041156} //namespace lemon
    7051157 
  • lemon/min_cut.h

    r2115 r2116  
    2424
    2525#include <lemon/list_graph.h>
    26 #include <lemon/list_ugraph.h>
    2726#include <lemon/bin_heap.h>
    2827#include <lemon/bucket_heap.h>
     
    196195  template <typename _Graph, typename _CapacityMap, typename _Traits>
    197196#else
    198   template <typename _Graph = ListGraph,
     197  template <typename _Graph = ListUGraph,
    199198            typename _CapacityMap = typename _Graph::template EdgeMap<int>,
    200199            typename _Traits =
  • lemon/smart_graph.h

    r2115 r2116  
    2222///\ingroup graphs
    2323///\file
    24 ///\brief SmartGraph class.
     24///\brief SmartGraph and SmartUGraph classes.
    2525
    2626#include <vector>
     
    2828#include <lemon/bits/invalid.h>
    2929
     30#include <lemon/bits/base_extender.h>
    3031#include <lemon/bits/graph_extender.h>
    3132
    3233#include <lemon/bits/utility.h>
     34#include <lemon/error.h>
    3335
    3436#include <lemon/bits/graph_extender.h>
     
    355357
    356358
     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  /// @} 
    357614} //namespace lemon
    358615
  • test/bipartite_matching_test.cc

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

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

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