COIN-OR::LEMON - Graph Library

Changeset 1820:22099ef840d7 in lemon-0.x


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
Files:
8 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
  • lemon/full_graph.h

    r1791 r1820  
    403403  };
    404404
     405
     406  class FullUndirBipartiteGraphBase {
     407  protected:
     408
     409    int _upperNodeNum;
     410    int _lowerNodeNum;
     411
     412    int _edgeNum;
     413
     414  public:
     415
     416    class NodeSetError : public LogicError {
     417      virtual const char* exceptionName() const {
     418        return "lemon::FullUndirBipartiteGraph::NodeSetError";
     419      }
     420    };
     421 
     422    class Node {
     423      friend class FullUndirBipartiteGraphBase;
     424    protected:
     425      int id;
     426
     427      Node(int _id) : id(_id) {}
     428    public:
     429      Node() {}
     430      Node(Invalid) { id = -1; }
     431      bool operator==(const Node i) const {return id==i.id;}
     432      bool operator!=(const Node i) const {return id!=i.id;}
     433      bool operator<(const Node i) const {return id<i.id;}
     434    };
     435
     436    class Edge {
     437      friend class FullUndirBipartiteGraphBase;
     438    protected:
     439      int id;
     440
     441      Edge(int _id) { id = _id;}
     442    public:
     443      Edge() {}
     444      Edge (Invalid) { id = -1; }
     445      bool operator==(const Edge i) const {return id==i.id;}
     446      bool operator!=(const Edge i) const {return id!=i.id;}
     447      bool operator<(const Edge i) const {return id<i.id;}
     448    };
     449
     450    void construct(int upperNodeNum, int lowerNodeNum) {
     451      _upperNodeNum = upperNodeNum;
     452      _lowerNodeNum = lowerNodeNum;
     453      _edgeNum = upperNodeNum * lowerNodeNum;
     454    }
     455
     456    void firstUpper(Node& node) const {
     457      node.id = 2 * _upperNodeNum - 2;
     458      if (node.id < 0) node.id = -1;
     459    }
     460    void nextUpper(Node& node) const {
     461      node.id -= 2;
     462      if (node.id < 0) node.id = -1;
     463    }
     464
     465    void firstLower(Node& node) const {
     466      node.id = 2 * _lowerNodeNum - 1;
     467    }
     468    void nextLower(Node& node) const {
     469      node.id -= 2;
     470    }
     471
     472    void first(Node& node) const {
     473      if (_upperNodeNum > 0) {
     474        node.id = 2 * _upperNodeNum - 2;
     475      } else {
     476        node.id = 2 * _lowerNodeNum - 1;
     477      }
     478    }
     479    void next(Node& node) const {
     480      node.id -= 2;
     481      if (node.id == -2) {
     482        node.id = 2 * _lowerNodeNum - 1;
     483      }
     484    }
     485 
     486    void first(Edge& edge) const {
     487      edge.id = _edgeNum - 1;
     488    }
     489    void next(Edge& edge) const {
     490      --edge.id;
     491    }
     492
     493    void firstDown(Edge& edge, const Node& node) const {
     494      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     495      edge.id = (node.id >> 1) * _lowerNodeNum;
     496    }
     497    void nextDown(Edge& edge) const {
     498      ++(edge.id);
     499      if (edge.id % _lowerNodeNum == 0) edge.id = -1;
     500    }
     501
     502    void firstUp(Edge& edge, const Node& node) const {
     503      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     504      edge.id = (node.id >> 1);
     505    }
     506    void nextUp(Edge& edge) const {
     507      edge.id += _lowerNodeNum;
     508      if (edge.id >= _edgeNum) edge.id = -1;
     509    }
     510
     511    static int id(const Node& node) {
     512      return node.id;
     513    }
     514    static Node nodeFromId(int id) {
     515      return Node(id);
     516    }
     517    int maxNodeId() const {
     518      return _upperNodeNum > _lowerNodeNum ?
     519        _upperNodeNum * 2 - 2 : _lowerNodeNum * 2 - 1;
     520    }
     521 
     522    static int id(const Edge& edge) {
     523      return edge.id;
     524    }
     525    static Edge edgeFromId(int id) {
     526      return Edge(id);
     527    }
     528    int maxEdgeId() const {
     529      return _edgeNum - 1;
     530    }
     531 
     532    static int upperId(const Node& node) {
     533      return node.id >> 1;
     534    }
     535    static Node fromUpperId(int id, Node) {
     536      return Node(id << 1);
     537    }
     538    int maxUpperId() const {
     539      return _upperNodeNum;
     540    }
     541
     542    static int lowerId(const Node& node) {
     543      return node.id >> 1;
     544    }
     545    static Node fromLowerId(int id) {
     546      return Node((id << 1) + 1);
     547    }
     548    int maxLowerId() const {
     549      return _lowerNodeNum;
     550    }
     551
     552    Node upperNode(const Edge& edge) const {
     553      return Node((edge.id / _lowerNodeNum) << 1);
     554    }
     555    Node lowerNode(const Edge& edge) const {
     556      return Node(((edge.id % _lowerNodeNum) << 1) + 1);
     557    }
     558
     559    static bool upper(const Node& node) {
     560      return (node.id & 1) == 0;
     561    }
     562
     563    static bool lower(const Node& node) {
     564      return (node.id & 1) == 1;
     565    }
     566
     567    static Node upperNode(int index) {
     568      return Node(index << 1);
     569    }
     570
     571    static Node lowerNode(int index) {
     572      return Node((index << 1) + 1);
     573    }
     574
     575  };
     576
     577
     578  typedef MappableUndirBipartiteGraphExtender<
     579    IterableUndirBipartiteGraphExtender<
     580    AlterableUndirBipartiteGraphExtender<
     581    UndirBipartiteGraphExtender <
     582    FullUndirBipartiteGraphBase> > > >
     583  ExtendedFullUndirBipartiteGraphBase;
     584
     585
     586  class FullUndirBipartiteGraph :
     587    public ExtendedFullUndirBipartiteGraphBase {
     588  public:
     589    typedef ExtendedFullUndirBipartiteGraphBase Parent;
     590    FullUndirBipartiteGraph(int upperNodeNum, int lowerNodeNum) {
     591      Parent::construct(upperNodeNum, lowerNodeNum);
     592    }
     593  };
     594
    405595} //namespace lemon
    406596
  • lemon/smart_graph.h

    r1791 r1820  
    3434
    3535#include <lemon/utility.h>
     36#include <lemon/error.h>
    3637
    3738namespace lemon {
     
    375376  };
    376377
     378
     379  class SmartUndirBipartiteGraphBase {
     380  public:
     381
     382    class NodeSetError : public LogicError {
     383      virtual const char* exceptionName() const {
     384        return "lemon::FullUndirBipartiteGraph::NodeSetError";
     385      }
     386    };
     387
     388  protected:
     389
     390    struct NodeT {
     391      int first;
     392      NodeT() {}
     393      NodeT(int _first) : first(_first) {}
     394    };
     395
     396    struct EdgeT {
     397      int upper, next_down;
     398      int lower, next_up;
     399    };
     400
     401    std::vector<NodeT> upperNodes;
     402    std::vector<NodeT> lowerNodes;
     403
     404    std::vector<EdgeT> edges;
     405
     406  public:
     407 
     408    class Node {
     409      friend class SmartUndirBipartiteGraphBase;
     410    protected:
     411      int id;
     412
     413      Node(int _id) : id(_id) {}
     414    public:
     415      Node() {}
     416      Node(Invalid) { id = -1; }
     417      bool operator==(const Node i) const {return id==i.id;}
     418      bool operator!=(const Node i) const {return id!=i.id;}
     419      bool operator<(const Node i) const {return id<i.id;}
     420    };
     421
     422    class Edge {
     423      friend class SmartUndirBipartiteGraphBase;
     424    protected:
     425      int id;
     426
     427      Edge(int _id) { id = _id;}
     428    public:
     429      Edge() {}
     430      Edge (Invalid) { id = -1; }
     431      bool operator==(const Edge i) const {return id==i.id;}
     432      bool operator!=(const Edge i) const {return id!=i.id;}
     433      bool operator<(const Edge i) const {return id<i.id;}
     434    };
     435
     436    void firstUpper(Node& node) const {
     437      node.id = 2 * upperNodes.size() - 2;
     438      if (node.id < 0) node.id = -1;
     439    }
     440    void nextUpper(Node& node) const {
     441      node.id -= 2;
     442      if (node.id < 0) node.id = -1;
     443    }
     444
     445    void firstLower(Node& node) const {
     446      node.id = 2 * lowerNodes.size() - 1;
     447    }
     448    void nextLower(Node& node) const {
     449      node.id -= 2;
     450    }
     451
     452    void first(Node& node) const {
     453      if (upperNodes.size() > 0) {
     454        node.id = 2 * upperNodes.size() - 2;
     455      } else {
     456        node.id = 2 * lowerNodes.size() - 1;
     457      }
     458    }
     459    void next(Node& node) const {
     460      node.id -= 2;
     461      if (node.id == -2) {
     462        node.id = 2 * lowerNodes.size() - 1;
     463      }
     464    }
     465 
     466    void first(Edge& edge) const {
     467      edge.id = edges.size() - 1;
     468    }
     469    void next(Edge& edge) const {
     470      --edge.id;
     471    }
     472
     473    void firstDown(Edge& edge, const Node& node) const {
     474      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
     475      edge.id = upperNodes[node.id >> 1].first;
     476    }
     477    void nextDown(Edge& edge) const {
     478      edge.id = edges[edge.id].next_down;
     479    }
     480
     481    void firstUp(Edge& edge, const Node& node) const {
     482      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
     483      edge.id = lowerNodes[node.id >> 1].first;
     484    }
     485    void nextUp(Edge& edge) const {
     486      edge.id = edges[edge.id].next_up;
     487    }
     488
     489    static int id(const Node& node) {
     490      return node.id;
     491    }
     492    static Node nodeFromId(int id) {
     493      return Node(id);
     494    }
     495    int maxNodeId() const {
     496      return upperNodes.size() > lowerNodes.size() ?
     497        upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
     498    }
     499 
     500    static int id(const Edge& edge) {
     501      return edge.id;
     502    }
     503    static Edge edgeFromId(int id) {
     504      return Edge(id);
     505    }
     506    int maxEdgeId() const {
     507      return edges.size();
     508    }
     509 
     510    static int upperId(const Node& node) {
     511      return node.id >> 1;
     512    }
     513    static Node fromUpperId(int id, Node) {
     514      return Node(id << 1);
     515    }
     516    int maxUpperId() const {
     517      return upperNodes.size();
     518    }
     519
     520    static int lowerId(const Node& node) {
     521      return node.id >> 1;
     522    }
     523    static Node fromLowerId(int id) {
     524      return Node((id << 1) + 1);
     525    }
     526    int maxLowerId() const {
     527      return lowerNodes.size();
     528    }
     529
     530    Node upperNode(const Edge& edge) const {
     531      return Node(edges[edge.id].upper);
     532    }
     533    Node lowerNode(const Edge& edge) const {
     534      return Node(edges[edge.id].lower);
     535    }
     536
     537    static bool upper(const Node& node) {
     538      return (node.id & 1) == 0;
     539    }
     540
     541    static bool lower(const Node& node) {
     542      return (node.id & 1) == 1;
     543    }
     544
     545    Node addUpperNode() {
     546      NodeT nodeT;
     547      nodeT.first = -1;
     548      upperNodes.push_back(nodeT);
     549      return Node(upperNodes.size() * 2 - 2);
     550    }
     551
     552    Node addLowerNode() {
     553      NodeT nodeT;
     554      nodeT.first = -1;
     555      lowerNodes.push_back(nodeT);
     556      return Node(lowerNodes.size() * 2 - 1);
     557    }
     558
     559    Edge addEdge(const Node& source, const Node& target) {
     560      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
     561      EdgeT edgeT;
     562      if ((source.id & 1) == 0) {
     563        edgeT.upper = source.id;
     564        edgeT.lower = target.id;
     565      } else {
     566        edgeT.upper = target.id;
     567        edgeT.lower = source.id;
     568      }
     569      edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
     570      upperNodes[edgeT.upper >> 1].first = edges.size();
     571      edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
     572      lowerNodes[edgeT.lower >> 1].first = edges.size();
     573      edges.push_back(edgeT);
     574      return Edge(edges.size() - 1);
     575    }
     576
     577    void clear() {
     578      upperNodes.clear();
     579      lowerNodes.clear();
     580      edges.clear();
     581    }
     582
     583  };
     584
     585
     586  typedef ClearableUndirBipartiteGraphExtender<
     587    ExtendableUndirBipartiteGraphExtender<
     588    MappableUndirBipartiteGraphExtender<
     589    IterableUndirBipartiteGraphExtender<
     590    AlterableUndirBipartiteGraphExtender<
     591    UndirBipartiteGraphExtender <
     592    SmartUndirBipartiteGraphBase> > > > > >
     593  ExtendedSmartUndirBipartiteGraphBase;
     594
     595
     596  class SmartUndirBipartiteGraph :
     597    public ExtendedSmartUndirBipartiteGraphBase {
     598  };
     599
    377600 
    378601  /// @} 
Note: See TracChangeset for help on using the changeset viewer.