COIN-OR::LEMON - Graph Library

Changeset 1820:22099ef840d7 in lemon-0.x for lemon/smart_graph.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/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.