COIN-OR::LEMON - Graph Library

Changeset 1910:f95eea8c34b0 in lemon-0.x for lemon/smart_graph.h


Ignore:
Timestamp:
01/26/06 17:24:40 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2485
Message:

Bipartite => Bp
Upper => A
Lower => B

+ some bug fix

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r1909 r1910  
    379379
    380380
    381   class SmartUBipartiteGraphBase {
     381  class SmartBpUGraphBase {
    382382  public:
    383383
    384384    class NodeSetError : public LogicError {
    385385      virtual const char* exceptionName() const {
    386         return "lemon::FullUBipartiteGraph::NodeSetError";
     386        return "lemon::SmartBpUGraph::NodeSetError";
    387387      }
    388388    };
     
    397397
    398398    struct EdgeT {
    399       int upper, next_down;
    400       int lower, next_up;
    401     };
    402 
    403     std::vector<NodeT> upperNodes;
    404     std::vector<NodeT> lowerNodes;
     399      int aNode, next_out;
     400      int bNode, next_in;
     401    };
     402
     403    std::vector<NodeT> aNodes;
     404    std::vector<NodeT> bNodes;
    405405
    406406    std::vector<EdgeT> edges;
     
    409409 
    410410    class Node {
    411       friend class SmartUBipartiteGraphBase;
     411      friend class SmartBpUGraphBase;
    412412    protected:
    413413      int id;
     
    423423
    424424    class Edge {
    425       friend class SmartUBipartiteGraphBase;
     425      friend class SmartBpUGraphBase;
    426426    protected:
    427427      int id;
     
    436436    };
    437437
    438     void firstUpper(Node& node) const {
    439       node.id = 2 * upperNodes.size() - 2;
     438    void firstANode(Node& node) const {
     439      node.id = 2 * aNodes.size() - 2;
    440440      if (node.id < 0) node.id = -1;
    441441    }
    442     void nextUpper(Node& node) const {
     442    void nextANode(Node& node) const {
    443443      node.id -= 2;
    444444      if (node.id < 0) node.id = -1;
    445445    }
    446446
    447     void firstLower(Node& node) const {
    448       node.id = 2 * lowerNodes.size() - 1;
    449     }
    450     void nextLower(Node& node) const {
     447    void firstBNode(Node& node) const {
     448      node.id = 2 * bNodes.size() - 1;
     449    }
     450    void nextBNode(Node& node) const {
    451451      node.id -= 2;
    452452    }
    453453
    454454    void first(Node& node) const {
    455       if (upperNodes.size() > 0) {
    456         node.id = 2 * upperNodes.size() - 2;
     455      if (aNodes.size() > 0) {
     456        node.id = 2 * aNodes.size() - 2;
    457457      } else {
    458         node.id = 2 * lowerNodes.size() - 1;
     458        node.id = 2 * bNodes.size() - 1;
    459459      }
    460460    }
     
    462462      node.id -= 2;
    463463      if (node.id == -2) {
    464         node.id = 2 * lowerNodes.size() - 1;
     464        node.id = 2 * bNodes.size() - 1;
    465465      }
    466466    }
     
    473473    }
    474474
    475     void firstDown(Edge& edge, const Node& node) const {
     475    void firstOut(Edge& edge, const Node& node) const {
    476476      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    477       edge.id = upperNodes[node.id >> 1].first;
    478     }
    479     void nextDown(Edge& edge) const {
    480       edge.id = edges[edge.id].next_down;
    481     }
    482 
    483     void firstUp(Edge& edge, const Node& node) const {
     477      edge.id = aNodes[node.id >> 1].first;
     478    }
     479    void nextOut(Edge& edge) const {
     480      edge.id = edges[edge.id].next_out;
     481    }
     482
     483    void firstIn(Edge& edge, const Node& node) const {
    484484      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    485       edge.id = lowerNodes[node.id >> 1].first;
    486     }
    487     void nextUp(Edge& edge) const {
    488       edge.id = edges[edge.id].next_up;
     485      edge.id = bNodes[node.id >> 1].first;
     486    }
     487    void nextIn(Edge& edge) const {
     488      edge.id = edges[edge.id].next_in;
    489489    }
    490490
     
    496496    }
    497497    int maxNodeId() const {
    498       return upperNodes.size() > lowerNodes.size() ?
    499         upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
     498      return aNodes.size() > bNodes.size() ?
     499        aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
    500500    }
    501501 
     
    510510    }
    511511 
    512     static int upperId(const Node& node) {
     512    static int aNodeId(const Node& node) {
    513513      return node.id >> 1;
    514514    }
    515     static Node fromUpperId(int id, Node) {
     515    static Node fromANodeId(int id, Node) {
    516516      return Node(id << 1);
    517517    }
    518     int maxUpperId() const {
    519       return upperNodes.size();
    520     }
    521 
    522     static int lowerId(const Node& node) {
     518    int maxANodeId() const {
     519      return aNodes.size();
     520    }
     521
     522    static int bNodeId(const Node& node) {
    523523      return node.id >> 1;
    524524    }
    525     static Node fromLowerId(int id) {
     525    static Node fromBNodeId(int id) {
    526526      return Node((id << 1) + 1);
    527527    }
    528     int maxLowerId() const {
    529       return lowerNodes.size();
    530     }
    531 
    532     Node upperNode(const Edge& edge) const {
    533       return Node(edges[edge.id].upper);
    534     }
    535     Node lowerNode(const Edge& edge) const {
    536       return Node(edges[edge.id].lower);
    537     }
    538 
    539     static bool upper(const Node& node) {
     528    int maxBNodeId() const {
     529      return bNodes.size();
     530    }
     531
     532    Node aNode(const Edge& edge) const {
     533      return Node(edges[edge.id].aNode);
     534    }
     535    Node bNode(const Edge& edge) const {
     536      return Node(edges[edge.id].bNode);
     537    }
     538
     539    static bool aNode(const Node& node) {
    540540      return (node.id & 1) == 0;
    541541    }
    542542
    543     static bool lower(const Node& node) {
     543    static bool bNode(const Node& node) {
    544544      return (node.id & 1) == 1;
    545545    }
    546546
    547     Node addUpperNode() {
     547    Node addANode() {
    548548      NodeT nodeT;
    549549      nodeT.first = -1;
    550       upperNodes.push_back(nodeT);
    551       return Node(upperNodes.size() * 2 - 2);
    552     }
    553 
    554     Node addLowerNode() {
     550      aNodes.push_back(nodeT);
     551      return Node(aNodes.size() * 2 - 2);
     552    }
     553
     554    Node addBNode() {
    555555      NodeT nodeT;
    556556      nodeT.first = -1;
    557       lowerNodes.push_back(nodeT);
    558       return Node(lowerNodes.size() * 2 - 1);
     557      bNodes.push_back(nodeT);
     558      return Node(bNodes.size() * 2 - 1);
    559559    }
    560560
     
    563563      EdgeT edgeT;
    564564      if ((source.id & 1) == 0) {
    565         edgeT.upper = source.id;
    566         edgeT.lower = target.id;
     565        edgeT.aNode = source.id;
     566        edgeT.bNode = target.id;
    567567      } else {
    568         edgeT.upper = target.id;
    569         edgeT.lower = source.id;
    570       }
    571       edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
    572       upperNodes[edgeT.upper >> 1].first = edges.size();
    573       edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
    574       lowerNodes[edgeT.lower >> 1].first = edges.size();
     568        edgeT.aNode = target.id;
     569        edgeT.bNode = source.id;
     570      }
     571      edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
     572      aNodes[edgeT.aNode >> 1].first = edges.size();
     573      edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
     574      bNodes[edgeT.bNode >> 1].first = edges.size();
    575575      edges.push_back(edgeT);
    576576      return Edge(edges.size() - 1);
     
    578578
    579579    void clear() {
    580       upperNodes.clear();
    581       lowerNodes.clear();
     580      aNodes.clear();
     581      bNodes.clear();
    582582      edges.clear();
    583583    }
     
    586586
    587587
    588   typedef ClearableUBipartiteGraphExtender<
    589     ExtendableUBipartiteGraphExtender<
    590     MappableUBipartiteGraphExtender<
    591     IterableUBipartiteGraphExtender<
    592     AlterableUBipartiteGraphExtender<
    593     UBipartiteGraphExtender <
    594     SmartUBipartiteGraphBase> > > > > >
    595   ExtendedSmartUBipartiteGraphBase;
    596 
    597 
    598   class SmartUBipartiteGraph :
    599     public ExtendedSmartUBipartiteGraphBase {
    600   };
     588  typedef ClearableBpUGraphExtender<
     589    ExtendableBpUGraphExtender<
     590    MappableBpUGraphExtender<
     591    IterableBpUGraphExtender<
     592    AlterableBpUGraphExtender<
     593    BpUGraphExtender <
     594    SmartBpUGraphBase> > > > > >
     595  ExtendedSmartBpUGraphBase;
     596
     597  /// \ingroup graphs
     598  ///
     599  /// \brief A smart bipartite undirected graph class.
     600  ///
     601  /// This is a simple and fast bipartite undirected graph implementation.
     602  /// It is also quite memory efficient, but at the price
     603  /// that <b> it does not support node and edge deletions</b>.
     604  /// Except from this it conforms to
     605  /// the \ref concept::BpUGraph "BpUGraph" concept.
     606  /// \sa concept::BpUGraph.
     607  ///
     608  class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
    601609
    602610 
Note: See TracChangeset for help on using the changeset viewer.