COIN-OR::LEMON - Graph Library

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

Type safe red and blue node set (#69)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/concepts/graph_components.h

    r1186 r1193  
    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
Note: See TracChangeset for help on using the changeset viewer.