COIN-OR::LEMON - Graph Library

Changeset 1025:c8fa41fcc4a7 in lemon-main


Ignore:
Timestamp:
12/01/11 09:05:47 (13 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Type safe red and blue node set (#69)

Files:
10 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r1020 r1025  
    761761
    762762    typedef typename Parent::Node Node;
     763    typedef typename Parent::RedNode RedNode;
     764    typedef typename Parent::BlueNode BlueNode;
    763765    typedef typename Parent::Arc Arc;
    764766    typedef typename Parent::Edge Edge;
     
    766768    // BpGraph extension
    767769
    768     class RedNode : public Node {
    769     public:
    770       RedNode() {}
    771       RedNode(const RedNode& node) : Node(node) {}
    772       RedNode(Invalid) : Node(INVALID){}
    773       RedNode(const Node& node) : Node(node) {}
    774     };
    775     class BlueNode : public Node {
    776     public:
    777       BlueNode() {}
    778       BlueNode(const BlueNode& node) : Node(node) {}
    779       BlueNode(Invalid) : Node(INVALID){}
    780       BlueNode(const Node& node) : Node(node) {}
    781     };
    782 
    783770    using Parent::first;
    784771    using Parent::next;
    785 
    786     void first(RedNode& node) const {
    787       Parent::firstRed(node);
    788     }
    789    
    790     void next(RedNode& node) const {
    791       Parent::nextRed(node);
    792     }
    793 
    794     void first(BlueNode& node) const {
    795       Parent::firstBlue(node);
    796     }
    797 
    798     void next(BlueNode& node) const {
    799       Parent::nextBlue(node);
    800     }
    801 
    802772    using Parent::id;
    803 
    804     int id(const RedNode& node) const {
    805       return Parent::redId(node);
    806     }
    807 
    808     int id(const BlueNode& node) const {
    809       return Parent::blueId(node);
    810     }
    811773
    812774    int maxId(Node) const {
     
    863825    }
    864826
     827    RedNode asRedNode(const Node& node) const {
     828      if (node == INVALID || Parent::blue(node)) {
     829        return INVALID;
     830      } else {
     831        return Parent::asRedNodeUnsafe(node);
     832      }
     833    }
     834
     835    BlueNode asBlueNode(const Node& node) const {
     836      if (node == INVALID || Parent::red(node)) {
     837        return INVALID;
     838      } else {
     839        return Parent::asBlueNodeUnsafe(node);
     840      }
     841    }
     842
     843    std::pair<RedNode, BlueNode> asRedBlueNode(const Node& node) const {
     844      if (node == INVALID) {
     845        return std::make_pair(RedNode(INVALID), BlueNode(INVALID));
     846      } else if (Parent::red(node)) {
     847        return std::make_pair(Parent::asRedNodeUnsafe(node), BlueNode(INVALID));
     848      } else {
     849        return std::make_pair(RedNode(INVALID), Parent::asBlueNodeUnsafe(node));
     850      }
     851    }
     852
    865853    // Alterable extension
    866854
     
    926914    };
    927915
    928     class RedIt : public Node {
     916    class RedIt : public RedNode {
    929917      const BpGraph* _graph;
    930918    public:
     
    932920      RedIt() {}
    933921
    934       RedIt(Invalid i) : Node(i) { }
     922      RedIt(Invalid i) : RedNode(i) { }
    935923
    936924      explicit RedIt(const BpGraph& graph) : _graph(&graph) {
    937         _graph->firstRed(static_cast<Node&>(*this));
    938       }
    939 
    940       RedIt(const BpGraph& graph, const Node& node)
    941         : Node(node), _graph(&graph) {
    942         LEMON_DEBUG(_graph->red(node), "Node has to be red.");
    943       }
     925        _graph->first(static_cast<RedNode&>(*this));
     926      }
     927
     928      RedIt(const BpGraph& graph, const RedNode& node)
     929        : RedNode(node), _graph(&graph) {}
    944930
    945931      RedIt& operator++() {
    946         _graph->nextRed(*this);
    947         return *this;
    948       }
    949 
    950     };
    951 
    952     class BlueIt : public Node {
     932        _graph->next(static_cast<RedNode&>(*this));
     933        return *this;
     934      }
     935
     936    };
     937
     938    class BlueIt : public BlueNode {
    953939      const BpGraph* _graph;
    954940    public:
     
    956942      BlueIt() {}
    957943
    958       BlueIt(Invalid i) : Node(i) { }
     944      BlueIt(Invalid i) : BlueNode(i) { }
    959945
    960946      explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
    961         _graph->firstBlue(static_cast<Node&>(*this));
    962       }
    963 
    964       BlueIt(const BpGraph& graph, const Node& node)
    965         : Node(node), _graph(&graph) {
    966         LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
    967       }
     947        _graph->first(static_cast<BlueNode&>(*this));
     948      }
     949
     950      BlueIt(const BpGraph& graph, const BlueNode& node)
     951        : BlueNode(node), _graph(&graph) {}
    968952
    969953      BlueIt& operator++() {
    970         _graph->nextBlue(*this);
     954        _graph->next(static_cast<BlueNode&>(*this));
    971955        return *this;
    972956      }
     
    12591243    // Alteration extension
    12601244
    1261     Node addRedNode() {
    1262       Node node = Parent::addRedNode();
     1245    RedNode addRedNode() {
     1246      RedNode node = Parent::addRedNode();
    12631247      notifier(RedNode()).add(node);
    12641248      notifier(Node()).add(node);
     
    12661250    }
    12671251
    1268     Node addBlueNode() {
    1269       Node node = Parent::addBlueNode();
     1252    BlueNode addBlueNode() {
     1253      BlueNode node = Parent::addBlueNode();
    12701254      notifier(BlueNode()).add(node);
    12711255      notifier(Node()).add(node);
     
    12731257    }
    12741258
    1275     Edge addEdge(const Node& from, const Node& to) {
     1259    Edge addEdge(const RedNode& from, const BlueNode& to) {
    12761260      Edge edge = Parent::addEdge(from, to);
    12771261      notifier(Edge()).add(edge);
     
    13181302
    13191303      if (Parent::red(node)) {
    1320         notifier(RedNode()).erase(node);
     1304        notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
    13211305      } else {
    1322         notifier(BlueNode()).erase(node);       
     1306        notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
    13231307      }
    13241308
  • lemon/concepts/bpgraph.h

    r1018 r1025  
    150150        RedNode(Invalid) { }
    151151
    152         /// Constructor for conversion from a node.
    153 
    154         /// Constructor for conversion from a node. The conversion can
    155         /// be invalid, since the Node can be member of the blue
    156         /// set.
    157         RedNode(const Node&) {}
    158152      };
    159153
     
    183177        BlueNode(Invalid) { }
    184178
    185         /// Constructor for conversion from a node.
    186 
    187         /// Constructor for conversion from a node. The conversion can
    188         /// be invalid, since the Node can be member of the red
    189         /// set.
    190         BlueNode(const Node&) {}
    191179      };
    192180
     
    200188      /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
    201189      ///\endcode
    202       class RedIt : public Node {
     190      class RedIt : public RedNode {
    203191      public:
    204192        /// Default constructor
     
    211199        /// Copy constructor.
    212200        ///
    213         RedIt(const RedIt& n) : Node(n) { }
     201        RedIt(const RedIt& n) : RedNode(n) { }
    214202        /// %Invalid constructor \& conversion.
    215203
     
    226214        /// Sets the iterator to the given red node of the given
    227215        /// digraph.
    228         RedIt(const BpGraph&, const Node&) { }
     216        RedIt(const BpGraph&, const RedNode&) { }
    229217        /// Next node.
    230218
     
    243231      /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
    244232      ///\endcode
    245       class BlueIt : public Node {
     233      class BlueIt : public BlueNode {
    246234      public:
    247235        /// Default constructor
     
    254242        /// Copy constructor.
    255243        ///
    256         BlueIt(const BlueIt& n) : Node(n) { }
     244        BlueIt(const BlueIt& n) : BlueNode(n) { }
    257245        /// %Invalid constructor \& conversion.
    258246
     
    269257        /// Sets the iterator to the given blue node of the given
    270258        /// digraph.
    271         BlueIt(const BpGraph&, const Node&) { }
     259        BlueIt(const BpGraph&, const BlueNode&) { }
    272260        /// Next node.
    273261
     
    785773      bool blue(const Node&) const { return true; }
    786774
     775      /// \brief Converts the node to red node object.
     776      ///
     777      /// This class is converts unsafely the node to red node
     778      /// object. It should be called only if the node is from the red
     779      /// partition or INVALID.
     780      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
     781
     782      /// \brief Converts the node to blue node object.
     783      ///
     784      /// This class is converts unsafely the node to blue node
     785      /// object. It should be called only if the node is from the red
     786      /// partition or INVALID.
     787      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
     788
     789      /// \brief Converts the node to red node object.
     790      ///
     791      /// This class is converts safely the node to red node
     792      /// object. If the node is not from the red partition, then it
     793      /// returns INVALID.
     794      RedNode asRedNode(const Node&) const { return RedNode(); }
     795
     796      /// \brief Converts the node to blue node object.
     797      ///
     798      /// This class is converts unsafely the node to blue node
     799      /// object. If the node is not from the blue partition, then it
     800      /// returns INVALID.
     801      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
     802
     803      /// \brief Convert the node to either red or blue node.
     804      ///
     805      /// If the node is from the red partition then it is returned in
     806      /// first and second is INVALID. If the node is from the blue
     807      /// partition then it is returned in second and first is
     808      /// INVALID. If the node INVALID then both first and second are
     809      /// INVALID in the return value.
     810      std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
     811        return std::make_pair(RedNode(), BlueNode());
     812      }
     813
    787814      /// \brief Gives back the red end node of the edge.
    788815      ///
    789816      /// Gives back the red end node of the edge.
    790       Node redNode(const Edge&) const { return Node(); }
     817      RedNode redNode(const Edge&) const { return RedNode(); }
    791818
    792819      /// \brief Gives back the blue end node of the edge.
    793820      ///
    794821      /// Gives back the blue end node of the edge.
    795       Node blueNode(const Edge&) const { return Node(); }
     822      BlueNode blueNode(const Edge&) const { return BlueNode(); }
    796823
    797824      /// \brief The first node of the edge.
     
    823850      ///
    824851      /// Returns the red ID of the given node.
    825       int redId(Node) const { return -1; }
    826 
    827       /// \brief The red ID of the node.
    828       ///
    829       /// Returns the red ID of the given node.
    830852      int id(RedNode) const { return -1; }
    831 
    832       /// \brief The blue ID of the node.
    833       ///
    834       /// Returns the blue ID of the given node.
    835       int blueId(Node) const { return -1; }
    836853
    837854      /// \brief The blue ID of the node.
     
    929946      void next(Node&) const {}
    930947
    931       void firstRed(Node&) const {}
    932       void nextRed(Node&) const {}
    933 
    934       void firstBlue(Node&) const {}
    935       void nextBlue(Node&) const {}
     948      void firstRed(RedNode&) const {}
     949      void nextRed(RedNode&) const {}
     950
     951      void firstBlue(BlueNode&) const {}
     952      void nextBlue(BlueNode&) const {}
    936953
    937954      void first(Edge&) const {}
  • lemon/concepts/graph_components.h

    r1018 r1025  
    318318      /// \brief Class to represent red nodes.
    319319      ///
    320       /// This class represents the red nodes of the graph. It does
    321       /// not supposed to be used directly, because the nodes can be
    322       /// represented as Node instances. This class can be used as
    323       /// template parameter for special map classes.
     320      /// This class represents the red nodes of the graph. The red
     321      /// nodes can be used also as normal nodes.
    324322      class RedNode : public Node {
    325323        typedef Node Parent;
     
    345343        /// \sa Invalid for more details.
    346344        RedNode(Invalid) {}
    347 
    348         /// \brief Constructor for conversion from a node.
    349         ///
    350         /// Constructor for conversion from a node. The conversion can
    351         /// be invalid, since the Node can be member of the blue
    352         /// set.
    353         RedNode(const Node&) {}
    354345      };
    355346
    356347      /// \brief Class to represent blue nodes.
    357348      ///
    358       /// This class represents the blue nodes of the graph. It does
    359       /// not supposed to be used directly, because the nodes can be
    360       /// represented as Node instances. This class can be used as
    361       /// template parameter for special map classes.
     349      /// This class represents the blue nodes of the graph. The blue
     350      /// nodes can be used also as normal nodes.
    362351      class BlueNode : public Node {
    363352        typedef Node Parent;
     
    405394      ///
    406395      /// Gives back the red end node of the edge.
    407       Node redNode(const Edge&) const { return Node(); }
     396      RedNode redNode(const Edge&) const { return RedNode(); }
    408397
    409398      /// \brief Gives back the blue end node of the edge.
    410399      ///
    411400      /// Gives back the blue end node of the edge.
    412       Node blueNode(const Edge&) const { return Node(); }
     401      BlueNode blueNode(const Edge&) const { return BlueNode(); }
     402
     403      /// \brief Converts the node to red node object.
     404      ///
     405      /// This class is converts unsafely the node to red node
     406      /// object. It should be called only if the node is from the red
     407      /// partition or INVALID.
     408      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
     409
     410      /// \brief Converts the node to blue node object.
     411      ///
     412      /// This class is converts unsafely the node to blue node
     413      /// object. It should be called only if the node is from the red
     414      /// partition or INVALID.
     415      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
     416
     417      /// \brief Converts the node to red node object.
     418      ///
     419      /// This class is converts safely the node to red node
     420      /// object. If the node is not from the red partition, then it
     421      /// returns INVALID.
     422      RedNode asRedNode(const Node&) const { return RedNode(); }
     423
     424      /// \brief Converts the node to blue node object.
     425      ///
     426      /// This class is converts unsafely the node to blue node
     427      /// object. If the node is not from the blue partition, then it
     428      /// returns INVALID.
     429      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
     430
     431      /// \brief Convert the node to either red or blue node.
     432      ///
     433      /// If the node is from the red partition then it is returned in
     434      /// first and second is INVALID. If the node is from the blue
     435      /// partition then it is returned in second and first is
     436      /// INVALID. If the node INVALID then both first and second are
     437      /// INVALID in the return value.
     438      std::pair<RedNode, BlueNode> asRedBlueNode(const Node&) const {
     439        return std::make_pair(RedNode(), BlueNode());
     440      }
    413441
    414442      template <typename _BpGraph>
     
    426454          {
    427455            Node n;
    428             RedNode rn = n;
    429             BlueNode bn = bn;
     456            RedNode rn;
     457            BlueNode bn;
     458            Node rnan = rn;
     459            Node bnan = bn;
    430460            Edge e;
    431461            bool b;
    432             b = bpgraph.red(n);
    433             b = bpgraph.blue(n);
    434             ignore_unused_variable_warning(b);
    435             n = bpgraph.redNode(e);
    436             n = bpgraph.blueNode(e);
    437             rn = n;
    438             bn = n;
     462            b = bpgraph.red(rnan);
     463            b = bpgraph.blue(bnan);
     464            rn = bpgraph.redNode(e);
     465            bn = bpgraph.blueNode(e);
     466            rn = bpgraph.asRedNodeUnsafe(rnan);
     467            bn = bpgraph.asBlueNodeUnsafe(bnan);
     468            rn = bpgraph.asRedNode(rnan);
     469            bn = bpgraph.asBlueNode(bnan);
     470            std::pair<RedNode, BlueNode> p = bpgraph.asRedBlueNode(rnan);
     471            ignore_unused_variable_warning(b,p);
    439472          }
    440473        }
     
    600633      ///
    601634      /// Return a unique integer id for the given node in the red set.
    602       int redId(const Node&) const { return -1; }
    603 
    604       /// \brief Return the same value as redId().
    605       ///
    606       /// Return the same value as redId().
    607635      int id(const RedNode&) const { return -1; }
    608636
     
    610638      ///
    611639      /// Return a unique integer id for the given node in the blue set.
    612       int blueId(const Node&) const { return -1; }
    613 
    614       /// \brief Return the same value as blueId().
    615       ///
    616       /// Return the same value as blueId().
    617640      int id(const BlueNode&) const { return -1; }
    618641
     
    639662          typename _BpGraph::RedNode red;
    640663          typename _BpGraph::BlueNode blue;
    641           int rid = bpgraph.redId(node);
    642           int bid = bpgraph.blueId(node);
    643           rid = bpgraph.id(red);
    644           bid = bpgraph.id(blue);
     664          int rid = bpgraph.id(red);
     665          int bid = bpgraph.id(blue);
    645666          rid = bpgraph.maxRedId();
    646667          bid = bpgraph.maxBlueId();
     
    11381159      typedef BAS Base;
    11391160      typedef typename Base::Node Node;
     1161      typedef typename Base::RedNode RedNode;
     1162      typedef typename Base::BlueNode BlueNode;
    11401163      typedef typename Base::Arc Arc;
    11411164      typedef typename Base::Edge Edge;
    1142 
    1143 
     1165     
    11441166      typedef IterableBpGraphComponent BpGraph;
    11451167
     1168      using IterableGraphComponent<BAS>::first;
     1169      using IterableGraphComponent<BAS>::next;
     1170
    11461171      /// \name Base Iteration
    11471172      ///
     
    11531178      ///
    11541179      /// This function gives back the first red node in the iteration order.
    1155       void firstRed(Node&) const {}
     1180      void first(RedNode&) const {}
    11561181
    11571182      /// \brief Return the next red node.
    11581183      ///
    11591184      /// This function gives back the next red node in the iteration order.
    1160       void nextRed(Node&) const {}
     1185      void next(RedNode&) const {}
    11611186
    11621187      /// \brief Return the first blue node.
    11631188      ///
    11641189      /// This function gives back the first blue node in the iteration order.
    1165       void firstBlue(Node&) const {}
     1190      void first(BlueNode&) const {}
    11661191
    11671192      /// \brief Return the next blue node.
    11681193      ///
    11691194      /// This function gives back the next blue node in the iteration order.
    1170       void nextBlue(Node&) const {}
     1195      void next(BlueNode&) const {}
    11711196
    11721197
     
    11821207      ///
    11831208      /// This iterator goes through each red node.
    1184       typedef GraphItemIt<BpGraph, Node> RedIt;
     1209      typedef GraphItemIt<BpGraph, RedNode> RedIt;
    11851210
    11861211      /// \brief This iterator goes through each blue node.
    11871212      ///
    11881213      /// This iterator goes through each blue node.
    1189       typedef GraphItemIt<BpGraph, Node> BlueIt;
     1214      typedef GraphItemIt<BpGraph, BlueNode> BlueIt;
    11901215
    11911216      /// @}
     
    11961221          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
    11971222
    1198           typename _BpGraph::Node node(INVALID);
    1199           bpgraph.firstRed(node);
    1200           bpgraph.nextRed(node);
    1201           bpgraph.firstBlue(node);
    1202           bpgraph.nextBlue(node);
    1203 
    1204           checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
     1223          typename _BpGraph::RedNode rn(INVALID);
     1224          bpgraph.first(rn);
     1225          bpgraph.next(rn);
     1226          typename _BpGraph::BlueNode bn(INVALID);
     1227          bpgraph.first(bn);
     1228          bpgraph.next(bn);
     1229
     1230          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
    12051231            typename _BpGraph::RedIt>();
    1206           checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::Node>,
     1232          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
    12071233            typename _BpGraph::BlueIt>();
    12081234        }
     
    17911817          { // int map test
    17921818            typedef typename _BpGraph::template RedMap<int> IntRedMap;
    1793             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
     1819            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
    17941820              IntRedMap >();
    17951821          } { // bool map test
    17961822            typedef typename _BpGraph::template RedMap<bool> BoolRedMap;
    1797             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
     1823            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
    17981824              BoolRedMap >();
    17991825          } { // Dummy map test
    18001826            typedef typename _BpGraph::template RedMap<Dummy> DummyRedMap;
    1801             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
     1827            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
    18021828              DummyRedMap >();
    18031829          }
     
    18051831          { // int map test
    18061832            typedef typename _BpGraph::template BlueMap<int> IntBlueMap;
    1807             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, int>,
     1833            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
    18081834              IntBlueMap >();
    18091835          } { // bool map test
    18101836            typedef typename _BpGraph::template BlueMap<bool> BoolBlueMap;
    1811             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, bool>,
     1837            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
    18121838              BoolBlueMap >();
    18131839          } { // Dummy map test
    18141840            typedef typename _BpGraph::template BlueMap<Dummy> DummyBlueMap;
    1815             checkConcept<GraphMap<_BpGraph, typename _BpGraph::Node, Dummy>,
     1841            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
    18161842              DummyBlueMap >();
    18171843          }
     
    19241950      typedef BAS Base;
    19251951      typedef typename Base::Node Node;
     1952      typedef typename Base::RedNode RedNode;
     1953      typedef typename Base::BlueNode BlueNode;
    19261954      typedef typename Base::Edge Edge;
    19271955
     
    19291957      ///
    19301958      /// This function adds a red new node to the digraph.
    1931       Node addRedNode() {
     1959      RedNode addRedNode() {
    19321960        return INVALID;
    19331961      }
     
    19361964      ///
    19371965      /// This function adds a blue new node to the digraph.
    1938       Node addBlueNode() {
     1966      BlueNode addBlueNode() {
    19391967        return INVALID;
    19401968      }
     
    19451973      /// of the graph. The first node has to be a red node, and the
    19461974      /// second one a blue node.
    1947       Edge addEdge(const Node&, const Node&) {
     1975      Edge addEdge(const RedNode&, const BlueNode&) {
    19481976        return INVALID;
    19491977      }
     1978      Edge addEdge(const BlueNode&, const RedNode&) {
     1979        return INVALID;
     1980      }
    19501981
    19511982      template <typename _BpGraph>
     
    19531984        void constraints() {
    19541985          checkConcept<Base, _BpGraph>();
    1955           typename _BpGraph::Node red_node, blue_node;
     1986          typename _BpGraph::RedNode red_node;
     1987          typename _BpGraph::BlueNode blue_node;
    19561988          red_node = bpgraph.addRedNode();
    19571989          blue_node = bpgraph.addBlueNode();
    19581990          typename _BpGraph::Edge edge;
    19591991          edge = bpgraph.addEdge(red_node, blue_node);
     1992          edge = bpgraph.addEdge(blue_node, red_node);
    19601993        }
    19611994
  • lemon/core.h

    r1022 r1025  
    551551      template <typename From, typename NodeRefMap, typename EdgeRefMap>
    552552      static void copy(const From& from, Graph &to,
    553                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     553                       NodeRefMap& nodeRefMap,
     554                       EdgeRefMap& edgeRefMap) {
    554555        to.build(from, nodeRefMap, edgeRefMap);
    555556      }
     
    558559    template <typename BpGraph, typename Enable = void>
    559560    struct BpGraphCopySelector {
    560       template <typename From, typename NodeRefMap, typename EdgeRefMap>
     561      template <typename From, typename RedNodeRefMap,
     562                typename BlueNodeRefMap, typename EdgeRefMap>
    561563      static void copy(const From& from, BpGraph &to,
    562                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
     564                       RedNodeRefMap& redNodeRefMap,
     565                       BlueNodeRefMap& blueNodeRefMap,
     566                       EdgeRefMap& edgeRefMap) {
    563567        to.clear();
    564568        for (typename From::RedIt it(from); it != INVALID; ++it) {
    565           nodeRefMap[it] = to.addRedNode();
     569          redNodeRefMap[it] = to.addRedNode();
    566570        }
    567571        for (typename From::BlueIt it(from); it != INVALID; ++it) {
    568           nodeRefMap[it] = to.addBlueNode();
     572          blueNodeRefMap[it] = to.addBlueNode();
    569573        }
    570574        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
    571           edgeRefMap[it] = to.addEdge(nodeRefMap[from.redNode(it)],
    572                                       nodeRefMap[from.blueNode(it)]);
     575          edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)],
     576                                      blueNodeRefMap[from.blueNode(it)]);
    573577        }
    574578      }
     
    580584      typename enable_if<typename BpGraph::BuildTag, void>::type>
    581585    {
    582       template <typename From, typename NodeRefMap, typename EdgeRefMap>
     586      template <typename From, typename RedNodeRefMap,
     587                typename BlueNodeRefMap, typename EdgeRefMap>
    583588      static void copy(const From& from, BpGraph &to,
    584                        NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    585         to.build(from, nodeRefMap, edgeRefMap);
     589                       RedNodeRefMap& redNodeRefMap,
     590                       BlueNodeRefMap& blueNodeRefMap,
     591                       EdgeRefMap& edgeRefMap) {
     592        to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap);
    586593      }
    587594    };
     
    11831190
    11841191    typedef typename To::Node TNode;
     1192    typedef typename To::RedNode TRedNode;
     1193    typedef typename To::BlueNode TBlueNode;
    11851194    typedef typename To::Arc TArc;
    11861195    typedef typename To::Edge TEdge;
    11871196
    1188     typedef typename From::template NodeMap<TNode> NodeRefMap;
     1197    typedef typename From::template RedMap<TRedNode> RedNodeRefMap;
     1198    typedef typename From::template BlueMap<TBlueNode> BlueNodeRefMap;
    11891199    typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
     1200
     1201    struct NodeRefMap {
     1202      NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref,
     1203                 const BlueNodeRefMap& blue_node_ref)
     1204        : _from(from), _red_node_ref(red_node_ref),
     1205          _blue_node_ref(blue_node_ref) {}
     1206
     1207      typedef typename From::Node Key;
     1208      typedef typename To::Node Value;
     1209
     1210      Value operator[](const Key& key) const {
     1211        std::pair<RedNode, BlueNode> red_blue_pair = _from.asRedBlueNode(key);
     1212        if (red_blue_pair.first != INVALID) {
     1213          return _red_node_ref[red_blue_pair.first];
     1214        } else {
     1215          return _blue_node_ref[red_blue_pair.second];
     1216        }
     1217      }
     1218
     1219      const From& _from;
     1220      const RedNodeRefMap& _red_node_ref;
     1221      const BlueNodeRefMap& _blue_node_ref;
     1222    };
    11901223
    11911224    struct ArcRefMap {
     
    12931326    BpGraphCopy& redRef(RedRef& map) {
    12941327      _red_maps.push_back(new _core_bits::RefCopy<From, RedNode,
    1295                           NodeRefMap, RedRef>(map));
     1328                          RedNodeRefMap, RedRef>(map));
    12961329      return *this;
    12971330    }
     
    13071340    BpGraphCopy& redCrossRef(RedCrossRef& map) {
    13081341      _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode,
    1309                           NodeRefMap, RedCrossRef>(map));
     1342                          RedNodeRefMap, RedCrossRef>(map));
    13101343      return *this;
    13111344    }
     
    13221355    BpGraphCopy& redMap(const FromMap& map, ToMap& tmap) {
    13231356      _red_maps.push_back(new _core_bits::MapCopy<From, RedNode,
    1324                            NodeRefMap, FromMap, ToMap>(map, tmap));
     1357                          RedNodeRefMap, FromMap, ToMap>(map, tmap));
     1358      return *this;
     1359    }
     1360
     1361    /// \brief Make a copy of the given red node.
     1362    ///
     1363    /// This function makes a copy of the given red node.
     1364    BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) {
     1365      _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode,
     1366                          RedNodeRefMap, TRedNode>(node, tnode));
    13251367      return *this;
    13261368    }
     
    13351377    BpGraphCopy& blueRef(BlueRef& map) {
    13361378      _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode,
    1337                            NodeRefMap, BlueRef>(map));
     1379                           BlueNodeRefMap, BlueRef>(map));
    13381380      return *this;
    13391381    }
     
    13491391    BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
    13501392      _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode,
    1351                            NodeRefMap, BlueCrossRef>(map));
     1393                           BlueNodeRefMap, BlueCrossRef>(map));
    13521394      return *this;
    13531395    }
     
    13641406    BpGraphCopy& blueMap(const FromMap& map, ToMap& tmap) {
    13651407      _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode,
    1366                            NodeRefMap, FromMap, ToMap>(map, tmap));
     1408                           BlueNodeRefMap, FromMap, ToMap>(map, tmap));
     1409      return *this;
     1410    }
     1411
     1412    /// \brief Make a copy of the given blue node.
     1413    ///
     1414    /// This function makes a copy of the given blue node.
     1415    BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) {
     1416      _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode,
     1417                           BlueNodeRefMap, TBlueNode>(node, tnode));
    13671418      return *this;
    13681419    }
     
    14711522    /// copying of the assigned data.
    14721523    void run() {
    1473       NodeRefMap nodeRefMap(_from);
     1524      RedNodeRefMap redNodeRefMap(_from);
     1525      BlueNodeRefMap blueNodeRefMap(_from);
     1526      NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap);
    14741527      EdgeRefMap edgeRefMap(_from);
    14751528      ArcRefMap arcRefMap(_from, _to, edgeRefMap);
    14761529      _core_bits::BpGraphCopySelector<To>::
    1477         copy(_from, _to, nodeRefMap, edgeRefMap);
     1530        copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap);
    14781531      for (int i = 0; i < int(_node_maps.size()); ++i) {
    14791532        _node_maps[i]->copy(_from, nodeRefMap);
    14801533      }
    14811534      for (int i = 0; i < int(_red_maps.size()); ++i) {
    1482         _red_maps[i]->copy(_from, nodeRefMap);
     1535        _red_maps[i]->copy(_from, redNodeRefMap);
    14831536      }
    14841537      for (int i = 0; i < int(_blue_maps.size()); ++i) {
    1485         _blue_maps[i]->copy(_from, nodeRefMap);
     1538        _blue_maps[i]->copy(_from, blueNodeRefMap);
    14861539      }
    14871540      for (int i = 0; i < int(_edge_maps.size()); ++i) {
     
    15011554      _node_maps;
    15021555
    1503     std::vector<_core_bits::MapCopyBase<From, RedNode, NodeRefMap>* >
     1556    std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* >
    15041557      _red_maps;
    15051558
    1506     std::vector<_core_bits::MapCopyBase<From, BlueNode, NodeRefMap>* >
     1559    std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* >
    15071560      _blue_maps;
    15081561
  • lemon/full_graph.h

    r1024 r1025  
    652652    };
    653653
     654    class RedNode : public Node {
     655      friend class FullBpGraphBase;
     656    protected:
     657
     658      explicit RedNode(int pid) : Node(pid) {}
     659
     660    public:
     661      RedNode() {}
     662      RedNode(const RedNode& node) : Node(node) {}
     663      RedNode(Invalid) : Node(INVALID){}
     664    };
     665
     666    class BlueNode : public Node {
     667      friend class FullBpGraphBase;
     668    protected:
     669
     670      explicit BlueNode(int pid) : Node(pid) {}
     671
     672    public:
     673      BlueNode() {}
     674      BlueNode(const BlueNode& node) : Node(node) {}
     675      BlueNode(Invalid) : Node(INVALID){}
     676    };
     677
    654678    class Edge {
    655679      friend class FullBpGraphBase;
     
    718742    bool blue(Node n) const { return n._id >= _red_num; }
    719743
     744    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
     745    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
     746
    720747    Node source(Arc a) const {
    721748      if (a._id & 1) {
     
    733760    }
    734761
    735     Node redNode(Edge e) const {
    736       return Node(e._id % _red_num);
    737     }
    738     Node blueNode(Edge e) const {
    739       return Node(e._id / _red_num + _red_num);
     762    RedNode redNode(Edge e) const {
     763      return RedNode(e._id % _red_num);
     764    }
     765    BlueNode blueNode(Edge e) const {
     766      return BlueNode(e._id / _red_num + _red_num);
    740767    }
    741768
     
    756783    }
    757784
    758     void firstRed(Node& node) const {
     785    void first(RedNode& node) const {
    759786      node._id = _red_num - 1;
    760787    }
    761788
    762     static void nextRed(Node& node) {
     789    static void next(RedNode& node) {
    763790      --node._id;
    764791    }
    765792
    766     void firstBlue(Node& node) const {
     793    void first(BlueNode& node) const {
    767794      if (_red_num == _node_num) node._id = -1;
    768795      else node._id = _node_num - 1;
    769796    }
    770797
    771     void nextBlue(Node& node) const {
     798    void next(BlueNode& node) const {
    772799      if (node._id == _red_num) node._id = -1;
    773800      else --node._id;
     
    843870    }
    844871
    845     static int id(Node v) { return v._id; }
    846     int redId(Node v) const {
    847       LEMON_DEBUG(v._id < _red_num, "Node has to be red");
    848       return v._id;
    849     }
    850     int blueId(Node v) const {
    851       LEMON_DEBUG(v._id >= _red_num, "Node has to be blue");
    852       return v._id - _red_num;
    853     }
     872    static int id(const Node& v) { return v._id; }
     873    int id(const RedNode& v) const { return v._id; }
     874    int id(const BlueNode& v) const { return v._id - _red_num; }
    854875    static int id(Arc e) { return e._id; }
    855876    static int id(Edge e) { return e._id; }
     
    869890    }
    870891
    871     Node redNode(int index) const {
    872       return Node(index);
    873     }
    874 
    875     int redIndex(Node n) const {
     892    RedNode redNode(int index) const {
     893      return RedNode(index);
     894    }
     895
     896    int index(RedNode n) const {
    876897      return n._id;
    877898    }
    878899
    879     Node blueNode(int index) const {
    880       return Node(index + _red_num);
    881     }
    882 
    883     int blueIndex(Node n) const {
     900    BlueNode blueNode(int index) const {
     901      return BlueNode(index + _red_num);
     902    }
     903
     904    int index(BlueNode n) const {
    884905      return n._id - _red_num;
    885906    }
     
    10011022    /// with integers from the range <tt>[0..redNum()-1]</tt>.
    10021023    /// \sa redIndex()
    1003     Node redNode(int index) const { return Parent::redNode(index); }
     1024    RedNode redNode(int index) const { return Parent::redNode(index); }
    10041025
    10051026    /// \brief Returns the index of the given red node.
     
    10101031    ///
    10111032    /// \sa operator()()
    1012     int redIndex(Node node) const { return Parent::redIndex(node); }
     1033    int index(RedNode node) const { return Parent::index(node); }
    10131034
    10141035    /// \brief Returns the blue node with the given index.
     
    10181039    /// with integers from the range <tt>[0..blueNum()-1]</tt>.
    10191040    /// \sa blueIndex()
    1020     Node blueNode(int index) const { return Parent::blueNode(index); }
     1041    BlueNode blueNode(int index) const { return Parent::blueNode(index); }
    10211042
    10221043    /// \brief Returns the index of the given blue node.
     
    10271048    ///
    10281049    /// \sa operator()()
    1029     int blueIndex(Node node) const { return Parent::blueIndex(node); }
     1050    int index(BlueNode node) const { return Parent::index(node); }
    10301051
    10311052    /// \brief Returns the edge which connects the given nodes.
  • lemon/list_graph.h

    r1021 r1025  
    16481648    };
    16491649
     1650    class RedNode : public Node {
     1651      friend class ListBpGraphBase;
     1652    protected:
     1653
     1654      explicit RedNode(int pid) : Node(pid) {}
     1655
     1656    public:
     1657      RedNode() {}
     1658      RedNode(const RedNode& node) : Node(node) {}
     1659      RedNode(Invalid) : Node(INVALID){}
     1660    };
     1661
     1662    class BlueNode : public Node {
     1663      friend class ListBpGraphBase;
     1664    protected:
     1665
     1666      explicit BlueNode(int pid) : Node(pid) {}
     1667
     1668    public:
     1669      BlueNode() {}
     1670      BlueNode(const BlueNode& node) : Node(node) {}
     1671      BlueNode(Invalid) : Node(INVALID){}
     1672    };
     1673
    16501674    class Edge {
    16511675      friend class ListBpGraphBase;
     
    16931717    bool blue(Node n) const { return !nodes[n.id].red; }
    16941718
     1719    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
     1720    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
     1721
    16951722    int maxNodeId() const { return nodes.size()-1; }
    16961723    int maxRedId() const { return max_red; }
     
    17021729    Node target(Arc e) const { return Node(arcs[e.id].target); }
    17031730
    1704     Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
    1705     Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
     1731    RedNode redNode(Edge e) const {
     1732      return RedNode(arcs[2 * e.id].target);
     1733    }
     1734    BlueNode blueNode(Edge e) const {
     1735      return BlueNode(arcs[2 * e.id + 1].target);
     1736    }
    17061737
    17071738    static bool direction(Arc e) {
     
    17211752    }
    17221753
    1723     void firstRed(Node& node) const {
     1754    void first(RedNode& node) const {
    17241755      node.id = first_red;
    17251756    }
    17261757
    1727     void nextRed(Node& node) const {
     1758    void next(RedNode& node) const {
    17281759      node.id = nodes[node.id].partition_next;
    17291760    }
    17301761
    1731     void firstBlue(Node& node) const {
     1762    void first(BlueNode& node) const {
    17321763      node.id = first_blue;
    17331764    }
    17341765
    1735     void nextBlue(Node& node) const {
     1766    void next(BlueNode& node) const {
    17361767      node.id = nodes[node.id].partition_next;
    17371768    }   
     
    18361867
    18371868    static int id(Node v) { return v.id; }
    1838     int redId(Node v) const {
    1839       LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
    1840       return nodes[v.id].partition_index;
    1841     }
    1842     int blueId(Node v) const {
    1843       LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue");
    1844       return nodes[v.id].partition_index;
    1845     }
     1869    int id(RedNode v) const { return nodes[v.id].partition_index; }
     1870    int id(BlueNode v) const { return nodes[v.id].partition_index; }
    18461871    static int id(Arc e) { return e.id; }
    18471872    static int id(Edge e) { return e.id; }
     
    18661891    }
    18671892
    1868     Node addRedNode() {
     1893    RedNode addRedNode() {
    18691894      int n;
    18701895
     
    18911916      nodes[n].first_out = -1;
    18921917
    1893       return Node(n);
    1894     }
    1895 
    1896     Node addBlueNode() {
     1918      return RedNode(n);
     1919    }
     1920
     1921    BlueNode addBlueNode() {
    18971922      int n;
    18981923
     
    19191944      nodes[n].first_out = -1;
    19201945
    1921       return Node(n);
     1946      return BlueNode(n);
    19221947    }
    19231948
     
    20302055  protected:
    20312056
    2032     void changeRed(Edge e, Node n) {
    2033       LEMON_DEBUG(nodes[n].red, "Node has to be red");
     2057    void changeRed(Edge e, RedNode n) {
    20342058      if(arcs[(2 * e.id) | 1].next_out != -1) {
    20352059        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
     
    20532077    }
    20542078
    2055     void changeBlue(Edge e, Node n) {
    2056       LEMON_DEBUG(nodes[n].red, "Node has to be blue");
    2057       if(arcs[2 * e.id].next_out != -1) {
     2079    void changeBlue(Edge e, BlueNode n) {
     2080       if(arcs[2 * e.id].next_out != -1) {
    20582081        arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
    20592082      }
     
    21202143    /// This function adds a red new node to the graph.
    21212144    /// \return The new node.
    2122     Node addRedNode() { return Parent::addRedNode(); }
     2145    RedNode addRedNode() { return Parent::addRedNode(); }
    21232146
    21242147    /// \brief Add a new blue node to the graph.
     
    21262149    /// This function adds a blue new node to the graph.
    21272150    /// \return The new node.
    2128     Node addBlueNode() { return Parent::addBlueNode(); }
     2151    BlueNode addBlueNode() { return Parent::addBlueNode(); }
    21292152
    21302153    /// \brief Add a new edge to the graph.
     
    21342157    /// node \c v.
    21352158    /// \return The new edge.
    2136     Edge addEdge(Node u, Node v) {
     2159    Edge addEdge(RedNode u, BlueNode v) {
     2160      return Parent::addEdge(u, v);
     2161    }
     2162    Edge addEdge(BlueNode v, RedNode u) {
    21372163      return Parent::addEdge(u, v);
    21382164    }
     
    21892215    ///\warning This functionality cannot be used together with the
    21902216    ///Snapshot feature.
    2191     void changeRed(Edge e, Node n) {
    2192       Parent::changeRed(e,n);
     2217    void changeRed(Edge e, RedNode n) {
     2218      Parent::changeRed(e, n);
    21932219    }
    21942220    /// \brief Change the blue node of an edge.
     
    22032229    ///\warning This functionality cannot be used together with the
    22042230    ///Snapshot feature.
    2205     void changeBlue(Edge e, Node n) {
    2206       Parent::changeBlue(e,n);
     2231    void changeBlue(Edge e, BlueNode n) {
     2232      Parent::changeBlue(e, n);
    22072233    }
    22082234
  • lemon/smart_graph.h

    r1023 r1025  
    855855    };
    856856
     857    class RedNode : public Node {
     858      friend class SmartBpGraphBase;
     859    protected:
     860
     861      explicit RedNode(int pid) : Node(pid) {}
     862
     863    public:
     864      RedNode() {}
     865      RedNode(const RedNode& node) : Node(node) {}
     866      RedNode(Invalid) : Node(INVALID){}
     867    };
     868
     869    class BlueNode : public Node {
     870      friend class SmartBpGraphBase;
     871    protected:
     872
     873      explicit BlueNode(int pid) : Node(pid) {}
     874
     875    public:
     876      BlueNode() {}
     877      BlueNode(const BlueNode& node) : Node(node) {}
     878      BlueNode(Invalid) : Node(INVALID){}
     879    };
     880
    857881    class Edge {
    858882      friend class SmartBpGraphBase;
     
    914938    bool blue(Node n) const { return !nodes[n._id].red; }
    915939
     940    static RedNode asRedNodeUnsafe(Node n) { return RedNode(n._id); }
     941    static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n._id); }
     942
    916943    Node source(Arc a) const { return Node(arcs[a._id ^ 1].target); }
    917944    Node target(Arc a) const { return Node(arcs[a._id].target); }
    918945
    919     Node redNode(Edge e) const { return Node(arcs[2 * e._id].target); }
    920     Node blueNode(Edge e) const { return Node(arcs[2 * e._id + 1].target); }
     946    RedNode redNode(Edge e) const {
     947      return RedNode(arcs[2 * e._id].target);
     948    }
     949    BlueNode blueNode(Edge e) const {
     950      return BlueNode(arcs[2 * e._id + 1].target);
     951    }
    921952
    922953    static bool direction(Arc a) {
     
    936967    }
    937968
    938     void firstRed(Node& node) const {
     969    void first(RedNode& node) const {
    939970      node._id = first_red;
    940971    }
    941972
    942     void nextRed(Node& node) const {
     973    void next(RedNode& node) const {
    943974      node._id = nodes[node._id].partition_next;
    944975    }
    945976
    946     void firstBlue(Node& node) const {
     977    void first(BlueNode& node) const {
    947978      node._id = first_blue;
    948979    }
    949980
    950     void nextBlue(Node& node) const {
     981    void next(BlueNode& node) const {
    951982      node._id = nodes[node._id].partition_next;
    952983    }
     
    10061037
    10071038    static int id(Node v) { return v._id; }
    1008     int redId(Node v) const {
    1009       LEMON_DEBUG(nodes[v._id].red, "Node has to be red");
    1010       return nodes[v._id].partition_index;
    1011     }
    1012     int blueId(Node v) const {
    1013       LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
    1014       return nodes[v._id].partition_index;
    1015     }
     1039    int id(RedNode v) const { return nodes[v._id].partition_index; }
     1040    int id(BlueNode v) const { return nodes[v._id].partition_index; }
    10161041    static int id(Arc e) { return e._id; }
    10171042    static int id(Edge e) { return e._id; }
     
    10311056    }
    10321057
    1033     Node addRedNode() {
     1058    RedNode addRedNode() {
    10341059      int n = nodes.size();
    10351060      nodes.push_back(NodeT());
     
    10401065      first_red = n;
    10411066
    1042       return Node(n);
    1043     }
    1044 
    1045     Node addBlueNode() {
     1067      return RedNode(n);
     1068    }
     1069
     1070    BlueNode addBlueNode() {
    10461071      int n = nodes.size();
    10471072      nodes.push_back(NodeT());
     
    10521077      first_blue = n;
    10531078
    1054       return Node(n);
    1055     }
    1056 
    1057     Edge addEdge(Node u, Node v) {
     1079      return BlueNode(n);
     1080    }
     1081
     1082    Edge addEdge(RedNode u, BlueNode v) {
    10581083      int n = arcs.size();
    10591084      arcs.push_back(ArcT());
     
    11251150    /// This function adds a red new node to the graph.
    11261151    /// \return The new node.
    1127     Node addRedNode() { return Parent::addRedNode(); }
     1152    RedNode addRedNode() { return Parent::addRedNode(); }
    11281153
    11291154    /// \brief Add a new blue node to the graph.
     
    11311156    /// This function adds a blue new node to the graph.
    11321157    /// \return The new node.
    1133     Node addBlueNode() { return Parent::addBlueNode(); }
     1158    BlueNode addBlueNode() { return Parent::addBlueNode(); }
    11341159
    11351160    /// \brief Add a new edge to the graph.
     
    11391164    /// node \c v.
    11401165    /// \return The new edge.
    1141     Edge addEdge(Node red, Node blue) {
    1142       LEMON_DEBUG(Parent::red(red) && Parent::blue(blue),
    1143                   "Edge has to be formed by a red and a blue nodes");
    1144       return Parent::addEdge(red, blue);
     1166    Edge addEdge(RedNode u, BlueNode v) {
     1167      return Parent::addEdge(u, v);
     1168    }
     1169    Edge addEdge(BlueNode v, RedNode u) {
     1170      return Parent::addEdge(u, v);
    11451171    }
    11461172
     
    12381264            max_red = -1;
    12391265          }
    1240           Parent::notifier(RedNode()).erase(node);         
     1266          Parent::notifier(RedNode()).erase(asRedNodeUnsafe(node));         
    12411267        } else {
    12421268          first_blue = nodes[n].partition_next;
     
    12461272            max_blue = -1;
    12471273          }
    1248           Parent::notifier(BlueNode()).erase(node);
     1274          Parent::notifier(BlueNode()).erase(asBlueNodeUnsafe(node));
    12491275        }
    12501276        Parent::notifier(Node()).erase(node);
  • test/bpgraph_test.cc

    r1021 r1025  
    4242  G.reserveEdge(3);
    4343
    44   Node
     44  RedNode
    4545    rn1 = G.addRedNode();
    4646  checkGraphNodeList(G, 1);
     
    5050  checkGraphArcList(G, 0);
    5151
    52   Node
     52  BlueNode
    5353    bn1 = G.addBlueNode(),
    5454    bn2 = G.addBlueNode();
     
    7777
    7878  Edge
    79     e2 = G.addEdge(rn1, bn1),
     79    e2 = G.addEdge(bn1, rn1),
    8080    e3 = G.addEdge(rn1, bn2);
    8181
     
    113113
    114114  BpGraph G;
    115   Node
    116     n1 = G.addRedNode(), n2 = G.addBlueNode(),
    117     n3 = G.addBlueNode(), n4 = G.addRedNode();
     115  RedNode
     116    n1 = G.addRedNode(), n4 = G.addRedNode();
     117  BlueNode
     118    n2 = G.addBlueNode(), n3 = G.addBlueNode();
    118119  Edge
    119120    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     
    160161
    161162  BpGraph G;
    162   Node
    163     n1 = G.addRedNode(), n2 = G.addBlueNode(),
    164     n3 = G.addBlueNode(), n4 = G.addRedNode();
     163  RedNode
     164    n1 = G.addRedNode(), n4 = G.addRedNode();
     165  BlueNode
     166    n2 = G.addBlueNode(), n3 = G.addBlueNode();
    165167  Edge
    166168    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     
    210212
    211213  BpGraph G;
    212   Node
    213     n1 = G.addRedNode(),
     214  RedNode
     215    n1 = G.addRedNode();
     216  BlueNode
    214217    n2 = G.addBlueNode(),
    215218    n3 = G.addBlueNode();
     
    226229  typename BpGraph::Snapshot snapshot(G);
    227230
    228   Node n4 = G.addRedNode();
     231  RedNode n4 = G.addRedNode();
    229232  G.addEdge(n4, n2);
    230233  G.addEdge(n4, n3);
     
    293296  BpGraph g;
    294297
    295   Node
    296     n1 = g.addRedNode(),
     298  RedNode
     299    n1 = g.addRedNode();
     300  BlueNode
    297301    n2 = g.addBlueNode(),
    298302    n3 = g.addBlueNode();
     
    397401  for (int i = 0; i < G.redNum(); ++i) {
    398402    check(G.red(G.redNode(i)), "Wrong node");
    399     check(G.redIndex(G.redNode(i)) == i, "Wrong index");
     403    check(G.index(G.redNode(i)) == i, "Wrong index");
    400404  }
    401405
    402406  for (int i = 0; i < G.blueNum(); ++i) {
    403407    check(G.blue(G.blueNode(i)), "Wrong node");
    404     check(G.blueIndex(G.blueNode(i)) == i, "Wrong index");
     408    check(G.index(G.blueNode(i)) == i, "Wrong index");
    405409  }
    406410
  • test/graph_copy_test.cc

    r1022 r1025  
    222222  SmartBpGraph::EdgeMap<int> fem(from);
    223223  SmartBpGraph::Node fn = INVALID;
     224  SmartBpGraph::RedNode frn = INVALID;
     225  SmartBpGraph::BlueNode fbn = INVALID;
    224226  SmartBpGraph::Arc fa = INVALID;
    225227  SmartBpGraph::Edge fe = INVALID;
    226228
    227   std::vector<SmartBpGraph::Node> frnv;
    228   for (int i = 0; i < nn; ++i) {
    229     SmartBpGraph::Node node = from.addRedNode();
     229  std::vector<SmartBpGraph::RedNode> frnv;
     230  for (int i = 0; i < nn; ++i) {
     231    SmartBpGraph::RedNode node = from.addRedNode();
    230232    frnv.push_back(node);
    231233    fnm[node] = i * i;
    232234    frnm[node] = i + i;
    233     if (i == 0) fn = node;
    234   }
    235 
    236   std::vector<SmartBpGraph::Node> fbnv;
    237   for (int i = 0; i < nn; ++i) {
    238     SmartBpGraph::Node node = from.addBlueNode();
     235    if (i == 0) {
     236      fn = node;
     237      frn = node;
     238    }
     239  }
     240
     241  std::vector<SmartBpGraph::BlueNode> fbnv;
     242  for (int i = 0; i < nn; ++i) {
     243    SmartBpGraph::BlueNode node = from.addBlueNode();
    239244    fbnv.push_back(node);
    240245    fnm[node] = i * i;
    241246    fbnm[node] = i + i;
     247    if (i == 0) fbn = node;
    242248  }
    243249
     
    261267  typename GR::template EdgeMap<int> tem(to);
    262268  typename GR::Node tn;
     269  typename GR::RedNode trn;
     270  typename GR::BlueNode tbn;
    263271  typename GR::Arc ta;
    264272  typename GR::Edge te;
    265273
    266274  SmartBpGraph::NodeMap<typename GR::Node> nr(from);
    267   SmartBpGraph::RedMap<typename GR::Node> rnr(from);
    268   SmartBpGraph::BlueMap<typename GR::Node> bnr(from);
     275  SmartBpGraph::RedMap<typename GR::RedNode> rnr(from);
     276  SmartBpGraph::BlueMap<typename GR::BlueNode> bnr(from);
    269277  SmartBpGraph::ArcMap<typename GR::Arc> ar(from);
    270278  SmartBpGraph::EdgeMap<typename GR::Edge> er(from);
    271279
    272280  typename GR::template NodeMap<SmartBpGraph::Node> ncr(to);
    273   typename GR::template RedMap<SmartBpGraph::Node> rncr(to);
    274   typename GR::template BlueMap<SmartBpGraph::Node> bncr(to);
     281  typename GR::template RedMap<SmartBpGraph::RedNode> rncr(to);
     282  typename GR::template BlueMap<SmartBpGraph::BlueNode> bncr(to);
    275283  typename GR::template ArcMap<SmartBpGraph::Arc> acr(to);
    276284  typename GR::template EdgeMap<SmartBpGraph::Edge> ecr(to);
     
    283291    nodeCrossRef(ncr).redCrossRef(rncr).blueCrossRef(bncr).
    284292    arcCrossRef(acr).edgeCrossRef(ecr).
    285     node(fn, tn).arc(fa, ta).edge(fe, te).run();
     293    node(fn, tn).redNode(frn, trn).blueNode(fbn, tbn).
     294    arc(fa, ta).edge(fe, te).run();
    286295
    287296  check(countNodes(from) == countNodes(to), "Wrong copy.");
     
    294303    check(ncr[nr[it]] == it, "Wrong copy.");
    295304    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
    296     if (from.red(it)) {
    297       check(rnr[it] == nr[it], "Wrong copy.");
    298       check(rncr[rnr[it]] == it, "Wrong copy.");
    299       check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
    300       check(to.red(rnr[it]), "Wrong copy.");
    301     } else {
    302       check(bnr[it] == nr[it], "Wrong copy.");
    303       check(bncr[bnr[it]] == it, "Wrong copy.");
    304       check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
    305       check(to.blue(bnr[it]), "Wrong copy.");
    306     }
     305  }
     306
     307  for (SmartBpGraph::RedIt it(from); it != INVALID; ++it) {
     308    check(ncr[nr[it]] == it, "Wrong copy.");
     309    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
     310    check(rnr[it] == nr[it], "Wrong copy.");
     311    check(rncr[rnr[it]] == it, "Wrong copy.");
     312    check(frnm[it] == trnm[rnr[it]], "Wrong copy.");
     313    check(to.red(rnr[it]), "Wrong copy.");
     314  }
     315
     316  for (SmartBpGraph::BlueIt it(from); it != INVALID; ++it) {
     317    check(ncr[nr[it]] == it, "Wrong copy.");
     318    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
     319    check(bnr[it] == nr[it], "Wrong copy.");
     320    check(bncr[bnr[it]] == it, "Wrong copy.");
     321    check(fbnm[it] == tbnm[bnr[it]], "Wrong copy.");
     322    check(to.blue(bnr[it]), "Wrong copy.");
    307323  }
    308324
     
    343359  }
    344360  check(tn == nr[fn], "Wrong copy.");
     361  check(trn == rnr[frn], "Wrong copy.");
     362  check(tbn == bnr[fbn], "Wrong copy.");
    345363  check(ta == ar[fa], "Wrong copy.");
    346364  check(te == er[fe], "Wrong copy.");
  • test/graph_test.h

    r1019 r1025  
    4747    for(int i=0;i<cnt;i++) {
    4848      check(n!=INVALID,"Wrong red Node list linking.");
     49      check(G.red(n),"Wrong node set check.");
     50      check(!G.blue(n),"Wrong node set check.");
     51      typename Graph::Node nn = n;
     52      check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
     53      check(G.asRedNode(nn) == n,"Wrong node conversion.");
     54      check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
     55      std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
     56        G.asRedBlueNode(nn);
     57      check(rbn.first == n,"Wrong node conversion.");
     58      check(rbn.second == INVALID,"Wrong node conversion.");
    4959      ++n;
    5060    }
     
    5969    for(int i=0;i<cnt;i++) {
    6070      check(n!=INVALID,"Wrong blue Node list linking.");
     71      check(G.blue(n),"Wrong node set check.");
     72      check(!G.red(n),"Wrong node set check.");
     73      typename Graph::Node nn = n;
     74      check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
     75      check(G.asBlueNode(nn) == n,"Wrong node conversion.");
     76      check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
     77      std::pair<typename Graph::RedNode, typename Graph::BlueNode> rbn =
     78        G.asRedBlueNode(nn);
     79      check(rbn.first == INVALID,"Wrong node conversion.");
     80      check(rbn.second == n,"Wrong node conversion.");
    6181      ++n;
    6282    }
     
    208228    for (typename Graph::RedIt n(G); n != INVALID; ++n) {
    209229      check(G.red(n), "Wrong partition");
    210       check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
    211       check(values.find(G.redId(n)) == values.end(), "Wrong id");
    212       check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
     230      check(values.find(G.id(n)) == values.end(), "Wrong id");
     231      check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
    213232      values.insert(G.id(n));
    214233    }
     
    222241    for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
    223242      check(G.blue(n), "Wrong partition");
    224       check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
    225       check(values.find(G.blueId(n)) == values.end(), "Wrong id");
    226       check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
     243      check(values.find(G.id(n)) == values.end(), "Wrong id");
     244      check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
    227245      values.insert(G.id(n));
    228246    }
Note: See TracChangeset for help on using the changeset viewer.