# HG changeset patch # User deba # Date 1123775717 0 # Node ID 3fd1ba6e9872b4e8f0ab5ce5854db5f8aaf77d91 # Parent e251336be488ae5fd582722c7d653852cdc25278 Some modification on the undirected graph interface. Doc improvments diff -r e251336be488 -r 3fd1ba6e9872 lemon/bits/erasable_graph_extender.h --- a/lemon/bits/erasable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/bits/erasable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000 @@ -70,8 +70,8 @@ void erase(const UndirEdge& uedge) { std::vector edges; - edges.push_back(Edge(uedge,true)); - edges.push_back(Edge(uedge,false)); + edges.push_back(Parent::direct(uedge,true)); + edges.push_back(Parent::direct(uedge,false)); Parent::getNotifier(Edge()).erase(edges); Parent::getNotifier(UndirEdge()).erase(uedge); Parent::erase(uedge); diff -r e251336be488 -r 3fd1ba6e9872 lemon/bits/extendable_graph_extender.h --- a/lemon/bits/extendable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/bits/extendable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000 @@ -51,8 +51,8 @@ Parent::getNotifier(UndirEdge()).add(uedge); std::vector edges; - edges.push_back(Edge(uedge, true)); - edges.push_back(Edge(uedge, false)); + edges.push_back(Parent::direct(uedge, true)); + edges.push_back(Parent::direct(uedge, false)); Parent::getNotifier(Edge()).add(edges); return uedge; diff -r e251336be488 -r 3fd1ba6e9872 lemon/bits/iterable_graph_extender.h --- a/lemon/bits/iterable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/bits/iterable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000 @@ -118,50 +118,49 @@ }; - /// Base node of the iterator + /// \brief Base node of the iterator /// /// Returns the base node (ie. the source in this case) of the iterator - /// - /// \todo Document in the concept! Node baseNode(const OutEdgeIt &e) const { return Parent::source((Edge)e); } - /// Running node of the iterator + /// \brief Running node of the iterator /// /// Returns the running node (ie. the target in this case) of the /// iterator - /// - /// \todo Document in the concept! Node runningNode(const OutEdgeIt &e) const { return Parent::target((Edge)e); } - /// Base node of the iterator + /// \brief Base node of the iterator /// /// Returns the base node (ie. the target in this case) of the iterator - /// - /// \todo Document in the concept! Node baseNode(const InEdgeIt &e) const { return Parent::target((Edge)e); } - /// Running node of the iterator + /// \brief Running node of the iterator /// /// Returns the running node (ie. the source in this case) of the /// iterator - /// - /// \todo Document in the concept! Node runningNode(const InEdgeIt &e) const { return Parent::source((Edge)e); } using Parent::first; + /// \brief The opposite node on the given edge. + /// + /// Gives back the opposite on the given edge. + Node oppositeNode(const Node& n, const Edge& e) const { + if (Parent::source(e) == n) { + return Parent::target(e); + } else { + return Parent::source(e); + } + } + private: - // /// \todo When (and if) we change the iterators concept to use operator*, - // /// then the following shadowed methods will become superfluous. - // /// But for now these are important safety measures. - // void first(NodeIt &) const; // void first(EdgeIt &) const; // void first(OutEdgeIt &) const; @@ -190,7 +189,7 @@ typedef IterableGraphExtender<_Base> Parent; typedef IterableUndirGraphExtender<_Base> Graph; typedef typename Parent::Node Node; - + typedef typename Parent::Edge Edge; typedef typename Parent::UndirEdge UndirEdge; class UndirEdgeIt : public Parent::UndirEdge { @@ -261,6 +260,17 @@ return _dirTarget(e); } + /// \brief The opposite node on the given undirected edge. + /// + /// Gives back the opposite on the given undirected edge. + Node oppositeNode(const Node& n, const UndirEdge& e) const { + if (Parent::source(e) == n) { + return Parent::target(e); + } else { + return Parent::source(e); + } + } + }; } diff -r e251336be488 -r 3fd1ba6e9872 lemon/bits/undir_graph_extender.h --- a/lemon/bits/undir_graph_extender.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/bits/undir_graph_extender.h Thu Aug 11 15:55:17 2005 +0000 @@ -42,23 +42,11 @@ // be reasonable to syncronize... bool forward; - public: - Edge() {} - - /// \brief Directed edge from undirected edge and a direction. - /// - /// This constructor is not a part of the concept interface of - /// undirected graph, so please avoid using it if possible! Edge(const UndirEdge &ue, bool _forward) : UndirEdge(ue), forward(_forward) {} - /// \brief Directed edge from undirected edge and a source node. - /// - /// Constructs a directed edge from undirected edge and a source node. - /// - /// \note You have to specify the graph for this constructor. - Edge(const Graph &g, const UndirEdge &ue, const Node &n) : - UndirEdge(ue) { forward = (g.source(ue) == n); } + public: + Edge() {} /// Invalid edge constructor Edge(Invalid i) : UndirEdge(i), forward(true) {} @@ -79,7 +67,7 @@ /// \brief Edge of opposite direction. /// /// Returns the Edge of opposite direction. - Edge opposite(const Edge &e) const { + Edge oppositeEdge(const Edge &e) const { return Edge(e,!e.forward); } @@ -114,13 +102,6 @@ return _dirTarget(e); } - /// Returns whether the given directed edge is same orientation as the - /// corresponding undirected edge. - /// - /// \todo reference to the corresponding point of the undirected graph - /// concept. "What does the direction of an undirected edge mean?" - bool forward(const Edge &e) const { return e.forward; } - Node oppositeNode(const Node &n, const UndirEdge &e) const { if( n == Parent::source(e)) return Parent::target(e); @@ -130,18 +111,32 @@ return INVALID; } - /// Directed edge from an undirected edge and a source node. + /// \brief Directed edge from an undirected edge and a source node. /// /// Returns a (directed) Edge corresponding to the specified UndirEdge /// and source Node. /// - ///\todo Do we need this? + Edge direct(const UndirEdge &ue, const Node &s) const { + return Edge(ue, s == source(ue)); + } + + /// \brief Directed edge from an undirected edge. /// - ///\todo Better name... - Edge edgeWithSource(const UndirEdge &ue, const Node &s) const { - return Edge(*this, ue, s); + /// Returns a directed edge corresponding to the specified UndirEdge. + /// If the given bool is true the given undirected edge and the + /// returned edge have the same source node. + Edge direct(const UndirEdge &ue, bool d) const { + return Edge(ue, d); } + /// Returns whether the given directed edge is same orientation as the + /// corresponding undirected edge. + /// + /// \todo reference to the corresponding point of the undirected graph + /// concept. "What does the direction of an undirected edge mean?" + bool direction(const Edge &e) const { return e.forward; } + + using Parent::first; void first(Edge &e) const { Parent::first(e); diff -r e251336be488 -r 3fd1ba6e9872 lemon/concept/graph.h --- a/lemon/concept/graph.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/concept/graph.h Thu Aug 11 15:55:17 2005 +0000 @@ -479,25 +479,34 @@ /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. + /// It is always the target of the pointed edge. Node baseNode(const InEdgeIt&) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. + /// It is always the source of the pointed edge. Node runningNode(const InEdgeIt&) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. + /// It is always the source of the pointed edge. Node baseNode(const OutEdgeIt&) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. + /// It is always the target of the pointed edge. Node runningNode(const OutEdgeIt&) const { return INVALID; } - /// Read write map of the nodes to type \c T. - /// \ingroup concept + /// \brief The opposite node on the given edge. + /// + /// Gives back the opposite node on the given edge. + Node oppositeNode(const Node&, const Edge&) const { return INVALID; } + + /// \brief Read write map of the nodes to type \c T. + /// /// ReadWrite map of the nodes to type \c T. /// \sa Reference /// \warning Making maps that can handle bool type (NodeMap) @@ -519,10 +528,9 @@ // \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. + /// \brief Read write map of the edges to type \c T. + /// + /// Reference map of the edges to type \c T. /// \sa Reference /// \warning Making maps that can handle bool type (EdgeMap) /// needs some extra attention! @@ -610,67 +618,7 @@ 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 e251336be488 -r 3fd1ba6e9872 lemon/concept/graph_component.h --- a/lemon/concept/graph_component.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/concept/graph_component.h Thu Aug 11 15:55:17 2005 +0000 @@ -678,23 +678,33 @@ /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. + /// It is always the target of the pointed edge. Node baseNode(const InEdgeIt&) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. + /// It is always the source of the pointed edge. Node runningNode(const InEdgeIt&) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. + /// It is always the source of the pointed edge. Node baseNode(const OutEdgeIt&) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. + /// It is always the target of the pointed edge. 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 struct Constraints { @@ -707,7 +717,14 @@ typename _Graph::NodeIt >(); checkConcept, typename _Graph::InEdgeIt>(); checkConcept, typename _Graph::OutEdgeIt>(); + + typename _Graph::Node n; + typename _Graph::Edge e; + n = graph.oppositeNode(n, e); } + + const _Graph& graph; + }; }; diff -r e251336be488 -r 3fd1ba6e9872 lemon/concept/undir_graph.h --- a/lemon/concept/undir_graph.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/concept/undir_graph.h Thu Aug 11 15:55:17 2005 +0000 @@ -119,7 +119,10 @@ n = graph.oppositeNode(n0, ue); bool b; - b = graph.forward(e); + b = graph.direction(e); + Edge e = graph.direct(UndirEdge(), true); + e = graph.direct(UndirEdge(), n); + ignore_unused_variable_warning(b); } @@ -232,8 +235,12 @@ /// 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. + /// + /// You can assume that all undirected graph can be handled + /// as a static directed graph. This way it is fully conform + /// to the StaticGraph concept. - class UndirGraph : public StaticGraph { + class UndirGraph { public: ///\e @@ -241,8 +248,105 @@ /// typedef True UndirTag; + /// 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; } + + /// 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<(Node) const { return false; } + + }; + + /// 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& n) : Node(n) { } + /// 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 UndirGraph&) { } + /// Node -> NodeIt conversion. + + /// Sets the iterator to the node of \c the graph pointed by + /// the trivial iterator. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + NodeIt(const UndirGraph&, const Node&) { } + /// Next node. + + /// Assign the iterator to the next node. + /// + NodeIt& operator++() { return *this; } + }; + + /// The base type of the undirected edge iterators. - + /// The base type of the undirected edge iterators. /// class UndirEdge { @@ -257,11 +361,6 @@ /// Copy constructor. /// UndirEdge(const UndirEdge&) { } - /// Edge -> UndirEdge conversion - - /// Edge -> UndirEdge conversion - /// - UndirEdge(const Edge&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. @@ -278,18 +377,24 @@ /// bool operator!=(UndirEdge) const { return true; } - ///\e + /// 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<(UndirEdge) const { return false; } + }; - ///\todo Do we need this? - /// - bool operator<(const UndirEdge &that) const { return true; } - }; - /// This iterator goes through each undirected edge. /// This iterator goes through each undirected 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: + /// of undirected edges in a graph \c g of type \c Graph as follows: /// \code /// int count=0; /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count; @@ -297,12 +402,12 @@ class UndirEdgeIt : public UndirEdge { public: /// Default constructor - + /// @warning The default constructor sets the iterator /// to an undefined value. UndirEdgeIt() { } /// Copy constructor. - + /// Copy constructor. /// UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { } @@ -311,24 +416,26 @@ /// Initialize the iterator to be invalid. /// UndirEdgeIt(Invalid) { } - /// This constructor sets the iterator to the first edge. + /// This constructor sets the iterator to the first undirected edge. - /// This constructor sets the iterator to the first edge of \c g. + /// This constructor sets the iterator to the first undirected edge. UndirEdgeIt(const UndirGraph&) { } /// UndirEdge -> UndirEdgeIt 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. + /// Sets the iterator to the value of the trivial iterator. + /// This feature necessitates that each time we + /// iterate the undirected edge-set, the iteration order is the + /// same. UndirEdgeIt(const UndirGraph&, const UndirEdge&) { } - ///Next edge + /// Next undirected edge - /// Assign the iterator to the next edge. + /// Assign the iterator to the next undirected edge. UndirEdgeIt& operator++() { return *this; } }; - /// This iterator goes trough the incident undirected edges of a node. - + /// \brief This iterator goes trough the incident undirected + /// edges of a node. + /// /// This iterator goes trough the incident undirected edges /// of a certain node /// of a graph. @@ -375,6 +482,237 @@ IncEdgeIt& operator++() { return *this; } }; + /// The directed edge type. + + /// The directed edge type. It can be converted to the + /// undirected edge. + class Edge : public UndirEdge { + public: + /// Default constructor + + /// @warning The default constructor sets the iterator + /// to an undefined value. + Edge() { } + /// Copy constructor. + + /// Copy constructor. + /// + Edge(const Edge& e) : UndirEdge(e) { } + /// 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==(Edge n) + /// + bool operator!=(Edge) const { return true; } + + /// 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<(Edge) const { return false; } + + }; + /// This iterator goes through each directed 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& e) : Edge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + EdgeIt(Invalid) { } + /// This constructor sets the iterator to the first edge. + + /// This constructor sets the iterator to the first edge of \c g. + ///@param g the graph + EdgeIt(const UndirGraph&) { } + /// 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 UndirGraph&, const Edge&) { } + ///Next edge + + /// Assign the iterator to the next edge. + EdgeIt& operator++() { return *this; } + }; + + /// This iterator goes trough the outgoing directed 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& e) : Edge(e) { } + /// Initialize the iterator to be invalid. + + /// Initialize the iterator to be invalid. + /// + OutEdgeIt(Invalid) { } + /// This constructor sets the iterator to the first outgoing edge. + + /// This constructor sets the iterator to the first outgoing edge of + /// the node. + ///@param n the node + ///@param g the graph + OutEdgeIt(const UndirGraph&, const Node&) { } + /// Edge -> OutEdgeIt conversion + + /// Sets the iterator to the value of the trivial iterator. + /// This feature necessitates that each time we + /// iterate the edge-set, the iteration order is the same. + OutEdgeIt(const UndirGraph&, const Edge&) { } + ///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 directed 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& e) : Edge(e) { } + /// 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 + /// the node. + ///@param n the node + ///@param g the graph + InEdgeIt(const UndirGraph&, const Node&) { } + /// 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 UndirGraph&, const Edge&) { } + /// Next incoming edge + + /// Assign the iterator to the next inedge of the corresponding node. + /// + InEdgeIt& operator++() { return *this; } + }; + + /// \brief Read write map of the nodes to type \c T. + /// + /// 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 UndirGraph&) { } + ///\e + NodeMap(const UndirGraph&, T) { } + + ///Copy constructor + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } + ///Assignment operator + NodeMap& operator=(const NodeMap&) { return *this; } + // \todo fix this concept + }; + + /// \brief Read write map of the directed edges to type \c T. + /// + /// Reference map of the directed 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 UndirGraph&) { } + ///\e + EdgeMap(const UndirGraph&, T) { } + ///Copy constructor + EdgeMap(const EdgeMap& em) : ReadWriteMap(em) { } + ///Assignment operator + EdgeMap& operator=(const EdgeMap&) { return *this; } + // \todo fix this concept + }; + /// Read write map of the undirected edges to type \c T. /// Reference map of the edges to type \c T. @@ -391,122 +729,140 @@ ///\e UndirEdgeMap(const UndirGraph&, T) { } ///Copy constructor - UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap(em) { } + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap(em) {} ///Assignment operator UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; } // \todo fix this concept }; - /// Is the Edge oriented "forward"? + /// \brief Direct the given undirected edge. + /// + /// Direct the given undirected edge. The returned edge source + /// will be the given edge. + Edge direct(const UndirEdge&, const Node&) const { + return INVALID; + } + /// \brief Direct the given undirected edge. + /// + /// Direct the given undirected edge. The returned edge source + /// will be the source of the undirected edge if the given bool + /// is true. + Edge direct(const UndirEdge&, bool) const { + return INVALID; + } + + /// \brief Returns true if the edge has default orientation. + /// /// Returns whether the given directed edge is same orientation as /// the corresponding undirected edge. + bool direction(Edge) const { return true; } + + /// \brief Returns the opposite directed edge. /// - /// \todo "What does the direction of an undirected edge mean?" - bool forward(Edge) const { return true; } + /// Returns the opposite directed edge. + Edge oppositeEdge(Edge) const { return INVALID; } - /// Opposite node on an edge - + /// \brief 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. - + /// \brief 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 + /// undirected edge, and is used to define the "default" direction /// of the directed versions of the edges. - /// \sa forward + /// \sa direction Node source(UndirEdge) const { return INVALID; } - /// Second node of the undirected edge. + /// \brief Second node of the undirected edge. Node target(UndirEdge) const { return INVALID; } - /// Source node of the directed edge. + /// \brief Source node of the directed edge. Node source(Edge) const { return INVALID; } - /// Target node of the directed edge. + /// \brief Target node of the directed edge. Node target(Edge) const { return INVALID; } - /// First node of the graph - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 - + /// \brief 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 {} - /// Base node of the iterator + /// \brief Base node of the iterator /// /// Returns the base node (the source in this case) of the iterator Node baseNode(OutEdgeIt e) const { return source(e); } - /// Running node of the iterator + /// \brief Running node of the iterator /// /// Returns the running node (the target in this case) of the /// iterator @@ -514,13 +870,13 @@ return target(e); } - /// Base node of the iterator + /// \brief Base node of the iterator /// /// Returns the base node (the target in this case) of the iterator Node baseNode(InEdgeIt e) const { return target(e); } - /// Running node of the iterator + /// \brief Running node of the iterator /// /// Returns the running node (the source in this case) of the /// iterator @@ -528,20 +884,20 @@ return source(e); } - /// Base node of the iterator + /// \brief Base node of the iterator /// /// Returns the base node of the iterator Node baseNode(IncEdgeIt) const { return INVALID; } - /// Running node of the iterator + + /// \brief Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(IncEdgeIt) const { return INVALID; } - template struct Constraints { void constraints() { @@ -553,8 +909,30 @@ }; + /// \brief An empty non-static undirected graph class. + /// + /// This class provides everything that \ref UndirGraph does. + /// Additionally it enables building graphs from scratch. class ExtendableUndirGraph : public UndirGraph { public: + + /// \brief Add a new node to the graph. + /// + /// Add a new node to the graph. + /// \return the new node. + Node addNode(); + + /// \brief Add a new undirected edge to the graph. + /// + /// Add a new undirected edge to the graph. + /// \return the new edge. + UndirEdge addEdge(const Node& from, const Node& to); + + /// \brief Resets the graph. + /// + /// This function deletes all undirected edges and nodes of the graph. + /// It also frees the memory allocated to store them. + void clear() { } template struct Constraints { @@ -571,9 +949,24 @@ }; + /// \brief An empty erasable undirected graph class. + /// + /// This class is an extension of \ref ExtendableUndirGraph. It makes it + /// possible to erase undirected edges or nodes. class ErasableUndirGraph : public ExtendableUndirGraph { public: + /// \brief Deletes a node. + /// + /// Deletes a node. + /// + void erase(Node) { } + /// \brief Deletes an undirected edge. + /// + /// Deletes an undirected edge. + /// + void erase(UndirEdge) { } + template struct Constraints { void constraints() { diff -r e251336be488 -r 3fd1ba6e9872 lemon/graph_adaptor.h --- a/lemon/graph_adaptor.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/graph_adaptor.h Thu Aug 11 15:55:17 2005 +0000 @@ -105,13 +105,12 @@ void clear() const { graph->clear(); } - bool forward(const Edge& e) const { return graph->forward(e); } - bool backward(const Edge& e) const { return graph->backward(e); } - int id(const Node& v) const { return graph->id(v); } int id(const Edge& e) const { return graph->id(e); } - Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); } + Edge oppositeNode(const Edge& e) const { + return Edge(graph->opposite(e)); + } template class NodeMap : public _Graph::template NodeMap<_Value> { @@ -608,14 +607,14 @@ forward_map(*(g->graph), a), backward_map(*(g->graph), a) { } void set(Edge e, T a) { - if (g->forward(e)) + if (g->direction(e)) forward_map.set(e, a); else backward_map.set(e, a); } T operator[](Edge e) const { - if (g->forward(e)) + if (g->direction(e)) return forward_map[e]; else return backward_map[e]; diff -r e251336be488 -r 3fd1ba6e9872 lemon/graph_utils.h --- a/lemon/graph_utils.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/graph_utils.h Thu Aug 11 15:55:17 2005 +0000 @@ -995,7 +995,7 @@ /// \param key An undirected edge /// \return The "forward" directed edge view of undirected edge Value operator[](const Key& key) const { - return graph.edgeWithSource(key, graph.source(key)); + return graph.direct(key, true); } private: @@ -1035,7 +1035,7 @@ /// \param key An undirected edge /// \return The "backward" directed edge view of undirected edge Value operator[](const Key& key) const { - return graph.edgeWithSource(key, graph.target(key)); + return graph.direct(key, false); } private: diff -r e251336be488 -r 3fd1ba6e9872 lemon/lemon_reader.h --- a/lemon/lemon_reader.h Thu Aug 11 15:24:24 2005 +0000 +++ b/lemon/lemon_reader.h Thu Aug 11 15:55:17 2005 +0000 @@ -1322,9 +1322,9 @@ is >> c; UndirEdge undirEdge = inverter->read(is); if (c == '+') { - edge = graph.edgeWithSource(undirEdge, graph.source(undirEdge)); + edge = graph.direct(undirEdge, true); } else if (c == '-') { - edge = graph.edgeWithSource(undirEdge, graph.target(undirEdge)); + edge = graph.direct(undirEdge, false); } else { throw DataFormatError("Wrong id format for edge " "in undirected edgeset");