# HG changeset patch # User klao # Date 1102293044 0 # Node ID c8a41699e613032cbf95ec4f6dd17c3ab6bdaccd # Parent 53e7969a92eb76102b507338e3b50a170e7edc16 Undirected graph documentation and concept refinements. * quite a few bug fixes * concept::UndirGraph is almost complete and looks quite good. diff -r 53e7969a92eb -r c8a41699e613 doc/Doxyfile --- a/doc/Doxyfile Fri Dec 03 12:19:26 2004 +0000 +++ b/doc/Doxyfile Mon Dec 06 00:30:44 2004 +0000 @@ -425,12 +425,14 @@ INPUT = mainpage.dox \ graphs.dox \ + undir_graphs.dox \ named-param.dox \ maps.dox \ coding_style.dox \ groups.dox \ namespaces.dox \ license.dox \ + developpers_interface.dox \ ../src/lemon \ ../src/lemon/concept \ ../src/test/test_tools.h diff -r 53e7969a92eb -r c8a41699e613 doc/developpers_interface.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/developpers_interface.dox Mon Dec 06 00:30:44 2004 +0000 @@ -0,0 +1,7 @@ +/*! + +\page developpers_interface Developpers' interface to graph structures + +Under construction + +*/ diff -r 53e7969a92eb -r c8a41699e613 doc/groups.dox --- a/doc/groups.dox Fri Dec 03 12:19:26 2004 +0000 +++ b/doc/groups.dox Mon Dec 06 00:30:44 2004 +0000 @@ -80,15 +80,27 @@ */ /** -@defgroup concept Concept +@defgroup concept Concepts \brief Skeleton classes and concept checking classes This group describes the data/algorithm skeletons and concept checking -classes implemented in LEMON. These classes exist in order to make it -easier to check if a certain template class or template function is -correctly implemented. +classes implemented in LEMON. + +One aim of these classes is to make it easier to check if a certain +class or template function is correctly implemented. + +The other (sometimes even more important) aim is to document the concepts. + */ +/** +@defgroup graph_concepts Graph Structure Concepts +@ingroup concept +\brief Skeleton and concept checking classes for graph structures + +This group contains the skeletons and concept checking classes of LEMON's +graph structures and helper classes used to implement these. +*/ /** @defgroup experimental Experimental Structures and Algorithms diff -r 53e7969a92eb -r c8a41699e613 doc/undir_graphs.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/undir_graphs.dox Mon Dec 06 00:30:44 2004 +0000 @@ -0,0 +1,9 @@ +/*! + +\page undir_graphs Undirected graph structures + +The primary data structures of LEMON are the graph classes. + +Under construction. + +*/ diff -r 53e7969a92eb -r c8a41699e613 src/lemon/concept/graph.h --- a/src/lemon/concept/graph.h Fri Dec 03 12:19:26 2004 +0000 +++ b/src/lemon/concept/graph.h Mon Dec 06 00:30:44 2004 +0000 @@ -17,7 +17,7 @@ #ifndef LEMON_CONCEPT_GRAPH_H #define LEMON_CONCEPT_GRAPH_H -///\ingroup concept +///\ingroup graph_concepts ///\file ///\brief Declaration of Graph. @@ -29,7 +29,7 @@ namespace lemon { namespace concept { - /// \addtogroup concept + /// \addtogroup graph_concepts /// @{ // /// An empty static graph class. diff -r 53e7969a92eb -r c8a41699e613 src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Fri Dec 03 12:19:26 2004 +0000 +++ b/src/lemon/concept/graph_component.h Mon Dec 06 00:30:44 2004 +0000 @@ -14,7 +14,7 @@ * */ -///\ingroup concept +///\ingroup graph_concepts ///\file ///\brief The graph components. @@ -28,22 +28,32 @@ namespace lemon { namespace concept { + /// \addtogroup graph_concepts + /// @{ /**************** Graph iterator concepts ****************/ - /// Skeleton class for graph Node and Edge + /// Skeleton class for graph Node and Edge types - /// \note Because Node and Edge are forbidden to inherit from the same - /// base class, this is a template. For Node you should instantiate it - /// with character 'n' and for Edge with 'e'. + /// This class describes the interface of Node and Edge (and UndirEdge + /// in undirected graphs) subtypes of graph types. + /// + /// \note This class is a template class so that we can use it to + /// create graph skeleton classes. The reason for this is than Node + /// and Edge types should \em not derive from the same base class. + /// For Node you should instantiate it with character 'n' and for Edge + /// with 'e'. - template +#ifndef DOXYGEN + template +#endif class GraphItem { public: /// Default constructor. - /// @warning The default constructor sets the item - /// to an undefined value. + /// \warning The default constructor is not required to set + /// the item to some well-defined value. So you should consider it + /// as uninitialized. GraphItem() {} /// Copy constructor. @@ -71,9 +81,17 @@ /// bool operator!=(GraphItem) const { return false; } - // Technical requirement. Do we really need this? - // bool operator<(GraphItem) const { return false; } + /// Artificial ordering operator. + /// To allow the use of graph descriptors as key type in std::map or + /// similar associative container we require this. + /// + /// \note This operator only have to define some strict ordering of + /// the items; this order has nothing to do with the iteration + /// ordering of the items. + /// + /// \bug This is a technical requirement. Do we really need this? + bool operator<(GraphItem) const { return false; } template struct Constraints { @@ -88,6 +106,7 @@ // b = (ia == ib) && (ia != ib) && (ia < ib); b = (ia == ib) && (ia != ib); b = (ia == INVALID) && (ib != INVALID); + b = (ia < ib); } const _GraphItem &ia; @@ -95,6 +114,21 @@ }; }; + /// A type describing the concept of graph node + + /// This is an instantiation of \ref GraphItem which can be used as a + /// Node subtype in graph skeleton definitions + typedef GraphItem<'n'> GraphNode; + + /// A type describing the concept of graph edge + + /// This is an instantiation of \ref GraphItem which can be used as a + /// Edge subtype in graph skeleton definitions + typedef GraphItem<'e'> GraphEdge; + + + /**************** Basic features of graphs ****************/ + /// An empty base graph class. /// This class provides the minimal set of features needed for a graph @@ -629,6 +663,11 @@ }; + /// Class describing the concept of graph maps + + /// This class describes the common interface of the graph maps + /// (NodeMap, EdgeMap), that is \ref maps "maps" which can be used to + /// associate data to graph descriptors (nodes or edges). template class GraphMap : public ReadWriteMap { protected: @@ -804,6 +843,8 @@ }; }; + /// @} + } } diff -r 53e7969a92eb -r c8a41699e613 src/lemon/concept/undir_graph.h --- a/src/lemon/concept/undir_graph.h Fri Dec 03 12:19:26 2004 +0000 +++ b/src/lemon/concept/undir_graph.h Mon Dec 06 00:30:44 2004 +0000 @@ -17,7 +17,7 @@ * */ -///\ingroup concept +///\ingroup graph_concepts ///\file ///\brief Undirected graphs and components of. @@ -30,7 +30,62 @@ namespace lemon { namespace concept { - /// \todo to be done + /// \addtogroup graph_concepts + /// @{ + + + /// Skeleton class which describes an edge with direction in \ref + /// UndirGraph "undirected graph". + template + class UndirGraphEdge : public UndirEdge { + public: + + /// \e + UndirGraphEdge() {} + + /// \e + UndirGraphEdge(const UndirGraphEdge&) {} + + /// \e + UndirGraphEdge(Invalid) {} + + /// \brief Constructs a directed version of an undirected edge + /// + /// \param forward If \c true the direction of the contructed edge + /// is the same as the inherent direction of the \c undir_edge; if + /// \c false --- the opposite. + UndirGraphEdge(UndirEdge undir_edge, bool forward) { + ignore_unused_variable_warning(undir_edge); + ignore_unused_variable_warning(forward); + } + + /// \e + UndirGraphEdge& operator=(UndirGraphEdge) { return *this; } + + /// \e + bool operator==(UndirGraphEdge) const { return true; } + /// \e + bool operator!=(UndirGraphEdge) const { return false; } + + /// \e + bool operator<(UndirGraphEdge) const { return false; } + + template + struct Constraints { + void constraints() { + /// \bug This should be is_base_and_derived ... + UndirEdge ue = e; + ue = e; + Edge forward(ue, true); + Edge backward(ue, false); + + ignore_unused_variable_warning(forward); + ignore_unused_variable_warning(backward); + } + Edge e; + }; + }; + struct BaseIterableUndirGraphConcept { @@ -43,21 +98,29 @@ void constraints() { checkConcept(); - checkConcept, UndirEdge >(); + checkConcept, UndirEdge>(); + checkConcept, Edge>(); - /// \bug this should be base_and_derived: - UndirEdge ue = e; - ue = e; + graph.first(ue); + graph.next(ue); + const_constraints(); + } + void const_constraints() { Node n; n = graph.target(ue); n = graph.source(ue); + n = graph.oppositeNode(n0, ue); - graph.first(ue); - graph.next(ue); + bool b; + b = graph.forward(e); + ignore_unused_variable_warning(b); } - const Graph &graph; + + Graph graph; Edge e; + Node n0; + UndirEdge ue; }; }; @@ -76,10 +139,10 @@ typedef typename Graph::UndirEdge UndirEdge; typedef typename Graph::UndirEdgeIt UndirEdgeIt; - typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt; + typedef typename Graph::IncEdgeIt IncEdgeIt; checkConcept, UndirEdgeIt>(); - checkConcept, UndirIncEdgeIt>(); + checkConcept, IncEdgeIt>(); } }; @@ -145,9 +208,228 @@ }; + /// Class describing the concept of Undirected Graphs. + + /// This class describes the common interface of all Undirected + /// Graphs. + /// + /// As all concept describing classes it provides only interface + /// without any sensible implementation. So any algorithm for + /// undirected graph should compile with this class, but it will not + /// run properly, of couse. + /// + /// In LEMON undirected graphs also fulfill the concept of directed + /// graphs (\ref lemon::concept::Graph "Graph Concept"). For + /// explanation of this and more see also the page \ref undir_graphs, + /// a tutorial about undirected graphs. + class UndirGraph { public: + /// Type describing a node in the graph + typedef GraphNode Node; + + /// Type describing an undirected edge + typedef GraphItem<'u'> UndirEdge; + + /// Type describing an UndirEdge with direction +#ifndef DOXYGEN + typedef UndirGraphEdge Edge; +#else + typedef UndirGraphEdge Edge; +#endif + + /// Iterator type which iterates over all nodes +#ifndef DOXYGEN + typedef GraphIterator NodeIt; +#else + typedef GraphIterator NodeIt; +#endif + + /// Iterator type which iterates over all undirected edges +#ifndef DOXYGEN + typedef GraphIterator UndirEdgeIt; +#else + typedef GraphIterator UndirEdgeIt; +#endif + + /// Iterator type which iterates over all directed edges. + + /// Iterator type which iterates over all edges (each undirected + /// edge occurs twice with both directions. +#ifndef DOXYGEN + typedef GraphIterator EdgeIt; +#else + typedef GraphIterator EdgeIt; +#endif + + + /// Iterator of undirected edges incident to a node +#ifndef DOXYGEN + typedef GraphIncIterator IncEdgeIt; +#else + typedef GraphIncIterator IncEdgeIt; +#endif + + /// Iterator of edges incoming to a node +#ifndef DOXYGEN + typedef GraphIncIterator InEdgeIt; +#else + typedef GraphIncIterator InEdgeIt; +#endif + + /// Iterator of edges outgoing from a node +#ifndef DOXYGEN + typedef GraphIncIterator OutEdgeIt; +#else + typedef GraphIncIterator OutEdgeIt; +#endif + + /// NodeMap template +#ifdef DOXYGEN + typedef GraphMap NodeMap; +#endif + + /// UndirEdgeMap template +#ifdef DOXYGEN + typedef GraphMap UndirEdgeMap; +#endif + + /// EdgeMap template +#ifdef DOXYGEN + typedef GraphMap EdgeMap; +#endif + + template + class NodeMap : public GraphMap { + typedef GraphMap Parent; + public: + + explicit NodeMap(const UndirGraph &g) : Parent(g) {} + NodeMap(const UndirGraph &g, T t) : Parent(g, t) {} + }; + + template + class UndirEdgeMap : public GraphMap { + typedef GraphMap Parent; + public: + + explicit UndirEdgeMap(const UndirGraph &g) : Parent(g) {} + UndirEdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} + }; + + template + class EdgeMap : public GraphMap { + typedef GraphMap Parent; + public: + + explicit EdgeMap(const UndirGraph &g) : Parent(g) {} + EdgeMap(const UndirGraph &g, T t) : Parent(g, t) {} + }; + + /// Is the Edge oriented "forward"? + + /// Returns whether the given directed edge is same orientation as + /// the corresponding undirected edge. + /// + /// \todo "What does the direction of an undirected edge mean?" + bool forward(Edge) const { return true; } + + /// Opposite node on an edge + + /// \return the opposite of the given Node on the given Edge + /// + /// \todo What should we do if given Node and Edge are not incident? + Node oppositeNode(Node, UndirEdge) const { return INVALID; } + + /// First node of the undirected edge. + + /// \return the first node of the given UndirEdge. + /// + /// Naturally undirectected edges don't have direction and thus + /// don't have source and target node. But we use these two methods + /// to query the two endnodes of the edge. The direction of the edge + /// which arises this way is called the inherent direction of the + /// undirected edge, and is used to define the "forward" direction + /// of the directed versions of the edges. + /// \sa forward + Node source(UndirEdge) const { return INVALID; } + + /// Second node of the undirected edge. + Node target(UndirEdge) const { return INVALID; } + + /// Source node of the directed edge. + Node source(Edge) const { return INVALID; } + + /// Target node of the directed edge. + Node target(Edge) const { return INVALID; } + + /// First node of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void first(Node&) const {} + /// Next node of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void next(Node&) const {} + + /// First undirected edge of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void first(UndirEdge&) const {} + /// Next undirected edge of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void next(UndirEdge&) const {} + + /// First directed edge of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void first(Edge&) const {} + /// Next directed edge of the graph + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void next(Edge&) const {} + + /// First outgoing edge from a given node + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void firstOut(Edge&, Node) const {} + /// Next outgoing edge to a node + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void nextOut(Edge&) const {} + + /// First incoming edge to a given node + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void firstIn(Edge&, Node) const {} + /// Next incoming edge to a node + + /// \note This method is part of so called \ref + /// developpers_interface "Developpers' interface", so it shouldn't + /// be used in an end-user program. + void nextIn(Edge&) const {} + + template struct Constraints { void constraints() { @@ -190,6 +472,8 @@ }; + /// @} + } } diff -r 53e7969a92eb -r c8a41699e613 src/lemon/iterable_graph_extender.h --- a/src/lemon/iterable_graph_extender.h Fri Dec 03 12:19:26 2004 +0000 +++ b/src/lemon/iterable_graph_extender.h Mon Dec 06 00:30:44 2004 +0000 @@ -157,7 +157,7 @@ }; - class UndirIncEdgeIt : public UndirEdge { + class IncEdgeIt : public UndirEdge { const Graph* graph; bool forward; friend class IterableUndirGraphExtender; @@ -165,30 +165,30 @@ friend class UndirGraphExtender; public: - UndirIncEdgeIt() { } + IncEdgeIt() { } - UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } + IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } - explicit UndirIncEdgeIt(const Graph& _graph, const Node &n) + explicit IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { _graph._dirFirstOut(*this, n); } // FIXME: Do we need this type of constructor here? - // UndirIncEdgeIt(const Graph& _graph, const Edge& e) : + // IncEdgeIt(const Graph& _graph, const Edge& e) : // UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { } // or - // UndirIncEdgeIt(const Graph& _graph, const Node& n, + // IncEdgeIt(const Graph& _graph, const Node& n, // Const UndirEdge &e) ... ? - UndirIncEdgeIt& operator++() { + IncEdgeIt& operator++() { graph->_dirNextOut(*this); return *this; } }; - Node source(const UndirIncEdgeIt &e) const { + Node source(const IncEdgeIt &e) const { return _dirSource(e); } @@ -197,7 +197,7 @@ using Parent::source; /// Target of the given Edge. - Node target(const UndirIncEdgeIt &e) const { + Node target(const IncEdgeIt &e) const { return _dirTarget(e); } diff -r 53e7969a92eb -r c8a41699e613 src/lemon/undir_graph_extender.h --- a/src/lemon/undir_graph_extender.h Fri Dec 03 12:19:26 2004 +0000 +++ b/src/lemon/undir_graph_extender.h Mon Dec 06 00:30:44 2004 +0000 @@ -108,7 +108,7 @@ /// concept. "What does the direction of an undirected edge mean?" bool forward(const Edge &e) const { return e.forward; } - Node oppsiteNode(const Node &n, const Edge &e) const { + Node oppositeNode(const Node &n, const UndirEdge &e) const { if( n == Parent::source(e)) return Parent::target(e); else if( n == Parent::target(e)) diff -r 53e7969a92eb -r c8a41699e613 src/test/undir_graph_test.cc --- a/src/test/undir_graph_test.cc Fri Dec 03 12:19:26 2004 +0000 +++ b/src/test/undir_graph_test.cc Mon Dec 06 00:30:44 2004 +0000 @@ -33,5 +33,7 @@ checkConcept(); checkConcept(); + checkConcept(); + return 0; }