Context Navigation

← Previous Change
Next Change →

graph_components.h

Timestamp:

10/03/06 13:46:39 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2973

Message:

Some rearrangement of concepts and extenders
BpUGraph concepts and concept check test

File:

: 1 edited

lemon/concept/graph_components.h (modified) (26 diffs)

Legend:

: Unmodified
: Added
: Removed

lemon/concept/graph_components.h

-                      r2181
+                      r2231
         /// be convertible to the represented undirected edge.
         UEdge(const Edge&) {}
+        /// \brief Assign edge to undirected edge.
+        ///
+        /// Besides the core graph item functionality each edge should
+        /// be convertible to the represented undirected edge.
+        UEdge& operator=(const Edge&) { return *this; }
       };
 …
     };
     /// \brief An empty iterable base graph class.
+    /// \brief An empty base bipartite undirected graph class.
     ///
+    /// This class provides beside the core graph features
+    /// core iterable interface for the graph structure.
+    /// Most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseGraphComponent>
+    class BaseIterableGraphComponent : public _Base {
+    public:
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::Edge Edge;
+      /// \brief Gives back the first node in the iterating order.
+      ///
+      /// Gives back the first node in the iterating order.
+      ///
+      void first(Node&) const {}
+      /// \brief Gives back the next node in the iterating order.
+      ///
+      /// Gives back the next node in the iterating order.
+      ///
+      void next(Node&) const {}
+      /// \brief Gives back the first edge in the iterating order.
+      ///
+      /// Gives back the first edge in the iterating order.
+      ///
+      void first(Edge&) const {}
+      /// \brief Gives back the next edge in the iterating order.
+      ///
+      /// Gives back the next edge in the iterating order.
+      ///
+      void next(Edge&) const {}
+      /// \brief Gives back the first of the edges point to the given
+      /// node.
+      ///
+      /// Gives back the first of the edges point to the given node.
+      ///
+      void firstIn(Edge&, const Node&) const {}
+      /// \brief Gives back the next of the edges points to the given
+      /// node.
+      ///
+      /// Gives back the next of the edges points to the given node.
+      ///
+      void nextIn(Edge&) const {}
+      /// \brief Gives back the first of the edges start from the
+      /// given node.
+      ///
+      /// Gives back the first of the edges start from the given node.
+      ///
+      void firstOut(Edge&, const Node&) const {}
+      /// \brief Gives back the next of the edges start from the given
+      /// node.
+      ///
+      /// Gives back the next of the edges start from the given node.
+      ///
+      void nextOut(Edge&) const {}
+    /// This class provides the minimal set of features needed for an
+    /// bipartite undirected graph structure. All bipartite undirected
+    /// graph concepts have to be conform to this base graph. It just
+    /// provides types for nodes, A-nodes, B-nodes, edges and
+    /// undirected edges and functions to get the source and the
+    /// target of the edges and undirected edges, conversion from
+    /// edges to undirected edges and function to get both direction
+    /// of the undirected edges.
+    class BaseBpUGraphComponent : public BaseUGraphComponent {
+    public:
+      typedef BaseUGraphComponent::Node Node;
+      typedef BaseUGraphComponent::Edge Edge;
+      typedef BaseUGraphComponent::UEdge UEdge;
+      /// \brief Helper class for A-nodes.
+      ///
+      /// This class is just a helper class for A-nodes, it is not
+      /// suggested to use it directly. It can be converted easily to
+      /// node and vice versa. The usage of this class is limited
+      /// to use just as template parameters for special map types.
+      class ANode : public Node {
+      public:
+        typedef Node Parent;
+        /// \brief 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.
+        ANode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        ///
+        ANode(const ANode &) : Parent() {}
+        /// \brief Invalid constructor \& conversion.
+        ///
+        /// This constructor initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        ANode(Invalid) {}
+        /// \brief Converter from node to A-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented A-node if it is it possible.
+        ANode(const Node&) {}
+        /// \brief Assign node to A-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented A-node if it is it possible.
+        ANode& operator=(const Node&) { return *this; }
+      };
+      /// \brief Helper class for B-nodes.
+      ///
+      /// This class is just a helper class for B-nodes, it is not
+      /// suggested to use it directly. It can be converted easily to
+      /// node and vice versa. The usage of this class is limited
+      /// to use just as template parameters for special map types.
+      class BNode : public Node {
+      public:
+        typedef Node Parent;
+        /// \brief 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.
+        BNode() {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy constructor.
+        ///
+        BNode(const BNode &) : Parent() {}
+        /// \brief Invalid constructor \& conversion.
+        ///
+        /// This constructor initializes the item to be invalid.
+        /// \sa Invalid for more details.
+        BNode(Invalid) {}
+        /// \brief Converter from node to B-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented B-node if it is it possible.
+        BNode(const Node&) {}
+        /// \brief Assign node to B-node.
+        ///
+        /// Besides the core graph item functionality each node should
+        /// be convertible to the represented B-node if it is it possible.
+        BNode& operator=(const Node&) { return *this; }
+      };
+      /// \brief Gives back %true when the node is A-node.
+      ///
+      /// Gives back %true when the node is A-node.
+      bool aNode(const Node&) const { return false; }
+      /// \brief Gives back %true when the node is B-node.
+      ///
+      /// Gives back %true when the node is B-node.
+      bool bNode(const Node&) const { return false; }
+      /// \brief Gives back the A-node of the undirected edge.
+      ///
+      /// Gives back the A-node of the undirected edge.
+      Node aNode(const UEdge&) const { return INVALID; }
+      /// \brief Gives back the B-node of the undirected edge.
+      ///
+      /// Gives back the B-node of the undirected edge.
+      Node bNode(const UEdge&) const { return INVALID; }
       template <typename _Graph>
       struct Constraints {
+        typedef typename _Graph::Node Node;
+        typedef typename _Graph::ANode ANode;
+        typedef typename _Graph::BNode BNode;
+        typedef typename _Graph::Edge Edge;
+        typedef typename _Graph::UEdge UEdge;
         void constraints() {
           checkConcept< BaseGraphComponent, _Graph >();
           typename _Graph::Node node(INVALID);
           typename _Graph::Edge edge(INVALID);
+          checkConcept<BaseUGraphComponent, _Graph>();
+          checkConcept<GraphItem<'a'>, ANode>();
+          checkConcept<GraphItem<'b'>, BNode>();
+          {
+            graph.first(node);
+            graph.next(node);
+          }
+          {
+            graph.first(edge);
+            graph.next(edge);
+          }
+          {
+            graph.firstIn(edge, node);
+            graph.nextIn(edge);
+          }
+          {
+            graph.firstOut(edge, node);
+            graph.nextOut(edge);
+          }
+        }
+            Node n;
+            UEdge ue(INVALID);
+            bool b;
+            n = graph.aNode(ue);
+            n = graph.bNode(ue);
+            b = graph.aNode(n);
+            b = graph.bNode(n);
+            ANode an;
+            an = n; n = an;
+            BNode bn;
+            bn = n; n = bn;
+            ignore_unused_variable_warning(b);
+          }
+        }
         const _Graph& graph;
       };
+    };
+    /// \brief An empty iterable base undirected graph class.
+    ///
+    /// This class provides beside the core undirceted graph features
+    /// core iterable interface for the undirected graph structure.
+    /// Most of the base undirected graphs should be conform to this
+    /// concept.
+    template <typename _Base = BaseUGraphComponent>
+    class BaseIterableUGraphComponent
+      : public BaseIterableGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+      typedef typename Base::UEdge UEdge;
+      typedef typename Base::Node Node;
+      using BaseIterableGraphComponent<_Base>::first;
+      using BaseIterableGraphComponent<_Base>::next;
+      /// \brief Gives back the first undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the first undirected edge in the iterating order.
+      ///
+      void first(UEdge&) const {}
+      /// \brief Gives back the next undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the next undirected edge in the iterating order.
+      ///
+      void next(UEdge&) const {}
+      /// \brief Gives back the first of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the first of the undirected edges from the given
+      /// node. The bool parameter gives back that direction which
+      /// gives a good direction of the uedge so the source of the
+      /// directed edge is the given node.
+      void firstInc(UEdge&, bool&, const Node&) const {}
+      /// \brief Gives back the next of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the next of the undirected edges from the given
+      /// node. The bool parameter should be used as the \c firstInc()
+      /// use it.
+      void nextInc(UEdge&, bool&) const {}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<Base, _Graph >();
+          checkConcept<BaseIterableGraphComponent<Base>, _Graph>();
+          typename _Graph::Node node(INVALID);
+          typename _Graph::UEdge uedge(INVALID);
+          bool dir;
+          {
+            graph.first(uedge);
+            graph.next(uedge);
+          }
+          {
+            graph.firstInc(uedge, dir, node);
+            graph.nextInc(uedge, dir);
+          }
+        }
+        const _Graph& graph;
+      };
     };
 …
         void constraints() {
           checkConcept< BaseGraphComponent, _Graph >();
+          checkConcept<Base, _Graph >();
           typename _Graph::Node node;
           int nid = graph.id(node);
 …
     };
+    /// \brief An empty extendable base graph class.
+    ///
+    /// This class provides beside the core graph features
+    /// core graph extend interface for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseGraphComponent>
+    class BaseExtendableGraphComponent : public _Base {
+    public:
+      typedef typename _Base::Node Node;
+      typedef typename _Base::Edge Edge;
+      /// \brief Adds a new node to the graph.
+      ///
+      /// Adds a new node to the graph.
+      ///
+      Node addNode() {
+        return INVALID;
+      }
+      /// \brief Adds a new edge connects the given two nodes.
+      ///
+      /// Adds a new edge connects the the given two nodes.
+      Edge addEdge(const Node&, const Node&) {
+        return INVALID;
+      }
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          typename _Graph::Node node_a, node_b;
+          node_a = graph.addNode();
+          node_b = graph.addNode();
+          typename _Graph::Edge edge;
+          edge = graph.addEdge(node_a, node_b);
+        }
+        _Graph& graph;
+      };
+    };
+    /// \brief An empty extendable base undirected graph class.
+    ///
+    /// This class provides beside the core undirected graph features
+    /// core undircted graph extend interface for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseUGraphComponent>
+    class BaseExtendableUGraphComponent : public _Base {
+    public:
+      typedef typename _Base::Node Node;
+      typedef typename _Base::UEdge UEdge;
+      /// \brief Adds a new node to the graph.
+      ///
+      /// Adds a new node to the graph.
+      ///
+      Node addNode() {
+        return INVALID;
+      }
+      /// \brief Adds a new edge connects the given two nodes.
+      ///
+      /// Adds a new edge connects the the given two nodes.
+      UEdge addEdge(const Node&, const Node&) {
+        return INVALID;
+      }
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          typename _Graph::Node node_a, node_b;
+          node_a = graph.addNode();
+          node_b = graph.addNode();
+          typename _Graph::UEdge uedge;
+          uedge = graph.addUEdge(node_a, node_b);
+        }
+        _Graph& graph;
+      };
+    };
+    /// \brief An empty erasable base graph class.
+    /// \brief An empty idable base bipartite undirected graph class.
     ///
+    /// This class provides beside the core graph features
+    /// core erase functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseGraphComponent>
+    class BaseErasableGraphComponent : public _Base {
+    /// This class provides beside the core bipartite undirected graph
+    /// features core id functions for the bipartite undirected graph
+    /// structure.  The most of the base undirected graphs should be
+    /// conform to this concept.
+    template <typename _Base = BaseBpUGraphComponent>
+    class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> {
     public:
       typedef _Base Base;
       typedef typename Base::Node Node;
+      typedef typename Base::Edge Edge;
+      /// \brief Erase a node from the graph.
+      ///
+      /// Erase a node from the graph. This function should not
+      /// erase edges connecting to the Node.
+      void erase(const Node&) {}
+      /// \brief Erase an edge from the graph.
+      ///
+      /// Erase an edge from the graph.
+      ///
+      void erase(const Edge&) {}
+      using IDableUGraphComponent<_Base>::id;
+      /// \brief Gives back an unique integer id for the ANode.
+      ///
+      /// Gives back an unique integer id for the ANode.
+      ///
+      int aNodeId(const Node&) const { return -1;}
+      /// \brief Gives back the undirected edge by the unique id.
+      ///
+      /// Gives back the undirected edge by the unique id.  If the
+      /// graph does not contain edge with the given id then the
+      /// result of the function is undetermined.
+      Node nodeFromANodeId(int) const { return INVALID;}
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// ANode id.
+      ///
+      /// Gives back an integer greater or equal to the maximum ANode
+      /// id.
+      int maxANodeId() const { return -1;}
+      /// \brief Gives back an unique integer id for the BNode.
+      ///
+      /// Gives back an unique integer id for the BNode.
+      ///
+      int bNodeId(const Node&) const { return -1;}
+      /// \brief Gives back the undirected edge by the unique id.
+      ///
+      /// Gives back the undirected edge by the unique id.  If the
+      /// graph does not contain edge with the given id then the
+      /// result of the function is undetermined.
+      Node nodeFromBNodeId(int) const { return INVALID;}
+      /// \brief Gives back an integer greater or equal to the maximum
+      /// BNode id.
+      ///
+      /// Gives back an integer greater or equal to the maximum BNode
+      /// id.
+      int maxBNodeId() const { return -1;}
       template <typename _Graph>
       struct Constraints {
+        void constraints() {
+          typename _Graph::Node node;
+          graph.erase(node);
+          typename _Graph::Edge edge;
+          graph.erase(edge);
+        }
+        _Graph& graph;
+      };
+    };
+    /// \brief An empty erasable base undirected graph class.
+    ///
+    /// This class provides beside the core undirected graph features
+    /// core erase functions for the undirceted graph structure.
+    template <typename _Base = BaseUGraphComponent>
+    class BaseErasableUGraphComponent : public _Base {
+    public:
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::UEdge UEdge;
+      /// \brief Erase a node from the graph.
+      ///
+      /// Erase a node from the graph. This function should not
+      /// erase edges connecting to the Node.
+      void erase(const Node&) {}
+      /// \brief Erase an edge from the graph.
+      ///
+      /// Erase an edge from the graph.
+      ///
+      void erase(const UEdge&) {}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          typename _Graph::Node node;
+          graph.erase(node);
+          typename _Graph::Edge edge;
+          graph.erase(edge);
+        }
+        _Graph& graph;
+      };
+    };
+    /// \brief An empty clearable base graph class.
+    ///
+    /// This class provides beside the core graph features
+    /// core clear functions for the graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseGraphComponent>
+    class BaseClearableGraphComponent : public _Base {
+    public:
+      /// \brief Erase all the nodes and edges from the graph.
+      ///
+      /// Erase all the nodes and edges from the graph.
+      ///
+      void clear() {}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          graph.clear();
+        }
+        _Graph graph;
+      };
+    };
+    /// \brief An empty clearable base undirected graph class.
+    ///
+    /// This class provides beside the core undirected graph features
+    /// core clear functions for the undirected graph structure.
+    /// The most of the base graphs should be conform to this concept.
+    template <typename _Base = BaseUGraphComponent>
+    class BaseClearableUGraphComponent : public _Base {
+    public:
+      /// \brief Erase all the nodes and undirected edges from the graph.
+      ///
+      /// Erase all the nodes and undirected edges from the graph.
+      ///
+      void clear() {}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          graph.clear();
+        }
+        _Graph graph;
+      };
+    };
+        void constraints() {
+          checkConcept<Base, _Graph >();
+          checkConcept<IDableGraphComponent<Base>, _Graph >();
+          typename _Graph::Node node(INVALID);
+          int id;
+          id = graph.aNodeId(node);
+          id = graph.bNodeId(node);
+          node = graph.nodeFromANodeId(id);
+          node = graph.nodeFromBNodeId(id);
+          id = graph.maxANodeId();
+          id = graph.maxBNodeId();
+        }
+        const _Graph& graph;
+      };
+    };
     /// \brief Skeleton class for graph NodeIt and EdgeIt
 …
     /// This class provides beside the core graph features
     /// iterator based iterable interface for the graph structure.
     /// This concept is part of the GraphConcept.
+    /// This concept is part of the Graph concept.
     template <typename _Base = BaseGraphComponent>
     class IterableGraphComponent : public _Base {
 …
       typedef IterableGraphComponent Graph;
+      /// \name Base iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
+      /// \brief Gives back the first node in the iterating order.
+      ///
+      /// Gives back the first node in the iterating order.
+      ///
+      void first(Node&) const {}
+      /// \brief Gives back the next node in the iterating order.
+      ///
+      /// Gives back the next node in the iterating order.
+      ///
+      void next(Node&) const {}
+      /// \brief Gives back the first edge in the iterating order.
+      ///
+      /// Gives back the first edge in the iterating order.
+      ///
+      void first(Edge&) const {}
+      /// \brief Gives back the next edge in the iterating order.
+      ///
+      /// Gives back the next edge in the iterating order.
+      ///
+      void next(Edge&) const {}
+      /// \brief Gives back the first of the edges point to the given
+      /// node.
+      ///
+      /// Gives back the first of the edges point to the given node.
+      ///
+      void firstIn(Edge&, const Node&) const {}
+      /// \brief Gives back the next of the edges points to the given
+      /// node.
+      ///
+      /// Gives back the next of the edges points to the given node.
+      ///
+      void nextIn(Edge&) const {}
+      /// \brief Gives back the first of the edges start from the
+      /// given node.
+      ///
+      /// Gives back the first of the edges start from the given node.
+      ///
+      void firstOut(Edge&, const Node&) const {}
+      /// \brief Gives back the next of the edges start from the given
+      /// node.
+      ///
+      /// Gives back the next of the edges start from the given node.
+      ///
+      void nextOut(Edge&) const {}
+      /// @}
+      /// \name Class based iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
       /// \brief This iterator goes through each node.
 …
       Node runningNode(const OutEdgeIt&) const { return INVALID; }
+      /// \brief The opposite node on the given edge.
+      ///
+      /// Gives back the opposite on the given edge.
+      /// \todo It should not be here.
+      Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
+      /// @}
       template <typename _Graph>
       struct Constraints {
         void constraints() {
           checkConcept<Base, _Graph>();
+          checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
+            typename _Graph::EdgeIt >();
+          checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+            typename _Graph::NodeIt >();
+          checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
+            typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
+          checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
+            typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
+          typename _Graph::Node n;
+          typename _Graph::InEdgeIt ieit(INVALID);
+          typename _Graph::OutEdgeIt oeit(INVALID);
+          n = graph.baseNode(ieit);
+          n = graph.runningNode(ieit);
+          n = graph.baseNode(oeit);
+          n = graph.runningNode(oeit);
+          ignore_unused_variable_warning(n);
+          {
+            typename _Graph::Node node(INVALID);
+            typename _Graph::Edge edge(INVALID);
+            {
+              graph.first(node);
+              graph.next(node);
+            }
+            {
+              graph.first(edge);
+              graph.next(edge);
+            }
+            {
+              graph.firstIn(edge, node);
+              graph.nextIn(edge);
+            }
+            {
+              graph.firstOut(edge, node);
+              graph.nextOut(edge);
+            }
+          }
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
+              typename _Graph::EdgeIt >();
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::NodeIt >();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
+              typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
+              typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();
+            typename _Graph::Node n;
+            typename _Graph::InEdgeIt ieit(INVALID);
+            typename _Graph::OutEdgeIt oeit(INVALID);
+            n = graph.baseNode(ieit);
+            n = graph.runningNode(ieit);
+            n = graph.baseNode(oeit);
+            n = graph.runningNode(oeit);
+            ignore_unused_variable_warning(n);
+          }
+        }
 …
     /// This class provides beside the core graph features iterator
     /// based iterable interface for the undirected graph structure.
     /// This concept is part of the GraphConcept.
+    /// This concept is part of the UGraph concept.
     template <typename _Base = BaseUGraphComponent>
     class IterableUGraphComponent : public IterableGraphComponent<_Base> {
 …
       typedef IterableUGraphComponent Graph;
+      /// \name Base iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      /// @{
+      using IterableGraphComponent<_Base>::first;
+      using IterableGraphComponent<_Base>::next;
+      /// \brief Gives back the first undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the first undirected edge in the iterating order.
+      ///
+      void first(UEdge&) const {}
+      /// \brief Gives back the next undirected edge in the iterating
+      /// order.
+      ///
+      /// Gives back the next undirected edge in the iterating order.
+      ///
+      void next(UEdge&) const {}
+      /// \brief Gives back the first of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the first of the undirected edges from the given
+      /// node. The bool parameter gives back that direction which
+      /// gives a good direction of the uedge so the source of the
+      /// directed edge is the given node.
+      void firstInc(UEdge&, bool&, const Node&) const {}
+      /// \brief Gives back the next of the undirected edges from the
+      /// given node.
+      ///
+      /// Gives back the next of the undirected edges from the given
+      /// node. The bool parameter should be used as the \c firstInc()
+      /// use it.
+      void nextInc(UEdge&, bool&) const {}
       using IterableGraphComponent<_Base>::baseNode;
       using IterableGraphComponent<_Base>::runningNode;
+      /// @}
+      /// \name Class based iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
       /// \brief This iterator goes through each node.
 …
       Node runningNode(const IncEdgeIt&) const { return INVALID; }
+      /// @}
       template <typename _Graph>
       struct Constraints {
         void constraints() {
-          checkConcept<Base, _Graph>();
           checkConcept<IterableGraphComponent<Base>, _Graph>();
+          checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
+            typename _Graph::UEdgeIt >();
+          checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
+            typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
+          typename _Graph::Node n;
+          typename _Graph::IncEdgeIt ueit(INVALID);
+          n = graph.baseNode(ueit);
+          n = graph.runningNode(ueit);
+          {
+            typename _Graph::Node node(INVALID);
+            typename _Graph::UEdge uedge(INVALID);
+            bool dir;
+            {
+              graph.first(uedge);
+              graph.next(uedge);
+            }
+            {
+              graph.firstInc(uedge, dir, node);
+              graph.nextInc(uedge, dir);
+            }
+          }
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,
+              typename _Graph::UEdgeIt >();
+            checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge,
+              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
+            typename _Graph::Node n;
+            typename _Graph::IncEdgeIt ueit(INVALID);
+            n = graph.baseNode(ueit);
+            n = graph.runningNode(ueit);
+          }
+        }
+        const _Graph& graph;
+      };
+    };
+    /// \brief An empty iterable bipartite undirected graph class.
+    ///
+    /// This class provides beside the core graph features iterator
+    /// based iterable interface for the bipartite undirected graph
+    /// structure. This concept is part of the BpUGraph concept.
+    template <typename _Base = BaseUGraphComponent>
+    class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::UEdge UEdge;
+      typedef IterableBpUGraphComponent Graph;
+      /// \name Base iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      /// @{
+      using IterableUGraphComponent<_Base>::first;
+      using IterableUGraphComponent<_Base>::next;
+      /// \brief Gives back the first A-node in the iterating order.
+      ///
+      /// Gives back the first undirected A-node in the iterating
+      /// order.
+      ///
+      void firstANode(Node&) const {}
+      /// \brief Gives back the next A-node in the iterating order.
+      ///
+      /// Gives back the next A-node in the iterating order.
+      ///
+      void nextANode(Node&) const {}
+      /// \brief Gives back the first B-node in the iterating order.
+      ///
+      /// Gives back the first undirected B-node in the iterating
+      /// order.
+      ///
+      void firstBNode(Node&) const {}
+      /// \brief Gives back the next B-node in the iterating order.
+      ///
+      /// Gives back the next B-node in the iterating order.
+      ///
+      void nextBNode(Node&) const {}
+      /// \brief Gives back the first of the undirected edges start
+      /// from the given A-node.
+      ///
+      /// Gives back the first of the undirected edges start from the
+      /// given A-node.
+      void firstFromANode(UEdge&, const Node&) const {}
+      /// \brief Gives back the next of the undirected edges start
+      /// from the given A-node.
+      ///
+      /// Gives back the next of the undirected edges start from the
+      /// given A-node.
+      void nextFromANode(UEdge&) const {}
+      /// \brief Gives back the first of the undirected edges start
+      /// from the given B-node.
+      ///
+      /// Gives back the first of the undirected edges start from the
+      /// given B-node.
+      void firstFromBNode(UEdge&, const Node&) const {}
+      /// \brief Gives back the next of the undirected edges start
+      /// from the given B-node.
+      ///
+      /// Gives back the next of the undirected edges start from the
+      /// given B-node.
+      void nextFromBNode(UEdge&) const {}
+      /// @}
+      /// \name Class based iteration
+      ///
+      /// This interface provides functions for iteration on graph items
+      ///
+      /// @{
+      /// \brief This iterator goes through each A-node.
+      ///
+      /// This iterator goes through each A-node.
+      typedef GraphItemIt<Graph, Node> ANodeIt;
+      /// \brief This iterator goes through each B-node.
+      ///
+      /// This iterator goes through each B-node.
+      typedef GraphItemIt<Graph, Node> BNodeIt;
+      /// @}
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<IterableUGraphComponent<Base>, _Graph>();
+          {
+            typename _Graph::Node node(INVALID);
+            typename _Graph::UEdge uedge(INVALID);
+            graph.firstANode(node);
+            graph.nextANode(node);
+            graph.firstBNode(node);
+            graph.nextBNode(node);
+            graph.firstFromANode(uedge, node);
+            graph.nextFromANode(uedge);
+            graph.firstFromBNode(uedge, node);
+            graph.nextFromBNode(uedge);
+          }
+          {
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::ANodeIt >();
+            checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,
+              typename _Graph::BNodeIt >();
+          }
+        }
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
+          checkConcept<AlterableGraphComponent, _Graph>();
+          checkConcept<AlterableGraphComponent<Base>, _Graph>();
           typename _Graph::UEdgeNotifier& uen
             = graph.getNotifier(typename _Graph::UEdge());
           ignore_unused_variable_warning(uen);
+        }
+        const _Graph& graph;
+      };
+    };
+    /// \brief An empty alteration notifier bipartite undirected graph
+    /// class.
+    ///
+    /// This class provides beside the core graph features alteration
+    /// notifier interface for the graph structure.  This implements
+    /// an observer-notifier pattern for each graph item. More
+    /// obsevers can be registered into the notifier and whenever an
+    /// alteration occured in the graph all the observers will
+    /// notified about it.
+    template <typename _Base = BaseUGraphComponent>
+    class AlterableBpUGraphComponent : public AlterableUGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+      typedef typename Base::ANode ANode;
+      typedef typename Base::BNode BNode;
+      /// The A-node observer registry.
+      typedef AlterationNotifier<AlterableBpUGraphComponent, ANode>
+      ANodeNotifier;
+      /// The B-node observer registry.
+      typedef AlterationNotifier<AlterableBpUGraphComponent, BNode>
+      BNodeNotifier;
+      /// \brief Gives back the A-node alteration notifier.
+      ///
+      /// Gives back the A-node alteration notifier.
+      ANodeNotifier& getNotifier(ANode) const {
+        return ANodeNotifier();
+      }
+      /// \brief Gives back the B-node alteration notifier.
+      ///
+      /// Gives back the B-node alteration notifier.
+      BNodeNotifier& getNotifier(BNode) const {
+        return BNodeNotifier();
+      }
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<AlterableUGraphComponent<Base>, _Graph>();
+          typename _Graph::ANodeNotifier& ann
+            = graph.getNotifier(typename _Graph::ANode());
+          typename _Graph::BNodeNotifier& bnn
+            = graph.getNotifier(typename _Graph::BNode());
+          ignore_unused_variable_warning(ann);
+          ignore_unused_variable_warning(bnn);
+        }
 …
     };
     /// \brief An empty mappable base graph class.
+    /// \brief An empty mappable base bipartite undirected graph class.
     ///
     /// This class provides beside the core graph features
 …
         void constraints() {
-          checkConcept<Base, _Graph>();
           checkConcept<MappableGraphComponent<Base>, _Graph>();
 …
     };
+    /// \brief An empty mappable base bipartite undirected graph
+    /// class.
+    ///
+    /// This class provides beside the core graph features
+    /// map interface for the graph structure.
+    /// This concept is part of the BpUGraph concept.
+    template <typename _Base = BaseBpUGraphComponent>
+    class MappableBpUGraphComponent : public MappableUGraphComponent<_Base>  {
+    public:
+      typedef _Base Base;
+      typedef typename Base::Node Node;
+      typedef MappableBpUGraphComponent Graph;
+      /// \brief ReadWrite map of the A-nodes.
+      ///
+      /// ReadWrite map of the A-nodes.
+      ///
+      template <typename _Value>
+      class ANodeMap : public GraphMap<Graph, Node, _Value> {
+      public:
+        typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        /// \todo call the right parent class constructor
+        explicit ANodeMap(const MappableBpUGraphComponent& graph)
+          : Parent(graph) {}
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalise the values.
+        ANodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
+          : Parent(graph, value) {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        ANodeMap(const ANodeMap& nm) : Parent(nm) {}
+        /// \brief Assign operator.
+        ///
+        /// Assign operator.
+        template <typename CMap>
+        ANodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, _Value>, CMap>();
+          return *this;
+        }
+      };
+      /// \brief ReadWrite map of the B-nodes.
+      ///
+      /// ReadWrite map of the A-nodes.
+      ///
+      template <typename _Value>
+      class BNodeMap : public GraphMap<Graph, Node, _Value> {
+      public:
+        typedef GraphMap<MappableBpUGraphComponent, Node, _Value> Parent;
+        /// \brief Construct a new map.
+        ///
+        /// Construct a new map for the graph.
+        /// \todo call the right parent class constructor
+        explicit BNodeMap(const MappableBpUGraphComponent& graph)
+          : Parent(graph) {}
+        /// \brief Construct a new map with default value.
+        ///
+        /// Construct a new map for the graph and initalise the values.
+        BNodeMap(const MappableBpUGraphComponent& graph, const _Value& value)
+          : Parent(graph, value) {}
+        /// \brief Copy constructor.
+        ///
+        /// Copy Constructor.
+        BNodeMap(const BNodeMap& nm) : Parent(nm) {}
+        /// \brief Assign operator.
+        ///
+        /// Assign operator.
+        template <typename CMap>
+        BNodeMap& operator=(const CMap&) {
+          checkConcept<ReadMap<Node, _Value>, CMap>();
+          return *this;
+        }
+      };
+      template <typename _Graph>
+      struct Constraints {
+        struct Dummy {
+          int value;
+          Dummy() : value(0) {}
+          Dummy(int _v) : value(_v) {}
+        };
+        void constraints() {
+          checkConcept<MappableUGraphComponent<Base>, _Graph>();
+          { // int map test
+            typedef typename _Graph::template ANodeMap<int> IntANodeMap;
+            checkConcept<GraphMap<_Graph, typename _Graph::ANode, int>,
+              IntANodeMap >();
+          } { // bool map test
+            typedef typename _Graph::template ANodeMap<bool> BoolANodeMap;
+            checkConcept<GraphMap<_Graph, typename _Graph::ANode, bool>,
+              BoolANodeMap >();
+          } { // Dummy map test
+            typedef typename _Graph::template ANodeMap<Dummy> DummyANodeMap;
+            checkConcept<GraphMap<_Graph, typename _Graph::ANode, Dummy>,
+              DummyANodeMap >();
+          }
+        }
+        _Graph& graph;
+      };
+    };
     /// \brief An empty extendable graph class.
 …
     class ExtendableGraphComponent : public _Base {
     public:
+      typedef _Base Base;
       typedef typename _Base::Node Node;
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
           typename _Graph::Node node_a, node_b;
           node_a = graph.addNode();
 …
     public:
+      typedef _Base Base;
       typedef typename _Base::Node Node;
       typedef typename _Base::UEdge UEdge;
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
           typename _Graph::Node node_a, node_b;
           node_a = graph.addNode();
 …
         _Graph& graph;
+      };
+    };
+    /// \brief An empty extendable base undirected graph class.
+    ///
+    /// This class provides beside the core bipartite undirected graph
+    /// features core undircted graph extend interface for the graph
+    /// structure.  The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseBpUGraphComponent>
+    class ExtendableBpUGraphComponent
+      : public ExtendableUGraphComponent<_Base> {
+      typedef _Base Base;
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<ExtendableUGraphComponent<Base>, _Graph>();
+        }
       };
     };
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
           typename _Graph::Node node;
           graph.erase(node);
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
           typename _Graph::Node node;
           graph.erase(node);
 …
         _Graph& graph;
+      };
+    };
+    /// \brief An empty erasable base bipartite undirected graph class.
+    ///
+    /// This class provides beside the core bipartite undirected graph
+    /// features core erase functions for the undirceted graph
+    /// structure. The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseBpUGraphComponent>
+    class ErasableBpUGraphComponent : public ErasableUGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<ErasableUGraphComponent<Base>, _Graph>();
+        }
       };
     };
 …
     public:
+      typedef _Base Base;
       /// \brief Erase all nodes and edges from the graph.
       ///
 …
       struct Constraints {
         void constraints() {
+          checkConcept<Base, _Graph>();
           graph.clear();
+        }
 …
     /// the graph alterations should handled already on this level.
     template <typename _Base = BaseUGraphComponent>
+    class ClearableUGraphComponent : public _Base {
+    public:
+      /// \brief Erase all nodes and undirected edges from the graph.
+      ///
+      /// Erase all nodes and undirected edges from the graph.
+      ///
+      void clear() {}
+    class ClearableUGraphComponent : public ClearableUGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
       template <typename _Graph>
       struct Constraints {
         void constraints() {
           graph.clear();
+          checkConcept<ClearableUGraphComponent<Base>, _Graph>();
+        }
 …
     };
+    /// \brief An empty clearable base bipartite undirected graph
+    /// class.
+    ///
+    /// This class provides beside the core bipartite undirected graph
+    /// features core clear functions for the undirected graph
+    /// structure. The main difference between the base and this
+    /// interface is that the graph alterations should handled already
+    /// on this level.
+    template <typename _Base = BaseUGraphComponent>
+    class ClearableBpUGraphComponent
+      : public ClearableBpUGraphComponent<_Base> {
+    public:
+      typedef _Base Base;
+      template <typename _Graph>
+      struct Constraints {
+        void constraints() {
+          checkConcept<ClearableBpUGraphComponent<Base>, _Graph>();
+        }
+      };
+    };
+  }

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 2231:06faf3f06d67 in lemon-0.x for lemon/concept/graph_components.h

Legend:

lemon/concept/graph_components.h

Download in other formats: