COIN-OR::LEMON - Graph Library

Changeset 1820:22099ef840d7 in lemon-0.x for lemon/bits


Ignore:
Timestamp:
11/21/05 18:48:00 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2370
Message:

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

Location:
lemon/bits
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/alteration_notifier.h

    r1729 r1820  
    440440    }
    441441  };
     442
     443
     444  template <typename _Base>
     445  class AlterableUndirBipartiteGraphExtender : public _Base {
     446  public:
     447
     448    typedef _Base Parent;
     449    typedef AlterableUndirBipartiteGraphExtender Graph;
     450 
     451    typedef typename Parent::Node Node;
     452    typedef typename Parent::LowerNode LowerNode;
     453    typedef typename Parent::UpperNode UpperNode;
     454    typedef typename Parent::Edge Edge;
     455    typedef typename Parent::UndirEdge UndirEdge;
     456 
     457 
     458    typedef AlterationNotifier<Node> NodeNotifier;
     459    typedef AlterationNotifier<LowerNode> LowerNodeNotifier;
     460    typedef AlterationNotifier<UpperNode> UpperNodeNotifier;
     461    typedef AlterationNotifier<Edge> EdgeNotifier;
     462    typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
     463
     464  protected:
     465
     466    mutable NodeNotifier nodeNotifier;
     467    mutable LowerNodeNotifier lowerNodeNotifier;
     468    mutable UpperNodeNotifier upperNodeNotifier;
     469    mutable EdgeNotifier edgeNotifier;
     470    mutable UndirEdgeNotifier undirEdgeNotifier;
     471
     472  public:
     473
     474    NodeNotifier& getNotifier(Node) const {
     475      return nodeNotifier;
     476    }
     477
     478    LowerNodeNotifier& getNotifier(LowerNode) const {
     479      return lowerNodeNotifier;
     480    }
     481
     482    UpperNodeNotifier& getNotifier(UpperNode) const {
     483      return upperNodeNotifier;
     484    }
     485
     486    EdgeNotifier& getNotifier(Edge) const {
     487      return edgeNotifier;
     488    }
     489
     490    UndirEdgeNotifier& getNotifier(UndirEdge) const {
     491      return undirEdgeNotifier;
     492    }
     493
     494    ~AlterableUndirBipartiteGraphExtender() {
     495      nodeNotifier.clear();
     496      lowerNodeNotifier.clear();
     497      upperNodeNotifier.clear();
     498      edgeNotifier.clear();
     499      undirEdgeNotifier.clear();
     500    }
     501
     502  };
    442503 
    443504/// @}
  • lemon/bits/clearable_graph_extender.h

    r1435 r1820  
    4545  };
    4646
     47
     48  template <typename _Base>
     49  class ClearableUndirBipartiteGraphExtender : public _Base {
     50  public:
     51
     52    typedef _Base Parent;
     53    typedef ClearableUndirBipartiteGraphExtender Graph;
     54
     55    typedef typename Parent::Node Node;
     56    typedef typename Parent::LowerNode LowerNode;
     57    typedef typename Parent::UpperNode UpperNode;
     58    typedef typename Parent::Edge Edge;
     59    typedef typename Parent::UndirEdge UndirEdge;
     60
     61    void clear() {
     62      Parent::getNotifier(Edge()).clear();
     63      Parent::getNotifier(UndirEdge()).clear();
     64      Parent::getNotifier(Node()).clear();
     65      Parent::getNotifier(LowerNode()).clear();
     66      Parent::getNotifier(UpperNode()).clear();
     67      Parent::clear();
     68    }
     69
     70  };
     71
    4772}
    4873
  • lemon/bits/default_map.h

    r1703 r1820  
    267267  };
    268268
     269
     270  template <typename _Base>
     271  class MappableUndirBipartiteGraphExtender : public _Base {
     272  public:
     273
     274    typedef _Base Parent;
     275    typedef MappableUndirBipartiteGraphExtender Graph;
     276
     277    typedef typename Parent::Node Node;
     278    typedef typename Parent::UpperNode UpperNode;
     279    typedef typename Parent::LowerNode LowerNode;
     280    typedef typename Parent::Edge Edge;
     281    typedef typename Parent::UndirEdge UndirEdge;
     282   
     283    template <typename _Value>
     284    class UpperNodeMap
     285      : public IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> > {
     286    public:
     287      typedef MappableUndirBipartiteGraphExtender Graph;
     288      typedef IterableMapExtender<DefaultMap<Graph, UpperNode, _Value> >
     289      Parent;
     290   
     291      UpperNodeMap(const Graph& _g)
     292        : Parent(_g) {}
     293      UpperNodeMap(const Graph& _g, const _Value& _v)
     294        : Parent(_g, _v) {}
     295   
     296      UpperNodeMap& operator=(const UpperNodeMap& cmap) {
     297        return operator=<UpperNodeMap>(cmap);
     298      }
     299   
     300
     301      /// \brief Template assign operator.
     302      ///
     303      /// The given parameter should be conform to the ReadMap
     304      /// concept and could be indiced by the current item set of
     305      /// the UpperNodeMap. In this case the value for each item
     306      /// is assigned by the value of the given ReadMap.
     307      template <typename CMap>
     308      UpperNodeMap& operator=(const CMap& cmap) {
     309        checkConcept<concept::ReadMap<UpperNode, _Value>, CMap>();
     310        const typename Parent::Graph* graph = Parent::getGraph();
     311        UpperNode it;
     312        for (graph->first(it); it != INVALID; graph->next(it)) {
     313          Parent::set(it, cmap[it]);
     314        }
     315        return *this;
     316      }
     317   
     318    };
     319
     320    template <typename _Value>
     321    class LowerNodeMap
     322      : public IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> > {
     323    public:
     324      typedef MappableUndirBipartiteGraphExtender Graph;
     325      typedef IterableMapExtender<DefaultMap<Graph, LowerNode, _Value> >
     326      Parent;
     327   
     328      LowerNodeMap(const Graph& _g)
     329        : Parent(_g) {}
     330      LowerNodeMap(const Graph& _g, const _Value& _v)
     331        : Parent(_g, _v) {}
     332   
     333      LowerNodeMap& operator=(const LowerNodeMap& cmap) {
     334        return operator=<LowerNodeMap>(cmap);
     335      }
     336   
     337
     338      /// \brief Template assign operator.
     339      ///
     340      /// The given parameter should be conform to the ReadMap
     341      /// concept and could be indiced by the current item set of
     342      /// the LowerNodeMap. In this case the value for each item
     343      /// is assigned by the value of the given ReadMap.
     344      template <typename CMap>
     345      LowerNodeMap& operator=(const CMap& cmap) {
     346        checkConcept<concept::ReadMap<LowerNode, _Value>, CMap>();
     347        const typename Parent::Graph* graph = Parent::getGraph();
     348        LowerNode it;
     349        for (graph->first(it); it != INVALID; graph->next(it)) {
     350          Parent::set(it, cmap[it]);
     351        }
     352        return *this;
     353      }
     354   
     355    };
     356
     357  protected:
     358
     359    template <typename _Value>
     360    class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
     361    public:
     362      typedef MappableUndirBipartiteGraphExtender Graph;
     363
     364      typedef Node Key;
     365      typedef _Value Value;
     366
     367      /// The reference type of the map;
     368      typedef typename LowerNodeMap<_Value>::Reference Reference;
     369      /// The pointer type of the map;
     370      typedef typename LowerNodeMap<_Value>::Pointer Pointer;
     371     
     372      /// The const value type of the map.
     373      typedef const Value ConstValue;
     374      /// The const reference type of the map;
     375      typedef typename LowerNodeMap<_Value>::ConstReference ConstReference;
     376      /// The pointer type of the map;
     377      typedef typename LowerNodeMap<_Value>::ConstPointer ConstPointer;
     378
     379      typedef True ReferenceMapTag;
     380
     381      NodeMapBase(const Graph& _g)
     382        : graph(&_g), lowerMap(_g), upperMap(_g) {
     383        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     384      }
     385      NodeMapBase(const Graph& _g, const _Value& _v)
     386        : graph(&_g), lowerMap(_g, _v),
     387          upperMap(_g, _v) {
     388        Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     389      }
     390
     391      virtual ~NodeMapBase() {     
     392        if (Parent::NodeNotifier::ObserverBase::attached()) {
     393          Parent::NodeNotifier::ObserverBase::detach();
     394        }
     395      }
     396   
     397      ConstReference operator[](const Key& node) const {
     398        if (Parent::upper(node)) {
     399          return upperMap[node];
     400        } else {
     401          return lowerMap[node];
     402        }
     403      }
     404
     405      Reference operator[](const Key& node) {
     406        if (Parent::upper(node)) {
     407          return upperMap[node];
     408        } else {
     409          return lowerMap[node];
     410        }
     411      }
     412
     413      void set(const Key& node, const Value& value) {
     414        if (Parent::upper(node)) {
     415          upperMap.set(node, value);
     416        } else {
     417          lowerMap.set(node, value);
     418        }
     419      }
     420
     421    protected:
     422     
     423      virtual void add(const Node&) {}
     424      virtual void erase(const Node&) {}
     425      virtual void clear() {}
     426      virtual void build() {}
     427
     428      const Graph* getGraph() const { return graph; }
     429     
     430    private:
     431      const Graph* graph;
     432      LowerNodeMap<_Value> lowerMap;
     433      UpperNodeMap<_Value> upperMap;
     434    };
     435   
     436  public:
     437
     438    template <typename _Value>
     439    class NodeMap
     440      : public IterableMapExtender<NodeMapBase<_Value> > {
     441    public:
     442      typedef MappableUndirBipartiteGraphExtender Graph;
     443      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
     444   
     445      NodeMap(const Graph& _g)
     446        : Parent(_g) {}
     447      NodeMap(const Graph& _g, const _Value& _v)
     448        : Parent(_g, _v) {}
     449   
     450      NodeMap& operator=(const NodeMap& cmap) {
     451        return operator=<NodeMap>(cmap);
     452      }
     453   
     454
     455      /// \brief Template assign operator.
     456      ///
     457      /// The given parameter should be conform to the ReadMap
     458      /// concept and could be indiced by the current item set of
     459      /// the NodeMap. In this case the value for each item
     460      /// is assigned by the value of the given ReadMap.
     461      template <typename CMap>
     462      NodeMap& operator=(const CMap& cmap) {
     463        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     464        const typename Parent::Graph* graph = Parent::getGraph();
     465        Node it;
     466        for (graph->first(it); it != INVALID; graph->next(it)) {
     467          Parent::set(it, cmap[it]);
     468        }
     469        return *this;
     470      }
     471   
     472    };
     473
     474
     475
     476    template <typename _Value>
     477    class EdgeMap
     478      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     479    public:
     480      typedef MappableUndirBipartiteGraphExtender Graph;
     481      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     482   
     483      EdgeMap(const Graph& _g)
     484        : Parent(_g) {}
     485      EdgeMap(const Graph& _g, const _Value& _v)
     486        : Parent(_g, _v) {}
     487   
     488      EdgeMap& operator=(const EdgeMap& cmap) {
     489        return operator=<EdgeMap>(cmap);
     490      }
     491   
     492      template <typename CMap>
     493      EdgeMap& operator=(const CMap& cmap) {
     494        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     495        const typename Parent::Graph* graph = Parent::getGraph();
     496        Edge it;
     497        for (graph->first(it); it != INVALID; graph->next(it)) {
     498          Parent::set(it, cmap[it]);
     499        }
     500        return *this;
     501      }
     502    };
     503
     504    template <typename _Value>
     505    class UndirEdgeMap
     506      : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
     507    public:
     508      typedef MappableUndirBipartiteGraphExtender Graph;
     509      typedef IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> >
     510      Parent;
     511   
     512      UndirEdgeMap(const Graph& _g)
     513        : Parent(_g) {}
     514      UndirEdgeMap(const Graph& _g, const _Value& _v)
     515        : Parent(_g, _v) {}
     516   
     517      UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
     518        return operator=<UndirEdgeMap>(cmap);
     519      }
     520   
     521      template <typename CMap>
     522      UndirEdgeMap& operator=(const CMap& cmap) {
     523        checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
     524        const typename Parent::Graph* graph = Parent::getGraph();
     525        UndirEdge it;
     526        for (graph->first(it); it != INVALID; graph->next(it)) {
     527          Parent::set(it, cmap[it]);
     528        }
     529        return *this;
     530      }
     531    };
     532 
     533  };
     534
    269535}
    270536
  • lemon/bits/extendable_graph_extender.h

    r1627 r1820  
    6161  };
    6262
     63
     64  template <typename _Base>
     65  class ExtendableUndirBipartiteGraphExtender : public _Base {
     66  public:
     67
     68    typedef _Base Parent;
     69    typedef ExtendableUndirBipartiteGraphExtender Graph;
     70 
     71    typedef typename Parent::Node Node;
     72    typedef typename Parent::LowerNode LowerNode;
     73    typedef typename Parent::UpperNode UpperNode;
     74    typedef typename Parent::Edge Edge;
     75    typedef typename Parent::UndirEdge UndirEdge;
     76 
     77    Node addUpperNode() {
     78      Node node = Parent::addUpperNode();
     79      Parent::getNotifier(UpperNode()).add(node);
     80      Parent::getNotifier(Node()).add(node);
     81      return node;
     82    }
     83
     84    Node addLowerNode() {
     85      Node node = Parent::addLowerNode();
     86      Parent::getNotifier(LowerNode()).add(node);
     87      Parent::getNotifier(Node()).add(node);
     88      return node;
     89    }
     90 
     91    UndirEdge addEdge(const Node& source, const Node& target) {
     92      UndirEdge undiredge = Parent::addEdge(source, target);
     93      Parent::getNotifier(UndirEdge()).add(undiredge);
     94   
     95      std::vector<Edge> edges;
     96      edges.push_back(Parent::direct(undiredge, true));
     97      edges.push_back(Parent::direct(undiredge, false));
     98      Parent::getNotifier(Edge()).add(edges);
     99   
     100      return undiredge;
     101    }
     102
     103  };
     104
    63105}
    64106
  • lemon/bits/graph_extender.h

    r1791 r1820  
    2020
    2121#include <lemon/invalid.h>
     22#include <lemon/error.h>
    2223
    2324namespace lemon {
     
    377378  };
    378379
     380
     381  template <typename _Base>
     382  class UndirBipartiteGraphExtender : public _Base {
     383  public:
     384    typedef _Base Parent;
     385    typedef UndirBipartiteGraphExtender Graph;
     386
     387    typedef typename Parent::Node Node;
     388    typedef typename Parent::Edge UndirEdge;
     389
     390    using Parent::first;
     391    using Parent::next;
     392
     393    using Parent::id;
     394
     395    Node source(const UndirEdge& edge) const {
     396      return upperNode(edge);
     397    }
     398    Node target(const UndirEdge& edge) const {
     399      return lowerNode(edge);
     400    }
     401
     402    void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
     403      if (Parent::upper(node)) {
     404        Parent::firstDown(edge, node);
     405        direction = true;
     406      } else {
     407        Parent::firstUp(edge, node);
     408        direction = static_cast<UndirEdge&>(edge) == INVALID;
     409      }
     410    }
     411    void nextInc(UndirEdge& edge, bool& direction) const {
     412      if (direction) {
     413        Parent::nextDown(edge);
     414      } else {
     415        Parent::nextUp(edge);
     416        if (edge == INVALID) direction = true;
     417      }
     418    }
     419
     420    int maxUndirEdgeId() const {
     421      return Parent::maxEdgeId();
     422    }
     423
     424    UndirEdge undirEdgeFromId(int id) const {
     425      return Parent::edgeFromId(id);
     426    }
     427
     428    class Edge : public UndirEdge {
     429      friend class UndirBipartiteGraphExtender;
     430    protected:
     431      bool forward;
     432
     433      Edge(const UndirEdge& edge, bool _forward)
     434        : UndirEdge(edge), forward(_forward) {}
     435
     436    public:
     437      Edge() {}
     438      Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
     439      bool operator==(const Edge& i) const {
     440        return UndirEdge::operator==(i) && forward == i.forward;
     441      }
     442      bool operator!=(const Edge& i) const {
     443        return UndirEdge::operator!=(i) || forward != i.forward;
     444      }
     445      bool operator<(const Edge& i) const {
     446        return UndirEdge::operator<(i) ||
     447          (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
     448      }
     449    };
     450
     451    void first(Edge& edge) const {
     452      Parent::first(static_cast<UndirEdge&>(edge));
     453      edge.forward = true;
     454    }
     455
     456    void next(Edge& edge) const {
     457      if (!edge.forward) {
     458        Parent::next(static_cast<UndirEdge&>(edge));
     459      }
     460      edge.forward = !edge.forward;
     461    }
     462
     463    void firstOut(Edge& edge, const Node& node) const {
     464      if (Parent::upper(node)) {
     465        Parent::firstDown(edge, node);
     466        edge.forward = true;
     467      } else {
     468        Parent::firstUp(edge, node);
     469        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     470      }
     471    }
     472    void nextOut(Edge& edge) const {
     473      if (edge.forward) {
     474        Parent::nextDown(edge);
     475      } else {
     476        Parent::nextUp(edge);
     477        if (edge == INVALID) {
     478          edge.forward = true;
     479        }       
     480      }
     481    }
     482
     483    void firstIn(Edge& edge, const Node& node) const {
     484      if (Parent::lower(node)) {
     485        Parent::firstUp(edge, node);
     486        edge.forward = true;   
     487      } else {
     488        Parent::firstDown(edge, node);
     489        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     490      }
     491    }
     492    void nextIn(Edge& edge) const {
     493      if (edge.forward) {
     494        Parent::nextUp(edge);
     495      } else {
     496        Parent::nextDown(edge);
     497        if (edge == INVALID) {
     498          edge.forward = true;
     499        }       
     500      }
     501    }
     502
     503    Node source(const Edge& edge) const {
     504      return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
     505    }
     506    Node target(const Edge& edge) const {
     507      return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
     508    }
     509
     510    bool direction(const Edge& edge) const {
     511      return edge.forward;
     512    }
     513
     514    Edge direct(const UndirEdge& edge, const Node& node) const {
     515      return Edge(edge, node == Parent::source(edge));
     516    }
     517
     518    Edge direct(const UndirEdge& edge, bool direction) const {
     519      return Edge(edge, direction);
     520    }
     521
     522    Node oppositeNode(const UndirEdge& edge, const Node& node) const {
     523      return source(edge) == node ?
     524        target(edge) : source(edge);
     525    }
     526
     527    Edge oppositeEdge(const Edge& edge) const {
     528      return Edge(edge, !edge.forward);
     529    }
     530
     531    int id(const Edge& edge) const {
     532      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
     533    }
     534    Edge edgeFromId(int id) const {
     535      return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
     536    }
     537    int maxEdgeId() const {
     538      return (Parent::maxId(UndirEdge()) << 1) + 1;
     539    }
     540
     541    class UpperNode : public Node {
     542      friend class UndirBipartiteGraphExtender;
     543    public:
     544      UpperNode() {}
     545      UpperNode(const Node& node) : Node(node) {
     546        LEMON_ASSERT(Parent::upper(node) || node == INVALID,
     547                     typename Parent::NodeSetError());
     548      }
     549      UpperNode(Invalid) : Node(INVALID) {}
     550    };
     551
     552    void first(UpperNode& node) const {
     553      Parent::firstUpper(static_cast<Node&>(node));
     554    }
     555    void next(UpperNode& node) const {
     556      Parent::nextUpper(static_cast<Node&>(node));
     557    }
     558
     559    int id(const UpperNode& node) const {
     560      return Parent::upperId(node);
     561    }
     562
     563    class LowerNode : public Node {
     564      friend class UndirBipartiteGraphExtender;
     565    public:
     566      LowerNode() {}
     567      LowerNode(const Node& node) : Node(node) {
     568        LEMON_ASSERT(Parent::lower(node) || node == INVALID,
     569                     typename Parent::NodeSetError());
     570      }
     571      LowerNode(Invalid) : Node(INVALID) {}
     572    };
     573
     574    void first(LowerNode& node) const {
     575      Parent::firstLower(static_cast<Node&>(node));
     576    }
     577    void next(LowerNode& node) const {
     578      Parent::nextLower(static_cast<Node&>(node));
     579    }
     580 
     581    int id(const LowerNode& node) const {
     582      return Parent::upperId(node);
     583    }
     584
     585
     586
     587    int maxId(Node) const {
     588      return Parent::maxNodeId();
     589    }
     590    int maxId(LowerNode) const {
     591      return Parent::maxLowerId();
     592    }
     593    int maxId(UpperNode) const {
     594      return Parent::maxUpperId();
     595    }
     596    int maxId(Edge) const {
     597      return maxEdgeId();
     598    }
     599    int maxId(UndirEdge) const {
     600      return maxUndirEdgeId();
     601    }
     602
     603
     604    Node fromId(int id, Node) const {
     605      return Parent::nodeFromId(id);
     606    }
     607    UpperNode fromId(int id, UpperNode) const {
     608      return Parent::fromUpperId(id);
     609    }
     610    LowerNode fromId(int id, LowerNode) const {
     611      return Parent::fromLowerId(id);
     612    }
     613    Edge fromId(int id, Edge) const {
     614      return edgeFromId(id);
     615    }
     616    UndirEdge fromId(int id, UndirEdge) const {
     617      return undirEdgeFromId(id);
     618    }
     619
     620  };
     621
    379622}
    380623
  • lemon/bits/iterable_graph_extender.h

    r1704 r1820  
    268268
    269269  };
     270
     271
     272  template <typename _Base>
     273  class IterableUndirBipartiteGraphExtender : public _Base {
     274  public:
     275    typedef _Base Parent;
     276    typedef IterableUndirBipartiteGraphExtender Graph;
     277   
     278    typedef typename Parent::Node Node;
     279    typedef typename Parent::UpperNode UpperNode;
     280    typedef typename Parent::LowerNode LowerNode;
     281    typedef typename Parent::Edge Edge;
     282    typedef typename Parent::UndirEdge UndirEdge;
     283 
     284    class NodeIt : public Node {
     285      const Graph* graph;
     286    public:
     287   
     288      NodeIt() { }
     289   
     290      NodeIt(Invalid i) : Node(INVALID) { }
     291   
     292      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     293        graph->first(static_cast<Node&>(*this));
     294      }
     295
     296      NodeIt(const Graph& _graph, const Node& node)
     297        : Node(node), graph(&_graph) { }
     298   
     299      NodeIt& operator++() {
     300        graph->next(*this);
     301        return *this;
     302      }
     303
     304    };
     305
     306    class UpperNodeIt : public Node {
     307      friend class IterableUndirBipartiteGraphExtender;
     308      const Graph* graph;
     309    public:
     310   
     311      UpperNodeIt() { }
     312   
     313      UpperNodeIt(Invalid i) : Node(INVALID) { }
     314   
     315      explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {
     316        graph->firstUpper(static_cast<Node&>(*this));
     317      }
     318
     319      UpperNodeIt(const Graph& _graph, const Node& node)
     320        : Node(node), graph(&_graph) {}
     321   
     322      UpperNodeIt& operator++() {
     323        graph->nextUpper(*this);
     324        return *this;
     325      }
     326    };
     327
     328    class LowerNodeIt : public Node {
     329      friend class IterableUndirBipartiteGraphExtender;
     330      const Graph* graph;
     331    public:
     332   
     333      LowerNodeIt() { }
     334   
     335      LowerNodeIt(Invalid i) : Node(INVALID) { }
     336   
     337      explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {
     338        graph->firstLower(static_cast<Node&>(*this));
     339      }
     340
     341      LowerNodeIt(const Graph& _graph, const Node& node)
     342        : Node(node), graph(&_graph) {}
     343   
     344      LowerNodeIt& operator++() {
     345        graph->nextLower(*this);
     346        return *this;
     347      }
     348    };
     349
     350    class EdgeIt : public Edge {
     351      friend class IterableUndirBipartiteGraphExtender;
     352      const Graph* graph;
     353    public:
     354   
     355      EdgeIt() { }
     356   
     357      EdgeIt(Invalid i) : Edge(INVALID) { }
     358   
     359      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     360        graph->first(static_cast<Edge&>(*this));
     361      }
     362
     363      EdgeIt(const Graph& _graph, const Edge& edge)
     364        : Edge(edge), graph(&_graph) { }
     365   
     366      EdgeIt& operator++() {
     367        graph->next(*this);
     368        return *this;
     369      }
     370
     371    };
     372
     373    class UndirEdgeIt : public UndirEdge {
     374      friend class IterableUndirBipartiteGraphExtender;
     375      const Graph* graph;
     376    public:
     377   
     378      UndirEdgeIt() { }
     379   
     380      UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }
     381   
     382      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
     383        graph->first(static_cast<UndirEdge&>(*this));
     384      }
     385
     386      UndirEdgeIt(const Graph& _graph, const UndirEdge& edge)
     387        : UndirEdge(edge), graph(&_graph) { }
     388   
     389      UndirEdgeIt& operator++() {
     390        graph->next(*this);
     391        return *this;
     392      }
     393    };
     394
     395    class OutEdgeIt : public Edge {
     396      friend class IterableUndirBipartiteGraphExtender;
     397      const Graph* graph;
     398    public:
     399   
     400      OutEdgeIt() { }
     401   
     402      OutEdgeIt(Invalid i) : Edge(i) { }
     403   
     404      OutEdgeIt(const Graph& _graph, const Node& node)
     405        : graph(&_graph) {
     406        graph->firstOut(*this, node);
     407      }
     408   
     409      OutEdgeIt(const Graph& _graph, const Edge& edge)
     410        : Edge(edge), graph(&_graph) {}
     411   
     412      OutEdgeIt& operator++() {
     413        graph->nextOut(*this);
     414        return *this;
     415      }
     416
     417    };
     418
     419
     420    class InEdgeIt : public Edge {
     421      friend class IterableUndirBipartiteGraphExtender;
     422      const Graph* graph;
     423    public:
     424   
     425      InEdgeIt() { }
     426   
     427      InEdgeIt(Invalid i) : Edge(i) { }
     428   
     429      InEdgeIt(const Graph& _graph, const Node& node)
     430        : graph(&_graph) {
     431        graph->firstIn(*this, node);
     432      }
     433   
     434      InEdgeIt(const Graph& _graph, const Edge& edge) :
     435        Edge(edge), graph(&_graph) {}
     436   
     437      InEdgeIt& operator++() {
     438        graph->nextIn(*this);
     439        return *this;
     440      }
     441
     442    };
     443 
     444    /// \brief Base node of the iterator
     445    ///
     446    /// Returns the base node (ie. the source in this case) of the iterator
     447    Node baseNode(const OutEdgeIt &e) const {
     448      return Parent::source((Edge&)e);
     449    }
     450    /// \brief Running node of the iterator
     451    ///
     452    /// Returns the running node (ie. the target in this case) of the
     453    /// iterator
     454    Node runningNode(const OutEdgeIt &e) const {
     455      return Parent::target((Edge&)e);
     456    }
     457 
     458    /// \brief Base node of the iterator
     459    ///
     460    /// Returns the base node (ie. the target in this case) of the iterator
     461    Node baseNode(const InEdgeIt &e) const {
     462      return Parent::target((Edge&)e);
     463    }
     464    /// \brief Running node of the iterator
     465    ///
     466    /// Returns the running node (ie. the source in this case) of the
     467    /// iterator
     468    Node runningNode(const InEdgeIt &e) const {
     469      return Parent::source((Edge&)e);
     470    }
     471 
     472    class IncEdgeIt : public Parent::UndirEdge {
     473      friend class IterableUndirBipartiteGraphExtender;
     474      const Graph* graph;
     475      bool direction;
     476    public:
     477   
     478      IncEdgeIt() { }
     479   
     480      IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }
     481   
     482      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     483        graph->firstInc(*this, direction, n);
     484      }
     485
     486      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
     487        : graph(&_graph), UndirEdge(ue) {
     488        direction = (graph->source(ue) == n);
     489      }
     490
     491      IncEdgeIt& operator++() {
     492        graph->nextInc(*this, direction);
     493        return *this;
     494      }
     495    };
     496 
     497
     498    /// Base node of the iterator
     499    ///
     500    /// Returns the base node of the iterator
     501    Node baseNode(const IncEdgeIt &e) const {
     502      return e.direction ? source(e) : target(e);
     503    }
     504
     505    /// Running node of the iterator
     506    ///
     507    /// Returns the running node of the iterator
     508    Node runningNode(const IncEdgeIt &e) const {
     509      return e.direction ? target(e) : source(e);
     510    }
     511 
     512  };
     513
    270514}
    271515
Note: See TracChangeset for help on using the changeset viewer.