# HG changeset patch # User Balazs Dezso # Date 1289748931 -3600 # Node ID 2e959a5a0c2d1597ddc731f8a3cc558d5787ba31 # Parent b4f4c08e12104568afd3bcd60594dfc119e06ebf Add bipartite graph concepts (#69) diff -r b4f4c08e1210 -r 2e959a5a0c2d lemon/concepts/bpgraph.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/concepts/bpgraph.h Sun Nov 14 16:35:31 2010 +0100 @@ -0,0 +1,1020 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +///\ingroup graph_concepts +///\file +///\brief The concept of undirected graphs. + +#ifndef LEMON_CONCEPTS_BPGRAPH_H +#define LEMON_CONCEPTS_BPGRAPH_H + +#include +#include +#include +#include + +namespace lemon { + namespace concepts { + + /// \ingroup graph_concepts + /// + /// \brief Class describing the concept of undirected bipartite graphs. + /// + /// This class describes the common interface of all undirected + /// bipartite graphs. + /// + /// Like all concept classes, it only provides an interface + /// without any sensible implementation. So any general algorithm for + /// undirected bipartite graphs should compile with this class, + /// but it will not run properly, of course. + /// An actual graph implementation like \ref ListBpGraph or + /// \ref SmartBpGraph may have additional functionality. + /// + /// The bipartite graphs also fulfill the concept of \ref Graph + /// "undirected graphs". Bipartite graphs provide a bipartition of + /// the node set, namely a red and blue set of the nodes. The + /// nodes can be iterated with the RedIt and BlueIt in the two + /// node sets. With RedMap and BlueMap values can be assigned to + /// the nodes in the two sets. + /// + /// The edges of the graph cannot connect two nodes of the same + /// set. The edges inherent orientation is from the red nodes to + /// the blue nodes. + /// + /// \sa Graph + class BpGraph { + private: + /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead. + BpGraph(const BpGraph&) {} + /// \brief Assignment of a graph to another one is \e not allowed. + /// Use bpGraphCopy instead. + void operator=(const BpGraph&) {} + + public: + /// Default constructor. + BpGraph() {} + + /// \brief Undirected graphs should be tagged with \c UndirectedTag. + /// + /// Undirected graphs should be tagged with \c UndirectedTag. + /// + /// This tag helps the \c enable_if technics to make compile time + /// specializations for undirected graphs. + typedef True UndirectedTag; + + /// The node type of the graph + + /// This class identifies a node of the graph. It also serves + /// as a base class of the node iterators, + /// thus they convert to this type. + class Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the object to an undefined value. + Node() { } + /// Copy constructor. + + /// Copy constructor. + /// + Node(const Node&) { } + + /// %Invalid constructor \& conversion. + + /// Initializes the object to be invalid. + /// \sa Invalid for more details. + Node(Invalid) { } + /// Equality operator + + /// Equality operator. + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are \c INVALID. + bool operator==(Node) const { return true; } + + /// Inequality operator + + /// Inequality operator. + bool operator!=(Node) const { return true; } + + /// Artificial ordering operator. + + /// Artificial ordering operator. + /// + /// \note This operator only has to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + bool operator<(Node) const { return false; } + + }; + + /// Class to represent red nodes. + + /// This class represents the red nodes of the graph. It does + /// not supposed to be used directly, because the nodes can be + /// represented as Node instances. This class can be used as + /// template parameter for special map classes. + class RedNode : public Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the object to an undefined value. + RedNode() { } + /// Copy constructor. + + /// Copy constructor. + /// + RedNode(const RedNode&) : Node() { } + + /// %Invalid constructor \& conversion. + + /// Initializes the object to be invalid. + /// \sa Invalid for more details. + RedNode(Invalid) { } + + /// 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 blue + /// set. + RedNode(const Node&) {} + }; + + /// Class to represent blue nodes. + + /// This class represents the blue nodes of the graph. It does + /// not supposed to be used directly, because the nodes can be + /// represented as Node instances. This class can be used as + /// template parameter for special map classes. + class BlueNode : public Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the object to an undefined value. + BlueNode() { } + /// Copy constructor. + + /// Copy constructor. + /// + BlueNode(const BlueNode&) : Node() { } + + /// %Invalid constructor \& conversion. + + /// Initializes the object to be invalid. + /// \sa Invalid for more details. + BlueNode(Invalid) { } + + /// 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&) {} + }; + + /// Iterator class for the red nodes. + + /// This iterator goes through each red node of the graph. + /// Its usage is quite simple, for example, you can count the number + /// of red nodes in a graph \c g of type \c %BpGraph like this: + ///\code + /// int count=0; + /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count; + ///\endcode + class RedIt : public Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + RedIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + RedIt(const RedIt& n) : Node(n) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + RedIt(Invalid) { } + /// Sets the iterator to the first red node. + + /// Sets the iterator to the first red node of the given + /// digraph. + explicit RedIt(const BpGraph&) { } + /// Sets the iterator to the given red node. + + /// Sets the iterator to the given red node of the given + /// digraph. + RedIt(const BpGraph&, const Node&) { } + /// Next node. + + /// Assign the iterator to the next red node. + /// + RedIt& operator++() { return *this; } + }; + + /// Iterator class for the blue nodes. + + /// This iterator goes through each blue node of the graph. + /// Its usage is quite simple, for example, you can count the number + /// of blue nodes in a graph \c g of type \c %BpGraph like this: + ///\code + /// int count=0; + /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count; + ///\endcode + class BlueIt : public Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + BlueIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + BlueIt(const BlueIt& n) : Node(n) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + BlueIt(Invalid) { } + /// Sets the iterator to the first blue node. + + /// Sets the iterator to the first blue node of the given + /// digraph. + explicit BlueIt(const BpGraph&) { } + /// Sets the iterator to the given blue node. + + /// Sets the iterator to the given blue node of the given + /// digraph. + BlueIt(const BpGraph&, const Node&) { } + /// Next node. + + /// Assign the iterator to the next blue node. + /// + BlueIt& operator++() { return *this; } + }; + + /// Iterator class for the nodes. + + /// This iterator goes through each node of the graph. + /// Its usage is quite simple, for example, you can count the number + /// of nodes in a graph \c g of type \c %BpGraph like this: + ///\code + /// int count=0; + /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count; + ///\endcode + class NodeIt : public Node { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + NodeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + NodeIt(const NodeIt& n) : Node(n) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + NodeIt(Invalid) { } + /// Sets the iterator to the first node. + + /// Sets the iterator to the first node of the given digraph. + /// + explicit NodeIt(const BpGraph&) { } + /// Sets the iterator to the given node. + + /// Sets the iterator to the given node of the given digraph. + /// + NodeIt(const BpGraph&, const Node&) { } + /// Next node. + + /// Assign the iterator to the next node. + /// + NodeIt& operator++() { return *this; } + }; + + + /// The edge type of the graph + + /// This class identifies an edge of the graph. It also serves + /// as a base class of the edge iterators, + /// thus they will convert to this type. + class Edge { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the object to an undefined value. + Edge() { } + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge&) { } + /// %Invalid constructor \& conversion. + + /// Initializes the object to be invalid. + /// \sa Invalid for more details. + Edge(Invalid) { } + /// Equality operator + + /// Equality operator. + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are \c INVALID. + bool operator==(Edge) const { return true; } + /// Inequality operator + + /// Inequality operator. + bool operator!=(Edge) const { return true; } + + /// Artificial ordering operator. + + /// Artificial ordering operator. + /// + /// \note This operator only has to define some strict ordering of + /// the edges; this order has nothing to do with the iteration + /// ordering of the edges. + bool operator<(Edge) const { return false; } + }; + + /// Iterator class for the edges. + + /// This iterator goes through each edge of the graph. + /// Its usage is quite simple, for example, you can count the number + /// of edges in a graph \c g of type \c %BpGraph as follows: + ///\code + /// int count=0; + /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count; + ///\endcode + class EdgeIt : public Edge { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + EdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + EdgeIt(const EdgeIt& e) : Edge(e) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + EdgeIt(Invalid) { } + /// Sets the iterator to the first edge. + + /// Sets the iterator to the first edge of the given graph. + /// + explicit EdgeIt(const BpGraph&) { } + /// Sets the iterator to the given edge. + + /// Sets the iterator to the given edge of the given graph. + /// + EdgeIt(const BpGraph&, const Edge&) { } + /// Next edge + + /// Assign the iterator to the next edge. + /// + EdgeIt& operator++() { return *this; } + }; + + /// Iterator class for the incident edges of a node. + + /// This iterator goes trough the incident undirected edges + /// of a certain node of a graph. + /// Its usage is quite simple, for example, you can compute the + /// degree (i.e. the number of incident edges) of a node \c n + /// in a graph \c g of type \c %BpGraph as follows. + /// + ///\code + /// int count=0; + /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; + ///\endcode + /// + /// \warning Loop edges will be iterated twice. + class IncEdgeIt : public Edge { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + IncEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + IncEdgeIt(Invalid) { } + /// Sets the iterator to the first incident edge. + + /// Sets the iterator to the first incident edge of the given node. + /// + IncEdgeIt(const BpGraph&, const Node&) { } + /// Sets the iterator to the given edge. + + /// Sets the iterator to the given edge of the given graph. + /// + IncEdgeIt(const BpGraph&, const Edge&) { } + /// Next incident edge + + /// Assign the iterator to the next incident edge + /// of the corresponding node. + IncEdgeIt& operator++() { return *this; } + }; + + /// The arc type of the graph + + /// This class identifies a directed arc of the graph. It also serves + /// as a base class of the arc iterators, + /// thus they will convert to this type. + class Arc { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the object to an undefined value. + Arc() { } + /// Copy constructor. + + /// Copy constructor. + /// + Arc(const Arc&) { } + /// %Invalid constructor \& conversion. + + /// Initializes the object to be invalid. + /// \sa Invalid for more details. + Arc(Invalid) { } + /// Equality operator + + /// Equality operator. + /// + /// Two iterators are equal if and only if they point to the + /// same object or both are \c INVALID. + bool operator==(Arc) const { return true; } + /// Inequality operator + + /// Inequality operator. + bool operator!=(Arc) const { return true; } + + /// Artificial ordering operator. + + /// Artificial ordering operator. + /// + /// \note This operator only has to define some strict ordering of + /// the arcs; this order has nothing to do with the iteration + /// ordering of the arcs. + bool operator<(Arc) const { return false; } + + /// Converison to \c Edge + + /// Converison to \c Edge. + /// + operator Edge() const { return Edge(); } + }; + + /// Iterator class for the arcs. + + /// This iterator goes through each directed arc of the graph. + /// Its usage is quite simple, for example, you can count the number + /// of arcs in a graph \c g of type \c %BpGraph as follows: + ///\code + /// int count=0; + /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count; + ///\endcode + class ArcIt : public Arc { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + ArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + ArcIt(const ArcIt& e) : Arc(e) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + ArcIt(Invalid) { } + /// Sets the iterator to the first arc. + + /// Sets the iterator to the first arc of the given graph. + /// + explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); } + /// Sets the iterator to the given arc. + + /// Sets the iterator to the given arc of the given graph. + /// + ArcIt(const BpGraph&, const Arc&) { } + /// Next arc + + /// Assign the iterator to the next arc. + /// + ArcIt& operator++() { return *this; } + }; + + /// Iterator class for the outgoing arcs of a node. + + /// This iterator goes trough the \e outgoing directed arcs of a + /// certain node of a graph. + /// Its usage is quite simple, for example, you can count the number + /// of outgoing arcs of a node \c n + /// in a graph \c g of type \c %BpGraph as follows. + ///\code + /// int count=0; + /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; + ///\endcode + class OutArcIt : public Arc { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + OutArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + OutArcIt(const OutArcIt& e) : Arc(e) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + OutArcIt(Invalid) { } + /// Sets the iterator to the first outgoing arc. + + /// Sets the iterator to the first outgoing arc of the given node. + /// + OutArcIt(const BpGraph& n, const Node& g) { + ignore_unused_variable_warning(n); + ignore_unused_variable_warning(g); + } + /// Sets the iterator to the given arc. + + /// Sets the iterator to the given arc of the given graph. + /// + OutArcIt(const BpGraph&, const Arc&) { } + /// Next outgoing arc + + /// Assign the iterator to the next + /// outgoing arc of the corresponding node. + OutArcIt& operator++() { return *this; } + }; + + /// Iterator class for the incoming arcs of a node. + + /// This iterator goes trough the \e incoming directed arcs of a + /// certain node of a graph. + /// Its usage is quite simple, for example, you can count the number + /// of incoming arcs of a node \c n + /// in a graph \c g of type \c %BpGraph as follows. + ///\code + /// int count=0; + /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; + ///\endcode + class InArcIt : public Arc { + public: + /// Default constructor + + /// Default constructor. + /// \warning It sets the iterator to an undefined value. + InArcIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + InArcIt(const InArcIt& e) : Arc(e) { } + /// %Invalid constructor \& conversion. + + /// Initializes the iterator to be invalid. + /// \sa Invalid for more details. + InArcIt(Invalid) { } + /// Sets the iterator to the first incoming arc. + + /// Sets the iterator to the first incoming arc of the given node. + /// + InArcIt(const BpGraph& g, const Node& n) { + ignore_unused_variable_warning(n); + ignore_unused_variable_warning(g); + } + /// Sets the iterator to the given arc. + + /// Sets the iterator to the given arc of the given graph. + /// + InArcIt(const BpGraph&, const Arc&) { } + /// Next incoming arc + + /// Assign the iterator to the next + /// incoming arc of the corresponding node. + InArcIt& operator++() { return *this; } + }; + + /// \brief Standard graph map type for the nodes. + /// + /// Standard graph map type for the nodes. + /// It conforms to the ReferenceMap concept. + template + class NodeMap : public ReferenceMap + { + public: + + /// Constructor + explicit NodeMap(const BpGraph&) { } + /// Constructor with given initial value + NodeMap(const BpGraph&, T) { } + + private: + ///Copy constructor + NodeMap(const NodeMap& nm) : + ReferenceMap(nm) { } + ///Assignment operator + template + NodeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Standard graph map type for the red nodes. + /// + /// Standard graph map type for the red nodes. + /// It conforms to the ReferenceMap concept. + template + class RedMap : public ReferenceMap + { + public: + + /// Constructor + explicit RedMap(const BpGraph&) { } + /// Constructor with given initial value + RedMap(const BpGraph&, T) { } + + private: + ///Copy constructor + RedMap(const RedMap& nm) : + ReferenceMap(nm) { } + ///Assignment operator + template + RedMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Standard graph map type for the blue nodes. + /// + /// Standard graph map type for the blue nodes. + /// It conforms to the ReferenceMap concept. + template + class BlueMap : public ReferenceMap + { + public: + + /// Constructor + explicit BlueMap(const BpGraph&) { } + /// Constructor with given initial value + BlueMap(const BpGraph&, T) { } + + private: + ///Copy constructor + BlueMap(const BlueMap& nm) : + ReferenceMap(nm) { } + ///Assignment operator + template + BlueMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Standard graph map type for the arcs. + /// + /// Standard graph map type for the arcs. + /// It conforms to the ReferenceMap concept. + template + class ArcMap : public ReferenceMap + { + public: + + /// Constructor + explicit ArcMap(const BpGraph&) { } + /// Constructor with given initial value + ArcMap(const BpGraph&, T) { } + + private: + ///Copy constructor + ArcMap(const ArcMap& em) : + ReferenceMap(em) { } + ///Assignment operator + template + ArcMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \brief Standard graph map type for the edges. + /// + /// Standard graph map type for the edges. + /// It conforms to the ReferenceMap concept. + template + class EdgeMap : public ReferenceMap + { + public: + + /// Constructor + explicit EdgeMap(const BpGraph&) { } + /// Constructor with given initial value + EdgeMap(const BpGraph&, T) { } + + private: + ///Copy constructor + EdgeMap(const EdgeMap& em) : + ReferenceMap(em) {} + ///Assignment operator + template + EdgeMap& operator=(const CMap&) { + checkConcept, CMap>(); + return *this; + } + }; + + /// \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. + Node redNode(const Edge&) const { return Node(); } + + /// \brief Gives back the blue end node of the edge. + /// + /// Gives back the blue end node of the edge. + Node blueNode(const Edge&) const { return Node(); } + + /// \brief The first node of the edge. + /// + /// It is a synonim for the \c redNode(). + Node u(Edge) const { return INVALID; } + + /// \brief The second node of the edge. + /// + /// It is a synonim for the \c blueNode(). + Node v(Edge) const { return INVALID; } + + /// \brief The source node of the arc. + /// + /// Returns the source node of the given arc. + Node source(Arc) const { return INVALID; } + + /// \brief The target node of the arc. + /// + /// Returns the target node of the given arc. + Node target(Arc) const { return INVALID; } + + /// \brief The ID of the node. + /// + /// Returns the ID of the given node. + int id(Node) const { return -1; } + + /// \brief The red ID of the node. + /// + /// Returns the red ID of the given node. + int redId(Node) const { return -1; } + + /// \brief The red ID of the node. + /// + /// Returns the red ID of the given node. + int id(RedNode) const { return -1; } + + /// \brief The blue ID of the node. + /// + /// Returns the blue ID of the given node. + int blueId(Node) const { return -1; } + + /// \brief The blue ID of the node. + /// + /// Returns the blue ID of the given node. + int id(BlueNode) const { return -1; } + + /// \brief The ID of the edge. + /// + /// Returns the ID of the given edge. + int id(Edge) const { return -1; } + + /// \brief The ID of the arc. + /// + /// Returns the ID of the given arc. + int id(Arc) const { return -1; } + + /// \brief The node with the given ID. + /// + /// Returns the node with the given ID. + /// \pre The argument should be a valid node ID in the graph. + Node nodeFromId(int) const { return INVALID; } + + /// \brief The edge with the given ID. + /// + /// Returns the edge with the given ID. + /// \pre The argument should be a valid edge ID in the graph. + Edge edgeFromId(int) const { return INVALID; } + + /// \brief The arc with the given ID. + /// + /// Returns the arc with the given ID. + /// \pre The argument should be a valid arc ID in the graph. + Arc arcFromId(int) const { return INVALID; } + + /// \brief An upper bound on the node IDs. + /// + /// Returns an upper bound on the node IDs. + int maxNodeId() const { return -1; } + + /// \brief An upper bound on the red IDs. + /// + /// Returns an upper bound on the red IDs. + int maxRedId() const { return -1; } + + /// \brief An upper bound on the blue IDs. + /// + /// Returns an upper bound on the blue IDs. + int maxBlueId() const { return -1; } + + /// \brief An upper bound on the edge IDs. + /// + /// Returns an upper bound on the edge IDs. + int maxEdgeId() const { return -1; } + + /// \brief An upper bound on the arc IDs. + /// + /// Returns an upper bound on the arc IDs. + int maxArcId() const { return -1; } + + /// \brief The direction of the arc. + /// + /// Returns \c true if the given arc goes from a red node to a blue node. + bool direction(Arc) const { return true; } + + /// \brief Direct the edge. + /// + /// Direct the given edge. The returned arc + /// represents the given edge and its direction comes + /// from the bool parameter. If it is \c true, then the source of the node + /// will be a red node. + Arc direct(Edge, bool) const { + return INVALID; + } + + /// \brief Direct the edge. + /// + /// Direct the given edge. The returned arc represents the given + /// edge and its source node is the given node. + Arc direct(Edge, Node) const { + return INVALID; + } + + /// \brief The oppositely directed arc. + /// + /// Returns the oppositely directed arc representing the same edge. + Arc oppositeArc(Arc) const { return INVALID; } + + /// \brief The opposite node on the edge. + /// + /// Returns the opposite node on the given edge. + Node oppositeNode(Node, Edge) const { return INVALID; } + + void first(Node&) const {} + void next(Node&) const {} + + void firstRed(Node&) const {} + void nextRed(Node&) const {} + + void firstBlue(Node&) const {} + void nextBlue(Node&) const {} + + void first(Edge&) const {} + void next(Edge&) const {} + + void first(Arc&) const {} + void next(Arc&) const {} + + void firstOut(Arc&, Node) const {} + void nextOut(Arc&) const {} + + void firstIn(Arc&, Node) const {} + void nextIn(Arc&) const {} + + void firstInc(Edge &, bool &, const Node &) const {} + void nextInc(Edge &, bool &) const {} + + // The second parameter is dummy. + Node fromId(int, Node) const { return INVALID; } + // The second parameter is dummy. + Edge fromId(int, Edge) const { return INVALID; } + // The second parameter is dummy. + Arc fromId(int, Arc) const { return INVALID; } + + // Dummy parameter. + int maxId(Node) const { return -1; } + // Dummy parameter. + int maxId(RedNode) const { return -1; } + // Dummy parameter. + int maxId(BlueNode) const { return -1; } + // Dummy parameter. + int maxId(Edge) const { return -1; } + // Dummy parameter. + int maxId(Arc) const { return -1; } + + /// \brief The base node of the iterator. + /// + /// Returns the base node of the given incident edge iterator. + Node baseNode(IncEdgeIt) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Returns the running node of the given incident edge iterator. + Node runningNode(IncEdgeIt) const { return INVALID; } + + /// \brief The base node of the iterator. + /// + /// Returns the base node of the given outgoing arc iterator + /// (i.e. the source node of the corresponding arc). + Node baseNode(OutArcIt) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Returns the running node of the given outgoing arc iterator + /// (i.e. the target node of the corresponding arc). + Node runningNode(OutArcIt) const { return INVALID; } + + /// \brief The base node of the iterator. + /// + /// Returns the base node of the given incomming arc iterator + /// (i.e. the target node of the corresponding arc). + Node baseNode(InArcIt) const { return INVALID; } + + /// \brief The running node of the iterator. + /// + /// Returns the running node of the given incomming arc iterator + /// (i.e. the source node of the corresponding arc). + Node runningNode(InArcIt) const { return INVALID; } + + template + struct Constraints { + void constraints() { + checkConcept(); + checkConcept, _BpGraph>(); + checkConcept, _BpGraph>(); + checkConcept, _BpGraph>(); + } + }; + + }; + + } + +} + +#endif diff -r b4f4c08e1210 -r 2e959a5a0c2d lemon/concepts/graph.h --- a/lemon/concepts/graph.h Sun Feb 24 19:44:14 2013 +0100 +++ b/lemon/concepts/graph.h Sun Nov 14 16:35:31 2010 +0100 @@ -72,10 +72,10 @@ /// \sa Digraph class Graph { private: - /// Graphs are \e not copy constructible. Use DigraphCopy instead. + /// Graphs are \e not copy constructible. Use GraphCopy instead. Graph(const Graph&) {} /// \brief Assignment of a graph to another one is \e not allowed. - /// Use DigraphCopy instead. + /// Use GraphCopy instead. void operator=(const Graph&) {} public: diff -r b4f4c08e1210 -r 2e959a5a0c2d lemon/concepts/graph_components.h --- a/lemon/concepts/graph_components.h Sun Feb 24 19:44:14 2013 +0100 +++ b/lemon/concepts/graph_components.h Sun Nov 14 16:35:31 2010 +0100 @@ -299,6 +299,151 @@ }; + /// \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. It does + /// not supposed to be used directly, because the nodes can be + /// represented as Node instances. This class can be used as + /// template parameter for special map classes. + 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 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 blue + /// set. + RedNode(const Node&) {} + }; + + /// \brief Class to represent blue nodes. + /// + /// This class represents the blue nodes of the graph. It does + /// not supposed to be used directly, because the nodes can be + /// represented as Node instances. This class can be used as + /// template parameter for special map classes. + 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. + Node redNode(const Edge&) const { return Node(); } + + /// \brief Gives back the blue end node of the edge. + /// + /// Gives back the blue end node of the edge. + Node blueNode(const Edge&) const { return Node(); } + + 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 = n; + BlueNode bn = bn; + Edge e; + bool b; + b = bpgraph.red(n); + b = bpgraph.blue(n); + ignore_unused_variable_warning(b); + n = bpgraph.redNode(e); + n = bpgraph.blueNode(e); + rn = n; + bn = n; + } + } + + const _BpGraph& bpgraph; + }; + + }; + /// \brief Skeleton class for \e idable directed graphs. /// /// This class describes the interface of \e idable directed graphs. @@ -431,6 +576,82 @@ }; }; + /// \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 redId(const Node&) const { return -1; } + + /// \brief Return the same value as redId(). + /// + /// Return the same value as redId(). + 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 blueId(const Node&) const { return -1; } + + /// \brief Return the same value as blueId(). + /// + /// Return the same value as blueId(). + 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.redId(node); + int bid = bpgraph.blueId(node); + rid = bpgraph.id(red); + bid = bpgraph.id(blue); + rid = bpgraph.maxRedId(); + bid = bpgraph.maxBlueId(); + ignore_unused_variable_warning(rid); + 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 @@ -904,6 +1125,92 @@ }; }; + /// \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::Arc Arc; + typedef typename Base::Edge Edge; + + + typedef IterableBpGraphComponent BpGraph; + + /// \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 firstRed(Node&) const {} + + /// \brief Return the next red node. + /// + /// This function gives back the next red node in the iteration order. + void nextRed(Node&) const {} + + /// \brief Return the first blue node. + /// + /// This function gives back the first blue node in the iteration order. + void firstBlue(Node&) const {} + + /// \brief Return the next blue node. + /// + /// This function gives back the next blue node in the iteration order. + void nextBlue(Node&) 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 RedIt; + + /// \brief This iterator goes through each blue node. + /// + /// This iterator goes through each blue node. + typedef GraphItemIt BlueIt; + + /// @} + + template + struct Constraints { + void constraints() { + checkConcept, _BpGraph>(); + + typename _BpGraph::Node node(INVALID); + bpgraph.firstRed(node); + bpgraph.nextRed(node); + bpgraph.firstBlue(node); + bpgraph.nextBlue(node); + + checkConcept, + typename _BpGraph::RedIt>(); + checkConcept, + typename _BpGraph::BlueIt>(); + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for alterable directed graphs. /// /// This class describes the interface of alterable directed @@ -929,18 +1236,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 @@ -976,6 +1286,7 @@ public: typedef BAS Base; + typedef AlterableDigraphComponent Parent; typedef typename Base::Edge Edge; @@ -983,11 +1294,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 @@ -1004,6 +1319,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()); + ignore_unused_variable_warning(rnn); + 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. @@ -1307,6 +1684,143 @@ }; }; + /// \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 + /// RedMap and BlueMap). 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 RedMap : public GraphMap { + typedef GraphMap Parent; + + public: + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit RedMap(const MappableBpGraphComponent& graph) + : Parent(graph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalize the values. + RedMap(const MappableBpGraphComponent& graph, const V& value) + : Parent(graph, value) {} + + private: + /// \brief Copy constructor. + /// + /// Copy Constructor. + RedMap(const RedMap& nm) : Parent(nm) {} + + /// \brief Assignment operator. + /// + /// Assignment operator. + template + RedMap& 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 BlueMap : public GraphMap { + typedef GraphMap Parent; + + public: + /// \brief Construct a new map. + /// + /// Construct a new map for the graph. + explicit BlueMap(const MappableBpGraphComponent& graph) + : Parent(graph) {} + + /// \brief Construct a new map with default value. + /// + /// Construct a new map for the graph and initalize the values. + BlueMap(const MappableBpGraphComponent& graph, const V& value) + : Parent(graph, value) {} + + private: + /// \brief Copy constructor. + /// + /// Copy Constructor. + BlueMap(const BlueMap& nm) : Parent(nm) {} + + /// \brief Assignment operator. + /// + /// Assignment operator. + template + BlueMap& 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 RedMap IntRedMap; + checkConcept, + IntRedMap >(); + } { // bool map test + typedef typename _BpGraph::template RedMap BoolRedMap; + checkConcept, + BoolRedMap >(); + } { // Dummy map test + typedef typename _BpGraph::template RedMap DummyRedMap; + checkConcept, + DummyRedMap >(); + } + + { // int map test + typedef typename _BpGraph::template BlueMap IntBlueMap; + checkConcept, + IntBlueMap >(); + } { // bool map test + typedef typename _BpGraph::template BlueMap BoolBlueMap; + checkConcept, + BoolBlueMap >(); + } { // Dummy map test + typedef typename _BpGraph::template BlueMap DummyBlueMap; + checkConcept, + DummyBlueMap >(); + } + } + + const _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for extendable directed graphs. /// /// This class describes the interface of extendable directed graphs. @@ -1397,6 +1911,58 @@ }; }; + /// \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::Edge Edge; + + /// \brief Add a new red node to the digraph. + /// + /// This function adds a red new node to the digraph. + Node addRedNode() { + return INVALID; + } + + /// \brief Add a new blue node to the digraph. + /// + /// This function adds a blue new node to the digraph. + Node 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 Node&, const Node&) { + return INVALID; + } + + template + struct Constraints { + void constraints() { + checkConcept(); + typename _BpGraph::Node red_node, blue_node; + red_node = bpgraph.addRedNode(); + blue_node = bpgraph.addBlueNode(); + typename _BpGraph::Edge edge; + edge = bpgraph.addEdge(red_node, blue_node); + } + + _BpGraph& bpgraph; + }; + }; + /// \brief Skeleton class for erasable directed graphs. /// /// This class describes the interface of erasable directed graphs. @@ -1477,6 +2043,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. @@ -1513,27 +2088,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 {}; } diff -r b4f4c08e1210 -r 2e959a5a0c2d test/CMakeLists.txt --- a/test/CMakeLists.txt Sun Feb 24 19:44:14 2013 +0100 +++ b/test/CMakeLists.txt Sun Nov 14 16:35:31 2010 +0100 @@ -16,6 +16,7 @@ arc_look_up_test bellman_ford_test bfs_test + bpgraph_test circulation_test connectivity_test counter_test diff -r b4f4c08e1210 -r 2e959a5a0c2d test/bpgraph_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/bpgraph_test.cc Sun Nov 14 16:35:31 2010 +0100 @@ -0,0 +1,70 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +//#include +//#include +//#include +//#include +//#include + +#include "test_tools.h" +#include "graph_test.h" + +using namespace lemon; +using namespace lemon::concepts; + +void checkConcepts() { + { // Checking graph components + checkConcept(); + + checkConcept, + IDableBpGraphComponent<> >(); + + checkConcept, + IterableBpGraphComponent<> >(); + + checkConcept, + AlterableBpGraphComponent<> >(); + + checkConcept, + MappableBpGraphComponent<> >(); + + checkConcept, + ExtendableBpGraphComponent<> >(); + + checkConcept, + ErasableBpGraphComponent<> >(); + + checkConcept, + ClearableGraphComponent<> >(); + + } + { // Checking skeleton graph + checkConcept(); + } +} + +void checkGraphs() { +} + +int main() { + checkConcepts(); + checkGraphs(); + return 0; +}