# HG changeset patch # User deba # Date 1107775717 0 # Node ID 8d066154b66ad92a5fa3f001fc388e7987ae2ae4 # Parent cfccb33ecf7b2fba22cdfdba2d6e87bc69ab7693 Graph documentation diff -r cfccb33ecf7b -r 8d066154b66a src/lemon/concept/graph.h --- a/src/lemon/concept/graph.h Mon Feb 07 10:50:05 2005 +0000 +++ b/src/lemon/concept/graph.h Mon Feb 07 11:28:37 2005 +0000 @@ -28,483 +28,18 @@ namespace lemon { namespace concept { + /// \addtogroup graph_concepts /// @{ -// /// An empty static graph class. - -// /// This class provides all the common features of a graph structure, -// /// however completely without implementations and real data structures -// /// behind the interface. -// /// All graph algorithms should compile with this class, but it will not -// /// run properly, of course. -// /// -// /// It can be used for checking the interface compatibility, -// /// or it can serve as a skeleton of a new graph structure. -// /// -// /// Also, you will find here the full documentation of a certain graph -// /// feature, the documentation of a real graph imlementation -// /// like @ref ListGraph or -// /// @ref SmartGraph will just refer to this structure. -// /// -// /// \todo A pages describing the concept of concept description would -// /// be nice. -// class StaticGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// StaticGraph() { } -// ///Copy consructor. - -// // ///\todo It is not clear, what we expect from a copy constructor. -// // ///E.g. How to assign the nodes/edges to each other? What about maps? -// // StaticGraph(const StaticGraph& g) { } - -// /// The base type of node iterators, -// /// or in other words, the trivial node iterator. - -// /// This is the base type of each node iterator, -// /// thus each kind of node iterator converts to this. -// /// More precisely each kind of node iterator should be inherited -// /// from the trivial node iterator. -// class Node { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// Node() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// Node(const Node&) { } - -// /// Invalid constructor \& conversion. - -// /// This constructor initializes the iterator to be invalid. -// /// \sa Invalid for more details. -// Node(Invalid) { } -// /// Equality operator - -// /// Two iterators are equal if and only if they point to the -// /// same object or both are invalid. -// bool operator==(Node) const { return true; } - -// /// Inequality operator - -// /// \sa operator==(Node n) -// /// -// bool operator!=(Node) const { return true; } - -// }; - -// /// This iterator goes through each node. - -// /// This iterator goes through each node. -// /// Its usage is quite simple, for example you can count the number -// /// of nodes in graph \c g of type \c Graph like this: -// /// \code -// /// int count=0; -// /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; -// /// \endcode -// class NodeIt : public Node { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// NodeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// NodeIt(const NodeIt&) { } -// /// Invalid constructor \& conversion. - -// /// Initialize 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 \c g. -// /// -// NodeIt(const StaticGraph& g) { } -// /// Node -> NodeIt conversion. - -// /// Sets the iterator to the node of \c g pointed by the trivial -// /// iterator n. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// NodeIt(const StaticGraph& g, const Node& n) { } -// /// Next node. - -// /// Assign the iterator to the next node. -// /// -// NodeIt& operator++() { return *this; } -// }; - - -// /// The base type of the edge iterators. - -// /// The base type of the edge iterators. -// /// -// class Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// Edge() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// Edge(const Edge&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// Edge(Invalid) { } -// /// Equality operator - -// /// Two iterators are equal if and only if they point to the -// /// same object or both are invalid. -// bool operator==(Edge) const { return true; } -// /// Inequality operator - -// /// \sa operator==(Node n) -// /// -// bool operator!=(Edge) const { return true; } -// }; - -// /// This iterator goes trough the outgoing edges of a node. - -// /// This iterator goes trough the \e outgoing edges of a certain node -// /// of a graph. -// /// Its usage is quite simple, for example you can count the number -// /// of outgoing edges of a node \c n -// /// in graph \c g of type \c Graph as follows. -// /// \code -// /// int count=0; -// /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; -// /// \endcode - -// class OutEdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// OutEdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// OutEdgeIt(const OutEdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// OutEdgeIt(Invalid) { } -// /// This constructor sets the iterator to first outgoing edge. - -// /// This constructor set the iterator to the first outgoing edge of -// /// node -// ///@param n the node -// ///@param g the graph -// OutEdgeIt(const StaticGraph& g, const Node& n) { } -// /// Edge -> OutEdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// OutEdgeIt(const StaticGraph& g, const Edge& e) { } -// ///Next outgoing edge - -// /// Assign the iterator to the next -// /// outgoing edge of the corresponding node. -// OutEdgeIt& operator++() { return *this; } -// }; - -// /// This iterator goes trough the incoming edges of a node. - -// /// This iterator goes trough the \e incoming edges of a certain node -// /// of a graph. -// /// Its usage is quite simple, for example you can count the number -// /// of outgoing edges of a node \c n -// /// in graph \c g of type \c Graph as follows. -// /// \code -// /// int count=0; -// /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; -// /// \endcode - -// class InEdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// InEdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// InEdgeIt(const InEdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// InEdgeIt(Invalid) { } -// /// This constructor sets the iterator to first incoming edge. - -// /// This constructor set the iterator to the first incoming edge of -// /// node -// ///@param n the node -// ///@param g the graph -// InEdgeIt(const StaticGraph& g, const Node& n) { } -// /// Edge -> InEdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// InEdgeIt(const StaticGraph& g, const Edge& n) { } -// /// Next incoming edge - -// /// Assign the iterator to the next inedge of the corresponding node. -// /// -// InEdgeIt& operator++() { return *this; } -// }; -// /// This iterator goes through each edge. - -// /// This iterator goes through each edge of a graph. -// /// Its usage is quite simple, for example you can count the number -// /// of edges in a graph \c g of type \c Graph as follows: -// /// \code -// /// int count=0; -// /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; -// /// \endcode -// class EdgeIt : public Edge { -// public: -// /// Default constructor - -// /// @warning The default constructor sets the iterator -// /// to an undefined value. -// EdgeIt() { } -// /// Copy constructor. - -// /// Copy constructor. -// /// -// EdgeIt(const EdgeIt&) { } -// /// Initialize the iterator to be invalid. - -// /// Initialize the iterator to be invalid. -// /// -// EdgeIt(Invalid) { } -// /// This constructor sets the iterator to first edge. - -// /// This constructor set the iterator to the first edge of -// /// node -// ///@param g the graph -// EdgeIt(const StaticGraph& g) { } -// /// Edge -> EdgeIt conversion - -// /// Sets the iterator to the value of the trivial iterator \c e. -// /// This feature necessitates that each time we -// /// iterate the edge-set, the iteration order is the same. -// EdgeIt(const StaticGraph&, const Edge&) { } -// ///Next edge - -// /// Assign the iterator to the next -// /// edge of the corresponding node. -// EdgeIt& operator++() { return *this; } -// }; -// ///Gives back the target node of an edge. - -// ///Gives back the target node of an edge. -// /// -// Node target(Edge) const { return INVALID; } -// ///Gives back the source node of an edge. - -// ///Gives back the source node of an edge. -// /// -// Node source(Edge) const { return INVALID; } -// /// Read write map of the nodes to type \c T. - -// /// \ingroup concept -// /// ReadWrite map of the nodes to type \c T. -// /// \sa Reference -// /// \warning Making maps that can handle bool type (NodeMap) -// /// needs some extra attention! -// template -// class NodeMap : public ReadWriteMap< Node, T > -// { -// public: - -// ///\e -// NodeMap(const StaticGraph&) { } -// ///\e -// NodeMap(const StaticGraph&, T) { } - -// ///Copy constructor -// NodeMap(const NodeMap&) { } -// ///Assignment operator -// NodeMap& operator=(const NodeMap&) { return *this; } -// // \todo fix this concept -// }; - -// /// Read write map of the edges to type \c T. - -// /// \ingroup concept -// ///Reference map of the edges to type \c T. -// /// \sa Reference -// /// \warning Making maps that can handle bool type (EdgeMap) -// /// needs some extra attention! -// template -// class EdgeMap : public ReadWriteMap -// { -// public: - -// ///\e -// EdgeMap(const StaticGraph&) { } -// ///\e -// EdgeMap(const StaticGraph&, T) { } -// ///Copy constructor -// EdgeMap(const EdgeMap&) { } -// ///Assignment operator -// EdgeMap& operator=(const EdgeMap&) { return *this; } -// // \todo fix this concept -// }; -// }; - -// /// An empty non-static graph class. - -// /// This class provides everything that \ref StaticGraph -// /// with additional functionality which enables to build a -// /// graph from scratch. -// class ExtendableGraph : public StaticGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// ExtendableGraph() { } -// ///Add a new node to the graph. - -// /// \return the new node. -// /// -// Node addNode() { return INVALID; } -// ///Add a new edge to the graph. - -// ///Add a new edge to the graph with source node \c s -// ///and target node \c t. -// ///\return the new edge. -// Edge addEdge(Node s, Node t) { return INVALID; } - -// /// Resets the graph. - -// /// This function deletes all edges and nodes of the graph. -// /// It also frees the memory allocated to store them. -// /// \todo It might belong to \ref ErasableGraph. -// void clear() { } -// }; - -// /// An empty erasable graph class. - -// /// This class is an extension of \ref ExtendableGraph. It also makes it -// /// possible to erase edges or nodes. -// class ErasableGraph : public ExtendableGraph -// { -// public: -// /// Defalult constructor. - -// /// Defalult constructor. -// /// -// ErasableGraph() { } -// /// Deletes a node. - -// /// Deletes node \c n node. -// /// -// void erase(Node n) { } -// /// Deletes an edge. - -// /// Deletes edge \c e edge. -// /// -// void erase(Edge e) { } -// }; - - - /************* New GraphBase stuff **************/ - - - /// A minimal GraphBase concept - - /// This class describes a minimal concept which can be extended to a - /// full-featured graph with \ref GraphFactory. - class GraphBase { - public: - - GraphBase() {} - - /// \bug Should we demand that Node and Edge be subclasses of the - /// Graph class??? - - typedef GraphItem<'n'> Node; - typedef GraphItem<'e'> Edge; - -// class Node : public BaseGraphItem<'n'> {}; -// class Edge : public BaseGraphItem<'e'> {}; - - // Graph operation - void firstNode(Node &n) const { } - void firstEdge(Edge &e) const { } - - void firstOutEdge(Edge &e, Node) const { } - void firstInEdge(Edge &e, Node) const { } - - void nextNode(Node &n) const { } - void nextEdge(Edge &e) const { } - - - // Question: isn't it reasonable if this methods have a Node - // parameter? Like this: - // Edge& nextOut(Edge &e, Node) const { return e; } - void nextOutEdge(Edge &e) const { } - void nextInEdge(Edge &e) const { } - - Node target(Edge) const { return Node(); } - Node source(Edge) const { return Node(); } - - - // Do we need id, nodeNum, edgeNum and co. in this basic graphbase - // concept? - - - // Maps. - // - // We need a special slimer concept which does not provide maps (it - // wouldn't be strictly slimer, cause for map-factory id() & friends - // a required...) - - template - class NodeMap : public GraphMap {}; - - template - class EdgeMap : public GraphMap {}; - }; - - - - /**************** The full-featured graph concepts ****************/ - - class StaticGraph + + /// \brief Modular builded static graph class. + /// + /// It should be the same as the \c StaticGraph class. + class _StaticGraph : virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent { public: @@ -520,8 +55,11 @@ }; }; - class ExtendableGraph - : virtual public BaseGraphComponent, public StaticGraph, + /// \brief Modular builded extendable graph class. + /// + /// It should be the same as the \c ExtendableGraph class. + class _ExtendableGraph + : virtual public BaseGraphComponent, public _StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent { public: typedef BaseGraphComponent::Node Node; @@ -530,15 +68,18 @@ template struct Constraints { void constraints() { - checkConcept(); + checkConcept<_StaticGraph, _Graph >(); checkConcept(); checkConcept(); } }; }; - class ErasableGraph - : virtual public BaseGraphComponent, public ExtendableGraph, + /// \brief Modular builded erasable graph class. + /// + /// It should be the same as the \c ErasableGraph class. + class _ErasableGraph + : virtual public BaseGraphComponent, public _ExtendableGraph, public ErasableGraphComponent { public: typedef BaseGraphComponent::Node Node; @@ -547,12 +88,490 @@ template struct Constraints { void constraints() { - checkConcept(); + checkConcept<_ExtendableGraph, _Graph >(); checkConcept(); } }; }; + /// An empty static graph class. + + /// This class provides all the common features of a graph structure, + /// however completely without implementations and real data structures + /// behind the interface. + /// All graph algorithms should compile with this class, but it will not + /// run properly, of course. + /// + /// It can be used for checking the interface compatibility, + /// or it can serve as a skeleton of a new graph structure. + /// + /// Also, you will find here the full documentation of a certain graph + /// feature, the documentation of a real graph imlementation + /// like @ref ListGraph or + /// @ref SmartGraph will just refer to this structure. + /// + /// \todo A pages describing the concept of concept description would + /// be nice. + class StaticGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + StaticGraph() { } + ///Copy consructor. + +// ///\todo It is not clear, what we expect from a copy constructor. +// ///E.g. How to assign the nodes/edges to each other? What about maps? +// StaticGraph(const StaticGraph& g) { } + + /// The base type of node iterators, + /// or in other words, the trivial node iterator. + + /// This is the base type of each node iterator, + /// thus each kind of node iterator converts to this. + /// More precisely each kind of node iterator should be inherited + /// from the trivial node iterator. + class Node { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Node() { } + /// Copy constructor. + + /// Copy constructor. + /// + Node(const Node&) { } + + /// Invalid constructor \& conversion. + + /// This constructor initializes the iterator to be invalid. + /// \sa Invalid for more details. + Node(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Node) const { return true; } + + /// Inequality operator + + /// \sa operator==(Node n) + /// + bool operator!=(Node) const { return true; } + + }; + + /// This iterator goes through each node. + + /// This iterator goes through each node. + /// Its usage is quite simple, for example you can count the number + /// of nodes in graph \c g of type \c Graph like this: + /// \code + /// int count=0; + /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count; + /// \endcode + class NodeIt : public Node { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + NodeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + NodeIt(const NodeIt&) { } + /// Invalid constructor \& conversion. + + /// Initialize 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 \c g. + /// + NodeIt(const StaticGraph& g) { } + /// Node -> NodeIt conversion. + + /// Sets the iterator to the node of \c g pointed by the trivial + /// iterator n. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + NodeIt(const StaticGraph& g, const Node& n) { } + /// Next node. + + /// Assign the iterator to the next node. + /// + NodeIt& operator++() { return *this; } + }; + + + /// The base type of the edge iterators. + + /// The base type of the edge iterators. + /// + class Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Edge() { } + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + Edge(Invalid) { } + /// Equality operator + + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. + bool operator==(Edge) const { return true; } + /// Inequality operator + + /// \sa operator==(Node n) + /// + bool operator!=(Edge) const { return true; } + }; + + /// This iterator goes trough the outgoing edges of a node. + + /// This iterator goes trough the \e outgoing edges of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count; + /// \endcode + + class OutEdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + OutEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + OutEdgeIt(const OutEdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + OutEdgeIt(Invalid) { } + /// This constructor sets the iterator to first outgoing edge. + + /// This constructor set the iterator to the first outgoing edge of + /// node + ///@param n the node + ///@param g the graph + OutEdgeIt(const StaticGraph& g, const Node& n) { } + /// Edge -> OutEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + OutEdgeIt(const StaticGraph& g, const Edge& e) { } + ///Next outgoing edge + + /// Assign the iterator to the next + /// outgoing edge of the corresponding node. + OutEdgeIt& operator++() { return *this; } + }; + + /// This iterator goes trough the incoming edges of a node. + + /// This iterator goes trough the \e incoming edges of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c g of type \c Graph as follows. + /// \code + /// int count=0; + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count; + /// \endcode + + class InEdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + InEdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + InEdgeIt(const InEdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + InEdgeIt(Invalid) { } + /// This constructor sets the iterator to first incoming edge. + + /// This constructor set the iterator to the first incoming edge of + /// node + ///@param n the node + ///@param g the graph + InEdgeIt(const StaticGraph& g, const Node& n) { } + /// Edge -> InEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + InEdgeIt(const StaticGraph& g, const Edge& n) { } + /// Next incoming edge + + /// Assign the iterator to the next inedge of the corresponding node. + /// + InEdgeIt& operator++() { return *this; } + }; + /// This iterator goes through each edge. + + /// This iterator goes through each edge of a graph. + /// Its usage is quite simple, for example you can count the number + /// of edges in a graph \c g of type \c Graph as follows: + /// \code + /// int count=0; + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count; + /// \endcode + class EdgeIt : public Edge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + EdgeIt() { } + /// Copy constructor. + + /// Copy constructor. + /// + EdgeIt(const EdgeIt&) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + EdgeIt(Invalid) { } + /// This constructor sets the iterator to first edge. + + /// This constructor set the iterator to the first edge of + /// node + ///@param g the graph + EdgeIt(const StaticGraph& g) { } + /// Edge -> EdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator \c e. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + EdgeIt(const StaticGraph&, const Edge&) { } + ///Next edge + + /// Assign the iterator to the next + /// edge of the corresponding node. + EdgeIt& operator++() { return *this; } + }; + ///Gives back the target node of an edge. + + ///Gives back the target node of an edge. + /// + Node target(Edge) const { return INVALID; } + ///Gives back the source node of an edge. + + ///Gives back the source node of an edge. + /// + Node source(Edge) const { return INVALID; } + /// Read write map of the nodes to type \c T. + + /// \ingroup concept + /// ReadWrite map of the nodes to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (NodeMap) + /// needs some extra attention! + template + class NodeMap : public ReadWriteMap< Node, T > + { + public: + + ///\e + NodeMap(const StaticGraph&) { } + ///\e + NodeMap(const StaticGraph&, T) { } + + ///Copy constructor + NodeMap(const NodeMap&) { } + ///Assignment operator + NodeMap& operator=(const NodeMap&) { return *this; } + // \todo fix this concept + }; + + /// Read write map of the edges to type \c T. + + /// \ingroup concept + ///Reference map of the edges to type \c T. + /// \sa Reference + /// \warning Making maps that can handle bool type (EdgeMap) + /// needs some extra attention! + template + class EdgeMap : public ReadWriteMap + { + public: + + ///\e + EdgeMap(const StaticGraph&) { } + ///\e + EdgeMap(const StaticGraph&, T) { } + ///Copy constructor + EdgeMap(const EdgeMap&) { } + ///Assignment operator + EdgeMap& operator=(const EdgeMap&) { return *this; } + // \todo fix this concept + }; + + template + struct Constraints : public _StaticGraph::Constraints<_Graph> {}; + + }; + + /// An empty non-static graph class. + + /// This class provides everything that \ref StaticGraph + /// with additional functionality which enables to build a + /// graph from scratch. + class ExtendableGraph : public StaticGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + ExtendableGraph() { } + ///Add a new node to the graph. + + /// \return the new node. + /// + Node addNode() { return INVALID; } + ///Add a new edge to the graph. + + ///Add a new edge to the graph with source node \c s + ///and target node \c t. + ///\return the new edge. + Edge addEdge(Node s, Node t) { return INVALID; } + + /// Resets the graph. + + /// This function deletes all edges and nodes of the graph. + /// It also frees the memory allocated to store them. + /// \todo It might belong to \ref ErasableGraph. + void clear() { } + + template + struct Constraints : public _ExtendableGraph::Constraints<_Graph> {}; + + }; + + /// An empty erasable graph class. + + /// This class is an extension of \ref ExtendableGraph. It also makes it + /// possible to erase edges or nodes. + class ErasableGraph : public ExtendableGraph + { + public: + /// Defalult constructor. + + /// Defalult constructor. + /// + ErasableGraph() { } + /// Deletes a node. + + /// Deletes node \c n node. + /// + void erase(Node n) { } + /// Deletes an edge. + + /// Deletes edge \c e edge. + /// + void erase(Edge e) { } + + template + struct Constraints : public _ErasableGraph::Constraints<_Graph> {}; + + }; + + + /************* New GraphBase stuff **************/ + + +// /// A minimal GraphBase concept + +// /// This class describes a minimal concept which can be extended to a +// /// full-featured graph with \ref GraphFactory. +// class GraphBase { +// public: + +// GraphBase() {} + +// /// \bug Should we demand that Node and Edge be subclasses of the +// /// Graph class??? + +// typedef GraphItem<'n'> Node; +// typedef GraphItem<'e'> Edge; + +// // class Node : public BaseGraphItem<'n'> {}; +// // class Edge : public BaseGraphItem<'e'> {}; + +// // Graph operation +// void firstNode(Node &n) const { } +// void firstEdge(Edge &e) const { } + +// void firstOutEdge(Edge &e, Node) const { } +// void firstInEdge(Edge &e, Node) const { } + +// void nextNode(Node &n) const { } +// void nextEdge(Edge &e) const { } + + +// // Question: isn't it reasonable if this methods have a Node +// // parameter? Like this: +// // Edge& nextOut(Edge &e, Node) const { return e; } +// void nextOutEdge(Edge &e) const { } +// void nextInEdge(Edge &e) const { } + +// Node target(Edge) const { return Node(); } +// Node source(Edge) const { return Node(); } + + +// // Do we need id, nodeNum, edgeNum and co. in this basic graphbase +// // concept? + + +// // Maps. +// // +// // We need a special slimer concept which does not provide maps (it +// // wouldn't be strictly slimer, cause for map-factory id() & friends +// // a required...) + +// template +// class NodeMap : public GraphMap {}; + +// template +// class EdgeMap : public GraphMap {}; +// }; + // @} } //namespace concept } //namespace lemon diff -r cfccb33ecf7b -r 8d066154b66a src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Mon Feb 07 10:50:05 2005 +0000 +++ b/src/lemon/concept/graph_component.h Mon Feb 07 11:28:37 2005 +0000 @@ -108,7 +108,7 @@ // b = (ia == ib) && (ia != ib) && (ia < ib); b = (ia == ib) && (ia != ib); b = (ia == INVALID) && (ib != INVALID); - b = (ia < ib); + // b = (ia < ib); } const _GraphItem &ia;