Some modification on the undirected graph interface.
Doc improvments
1.1 --- a/lemon/bits/erasable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000
1.2 +++ b/lemon/bits/erasable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000
1.3 @@ -70,8 +70,8 @@
1.4
1.5 void erase(const UndirEdge& uedge) {
1.6 std::vector<Edge> edges;
1.7 - edges.push_back(Edge(uedge,true));
1.8 - edges.push_back(Edge(uedge,false));
1.9 + edges.push_back(Parent::direct(uedge,true));
1.10 + edges.push_back(Parent::direct(uedge,false));
1.11 Parent::getNotifier(Edge()).erase(edges);
1.12 Parent::getNotifier(UndirEdge()).erase(uedge);
1.13 Parent::erase(uedge);
2.1 --- a/lemon/bits/extendable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000
2.2 +++ b/lemon/bits/extendable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000
2.3 @@ -51,8 +51,8 @@
2.4 Parent::getNotifier(UndirEdge()).add(uedge);
2.5
2.6 std::vector<Edge> edges;
2.7 - edges.push_back(Edge(uedge, true));
2.8 - edges.push_back(Edge(uedge, false));
2.9 + edges.push_back(Parent::direct(uedge, true));
2.10 + edges.push_back(Parent::direct(uedge, false));
2.11 Parent::getNotifier(Edge()).add(edges);
2.12
2.13 return uedge;
3.1 --- a/lemon/bits/iterable_graph_extender.h Thu Aug 11 15:24:24 2005 +0000
3.2 +++ b/lemon/bits/iterable_graph_extender.h Thu Aug 11 15:55:17 2005 +0000
3.3 @@ -118,50 +118,49 @@
3.4
3.5 };
3.6
3.7 - /// Base node of the iterator
3.8 + /// \brief Base node of the iterator
3.9 ///
3.10 /// Returns the base node (ie. the source in this case) of the iterator
3.11 - ///
3.12 - /// \todo Document in the concept!
3.13 Node baseNode(const OutEdgeIt &e) const {
3.14 return Parent::source((Edge)e);
3.15 }
3.16 - /// Running node of the iterator
3.17 + /// \brief Running node of the iterator
3.18 ///
3.19 /// Returns the running node (ie. the target in this case) of the
3.20 /// iterator
3.21 - ///
3.22 - /// \todo Document in the concept!
3.23 Node runningNode(const OutEdgeIt &e) const {
3.24 return Parent::target((Edge)e);
3.25 }
3.26
3.27 - /// Base node of the iterator
3.28 + /// \brief Base node of the iterator
3.29 ///
3.30 /// Returns the base node (ie. the target in this case) of the iterator
3.31 - ///
3.32 - /// \todo Document in the concept!
3.33 Node baseNode(const InEdgeIt &e) const {
3.34 return Parent::target((Edge)e);
3.35 }
3.36 - /// Running node of the iterator
3.37 + /// \brief Running node of the iterator
3.38 ///
3.39 /// Returns the running node (ie. the source in this case) of the
3.40 /// iterator
3.41 - ///
3.42 - /// \todo Document in the concept!
3.43 Node runningNode(const InEdgeIt &e) const {
3.44 return Parent::source((Edge)e);
3.45 }
3.46
3.47 using Parent::first;
3.48
3.49 + /// \brief The opposite node on the given edge.
3.50 + ///
3.51 + /// Gives back the opposite on the given edge.
3.52 + Node oppositeNode(const Node& n, const Edge& e) const {
3.53 + if (Parent::source(e) == n) {
3.54 + return Parent::target(e);
3.55 + } else {
3.56 + return Parent::source(e);
3.57 + }
3.58 + }
3.59 +
3.60 private:
3.61
3.62 - // /// \todo When (and if) we change the iterators concept to use operator*,
3.63 - // /// then the following shadowed methods will become superfluous.
3.64 - // /// But for now these are important safety measures.
3.65 -
3.66 // void first(NodeIt &) const;
3.67 // void first(EdgeIt &) const;
3.68 // void first(OutEdgeIt &) const;
3.69 @@ -190,7 +189,7 @@
3.70 typedef IterableGraphExtender<_Base> Parent;
3.71 typedef IterableUndirGraphExtender<_Base> Graph;
3.72 typedef typename Parent::Node Node;
3.73 -
3.74 + typedef typename Parent::Edge Edge;
3.75 typedef typename Parent::UndirEdge UndirEdge;
3.76
3.77 class UndirEdgeIt : public Parent::UndirEdge {
3.78 @@ -261,6 +260,17 @@
3.79 return _dirTarget(e);
3.80 }
3.81
3.82 + /// \brief The opposite node on the given undirected edge.
3.83 + ///
3.84 + /// Gives back the opposite on the given undirected edge.
3.85 + Node oppositeNode(const Node& n, const UndirEdge& e) const {
3.86 + if (Parent::source(e) == n) {
3.87 + return Parent::target(e);
3.88 + } else {
3.89 + return Parent::source(e);
3.90 + }
3.91 + }
3.92 +
3.93 };
3.94 }
3.95
4.1 --- a/lemon/bits/undir_graph_extender.h Thu Aug 11 15:24:24 2005 +0000
4.2 +++ b/lemon/bits/undir_graph_extender.h Thu Aug 11 15:55:17 2005 +0000
4.3 @@ -42,23 +42,11 @@
4.4 // be reasonable to syncronize...
4.5 bool forward;
4.6
4.7 - public:
4.8 - Edge() {}
4.9 -
4.10 - /// \brief Directed edge from undirected edge and a direction.
4.11 - ///
4.12 - /// This constructor is not a part of the concept interface of
4.13 - /// undirected graph, so please avoid using it if possible!
4.14 Edge(const UndirEdge &ue, bool _forward) :
4.15 UndirEdge(ue), forward(_forward) {}
4.16
4.17 - /// \brief Directed edge from undirected edge and a source node.
4.18 - ///
4.19 - /// Constructs a directed edge from undirected edge and a source node.
4.20 - ///
4.21 - /// \note You have to specify the graph for this constructor.
4.22 - Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
4.23 - UndirEdge(ue) { forward = (g.source(ue) == n); }
4.24 + public:
4.25 + Edge() {}
4.26
4.27 /// Invalid edge constructor
4.28 Edge(Invalid i) : UndirEdge(i), forward(true) {}
4.29 @@ -79,7 +67,7 @@
4.30 /// \brief Edge of opposite direction.
4.31 ///
4.32 /// Returns the Edge of opposite direction.
4.33 - Edge opposite(const Edge &e) const {
4.34 + Edge oppositeEdge(const Edge &e) const {
4.35 return Edge(e,!e.forward);
4.36 }
4.37
4.38 @@ -114,13 +102,6 @@
4.39 return _dirTarget(e);
4.40 }
4.41
4.42 - /// Returns whether the given directed edge is same orientation as the
4.43 - /// corresponding undirected edge.
4.44 - ///
4.45 - /// \todo reference to the corresponding point of the undirected graph
4.46 - /// concept. "What does the direction of an undirected edge mean?"
4.47 - bool forward(const Edge &e) const { return e.forward; }
4.48 -
4.49 Node oppositeNode(const Node &n, const UndirEdge &e) const {
4.50 if( n == Parent::source(e))
4.51 return Parent::target(e);
4.52 @@ -130,18 +111,32 @@
4.53 return INVALID;
4.54 }
4.55
4.56 - /// Directed edge from an undirected edge and a source node.
4.57 + /// \brief Directed edge from an undirected edge and a source node.
4.58 ///
4.59 /// Returns a (directed) Edge corresponding to the specified UndirEdge
4.60 /// and source Node.
4.61 ///
4.62 - ///\todo Do we need this?
4.63 + Edge direct(const UndirEdge &ue, const Node &s) const {
4.64 + return Edge(ue, s == source(ue));
4.65 + }
4.66 +
4.67 + /// \brief Directed edge from an undirected edge.
4.68 ///
4.69 - ///\todo Better name...
4.70 - Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
4.71 - return Edge(*this, ue, s);
4.72 + /// Returns a directed edge corresponding to the specified UndirEdge.
4.73 + /// If the given bool is true the given undirected edge and the
4.74 + /// returned edge have the same source node.
4.75 + Edge direct(const UndirEdge &ue, bool d) const {
4.76 + return Edge(ue, d);
4.77 }
4.78
4.79 + /// Returns whether the given directed edge is same orientation as the
4.80 + /// corresponding undirected edge.
4.81 + ///
4.82 + /// \todo reference to the corresponding point of the undirected graph
4.83 + /// concept. "What does the direction of an undirected edge mean?"
4.84 + bool direction(const Edge &e) const { return e.forward; }
4.85 +
4.86 +
4.87 using Parent::first;
4.88 void first(Edge &e) const {
4.89 Parent::first(e);
5.1 --- a/lemon/concept/graph.h Thu Aug 11 15:24:24 2005 +0000
5.2 +++ b/lemon/concept/graph.h Thu Aug 11 15:55:17 2005 +0000
5.3 @@ -479,25 +479,34 @@
5.4 /// \brief The base node of the iterator.
5.5 ///
5.6 /// Gives back the base node of the iterator.
5.7 + /// It is always the target of the pointed edge.
5.8 Node baseNode(const InEdgeIt&) const { return INVALID; }
5.9
5.10 /// \brief The running node of the iterator.
5.11 ///
5.12 /// Gives back the running node of the iterator.
5.13 + /// It is always the source of the pointed edge.
5.14 Node runningNode(const InEdgeIt&) const { return INVALID; }
5.15
5.16 /// \brief The base node of the iterator.
5.17 ///
5.18 /// Gives back the base node of the iterator.
5.19 + /// It is always the source of the pointed edge.
5.20 Node baseNode(const OutEdgeIt&) const { return INVALID; }
5.21
5.22 /// \brief The running node of the iterator.
5.23 ///
5.24 /// Gives back the running node of the iterator.
5.25 + /// It is always the target of the pointed edge.
5.26 Node runningNode(const OutEdgeIt&) const { return INVALID; }
5.27 - /// Read write map of the nodes to type \c T.
5.28
5.29 - /// \ingroup concept
5.30 + /// \brief The opposite node on the given edge.
5.31 + ///
5.32 + /// Gives back the opposite node on the given edge.
5.33 + Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
5.34 +
5.35 + /// \brief Read write map of the nodes to type \c T.
5.36 + ///
5.37 /// ReadWrite map of the nodes to type \c T.
5.38 /// \sa Reference
5.39 /// \warning Making maps that can handle bool type (NodeMap<bool>)
5.40 @@ -519,10 +528,9 @@
5.41 // \todo fix this concept
5.42 };
5.43
5.44 - /// Read write map of the edges to type \c T.
5.45 -
5.46 - /// \ingroup concept
5.47 - ///Reference map of the edges to type \c T.
5.48 + /// \brief Read write map of the edges to type \c T.
5.49 + ///
5.50 + /// Reference map of the edges to type \c T.
5.51 /// \sa Reference
5.52 /// \warning Making maps that can handle bool type (EdgeMap<bool>)
5.53 /// needs some extra attention!
5.54 @@ -610,67 +618,7 @@
5.55 struct Constraints : public _ErasableGraph::Constraints<_Graph> {};
5.56
5.57 };
5.58 -
5.59
5.60 - /************* New GraphBase stuff **************/
5.61 -
5.62 -
5.63 -// /// A minimal GraphBase concept
5.64 -
5.65 -// /// This class describes a minimal concept which can be extended to a
5.66 -// /// full-featured graph with \ref GraphFactory.
5.67 -// class GraphBase {
5.68 -// public:
5.69 -
5.70 -// GraphBase() {}
5.71 -
5.72 -// /// \bug Should we demand that Node and Edge be subclasses of the
5.73 -// /// Graph class???
5.74 -
5.75 -// typedef GraphItem<'n'> Node;
5.76 -// typedef GraphItem<'e'> Edge;
5.77 -
5.78 -// // class Node : public BaseGraphItem<'n'> {};
5.79 -// // class Edge : public BaseGraphItem<'e'> {};
5.80 -
5.81 -// // Graph operation
5.82 -// void firstNode(Node &n) const { }
5.83 -// void firstEdge(Edge &e) const { }
5.84 -
5.85 -// void firstOutEdge(Edge &e, Node) const { }
5.86 -// void firstInEdge(Edge &e, Node) const { }
5.87 -
5.88 -// void nextNode(Node &n) const { }
5.89 -// void nextEdge(Edge &e) const { }
5.90 -
5.91 -
5.92 -// // Question: isn't it reasonable if this methods have a Node
5.93 -// // parameter? Like this:
5.94 -// // Edge& nextOut(Edge &e, Node) const { return e; }
5.95 -// void nextOutEdge(Edge &e) const { }
5.96 -// void nextInEdge(Edge &e) const { }
5.97 -
5.98 -// Node target(Edge) const { return Node(); }
5.99 -// Node source(Edge) const { return Node(); }
5.100 -
5.101 -
5.102 -// // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
5.103 -// // concept?
5.104 -
5.105 -
5.106 -// // Maps.
5.107 -// //
5.108 -// // We need a special slimer concept which does not provide maps (it
5.109 -// // wouldn't be strictly slimer, cause for map-factory id() & friends
5.110 -// // a required...)
5.111 -
5.112 -// template<typename T>
5.113 -// class NodeMap : public GraphMap<GraphBase, Node, T> {};
5.114 -
5.115 -// template<typename T>
5.116 -// class EdgeMap : public GraphMap<GraphBase, Node, T> {};
5.117 -// };
5.118 -
5.119 // @}
5.120 } //namespace concept
5.121 } //namespace lemon
6.1 --- a/lemon/concept/graph_component.h Thu Aug 11 15:24:24 2005 +0000
6.2 +++ b/lemon/concept/graph_component.h Thu Aug 11 15:55:17 2005 +0000
6.3 @@ -678,23 +678,33 @@
6.4 /// \brief The base node of the iterator.
6.5 ///
6.6 /// Gives back the base node of the iterator.
6.7 + /// It is always the target of the pointed edge.
6.8 Node baseNode(const InEdgeIt&) const { return INVALID; }
6.9
6.10 /// \brief The running node of the iterator.
6.11 ///
6.12 /// Gives back the running node of the iterator.
6.13 + /// It is always the source of the pointed edge.
6.14 Node runningNode(const InEdgeIt&) const { return INVALID; }
6.15
6.16 /// \brief The base node of the iterator.
6.17 ///
6.18 /// Gives back the base node of the iterator.
6.19 + /// It is always the source of the pointed edge.
6.20 Node baseNode(const OutEdgeIt&) const { return INVALID; }
6.21
6.22 /// \brief The running node of the iterator.
6.23 ///
6.24 /// Gives back the running node of the iterator.
6.25 + /// It is always the target of the pointed edge.
6.26 Node runningNode(const OutEdgeIt&) const { return INVALID; }
6.27
6.28 + /// \brief The opposite node on the given edge.
6.29 + ///
6.30 + /// Gives back the opposite on the given edge.
6.31 + /// \todo It should not be here.
6.32 + Node oppositeNode(const Node&, const Edge&) const { return INVALID; }
6.33 +
6.34
6.35 template <typename _Graph>
6.36 struct Constraints {
6.37 @@ -707,7 +717,14 @@
6.38 typename _Graph::NodeIt >();
6.39 checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt>();
6.40 checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt>();
6.41 +
6.42 + typename _Graph::Node n;
6.43 + typename _Graph::Edge e;
6.44 + n = graph.oppositeNode(n, e);
6.45 }
6.46 +
6.47 + const _Graph& graph;
6.48 +
6.49 };
6.50 };
6.51
7.1 --- a/lemon/concept/undir_graph.h Thu Aug 11 15:24:24 2005 +0000
7.2 +++ b/lemon/concept/undir_graph.h Thu Aug 11 15:55:17 2005 +0000
7.3 @@ -119,7 +119,10 @@
7.4 n = graph.oppositeNode(n0, ue);
7.5
7.6 bool b;
7.7 - b = graph.forward(e);
7.8 + b = graph.direction(e);
7.9 + Edge e = graph.direct(UndirEdge(), true);
7.10 + e = graph.direct(UndirEdge(), n);
7.11 +
7.12 ignore_unused_variable_warning(b);
7.13 }
7.14
7.15 @@ -232,8 +235,12 @@
7.16 /// graphs (\ref lemon::concept::Graph "Graph Concept"). For
7.17 /// explanation of this and more see also the page \ref undir_graphs,
7.18 /// a tutorial about undirected graphs.
7.19 + ///
7.20 + /// You can assume that all undirected graph can be handled
7.21 + /// as a static directed graph. This way it is fully conform
7.22 + /// to the StaticGraph concept.
7.23
7.24 - class UndirGraph : public StaticGraph {
7.25 + class UndirGraph {
7.26 public:
7.27 ///\e
7.28
7.29 @@ -241,8 +248,105 @@
7.30 ///
7.31 typedef True UndirTag;
7.32
7.33 + /// The base type of node iterators,
7.34 + /// or in other words, the trivial node iterator.
7.35 +
7.36 + /// This is the base type of each node iterator,
7.37 + /// thus each kind of node iterator converts to this.
7.38 + /// More precisely each kind of node iterator should be inherited
7.39 + /// from the trivial node iterator.
7.40 + class Node {
7.41 + public:
7.42 + /// Default constructor
7.43 +
7.44 + /// @warning The default constructor sets the iterator
7.45 + /// to an undefined value.
7.46 + Node() { }
7.47 + /// Copy constructor.
7.48 +
7.49 + /// Copy constructor.
7.50 + ///
7.51 + Node(const Node&) { }
7.52 +
7.53 + /// Invalid constructor \& conversion.
7.54 +
7.55 + /// This constructor initializes the iterator to be invalid.
7.56 + /// \sa Invalid for more details.
7.57 + Node(Invalid) { }
7.58 + /// Equality operator
7.59 +
7.60 + /// Two iterators are equal if and only if they point to the
7.61 + /// same object or both are invalid.
7.62 + bool operator==(Node) const { return true; }
7.63 +
7.64 + /// Inequality operator
7.65 +
7.66 + /// \sa operator==(Node n)
7.67 + ///
7.68 + bool operator!=(Node) const { return true; }
7.69 +
7.70 + /// Artificial ordering operator.
7.71 +
7.72 + /// To allow the use of graph descriptors as key type in std::map or
7.73 + /// similar associative container we require this.
7.74 + ///
7.75 + /// \note This operator only have to define some strict ordering of
7.76 + /// the items; this order has nothing to do with the iteration
7.77 + /// ordering of the items.
7.78 + ///
7.79 + /// \bug This is a technical requirement. Do we really need this?
7.80 + bool operator<(Node) const { return false; }
7.81 +
7.82 + };
7.83 +
7.84 + /// This iterator goes through each node.
7.85 +
7.86 + /// This iterator goes through each node.
7.87 + /// Its usage is quite simple, for example you can count the number
7.88 + /// of nodes in graph \c g of type \c Graph like this:
7.89 + /// \code
7.90 + /// int count=0;
7.91 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
7.92 + /// \endcode
7.93 + class NodeIt : public Node {
7.94 + public:
7.95 + /// Default constructor
7.96 +
7.97 + /// @warning The default constructor sets the iterator
7.98 + /// to an undefined value.
7.99 + NodeIt() { }
7.100 + /// Copy constructor.
7.101 +
7.102 + /// Copy constructor.
7.103 + ///
7.104 + NodeIt(const NodeIt& n) : Node(n) { }
7.105 + /// Invalid constructor \& conversion.
7.106 +
7.107 + /// Initialize the iterator to be invalid.
7.108 + /// \sa Invalid for more details.
7.109 + NodeIt(Invalid) { }
7.110 + /// Sets the iterator to the first node.
7.111 +
7.112 + /// Sets the iterator to the first node of \c g.
7.113 + ///
7.114 + NodeIt(const UndirGraph&) { }
7.115 + /// Node -> NodeIt conversion.
7.116 +
7.117 + /// Sets the iterator to the node of \c the graph pointed by
7.118 + /// the trivial iterator.
7.119 + /// This feature necessitates that each time we
7.120 + /// iterate the edge-set, the iteration order is the same.
7.121 + NodeIt(const UndirGraph&, const Node&) { }
7.122 + /// Next node.
7.123 +
7.124 + /// Assign the iterator to the next node.
7.125 + ///
7.126 + NodeIt& operator++() { return *this; }
7.127 + };
7.128 +
7.129 +
7.130 /// The base type of the undirected edge iterators.
7.131 -
7.132 +
7.133 /// The base type of the undirected edge iterators.
7.134 ///
7.135 class UndirEdge {
7.136 @@ -257,11 +361,6 @@
7.137 /// Copy constructor.
7.138 ///
7.139 UndirEdge(const UndirEdge&) { }
7.140 - /// Edge -> UndirEdge conversion
7.141 -
7.142 - /// Edge -> UndirEdge conversion
7.143 - ///
7.144 - UndirEdge(const Edge&) { }
7.145 /// Initialize the iterator to be invalid.
7.146
7.147 /// Initialize the iterator to be invalid.
7.148 @@ -278,18 +377,24 @@
7.149 ///
7.150 bool operator!=(UndirEdge) const { return true; }
7.151
7.152 - ///\e
7.153 + /// Artificial ordering operator.
7.154 +
7.155 + /// To allow the use of graph descriptors as key type in std::map or
7.156 + /// similar associative container we require this.
7.157 + ///
7.158 + /// \note This operator only have to define some strict ordering of
7.159 + /// the items; this order has nothing to do with the iteration
7.160 + /// ordering of the items.
7.161 + ///
7.162 + /// \bug This is a technical requirement. Do we really need this?
7.163 + bool operator<(UndirEdge) const { return false; }
7.164 + };
7.165
7.166 - ///\todo Do we need this?
7.167 - ///
7.168 - bool operator<(const UndirEdge &that) const { return true; }
7.169 - };
7.170 -
7.171 /// This iterator goes through each undirected edge.
7.172
7.173 /// This iterator goes through each undirected edge of a graph.
7.174 /// Its usage is quite simple, for example you can count the number
7.175 - /// of edges in a graph \c g of type \c Graph as follows:
7.176 + /// of undirected edges in a graph \c g of type \c Graph as follows:
7.177 /// \code
7.178 /// int count=0;
7.179 /// for(Graph::UndirEdgeIt e(g); e!=INVALID; ++e) ++count;
7.180 @@ -297,12 +402,12 @@
7.181 class UndirEdgeIt : public UndirEdge {
7.182 public:
7.183 /// Default constructor
7.184 -
7.185 +
7.186 /// @warning The default constructor sets the iterator
7.187 /// to an undefined value.
7.188 UndirEdgeIt() { }
7.189 /// Copy constructor.
7.190 -
7.191 +
7.192 /// Copy constructor.
7.193 ///
7.194 UndirEdgeIt(const UndirEdgeIt& e) : UndirEdge(e) { }
7.195 @@ -311,24 +416,26 @@
7.196 /// Initialize the iterator to be invalid.
7.197 ///
7.198 UndirEdgeIt(Invalid) { }
7.199 - /// This constructor sets the iterator to the first edge.
7.200 + /// This constructor sets the iterator to the first undirected edge.
7.201
7.202 - /// This constructor sets the iterator to the first edge of \c g.
7.203 + /// This constructor sets the iterator to the first undirected edge.
7.204 UndirEdgeIt(const UndirGraph&) { }
7.205 /// UndirEdge -> UndirEdgeIt conversion
7.206
7.207 - /// Sets the iterator to the value of the trivial iterator \c e.
7.208 - /// This feature necessitates that each time we
7.209 - /// iterate the edge-set, the iteration order is the same.
7.210 + /// Sets the iterator to the value of the trivial iterator.
7.211 + /// This feature necessitates that each time we
7.212 + /// iterate the undirected edge-set, the iteration order is the
7.213 + /// same.
7.214 UndirEdgeIt(const UndirGraph&, const UndirEdge&) { }
7.215 - ///Next edge
7.216 + /// Next undirected edge
7.217
7.218 - /// Assign the iterator to the next edge.
7.219 + /// Assign the iterator to the next undirected edge.
7.220 UndirEdgeIt& operator++() { return *this; }
7.221 };
7.222
7.223 - /// This iterator goes trough the incident undirected edges of a node.
7.224 -
7.225 + /// \brief This iterator goes trough the incident undirected
7.226 + /// edges of a node.
7.227 + ///
7.228 /// This iterator goes trough the incident undirected edges
7.229 /// of a certain node
7.230 /// of a graph.
7.231 @@ -375,6 +482,237 @@
7.232 IncEdgeIt& operator++() { return *this; }
7.233 };
7.234
7.235 + /// The directed edge type.
7.236 +
7.237 + /// The directed edge type. It can be converted to the
7.238 + /// undirected edge.
7.239 + class Edge : public UndirEdge {
7.240 + public:
7.241 + /// Default constructor
7.242 +
7.243 + /// @warning The default constructor sets the iterator
7.244 + /// to an undefined value.
7.245 + Edge() { }
7.246 + /// Copy constructor.
7.247 +
7.248 + /// Copy constructor.
7.249 + ///
7.250 + Edge(const Edge& e) : UndirEdge(e) { }
7.251 + /// Initialize the iterator to be invalid.
7.252 +
7.253 + /// Initialize the iterator to be invalid.
7.254 + ///
7.255 + Edge(Invalid) { }
7.256 + /// Equality operator
7.257 +
7.258 + /// Two iterators are equal if and only if they point to the
7.259 + /// same object or both are invalid.
7.260 + bool operator==(Edge) const { return true; }
7.261 + /// Inequality operator
7.262 +
7.263 + /// \sa operator==(Edge n)
7.264 + ///
7.265 + bool operator!=(Edge) const { return true; }
7.266 +
7.267 + /// Artificial ordering operator.
7.268 +
7.269 + /// To allow the use of graph descriptors as key type in std::map or
7.270 + /// similar associative container we require this.
7.271 + ///
7.272 + /// \note This operator only have to define some strict ordering of
7.273 + /// the items; this order has nothing to do with the iteration
7.274 + /// ordering of the items.
7.275 + ///
7.276 + /// \bug This is a technical requirement. Do we really need this?
7.277 + bool operator<(Edge) const { return false; }
7.278 +
7.279 + };
7.280 + /// This iterator goes through each directed edge.
7.281 +
7.282 + /// This iterator goes through each edge of a graph.
7.283 + /// Its usage is quite simple, for example you can count the number
7.284 + /// of edges in a graph \c g of type \c Graph as follows:
7.285 + /// \code
7.286 + /// int count=0;
7.287 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
7.288 + /// \endcode
7.289 + class EdgeIt : public Edge {
7.290 + public:
7.291 + /// Default constructor
7.292 +
7.293 + /// @warning The default constructor sets the iterator
7.294 + /// to an undefined value.
7.295 + EdgeIt() { }
7.296 + /// Copy constructor.
7.297 +
7.298 + /// Copy constructor.
7.299 + ///
7.300 + EdgeIt(const EdgeIt& e) : Edge(e) { }
7.301 + /// Initialize the iterator to be invalid.
7.302 +
7.303 + /// Initialize the iterator to be invalid.
7.304 + ///
7.305 + EdgeIt(Invalid) { }
7.306 + /// This constructor sets the iterator to the first edge.
7.307 +
7.308 + /// This constructor sets the iterator to the first edge of \c g.
7.309 + ///@param g the graph
7.310 + EdgeIt(const UndirGraph&) { }
7.311 + /// Edge -> EdgeIt conversion
7.312 +
7.313 + /// Sets the iterator to the value of the trivial iterator \c e.
7.314 + /// This feature necessitates that each time we
7.315 + /// iterate the edge-set, the iteration order is the same.
7.316 + EdgeIt(const UndirGraph&, const Edge&) { }
7.317 + ///Next edge
7.318 +
7.319 + /// Assign the iterator to the next edge.
7.320 + EdgeIt& operator++() { return *this; }
7.321 + };
7.322 +
7.323 + /// This iterator goes trough the outgoing directed edges of a node.
7.324 +
7.325 + /// This iterator goes trough the \e outgoing edges of a certain node
7.326 + /// of a graph.
7.327 + /// Its usage is quite simple, for example you can count the number
7.328 + /// of outgoing edges of a node \c n
7.329 + /// in graph \c g of type \c Graph as follows.
7.330 + /// \code
7.331 + /// int count=0;
7.332 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
7.333 + /// \endcode
7.334 +
7.335 + class OutEdgeIt : public Edge {
7.336 + public:
7.337 + /// Default constructor
7.338 +
7.339 + /// @warning The default constructor sets the iterator
7.340 + /// to an undefined value.
7.341 + OutEdgeIt() { }
7.342 + /// Copy constructor.
7.343 +
7.344 + /// Copy constructor.
7.345 + ///
7.346 + OutEdgeIt(const OutEdgeIt& e) : Edge(e) { }
7.347 + /// Initialize the iterator to be invalid.
7.348 +
7.349 + /// Initialize the iterator to be invalid.
7.350 + ///
7.351 + OutEdgeIt(Invalid) { }
7.352 + /// This constructor sets the iterator to the first outgoing edge.
7.353 +
7.354 + /// This constructor sets the iterator to the first outgoing edge of
7.355 + /// the node.
7.356 + ///@param n the node
7.357 + ///@param g the graph
7.358 + OutEdgeIt(const UndirGraph&, const Node&) { }
7.359 + /// Edge -> OutEdgeIt conversion
7.360 +
7.361 + /// Sets the iterator to the value of the trivial iterator.
7.362 + /// This feature necessitates that each time we
7.363 + /// iterate the edge-set, the iteration order is the same.
7.364 + OutEdgeIt(const UndirGraph&, const Edge&) { }
7.365 + ///Next outgoing edge
7.366 +
7.367 + /// Assign the iterator to the next
7.368 + /// outgoing edge of the corresponding node.
7.369 + OutEdgeIt& operator++() { return *this; }
7.370 + };
7.371 +
7.372 + /// This iterator goes trough the incoming directed edges of a node.
7.373 +
7.374 + /// This iterator goes trough the \e incoming edges of a certain node
7.375 + /// of a graph.
7.376 + /// Its usage is quite simple, for example you can count the number
7.377 + /// of outgoing edges of a node \c n
7.378 + /// in graph \c g of type \c Graph as follows.
7.379 + /// \code
7.380 + /// int count=0;
7.381 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
7.382 + /// \endcode
7.383 +
7.384 + class InEdgeIt : public Edge {
7.385 + public:
7.386 + /// Default constructor
7.387 +
7.388 + /// @warning The default constructor sets the iterator
7.389 + /// to an undefined value.
7.390 + InEdgeIt() { }
7.391 + /// Copy constructor.
7.392 +
7.393 + /// Copy constructor.
7.394 + ///
7.395 + InEdgeIt(const InEdgeIt& e) : Edge(e) { }
7.396 + /// Initialize the iterator to be invalid.
7.397 +
7.398 + /// Initialize the iterator to be invalid.
7.399 + ///
7.400 + InEdgeIt(Invalid) { }
7.401 + /// This constructor sets the iterator to first incoming edge.
7.402 +
7.403 + /// This constructor set the iterator to the first incoming edge of
7.404 + /// the node.
7.405 + ///@param n the node
7.406 + ///@param g the graph
7.407 + InEdgeIt(const UndirGraph&, const Node&) { }
7.408 + /// Edge -> InEdgeIt conversion
7.409 +
7.410 + /// Sets the iterator to the value of the trivial iterator \c e.
7.411 + /// This feature necessitates that each time we
7.412 + /// iterate the edge-set, the iteration order is the same.
7.413 + InEdgeIt(const UndirGraph&, const Edge&) { }
7.414 + /// Next incoming edge
7.415 +
7.416 + /// Assign the iterator to the next inedge of the corresponding node.
7.417 + ///
7.418 + InEdgeIt& operator++() { return *this; }
7.419 + };
7.420 +
7.421 + /// \brief Read write map of the nodes to type \c T.
7.422 + ///
7.423 + /// ReadWrite map of the nodes to type \c T.
7.424 + /// \sa Reference
7.425 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
7.426 + /// needs some extra attention!
7.427 + template<class T>
7.428 + class NodeMap : public ReadWriteMap< Node, T >
7.429 + {
7.430 + public:
7.431 +
7.432 + ///\e
7.433 + NodeMap(const UndirGraph&) { }
7.434 + ///\e
7.435 + NodeMap(const UndirGraph&, T) { }
7.436 +
7.437 + ///Copy constructor
7.438 + NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
7.439 + ///Assignment operator
7.440 + NodeMap& operator=(const NodeMap&) { return *this; }
7.441 + // \todo fix this concept
7.442 + };
7.443 +
7.444 + /// \brief Read write map of the directed edges to type \c T.
7.445 + ///
7.446 + /// Reference map of the directed edges to type \c T.
7.447 + /// \sa Reference
7.448 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
7.449 + /// needs some extra attention!
7.450 + template<class T>
7.451 + class EdgeMap : public ReadWriteMap<Edge,T>
7.452 + {
7.453 + public:
7.454 +
7.455 + ///\e
7.456 + EdgeMap(const UndirGraph&) { }
7.457 + ///\e
7.458 + EdgeMap(const UndirGraph&, T) { }
7.459 + ///Copy constructor
7.460 + EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) { }
7.461 + ///Assignment operator
7.462 + EdgeMap& operator=(const EdgeMap&) { return *this; }
7.463 + // \todo fix this concept
7.464 + };
7.465 +
7.466 /// Read write map of the undirected edges to type \c T.
7.467
7.468 /// Reference map of the edges to type \c T.
7.469 @@ -391,122 +729,140 @@
7.470 ///\e
7.471 UndirEdgeMap(const UndirGraph&, T) { }
7.472 ///Copy constructor
7.473 - UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) { }
7.474 + UndirEdgeMap(const UndirEdgeMap& em) : ReadWriteMap<UndirEdge,T>(em) {}
7.475 ///Assignment operator
7.476 UndirEdgeMap &operator=(const UndirEdgeMap&) { return *this; }
7.477 // \todo fix this concept
7.478 };
7.479
7.480 - /// Is the Edge oriented "forward"?
7.481 + /// \brief Direct the given undirected edge.
7.482 + ///
7.483 + /// Direct the given undirected edge. The returned edge source
7.484 + /// will be the given edge.
7.485 + Edge direct(const UndirEdge&, const Node&) const {
7.486 + return INVALID;
7.487 + }
7.488
7.489 + /// \brief Direct the given undirected edge.
7.490 + ///
7.491 + /// Direct the given undirected edge. The returned edge source
7.492 + /// will be the source of the undirected edge if the given bool
7.493 + /// is true.
7.494 + Edge direct(const UndirEdge&, bool) const {
7.495 + return INVALID;
7.496 + }
7.497 +
7.498 + /// \brief Returns true if the edge has default orientation.
7.499 + ///
7.500 /// Returns whether the given directed edge is same orientation as
7.501 /// the corresponding undirected edge.
7.502 + bool direction(Edge) const { return true; }
7.503 +
7.504 + /// \brief Returns the opposite directed edge.
7.505 ///
7.506 - /// \todo "What does the direction of an undirected edge mean?"
7.507 - bool forward(Edge) const { return true; }
7.508 + /// Returns the opposite directed edge.
7.509 + Edge oppositeEdge(Edge) const { return INVALID; }
7.510
7.511 - /// Opposite node on an edge
7.512 -
7.513 + /// \brief Opposite node on an edge
7.514 + ///
7.515 /// \return the opposite of the given Node on the given Edge
7.516 - ///
7.517 - /// \todo What should we do if given Node and Edge are not incident?
7.518 Node oppositeNode(Node, UndirEdge) const { return INVALID; }
7.519
7.520 - /// First node of the undirected edge.
7.521 -
7.522 + /// \brief First node of the undirected edge.
7.523 + ///
7.524 /// \return the first node of the given UndirEdge.
7.525 ///
7.526 /// Naturally undirectected edges don't have direction and thus
7.527 /// don't have source and target node. But we use these two methods
7.528 /// to query the two endnodes of the edge. The direction of the edge
7.529 /// which arises this way is called the inherent direction of the
7.530 - /// undirected edge, and is used to define the "forward" direction
7.531 + /// undirected edge, and is used to define the "default" direction
7.532 /// of the directed versions of the edges.
7.533 - /// \sa forward
7.534 + /// \sa direction
7.535 Node source(UndirEdge) const { return INVALID; }
7.536
7.537 - /// Second node of the undirected edge.
7.538 + /// \brief Second node of the undirected edge.
7.539 Node target(UndirEdge) const { return INVALID; }
7.540
7.541 - /// Source node of the directed edge.
7.542 + /// \brief Source node of the directed edge.
7.543 Node source(Edge) const { return INVALID; }
7.544
7.545 - /// Target node of the directed edge.
7.546 + /// \brief Target node of the directed edge.
7.547 Node target(Edge) const { return INVALID; }
7.548
7.549 - /// First node of the graph
7.550 -
7.551 + /// \brief First node of the graph
7.552 + ///
7.553 /// \note This method is part of so called \ref
7.554 /// developpers_interface "Developpers' interface", so it shouldn't
7.555 /// be used in an end-user program.
7.556 void first(Node&) const {}
7.557 - /// Next node of the graph
7.558 -
7.559 + /// \brief Next node of the graph
7.560 + ///
7.561 /// \note This method is part of so called \ref
7.562 /// developpers_interface "Developpers' interface", so it shouldn't
7.563 /// be used in an end-user program.
7.564 void next(Node&) const {}
7.565
7.566 - /// First undirected edge of the graph
7.567 -
7.568 + /// \brief First undirected edge of the graph
7.569 + ///
7.570 /// \note This method is part of so called \ref
7.571 /// developpers_interface "Developpers' interface", so it shouldn't
7.572 /// be used in an end-user program.
7.573 void first(UndirEdge&) const {}
7.574 - /// Next undirected edge of the graph
7.575 -
7.576 + /// \brief Next undirected edge of the graph
7.577 + ///
7.578 /// \note This method is part of so called \ref
7.579 /// developpers_interface "Developpers' interface", so it shouldn't
7.580 /// be used in an end-user program.
7.581 void next(UndirEdge&) const {}
7.582
7.583 - /// First directed edge of the graph
7.584 -
7.585 + /// \brief First directed edge of the graph
7.586 + ///
7.587 /// \note This method is part of so called \ref
7.588 /// developpers_interface "Developpers' interface", so it shouldn't
7.589 /// be used in an end-user program.
7.590 void first(Edge&) const {}
7.591 - /// Next directed edge of the graph
7.592 -
7.593 + /// \brief Next directed edge of the graph
7.594 + ///
7.595 /// \note This method is part of so called \ref
7.596 /// developpers_interface "Developpers' interface", so it shouldn't
7.597 /// be used in an end-user program.
7.598 void next(Edge&) const {}
7.599
7.600 - /// First outgoing edge from a given node
7.601 -
7.602 + /// \brief First outgoing edge from a given node
7.603 + ///
7.604 /// \note This method is part of so called \ref
7.605 /// developpers_interface "Developpers' interface", so it shouldn't
7.606 /// be used in an end-user program.
7.607 void firstOut(Edge&, Node) const {}
7.608 - /// Next outgoing edge to a node
7.609 -
7.610 + /// \brief Next outgoing edge to a node
7.611 + ///
7.612 /// \note This method is part of so called \ref
7.613 /// developpers_interface "Developpers' interface", so it shouldn't
7.614 /// be used in an end-user program.
7.615 void nextOut(Edge&) const {}
7.616
7.617 - /// First incoming edge to a given node
7.618 -
7.619 + /// \brief First incoming edge to a given node
7.620 + ///
7.621 /// \note This method is part of so called \ref
7.622 /// developpers_interface "Developpers' interface", so it shouldn't
7.623 /// be used in an end-user program.
7.624 void firstIn(Edge&, Node) const {}
7.625 - /// Next incoming edge to a node
7.626 -
7.627 + /// \brief Next incoming edge to a node
7.628 + ///
7.629 /// \note This method is part of so called \ref
7.630 /// developpers_interface "Developpers' interface", so it shouldn't
7.631 /// be used in an end-user program.
7.632 void nextIn(Edge&) const {}
7.633
7.634
7.635 - /// Base node of the iterator
7.636 + /// \brief Base node of the iterator
7.637 ///
7.638 /// Returns the base node (the source in this case) of the iterator
7.639 Node baseNode(OutEdgeIt e) const {
7.640 return source(e);
7.641 }
7.642 - /// Running node of the iterator
7.643 + /// \brief Running node of the iterator
7.644 ///
7.645 /// Returns the running node (the target in this case) of the
7.646 /// iterator
7.647 @@ -514,13 +870,13 @@
7.648 return target(e);
7.649 }
7.650
7.651 - /// Base node of the iterator
7.652 + /// \brief Base node of the iterator
7.653 ///
7.654 /// Returns the base node (the target in this case) of the iterator
7.655 Node baseNode(InEdgeIt e) const {
7.656 return target(e);
7.657 }
7.658 - /// Running node of the iterator
7.659 + /// \brief Running node of the iterator
7.660 ///
7.661 /// Returns the running node (the source in this case) of the
7.662 /// iterator
7.663 @@ -528,20 +884,20 @@
7.664 return source(e);
7.665 }
7.666
7.667 - /// Base node of the iterator
7.668 + /// \brief Base node of the iterator
7.669 ///
7.670 /// Returns the base node of the iterator
7.671 Node baseNode(IncEdgeIt) const {
7.672 return INVALID;
7.673 }
7.674 - /// Running node of the iterator
7.675 +
7.676 + /// \brief Running node of the iterator
7.677 ///
7.678 /// Returns the running node of the iterator
7.679 Node runningNode(IncEdgeIt) const {
7.680 return INVALID;
7.681 }
7.682
7.683 -
7.684 template <typename Graph>
7.685 struct Constraints {
7.686 void constraints() {
7.687 @@ -553,8 +909,30 @@
7.688
7.689 };
7.690
7.691 + /// \brief An empty non-static undirected graph class.
7.692 + ///
7.693 + /// This class provides everything that \ref UndirGraph does.
7.694 + /// Additionally it enables building graphs from scratch.
7.695 class ExtendableUndirGraph : public UndirGraph {
7.696 public:
7.697 +
7.698 + /// \brief Add a new node to the graph.
7.699 + ///
7.700 + /// Add a new node to the graph.
7.701 + /// \return the new node.
7.702 + Node addNode();
7.703 +
7.704 + /// \brief Add a new undirected edge to the graph.
7.705 + ///
7.706 + /// Add a new undirected edge to the graph.
7.707 + /// \return the new edge.
7.708 + UndirEdge addEdge(const Node& from, const Node& to);
7.709 +
7.710 + /// \brief Resets the graph.
7.711 + ///
7.712 + /// This function deletes all undirected edges and nodes of the graph.
7.713 + /// It also frees the memory allocated to store them.
7.714 + void clear() { }
7.715
7.716 template <typename Graph>
7.717 struct Constraints {
7.718 @@ -571,9 +949,24 @@
7.719
7.720 };
7.721
7.722 + /// \brief An empty erasable undirected graph class.
7.723 + ///
7.724 + /// This class is an extension of \ref ExtendableUndirGraph. It makes it
7.725 + /// possible to erase undirected edges or nodes.
7.726 class ErasableUndirGraph : public ExtendableUndirGraph {
7.727 public:
7.728
7.729 + /// \brief Deletes a node.
7.730 + ///
7.731 + /// Deletes a node.
7.732 + ///
7.733 + void erase(Node) { }
7.734 + /// \brief Deletes an undirected edge.
7.735 + ///
7.736 + /// Deletes an undirected edge.
7.737 + ///
7.738 + void erase(UndirEdge) { }
7.739 +
7.740 template <typename Graph>
7.741 struct Constraints {
7.742 void constraints() {
8.1 --- a/lemon/graph_adaptor.h Thu Aug 11 15:24:24 2005 +0000
8.2 +++ b/lemon/graph_adaptor.h Thu Aug 11 15:55:17 2005 +0000
8.3 @@ -105,13 +105,12 @@
8.4
8.5 void clear() const { graph->clear(); }
8.6
8.7 - bool forward(const Edge& e) const { return graph->forward(e); }
8.8 - bool backward(const Edge& e) const { return graph->backward(e); }
8.9 -
8.10 int id(const Node& v) const { return graph->id(v); }
8.11 int id(const Edge& e) const { return graph->id(e); }
8.12
8.13 - Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
8.14 + Edge oppositeNode(const Edge& e) const {
8.15 + return Edge(graph->opposite(e));
8.16 + }
8.17
8.18 template <typename _Value>
8.19 class NodeMap : public _Graph::template NodeMap<_Value> {
8.20 @@ -608,14 +607,14 @@
8.21 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
8.22
8.23 void set(Edge e, T a) {
8.24 - if (g->forward(e))
8.25 + if (g->direction(e))
8.26 forward_map.set(e, a);
8.27 else
8.28 backward_map.set(e, a);
8.29 }
8.30
8.31 T operator[](Edge e) const {
8.32 - if (g->forward(e))
8.33 + if (g->direction(e))
8.34 return forward_map[e];
8.35 else
8.36 return backward_map[e];
9.1 --- a/lemon/graph_utils.h Thu Aug 11 15:24:24 2005 +0000
9.2 +++ b/lemon/graph_utils.h Thu Aug 11 15:55:17 2005 +0000
9.3 @@ -995,7 +995,7 @@
9.4 /// \param key An undirected edge
9.5 /// \return The "forward" directed edge view of undirected edge
9.6 Value operator[](const Key& key) const {
9.7 - return graph.edgeWithSource(key, graph.source(key));
9.8 + return graph.direct(key, true);
9.9 }
9.10
9.11 private:
9.12 @@ -1035,7 +1035,7 @@
9.13 /// \param key An undirected edge
9.14 /// \return The "backward" directed edge view of undirected edge
9.15 Value operator[](const Key& key) const {
9.16 - return graph.edgeWithSource(key, graph.target(key));
9.17 + return graph.direct(key, false);
9.18 }
9.19
9.20 private:
10.1 --- a/lemon/lemon_reader.h Thu Aug 11 15:24:24 2005 +0000
10.2 +++ b/lemon/lemon_reader.h Thu Aug 11 15:55:17 2005 +0000
10.3 @@ -1322,9 +1322,9 @@
10.4 is >> c;
10.5 UndirEdge undirEdge = inverter->read(is);
10.6 if (c == '+') {
10.7 - edge = graph.edgeWithSource(undirEdge, graph.source(undirEdge));
10.8 + edge = graph.direct(undirEdge, true);
10.9 } else if (c == '-') {
10.10 - edge = graph.edgeWithSource(undirEdge, graph.target(undirEdge));
10.11 + edge = graph.direct(undirEdge, false);
10.12 } else {
10.13 throw DataFormatError("Wrong id format for edge "
10.14 "in undirected edgeset");