diff -r cd72eae05bdf -r 3c00344f49c9 lemon/concepts/graph_components.h --- a/lemon/concepts/graph_components.h Mon Jul 16 16:21:40 2018 +0200 +++ b/lemon/concepts/graph_components.h Wed Oct 17 19:14:07 2018 +0200 @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2010 + * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -108,6 +108,8 @@ i1 = i2 = i3; bool b; + ::lemon::ignore_unused_variable_warning(b); + b = (ia == ib) && (ia != ib); b = (ia == INVALID) && (ib != INVALID); b = (ia < ib); @@ -287,7 +289,7 @@ e = graph.oppositeArc(e); ue = e; bool d = graph.direction(e); - ignore_unused_variable_warning(d); + ::lemon::ignore_unused_variable_warning(d); } } @@ -297,6 +299,172 @@ }; + /// \brief Base skeleton class for undirected bipartite graphs. + /// + /// This class describes the base interface of undirected + /// bipartite graph types. All bipartite graph %concepts have to + /// conform to this class. It extends the interface of \ref + /// BaseGraphComponent with an \c Edge type and functions to get + /// the end nodes of edges, to convert from arcs to edges and to + /// get both direction of edges. + class BaseBpGraphComponent : public BaseGraphComponent { + public: + + typedef BaseBpGraphComponent BpGraph; + + typedef BaseDigraphComponent::Node Node; + typedef BaseDigraphComponent::Arc Arc; + + /// \brief Class to represent red nodes. + /// + /// This class represents the red nodes of the graph. The red + /// nodes can also be used as normal nodes. + class RedNode : public Node { + typedef Node Parent; + + public: + /// \brief Default constructor. + /// + /// Default constructor. + /// \warning The default constructor is not required to set + /// the item to some well-defined value. So you should consider it + /// as uninitialized. + RedNode() {} + + /// \brief Copy constructor. + /// + /// Copy constructor. + RedNode(const RedNode &) : Parent() {} + + /// \brief Constructor for conversion from \c INVALID. + /// + /// Constructor for conversion from \c INVALID. + /// It initializes the item to be invalid. + /// \sa Invalid for more details. + RedNode(Invalid) {} + }; + + /// \brief Class to represent blue nodes. + /// + /// This class represents the blue nodes of the graph. The blue + /// nodes can also be used as normal nodes. + class BlueNode : public Node { + typedef Node Parent; + + public: + /// \brief Default constructor. + /// + /// Default constructor. + /// \warning The default constructor is not required to set + /// the item to some well-defined value. So you should consider it + /// as uninitialized. + BlueNode() {} + + /// \brief Copy constructor. + /// + /// Copy constructor. + BlueNode(const BlueNode &) : Parent() {} + + /// \brief Constructor for conversion from \c INVALID. + /// + /// Constructor for conversion from \c INVALID. + /// It initializes the item to be invalid. + /// \sa Invalid for more details. + BlueNode(Invalid) {} + + /// \brief Constructor for conversion from a node. + /// + /// Constructor for conversion from a node. The conversion can + /// be invalid, since the Node can be member of the red + /// set. + BlueNode(const Node&) {} + }; + + /// \brief Gives back %true for red nodes. + /// + /// Gives back %true for red nodes. + bool red(const Node&) const { return true; } + + /// \brief Gives back %true for blue nodes. + /// + /// Gives back %true for blue nodes. + bool blue(const Node&) const { return true; } + + /// \brief Gives back the red end node of the edge. + /// + /// Gives back the red end node of the edge. + RedNode redNode(const Edge&) const { return RedNode(); } + + /// \brief Gives back the blue end node of the edge. + /// + /// Gives back the blue end node of the edge. + BlueNode blueNode(const Edge&) const { return BlueNode(); } + + /// \brief Converts the node to red node object. + /// + /// This function converts unsafely the node to red node + /// object. It should be called only if the node is from the red + /// partition or INVALID. + RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); } + + /// \brief Converts the node to blue node object. + /// + /// This function converts unsafely the node to blue node + /// object. It should be called only if the node is from the red + /// partition or INVALID. + BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); } + + /// \brief Converts the node to red node object. + /// + /// This function converts safely the node to red node + /// object. If the node is not from the red partition, then it + /// returns INVALID. + RedNode asRedNode(const Node&) const { return RedNode(); } + + /// \brief Converts the node to blue node object. + /// + /// This function converts unsafely the node to blue node + /// object. If the node is not from the blue partition, then it + /// returns INVALID. + BlueNode asBlueNode(const Node&) const { return BlueNode(); } + + template + struct Constraints { + typedef typename _BpGraph::Node Node; + typedef typename _BpGraph::RedNode RedNode; + typedef typename _BpGraph::BlueNode BlueNode; + typedef typename _BpGraph::Arc Arc; + typedef typename _BpGraph::Edge Edge; + + void constraints() { + checkConcept(); + checkConcept, RedNode>(); + checkConcept, BlueNode>(); + { + Node n; + RedNode rn; + BlueNode bn; + Node rnan = rn; + Node bnan = bn; + Edge e; + bool b; + b = bpgraph.red(rnan); + b = bpgraph.blue(bnan); + rn = bpgraph.redNode(e); + bn = bpgraph.blueNode(e); + rn = bpgraph.asRedNodeUnsafe(rnan); + bn = bpgraph.asBlueNodeUnsafe(bnan); + rn = bpgraph.asRedNode(rnan); + bn = bpgraph.asBlueNode(bnan); + ::lemon::ignore_unused_variable_warning(b); + } + } + + const _BpGraph& bpgraph; + }; + + }; + /// \brief Skeleton class for \e idable directed graphs. /// /// This class describes the interface of \e idable directed graphs. @@ -366,9 +534,9 @@ arc = digraph.arcFromId(eid); nid = digraph.maxNodeId(); - ignore_unused_variable_warning(nid); + ::lemon::ignore_unused_variable_warning(nid); eid = digraph.maxArcId(); - ignore_unused_variable_warning(eid); + ::lemon::ignore_unused_variable_warning(eid); } const _Digraph& digraph; @@ -421,7 +589,7 @@ ueid = graph.id(edge); edge = graph.edgeFromId(ueid); ueid = graph.maxEdgeId(); - ignore_unused_variable_warning(ueid); + ::lemon::ignore_unused_variable_warning(ueid); } const _Graph& graph; @@ -429,6 +597,70 @@ }; }; + /// \brief Skeleton class for \e idable undirected bipartite graphs. + /// + /// This class describes the interface of \e idable undirected + /// bipartite graphs. It extends \ref IDableGraphComponent with + /// the core ID functions of undirected bipartite graphs. Beside + /// the regular node ids, this class also provides ids within the + /// the red and blue sets of the nodes. This concept is part of + /// the BpGraph concept. + template + class IDableBpGraphComponent : public IDableGraphComponent { + public: + + typedef BAS Base; + typedef IDableGraphComponent Parent; + typedef typename Base::Node Node; + typedef typename Base::RedNode RedNode; + typedef typename Base::BlueNode BlueNode; + + using Parent::id; + + /// \brief Return a unique integer id for the given node in the red set. + /// + /// Return a unique integer id for the given node in the red set. + int id(const RedNode&) const { return -1; } + + /// \brief Return a unique integer id for the given node in the blue set. + /// + /// Return a unique integer id for the given node in the blue set. + int id(const BlueNode&) const { return -1; } + + /// \brief Return an integer greater or equal to the maximum + /// node id in the red set. + /// + /// Return an integer greater or equal to the maximum + /// node id in the red set. + int maxRedId() const { return -1; } + + /// \brief Return an integer greater or equal to the maximum + /// node id in the blue set. + /// + /// Return an integer greater or equal to the maximum + /// node id in the blue set. + int maxBlueId() const { return -1; } + + template + struct Constraints { + + void constraints() { + checkConcept, _BpGraph>(); + typename _BpGraph::Node node; + typename _BpGraph::RedNode red; + typename _BpGraph::BlueNode blue; + int rid = bpgraph.id(red); + int bid = bpgraph.id(blue); + rid = bpgraph.maxRedId(); + bid = bpgraph.maxBlueId(); + ::lemon::ignore_unused_variable_warning(rid); + ::lemon::ignore_unused_variable_warning(bid); + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. /// /// This class describes the concept of \c NodeIt, \c ArcIt and @@ -494,8 +726,8 @@ _GraphItemIt it2; _GraphItemIt it3 = it1; _GraphItemIt it4 = INVALID; - ignore_unused_variable_warning(it3); - ignore_unused_variable_warning(it4); + ::lemon::ignore_unused_variable_warning(it3); + ::lemon::ignore_unused_variable_warning(it4); it2 = ++it1; ++it2 = it1; @@ -585,8 +817,8 @@ _GraphIncIt it2; _GraphIncIt it3 = it1; _GraphIncIt it4 = INVALID; - ignore_unused_variable_warning(it3); - ignore_unused_variable_warning(it4); + ::lemon::ignore_unused_variable_warning(it3); + ::lemon::ignore_unused_variable_warning(it4); it2 = ++it1; ++it2 = it1; @@ -643,15 +875,15 @@ /// This function gives back the next arc in the iteration order. void next(Arc&) const {} - /// \brief Return the first arc incomming to the given node. + /// \brief Return the first arc incoming to the given node. /// - /// This function gives back the first arc incomming to the + /// This function gives back the first arc incoming to the /// given node. void firstIn(Arc&, const Node&) const {} - /// \brief Return the next arc incomming to the given node. + /// \brief Return the next arc incoming to the given node. /// - /// This function gives back the next arc incomming to the + /// This function gives back the next arc incoming to the /// given node. void nextIn(Arc&) const {} @@ -768,7 +1000,7 @@ n = digraph.runningNode(iait); n = digraph.baseNode(oait); n = digraph.runningNode(oait); - ignore_unused_variable_warning(n); + ::lemon::ignore_unused_variable_warning(n); } } @@ -902,6 +1134,97 @@ }; }; + /// \brief Skeleton class for iterable undirected bipartite graphs. + /// + /// This class describes the interface of iterable undirected + /// bipartite graphs. It extends \ref IterableGraphComponent with + /// the core iterable interface of undirected bipartite graphs. + /// This concept is part of the BpGraph concept. + template + class IterableBpGraphComponent : public IterableGraphComponent { + public: + + typedef BAS Base; + typedef typename Base::Node Node; + typedef typename Base::RedNode RedNode; + typedef typename Base::BlueNode BlueNode; + typedef typename Base::Arc Arc; + typedef typename Base::Edge Edge; + + typedef IterableBpGraphComponent BpGraph; + + using IterableGraphComponent::first; + using IterableGraphComponent::next; + + /// \name Base Iteration + /// + /// This interface provides functions for iteration on red and blue nodes. + /// + /// @{ + + /// \brief Return the first red node. + /// + /// This function gives back the first red node in the iteration order. + void first(RedNode&) const {} + + /// \brief Return the next red node. + /// + /// This function gives back the next red node in the iteration order. + void next(RedNode&) const {} + + /// \brief Return the first blue node. + /// + /// This function gives back the first blue node in the iteration order. + void first(BlueNode&) const {} + + /// \brief Return the next blue node. + /// + /// This function gives back the next blue node in the iteration order. + void next(BlueNode&) const {} + + + /// @} + + /// \name Class Based Iteration + /// + /// This interface provides iterator classes for red and blue nodes. + /// + /// @{ + + /// \brief This iterator goes through each red node. + /// + /// This iterator goes through each red node. + typedef GraphItemIt RedNodeIt; + + /// \brief This iterator goes through each blue node. + /// + /// This iterator goes through each blue node. + typedef GraphItemIt BlueNodeIt; + + /// @} + + template + struct Constraints { + void constraints() { + checkConcept, _BpGraph>(); + + typename _BpGraph::RedNode rn(INVALID); + bpgraph.first(rn); + bpgraph.next(rn); + typename _BpGraph::BlueNode bn(INVALID); + bpgraph.first(bn); + bpgraph.next(bn); + + checkConcept, + typename _BpGraph::RedNodeIt>(); + checkConcept, + typename _BpGraph::BlueNodeIt>(); + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for alterable directed graphs. /// /// This class describes the interface of alterable directed @@ -927,18 +1250,21 @@ typedef AlterationNotifier ArcNotifier; + mutable NodeNotifier node_notifier; + mutable ArcNotifier arc_notifier; + /// \brief Return the node alteration notifier. /// /// This function gives back the node alteration notifier. NodeNotifier& notifier(Node) const { - return NodeNotifier(); + return node_notifier; } /// \brief Return the arc alteration notifier. /// /// This function gives back the arc alteration notifier. ArcNotifier& notifier(Arc) const { - return ArcNotifier(); + return arc_notifier; } template @@ -951,8 +1277,8 @@ typename _Digraph::ArcNotifier& en = digraph.notifier(typename _Digraph::Arc()); - ignore_unused_variable_warning(nn); - ignore_unused_variable_warning(en); + ::lemon::ignore_unused_variable_warning(nn); + ::lemon::ignore_unused_variable_warning(en); } const _Digraph& digraph; @@ -974,6 +1300,7 @@ public: typedef BAS Base; + typedef AlterableDigraphComponent Parent; typedef typename Base::Edge Edge; @@ -981,11 +1308,15 @@ typedef AlterationNotifier EdgeNotifier; + mutable EdgeNotifier edge_notifier; + + using Parent::notifier; + /// \brief Return the edge alteration notifier. /// /// This function gives back the edge alteration notifier. EdgeNotifier& notifier(Edge) const { - return EdgeNotifier(); + return edge_notifier; } template @@ -994,7 +1325,7 @@ checkConcept, _Graph>(); typename _Graph::EdgeNotifier& uen = graph.notifier(typename _Graph::Edge()); - ignore_unused_variable_warning(uen); + ::lemon::ignore_unused_variable_warning(uen); } const _Graph& graph; @@ -1002,6 +1333,68 @@ }; }; + /// \brief Skeleton class for alterable undirected bipartite graphs. + /// + /// This class describes the interface of alterable undirected + /// bipartite graphs. It extends \ref AlterableGraphComponent with + /// the alteration notifier interface of bipartite graphs. It + /// implements an observer-notifier pattern for the red and blue + /// nodes. More obsevers can be registered into the notifier and + /// whenever an alteration occured in the graph all the observers + /// will be notified about it. + template + class AlterableBpGraphComponent : public AlterableGraphComponent { + public: + + typedef BAS Base; + typedef AlterableGraphComponent Parent; + typedef typename Base::RedNode RedNode; + typedef typename Base::BlueNode BlueNode; + + + /// Red node alteration notifier class. + typedef AlterationNotifier + RedNodeNotifier; + + /// Blue node alteration notifier class. + typedef AlterationNotifier + BlueNodeNotifier; + + mutable RedNodeNotifier red_node_notifier; + mutable BlueNodeNotifier blue_node_notifier; + + using Parent::notifier; + + /// \brief Return the red node alteration notifier. + /// + /// This function gives back the red node alteration notifier. + RedNodeNotifier& notifier(RedNode) const { + return red_node_notifier; + } + + /// \brief Return the blue node alteration notifier. + /// + /// This function gives back the blue node alteration notifier. + BlueNodeNotifier& notifier(BlueNode) const { + return blue_node_notifier; + } + + template + struct Constraints { + void constraints() { + checkConcept, _BpGraph>(); + typename _BpGraph::RedNodeNotifier& rnn + = bpgraph.notifier(typename _BpGraph::RedNode()); + typename _BpGraph::BlueNodeNotifier& bnn + = bpgraph.notifier(typename _BpGraph::BlueNode()); + ::lemon::ignore_unused_variable_warning(rnn); + ::lemon::ignore_unused_variable_warning(bnn); + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Concept class for standard graph maps. /// /// This class describes the concept of standard graph maps, i.e. @@ -1068,9 +1461,9 @@ // ReadMap cmap; // m3 = cmap; - ignore_unused_variable_warning(m1); - ignore_unused_variable_warning(m2); - // ignore_unused_variable_warning(m3); + ::lemon::ignore_unused_variable_warning(m1); + ::lemon::ignore_unused_variable_warning(m2); + // ::lemon::ignore_unused_variable_warning(m3); } const _Map &m; @@ -1305,6 +1698,150 @@ }; }; + /// \brief Skeleton class for mappable undirected bipartite graphs. + /// + /// This class describes the interface of mappable undirected + /// bipartite graphs. It extends \ref MappableGraphComponent with + /// the standard graph map class for red and blue nodes (\c + /// RedNodeMap and BlueNodeMap). This concept is part of the + /// BpGraph concept. + template + class MappableBpGraphComponent : public MappableGraphComponent { + public: + + typedef BAS Base; + typedef typename Base::Node Node; + + typedef MappableBpGraphComponent BpGraph; + + /// \brief Standard graph map for the red nodes. + /// + /// Standard graph map for the red nodes. + /// It conforms to the ReferenceMap concept. + template + class RedNodeMap : public GraphMap { + typedef GraphMap Parent; + + public: + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit RedNodeMap(const MappableBpGraphComponent& graph) + : Parent(graph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalize the values. + RedNodeMap(const MappableBpGraphComponent& graph, const V& value) + : Parent(graph, value) {} + + private: + /// \brief Copy constructor. + /// + /// Copy Constructor. + RedNodeMap(const RedNodeMap& nm) : Parent(nm) {} + + /// \brief Assignment operator. + /// + /// Assignment operator. + template + RedNodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + /// \brief Standard graph map for the blue nodes. + /// + /// Standard graph map for the blue nodes. + /// It conforms to the ReferenceMap concept. + template + class BlueNodeMap : public GraphMap { + typedef GraphMap Parent; + + public: + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit BlueNodeMap(const MappableBpGraphComponent& graph) + : Parent(graph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalize the values. + BlueNodeMap(const MappableBpGraphComponent& graph, const V& value) + : Parent(graph, value) {} + + private: + /// \brief Copy constructor. + /// + /// Copy Constructor. + BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {} + + /// \brief Assignment operator. + /// + /// Assignment operator. + template + BlueNodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + + }; + + + template + struct Constraints { + + struct Dummy { + int value; + Dummy() : value(0) {} + Dummy(int _v) : value(_v) {} + }; + + void constraints() { + checkConcept, _BpGraph>(); + + { // int map test + typedef typename _BpGraph::template RedNodeMap + IntRedNodeMap; + checkConcept, + IntRedNodeMap >(); + } { // bool map test + typedef typename _BpGraph::template RedNodeMap + BoolRedNodeMap; + checkConcept, + BoolRedNodeMap >(); + } { // Dummy map test + typedef typename _BpGraph::template RedNodeMap + DummyRedNodeMap; + checkConcept, + DummyRedNodeMap >(); + } + + { // int map test + typedef typename _BpGraph::template BlueNodeMap + IntBlueNodeMap; + checkConcept, + IntBlueNodeMap >(); + } { // bool map test + typedef typename _BpGraph::template BlueNodeMap + BoolBlueNodeMap; + checkConcept, + BoolBlueNodeMap >(); + } { // Dummy map test + typedef typename _BpGraph::template BlueNodeMap + DummyBlueNodeMap; + checkConcept, + DummyBlueNodeMap >(); + } + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for extendable directed graphs. /// /// This class describes the interface of extendable directed graphs. @@ -1395,6 +1932,65 @@ }; }; + /// \brief Skeleton class for extendable undirected bipartite graphs. + /// + /// This class describes the interface of extendable undirected + /// bipartite graphs. It extends \ref BaseGraphComponent with + /// functions for adding nodes and edges to the graph. This + /// concept requires \ref AlterableBpGraphComponent. + template + class ExtendableBpGraphComponent : public BAS { + public: + + typedef BAS Base; + typedef typename Base::Node Node; + typedef typename Base::RedNode RedNode; + typedef typename Base::BlueNode BlueNode; + typedef typename Base::Edge Edge; + + /// \brief Add a new red node to the digraph. + /// + /// This function adds a red new node to the digraph. + RedNode addRedNode() { + return INVALID; + } + + /// \brief Add a new blue node to the digraph. + /// + /// This function adds a blue new node to the digraph. + BlueNode addBlueNode() { + return INVALID; + } + + /// \brief Add a new edge connecting the given two nodes. + /// + /// This function adds a new edge connecting the given two nodes + /// of the graph. The first node has to be a red node, and the + /// second one a blue node. + Edge addEdge(const RedNode&, const BlueNode&) { + return INVALID; + } + Edge addEdge(const BlueNode&, const RedNode&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _BpGraph::RedNode red_node; + typename _BpGraph::BlueNode blue_node; + red_node = bpgraph.addRedNode(); + blue_node = bpgraph.addBlueNode(); + typename _BpGraph::Edge edge; + edge = bpgraph.addEdge(red_node, blue_node); + edge = bpgraph.addEdge(blue_node, red_node); + } + + _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for erasable directed graphs. /// /// This class describes the interface of erasable directed graphs. @@ -1475,6 +2071,15 @@ }; }; + /// \brief Skeleton class for erasable undirected graphs. + /// + /// This class describes the interface of erasable undirected + /// bipartite graphs. It extends \ref BaseBpGraphComponent with + /// functions for removing nodes and edges from the graph. This + /// concept requires \ref AlterableBpGraphComponent. + template + class ErasableBpGraphComponent : public ErasableGraphComponent {}; + /// \brief Skeleton class for clearable directed graphs. /// /// This class describes the interface of clearable directed graphs. @@ -1511,27 +2116,16 @@ /// the graph. /// This concept requires \ref AlterableGraphComponent. template - class ClearableGraphComponent : public ClearableDigraphComponent { - public: + class ClearableGraphComponent : public ClearableDigraphComponent {}; - typedef BAS Base; - - /// \brief Erase all nodes and edges from the graph. - /// - /// This function erases all nodes and edges from the graph. - void clear() {} - - template - struct Constraints { - void constraints() { - checkConcept(); - graph.clear(); - } - - _Graph& graph; - Constraints() {} - }; - }; + /// \brief Skeleton class for clearable undirected biparite graphs. + /// + /// This class describes the interface of clearable undirected + /// bipartite graphs. It extends \ref BaseBpGraphComponent with a + /// function for clearing the graph. This concept requires \ref + /// AlterableBpGraphComponent. + template + class ClearableBpGraphComponent : public ClearableGraphComponent {}; }