1.1 --- a/lemon/bits/iterable_graph_extender.h Wed Oct 05 13:15:47 2005 +0000
1.2 +++ b/lemon/bits/iterable_graph_extender.h Wed Oct 05 13:17:42 2005 +0000
1.3 @@ -216,30 +216,25 @@
1.4
1.5 class IncEdgeIt : public Parent::UndirEdge {
1.6 const Graph* graph;
1.7 - bool forward;
1.8 + bool direction;
1.9 friend class IterableUndirGraphExtender;
1.10 - template <typename G>
1.11 - friend class UndirGraphExtender;
1.12 public:
1.13
1.14 IncEdgeIt() { }
1.15
1.16 - IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
1.17 + IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
1.18
1.19 - IncEdgeIt(const Graph& _graph, const Node &n)
1.20 - : graph(&_graph)
1.21 - {
1.22 - _graph._dirFirstOut(*this, n);
1.23 + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1.24 + _graph.firstInc(*this, direction, n);
1.25 }
1.26
1.27 IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
1.28 - : graph(&_graph), UndirEdge(ue)
1.29 - {
1.30 - forward = (_graph.source(ue) == n);
1.31 + : graph(&_graph), UndirEdge(ue) {
1.32 + direction = (_graph.source(ue) == n);
1.33 }
1.34
1.35 IncEdgeIt& operator++() {
1.36 - graph->_dirNextOut(*this);
1.37 + graph->nextInc(*this, direction);
1.38 return *this;
1.39 }
1.40 };
1.41 @@ -251,13 +246,13 @@
1.42 ///
1.43 /// Returns the base node of the iterator
1.44 Node baseNode(const IncEdgeIt &e) const {
1.45 - return _dirSource(e);
1.46 + return e.direction ? source(e) : target(e);
1.47 }
1.48 /// Running node of the iterator
1.49 ///
1.50 /// Returns the running node of the iterator
1.51 Node runningNode(const IncEdgeIt &e) const {
1.52 - return _dirTarget(e);
1.53 + return e.direction ? target(e) : source(e);
1.54 }
1.55
1.56 /// \brief The opposite node on the given undirected edge.
2.1 --- a/lemon/bits/undir_graph_extender.h Wed Oct 05 13:15:47 2005 +0000
2.2 +++ b/lemon/bits/undir_graph_extender.h Wed Oct 05 13:17:42 2005 +0000
2.3 @@ -71,18 +71,6 @@
2.4 return Edge(e,!e.forward);
2.5 }
2.6
2.7 - protected:
2.8 -
2.9 - template <typename E>
2.10 - Node _dirSource(const E &e) const {
2.11 - return e.forward ? Parent::source(e) : Parent::target(e);
2.12 - }
2.13 -
2.14 - template <typename E>
2.15 - Node _dirTarget(const E &e) const {
2.16 - return e.forward ? Parent::target(e) : Parent::source(e);
2.17 - }
2.18 -
2.19 public:
2.20 /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
2.21 /// or something???
2.22 @@ -90,7 +78,7 @@
2.23
2.24 /// Source of the given Edge.
2.25 Node source(const Edge &e) const {
2.26 - return _dirSource(e);
2.27 + return e.forward ? Parent::source(e) : Parent::target(e);
2.28 }
2.29
2.30 /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
2.31 @@ -99,7 +87,7 @@
2.32
2.33 /// Target of the given Edge.
2.34 Node target(const Edge &e) const {
2.35 - return _dirTarget(e);
2.36 + return e.forward ? Parent::target(e) : Parent::source(e);
2.37 }
2.38
2.39 Node oppositeNode(const Node &n, const UndirEdge &e) const {
2.40 @@ -154,11 +142,9 @@
2.41 }
2.42 }
2.43
2.44 -
2.45 - protected:
2.46 + public:
2.47
2.48 - template <typename E>
2.49 - void _dirFirstOut(E &e, const Node &n) const {
2.50 + void firstOut(Edge &e, const Node &n) const {
2.51 Parent::firstIn(e,n);
2.52 if( UndirEdge(e) != INVALID ) {
2.53 e.forward = false;
2.54 @@ -168,20 +154,7 @@
2.55 e.forward = true;
2.56 }
2.57 }
2.58 - template <typename E>
2.59 - void _dirFirstIn(E &e, const Node &n) const {
2.60 - Parent::firstOut(e,n);
2.61 - if( UndirEdge(e) != INVALID ) {
2.62 - e.forward = false;
2.63 - }
2.64 - else {
2.65 - Parent::firstIn(e,n);
2.66 - e.forward = true;
2.67 - }
2.68 - }
2.69 -
2.70 - template <typename E>
2.71 - void _dirNextOut(E &e) const {
2.72 + void nextOut(Edge &e) const {
2.73 if( ! e.forward ) {
2.74 Node n = Parent::target(e);
2.75 Parent::nextIn(e);
2.76 @@ -194,8 +167,18 @@
2.77 Parent::nextOut(e);
2.78 }
2.79 }
2.80 - template <typename E>
2.81 - void _dirNextIn(E &e) const {
2.82 +
2.83 + void firstIn(Edge &e, const Node &n) const {
2.84 + Parent::firstOut(e,n);
2.85 + if( UndirEdge(e) != INVALID ) {
2.86 + e.forward = false;
2.87 + }
2.88 + else {
2.89 + Parent::firstIn(e,n);
2.90 + e.forward = true;
2.91 + }
2.92 + }
2.93 + void nextIn(Edge &e) const {
2.94 if( ! e.forward ) {
2.95 Node n = Parent::source(e);
2.96 Parent::nextOut(e);
2.97 @@ -209,20 +192,38 @@
2.98 }
2.99 }
2.100
2.101 - public:
2.102 -
2.103 - void firstOut(Edge &e, const Node &n) const {
2.104 - _dirFirstOut(e, n);
2.105 + void firstInc(UndirEdge &e, const Node &n) const {
2.106 + Parent::firstOut(e, n);
2.107 + if (e != INVALID) return;
2.108 + Parent::firstIn(e, n);
2.109 }
2.110 - void firstIn(Edge &e, const Node &n) const {
2.111 - _dirFirstIn(e, n);
2.112 + void nextInc(UndirEdge &e, const Node &n) const {
2.113 + if (Parent::source(e) == n) {
2.114 + Parent::nextOut(e);
2.115 + if (e != INVALID) return;
2.116 + Parent::firstIn(e, n);
2.117 + } else {
2.118 + Parent::nextIn(e);
2.119 + }
2.120 }
2.121
2.122 - void nextOut(Edge &e) const {
2.123 - _dirNextOut(e);
2.124 + void firstInc(UndirEdge &e, bool &d, const Node &n) const {
2.125 + d = true;
2.126 + Parent::firstOut(e, n);
2.127 + if (e != INVALID) return;
2.128 + d = false;
2.129 + Parent::firstIn(e, n);
2.130 }
2.131 - void nextIn(Edge &e) const {
2.132 - _dirNextIn(e);
2.133 + void nextInc(UndirEdge &e, bool &d) const {
2.134 + if (d) {
2.135 + Node s = Parent::source(e);
2.136 + Parent::nextOut(e);
2.137 + if (e != INVALID) return;
2.138 + d = false;
2.139 + Parent::firstIn(e, s);
2.140 + } else {
2.141 + Parent::nextIn(e);
2.142 + }
2.143 }
2.144
2.145 // Miscellaneous stuff:
2.146 @@ -262,10 +263,47 @@
2.147 int edgeNum() const {
2.148 return 2 * Parent::edgeNum();
2.149 }
2.150 +
2.151 int undirEdgeNum() const {
2.152 return Parent::edgeNum();
2.153 }
2.154
2.155 + Edge findEdge(Node source, Node target, Edge prev) const {
2.156 + if (prev == INVALID) {
2.157 + UndirEdge edge = Parent::findEdge(source, target);
2.158 + if (edge != INVALID) return direct(edge, true);
2.159 + edge = Parent::findEdge(target, source);
2.160 + if (edge != INVALID) return direct(edge, false);
2.161 + } else if (direction(prev)) {
2.162 + UndirEdge edge = Parent::findEdge(source, target, prev);
2.163 + if (edge != INVALID) return direct(edge, true);
2.164 + edge = Parent::findEdge(target, source);
2.165 + if (edge != INVALID) return direct(edge, false);
2.166 + } else {
2.167 + UndirEdge edge = Parent::findEdge(target, source, prev);
2.168 + if (edge != INVALID) return direct(edge, false);
2.169 + }
2.170 + return INVALID;
2.171 + }
2.172 +
2.173 + UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
2.174 + if (prev == INVALID) {
2.175 + UndirEdge edge = Parent::findEdge(source, target);
2.176 + if (edge != INVALID) return edge;
2.177 + edge = Parent::findEdge(target, source);
2.178 + if (edge != INVALID) return edge;
2.179 + } else if (Parent::source(prev) == source) {
2.180 + UndirEdge edge = Parent::findEdge(source, target, prev);
2.181 + if (edge != INVALID) return edge;
2.182 + edge = Parent::findEdge(target, source);
2.183 + if (edge != INVALID) return edge;
2.184 + } else {
2.185 + UndirEdge edge = Parent::findEdge(target, source, prev);
2.186 + if (edge != INVALID) return edge;
2.187 + }
2.188 + return INVALID;
2.189 + }
2.190 +
2.191 };
2.192
2.193 }
3.1 --- a/lemon/graph_utils.h Wed Oct 05 13:15:47 2005 +0000
3.2 +++ b/lemon/graph_utils.h Wed Oct 05 13:17:42 2005 +0000
3.3 @@ -160,9 +160,9 @@
3.4 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
3.5 }
3.6
3.7 - /// \brief Function to count the number of the in-edges to node \c n.
3.8 + /// \brief Function to count the number of the inc-edges to node \c n.
3.9 ///
3.10 - /// This function counts the number of the in-edges to node \c n
3.11 + /// This function counts the number of the inc-edges to node \c n
3.12 /// in the graph.
3.13 template <typename Graph>
3.14 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
3.15 @@ -214,7 +214,6 @@
3.16 /// \endcode
3.17 // /// \todo We may want to use the "GraphBase"
3.18 // /// interface here...
3.19 - // /// It would not work with the undirected graphs.
3.20 template <typename Graph>
3.21 inline typename Graph::Edge findEdge(const Graph &g,
3.22 typename Graph::Node u,
3.23 @@ -271,6 +270,110 @@
3.24 const Graph& graph;
3.25 };
3.26
3.27 + template <typename Graph>
3.28 + inline
3.29 + typename enable_if<
3.30 + typename Graph::FindEdgeTag,
3.31 + typename Graph::UndirEdge>::type
3.32 + _findUndirEdge(const Graph &g,
3.33 + typename Graph::Node u, typename Graph::Node v,
3.34 + typename Graph::UndirEdge prev = INVALID) {
3.35 + return g.findUndirEdge(u, v, prev);
3.36 + }
3.37 +
3.38 + template <typename Graph>
3.39 + inline typename Graph::UndirEdge
3.40 + _findUndirEdge(Wrap<Graph> w,
3.41 + typename Graph::Node u,
3.42 + typename Graph::Node v,
3.43 + typename Graph::UndirEdge prev = INVALID) {
3.44 + const Graph& g = w.value;
3.45 + if (prev == INVALID) {
3.46 + typename Graph::OutEdgeIt e(g, u);
3.47 + while (e != INVALID && g.target(e) != v) ++e;
3.48 + return e;
3.49 + } else {
3.50 + typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
3.51 + while (e != INVALID && g.target(e) != v) ++e;
3.52 + return e;
3.53 + }
3.54 + }
3.55 +
3.56 + /// \brief Finds an undir edge between two nodes of a graph.
3.57 + ///
3.58 + /// Finds an undir edge from node \c u to node \c v in graph \c g.
3.59 + ///
3.60 + /// If \c prev is \ref INVALID (this is the default value), then
3.61 + /// it finds the first edge from \c u to \c v. Otherwise it looks for
3.62 + /// the next edge from \c u to \c v after \c prev.
3.63 + /// \return The found edge or \ref INVALID if there is no such an edge.
3.64 + ///
3.65 + /// Thus you can iterate through each edge from \c u to \c v as it follows.
3.66 + /// \code
3.67 + /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
3.68 + /// e = findUndirEdge(g,u,v,e)) {
3.69 + /// ...
3.70 + /// }
3.71 + /// \endcode
3.72 + // /// \todo We may want to use the "GraphBase"
3.73 + // /// interface here...
3.74 + template <typename Graph>
3.75 + inline typename Graph::UndirEdge
3.76 + findUndirEdge(const Graph &g,
3.77 + typename Graph::Node u,
3.78 + typename Graph::Node v,
3.79 + typename Graph::UndirEdge prev = INVALID) {
3.80 + return _findUndirEdge<Graph>(g, u, v, prev);
3.81 + }
3.82 +
3.83 + /// \brief Iterator for iterating on undir edges connected the same nodes.
3.84 + ///
3.85 + /// Iterator for iterating on undir edges connected the same nodes. It is
3.86 + /// higher level interface for the findUndirEdge() function. You can
3.87 + /// use it the following way:
3.88 + /// \code
3.89 + /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
3.90 + /// ...
3.91 + /// }
3.92 + /// \endcode
3.93 + ///
3.94 + /// \author Balazs Dezso
3.95 + template <typename _Graph>
3.96 + class ConUndirEdgeIt : public _Graph::UndirEdge {
3.97 + public:
3.98 +
3.99 + typedef _Graph Graph;
3.100 + typedef typename Graph::UndirEdge Parent;
3.101 +
3.102 + typedef typename Graph::UndirEdge UndirEdge;
3.103 + typedef typename Graph::Node Node;
3.104 +
3.105 + /// \brief Constructor.
3.106 + ///
3.107 + /// Construct a new ConUndirEdgeIt iterating on the edges which
3.108 + /// connects the \c u and \c v node.
3.109 + ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
3.110 + Parent::operator=(findUndirEdge(graph, u, v));
3.111 + }
3.112 +
3.113 + /// \brief Constructor.
3.114 + ///
3.115 + /// Construct a new ConUndirEdgeIt which continues the iterating from
3.116 + /// the \c e edge.
3.117 + ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
3.118 +
3.119 + /// \brief Increment operator.
3.120 + ///
3.121 + /// It increments the iterator and gives back the next edge.
3.122 + ConUndirEdgeIt& operator++() {
3.123 + Parent::operator=(findUndirEdge(graph, graph.source(*this),
3.124 + graph.target(*this), *this));
3.125 + return *this;
3.126 + }
3.127 + private:
3.128 + const Graph& graph;
3.129 + };
3.130 +
3.131 /// \brief Copy a map.
3.132 ///
3.133 /// This function copies the \c source map to the \c target map. It uses the
3.134 @@ -552,8 +655,6 @@
3.135 typedef _Item Item;
3.136 typedef _Item Key;
3.137
3.138 - typedef True NeedCopy;
3.139 -
3.140 /// \brief Constructor.
3.141 ///
3.142 /// Constructor for creating id map.
3.143 @@ -577,8 +678,6 @@
3.144 class InverseMap {
3.145 public:
3.146
3.147 - typedef True NeedCopy;
3.148 -
3.149 /// \brief Constructor.
3.150 ///
3.151 /// Constructor for creating an id-to-item map.
3.152 @@ -906,8 +1005,6 @@
3.153 class SourceMap {
3.154 public:
3.155
3.156 - typedef True NeedCopy;
3.157 -
3.158 typedef typename Graph::Node Value;
3.159 typedef typename Graph::Edge Key;
3.160
3.161 @@ -947,8 +1044,6 @@
3.162 class TargetMap {
3.163 public:
3.164
3.165 - typedef True NeedCopy;
3.166 -
3.167 typedef typename Graph::Node Value;
3.168 typedef typename Graph::Edge Key;
3.169
3.170 @@ -988,8 +1083,6 @@
3.171 class ForwardMap {
3.172 public:
3.173
3.174 - typedef True NeedCopy;
3.175 -
3.176 typedef typename Graph::Edge Value;
3.177 typedef typename Graph::UndirEdge Key;
3.178
3.179 @@ -1028,7 +1121,6 @@
3.180 template <typename Graph>
3.181 class BackwardMap {
3.182 public:
3.183 - typedef True NeedCopy;
3.184
3.185 typedef typename Graph::Edge Value;
3.186 typedef typename Graph::UndirEdge Key;
3.187 @@ -1296,11 +1388,10 @@
3.188 protected:
3.189
3.190 static int index(int i, int j) {
3.191 - int m = i > j ? i : j;
3.192 if (i < j) {
3.193 - return m * m + i;
3.194 + return j * j + i;
3.195 } else {
3.196 - return m * m + m + j;
3.197 + return i * i + i + j;
3.198 }
3.199 }
3.200