COIN-OR::LEMON - Graph Library

Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon


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

Location:
lemon
Files:
8 deleted
8 edited

Legend:

Unmodified
Added
Removed
  • 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
Note: See TracChangeset for help on using the changeset viewer.