COIN-OR::LEMON - Graph Library

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


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

File:
1 edited

Legend:

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