1.1 --- a/lemon/bits/undir_graph_extender.h Wed Oct 05 13:15:47 2005 +0000
1.2 +++ b/lemon/bits/undir_graph_extender.h Wed Oct 05 13:17:42 2005 +0000
1.3 @@ -71,18 +71,6 @@
1.4 return Edge(e,!e.forward);
1.5 }
1.6
1.7 - protected:
1.8 -
1.9 - template <typename E>
1.10 - Node _dirSource(const E &e) const {
1.11 - return e.forward ? Parent::source(e) : Parent::target(e);
1.12 - }
1.13 -
1.14 - template <typename E>
1.15 - Node _dirTarget(const E &e) const {
1.16 - return e.forward ? Parent::target(e) : Parent::source(e);
1.17 - }
1.18 -
1.19 public:
1.20 /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
1.21 /// or something???
1.22 @@ -90,7 +78,7 @@
1.23
1.24 /// Source of the given Edge.
1.25 Node source(const Edge &e) const {
1.26 - return _dirSource(e);
1.27 + return e.forward ? Parent::source(e) : Parent::target(e);
1.28 }
1.29
1.30 /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
1.31 @@ -99,7 +87,7 @@
1.32
1.33 /// Target of the given Edge.
1.34 Node target(const Edge &e) const {
1.35 - return _dirTarget(e);
1.36 + return e.forward ? Parent::target(e) : Parent::source(e);
1.37 }
1.38
1.39 Node oppositeNode(const Node &n, const UndirEdge &e) const {
1.40 @@ -154,11 +142,9 @@
1.41 }
1.42 }
1.43
1.44 -
1.45 - protected:
1.46 + public:
1.47
1.48 - template <typename E>
1.49 - void _dirFirstOut(E &e, const Node &n) const {
1.50 + void firstOut(Edge &e, const Node &n) const {
1.51 Parent::firstIn(e,n);
1.52 if( UndirEdge(e) != INVALID ) {
1.53 e.forward = false;
1.54 @@ -168,20 +154,7 @@
1.55 e.forward = true;
1.56 }
1.57 }
1.58 - template <typename E>
1.59 - void _dirFirstIn(E &e, const Node &n) const {
1.60 - Parent::firstOut(e,n);
1.61 - if( UndirEdge(e) != INVALID ) {
1.62 - e.forward = false;
1.63 - }
1.64 - else {
1.65 - Parent::firstIn(e,n);
1.66 - e.forward = true;
1.67 - }
1.68 - }
1.69 -
1.70 - template <typename E>
1.71 - void _dirNextOut(E &e) const {
1.72 + void nextOut(Edge &e) const {
1.73 if( ! e.forward ) {
1.74 Node n = Parent::target(e);
1.75 Parent::nextIn(e);
1.76 @@ -194,8 +167,18 @@
1.77 Parent::nextOut(e);
1.78 }
1.79 }
1.80 - template <typename E>
1.81 - void _dirNextIn(E &e) const {
1.82 +
1.83 + void firstIn(Edge &e, const Node &n) const {
1.84 + Parent::firstOut(e,n);
1.85 + if( UndirEdge(e) != INVALID ) {
1.86 + e.forward = false;
1.87 + }
1.88 + else {
1.89 + Parent::firstIn(e,n);
1.90 + e.forward = true;
1.91 + }
1.92 + }
1.93 + void nextIn(Edge &e) const {
1.94 if( ! e.forward ) {
1.95 Node n = Parent::source(e);
1.96 Parent::nextOut(e);
1.97 @@ -209,20 +192,38 @@
1.98 }
1.99 }
1.100
1.101 - public:
1.102 -
1.103 - void firstOut(Edge &e, const Node &n) const {
1.104 - _dirFirstOut(e, n);
1.105 + void firstInc(UndirEdge &e, const Node &n) const {
1.106 + Parent::firstOut(e, n);
1.107 + if (e != INVALID) return;
1.108 + Parent::firstIn(e, n);
1.109 }
1.110 - void firstIn(Edge &e, const Node &n) const {
1.111 - _dirFirstIn(e, n);
1.112 + void nextInc(UndirEdge &e, const Node &n) const {
1.113 + if (Parent::source(e) == n) {
1.114 + Parent::nextOut(e);
1.115 + if (e != INVALID) return;
1.116 + Parent::firstIn(e, n);
1.117 + } else {
1.118 + Parent::nextIn(e);
1.119 + }
1.120 }
1.121
1.122 - void nextOut(Edge &e) const {
1.123 - _dirNextOut(e);
1.124 + void firstInc(UndirEdge &e, bool &d, const Node &n) const {
1.125 + d = true;
1.126 + Parent::firstOut(e, n);
1.127 + if (e != INVALID) return;
1.128 + d = false;
1.129 + Parent::firstIn(e, n);
1.130 }
1.131 - void nextIn(Edge &e) const {
1.132 - _dirNextIn(e);
1.133 + void nextInc(UndirEdge &e, bool &d) const {
1.134 + if (d) {
1.135 + Node s = Parent::source(e);
1.136 + Parent::nextOut(e);
1.137 + if (e != INVALID) return;
1.138 + d = false;
1.139 + Parent::firstIn(e, s);
1.140 + } else {
1.141 + Parent::nextIn(e);
1.142 + }
1.143 }
1.144
1.145 // Miscellaneous stuff:
1.146 @@ -262,10 +263,47 @@
1.147 int edgeNum() const {
1.148 return 2 * Parent::edgeNum();
1.149 }
1.150 +
1.151 int undirEdgeNum() const {
1.152 return Parent::edgeNum();
1.153 }
1.154
1.155 + Edge findEdge(Node source, Node target, Edge prev) const {
1.156 + if (prev == INVALID) {
1.157 + UndirEdge edge = Parent::findEdge(source, target);
1.158 + if (edge != INVALID) return direct(edge, true);
1.159 + edge = Parent::findEdge(target, source);
1.160 + if (edge != INVALID) return direct(edge, false);
1.161 + } else if (direction(prev)) {
1.162 + UndirEdge edge = Parent::findEdge(source, target, prev);
1.163 + if (edge != INVALID) return direct(edge, true);
1.164 + edge = Parent::findEdge(target, source);
1.165 + if (edge != INVALID) return direct(edge, false);
1.166 + } else {
1.167 + UndirEdge edge = Parent::findEdge(target, source, prev);
1.168 + if (edge != INVALID) return direct(edge, false);
1.169 + }
1.170 + return INVALID;
1.171 + }
1.172 +
1.173 + UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
1.174 + if (prev == INVALID) {
1.175 + UndirEdge edge = Parent::findEdge(source, target);
1.176 + if (edge != INVALID) return edge;
1.177 + edge = Parent::findEdge(target, source);
1.178 + if (edge != INVALID) return edge;
1.179 + } else if (Parent::source(prev) == source) {
1.180 + UndirEdge edge = Parent::findEdge(source, target, prev);
1.181 + if (edge != INVALID) return edge;
1.182 + edge = Parent::findEdge(target, source);
1.183 + if (edge != INVALID) return edge;
1.184 + } else {
1.185 + UndirEdge edge = Parent::findEdge(target, source, prev);
1.186 + if (edge != INVALID) return edge;
1.187 + }
1.188 + return INVALID;
1.189 + }
1.190 +
1.191 };
1.192
1.193 }