Changeset 1704:467d7927a901 in lemon-0.x
- Timestamp:
- 10/05/05 15:17:42 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2231
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/iterable_graph_extender.h
r1627 r1704 217 217 class IncEdgeIt : public Parent::UndirEdge { 218 218 const Graph* graph; 219 bool forward;219 bool direction; 220 220 friend class IterableUndirGraphExtender; 221 template <typename G>222 friend class UndirGraphExtender;223 221 public: 224 222 225 223 IncEdgeIt() { } 226 224 227 IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } 228 229 IncEdgeIt(const Graph& _graph, const Node &n) 230 : graph(&_graph) 231 { 232 _graph._dirFirstOut(*this, n); 225 IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { } 226 227 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 228 _graph.firstInc(*this, direction, n); 233 229 } 234 230 235 231 IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n) 236 : graph(&_graph), UndirEdge(ue) 237 { 238 forward = (_graph.source(ue) == n); 232 : graph(&_graph), UndirEdge(ue) { 233 direction = (_graph.source(ue) == n); 239 234 } 240 235 241 236 IncEdgeIt& operator++() { 242 graph-> _dirNextOut(*this);237 graph->nextInc(*this, direction); 243 238 return *this; 244 239 } … … 252 247 /// Returns the base node of the iterator 253 248 Node baseNode(const IncEdgeIt &e) const { 254 return _dirSource(e);249 return e.direction ? source(e) : target(e); 255 250 } 256 251 /// Running node of the iterator … … 258 253 /// Returns the running node of the iterator 259 254 Node runningNode(const IncEdgeIt &e) const { 260 return _dirTarget(e);255 return e.direction ? target(e) : source(e); 261 256 } 262 257 -
lemon/bits/undir_graph_extender.h
r1627 r1704 72 72 } 73 73 74 protected:75 76 template <typename E>77 Node _dirSource(const E &e) const {78 return e.forward ? Parent::source(e) : Parent::target(e);79 }80 81 template <typename E>82 Node _dirTarget(const E &e) const {83 return e.forward ? Parent::target(e) : Parent::source(e);84 }85 86 74 public: 87 75 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" … … 91 79 /// Source of the given Edge. 92 80 Node source(const Edge &e) const { 93 return _dirSource(e);81 return e.forward ? Parent::source(e) : Parent::target(e); 94 82 } 95 83 … … 100 88 /// Target of the given Edge. 101 89 Node target(const Edge &e) const { 102 return _dirTarget(e);90 return e.forward ? Parent::target(e) : Parent::source(e); 103 91 } 104 92 … … 155 143 } 156 144 157 158 protected: 159 160 template <typename E> 161 void _dirFirstOut(E &e, const Node &n) const { 145 public: 146 147 void firstOut(Edge &e, const Node &n) const { 162 148 Parent::firstIn(e,n); 163 149 if( UndirEdge(e) != INVALID ) { … … 169 155 } 170 156 } 171 template <typename E> 172 void _dirFirstIn(E &e, const Node &n) const { 173 Parent::firstOut(e,n); 174 if( UndirEdge(e) != INVALID ) { 175 e.forward = false; 176 } 177 else { 178 Parent::firstIn(e,n); 179 e.forward = true; 180 } 181 } 182 183 template <typename E> 184 void _dirNextOut(E &e) const { 157 void nextOut(Edge &e) const { 185 158 if( ! e.forward ) { 186 159 Node n = Parent::target(e); … … 195 168 } 196 169 } 197 template <typename E> 198 void _dirNextIn(E &e) const { 170 171 void firstIn(Edge &e, const Node &n) const { 172 Parent::firstOut(e,n); 173 if( UndirEdge(e) != INVALID ) { 174 e.forward = false; 175 } 176 else { 177 Parent::firstIn(e,n); 178 e.forward = true; 179 } 180 } 181 void nextIn(Edge &e) const { 199 182 if( ! e.forward ) { 200 183 Node n = Parent::source(e); … … 210 193 } 211 194 212 public: 213 214 void firstOut(Edge &e, const Node &n) const { 215 _dirFirstOut(e, n); 216 } 217 void firstIn(Edge &e, const Node &n) const { 218 _dirFirstIn(e, n); 219 } 220 221 void nextOut(Edge &e) const { 222 _dirNextOut(e); 223 } 224 void nextIn(Edge &e) const { 225 _dirNextIn(e); 195 void firstInc(UndirEdge &e, const Node &n) const { 196 Parent::firstOut(e, n); 197 if (e != INVALID) return; 198 Parent::firstIn(e, n); 199 } 200 void nextInc(UndirEdge &e, const Node &n) const { 201 if (Parent::source(e) == n) { 202 Parent::nextOut(e); 203 if (e != INVALID) return; 204 Parent::firstIn(e, n); 205 } else { 206 Parent::nextIn(e); 207 } 208 } 209 210 void firstInc(UndirEdge &e, bool &d, const Node &n) const { 211 d = true; 212 Parent::firstOut(e, n); 213 if (e != INVALID) return; 214 d = false; 215 Parent::firstIn(e, n); 216 } 217 void nextInc(UndirEdge &e, bool &d) const { 218 if (d) { 219 Node s = Parent::source(e); 220 Parent::nextOut(e); 221 if (e != INVALID) return; 222 d = false; 223 Parent::firstIn(e, s); 224 } else { 225 Parent::nextIn(e); 226 } 226 227 } 227 228 … … 263 264 return 2 * Parent::edgeNum(); 264 265 } 266 265 267 int undirEdgeNum() const { 266 268 return Parent::edgeNum(); 267 269 } 268 270 271 Edge findEdge(Node source, Node target, Edge prev) const { 272 if (prev == INVALID) { 273 UndirEdge edge = Parent::findEdge(source, target); 274 if (edge != INVALID) return direct(edge, true); 275 edge = Parent::findEdge(target, source); 276 if (edge != INVALID) return direct(edge, false); 277 } else if (direction(prev)) { 278 UndirEdge edge = Parent::findEdge(source, target, prev); 279 if (edge != INVALID) return direct(edge, true); 280 edge = Parent::findEdge(target, source); 281 if (edge != INVALID) return direct(edge, false); 282 } else { 283 UndirEdge edge = Parent::findEdge(target, source, prev); 284 if (edge != INVALID) return direct(edge, false); 285 } 286 return INVALID; 287 } 288 289 UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const { 290 if (prev == INVALID) { 291 UndirEdge edge = Parent::findEdge(source, target); 292 if (edge != INVALID) return edge; 293 edge = Parent::findEdge(target, source); 294 if (edge != INVALID) return edge; 295 } else if (Parent::source(prev) == source) { 296 UndirEdge edge = Parent::findEdge(source, target, prev); 297 if (edge != INVALID) return edge; 298 edge = Parent::findEdge(target, source); 299 if (edge != INVALID) return edge; 300 } else { 301 UndirEdge edge = Parent::findEdge(target, source, prev); 302 if (edge != INVALID) return edge; 303 } 304 return INVALID; 305 } 306 269 307 }; 270 308 -
lemon/graph_utils.h
r1695 r1704 161 161 } 162 162 163 /// \brief Function to count the number of the in -edges to node \c n.164 /// 165 /// This function counts the number of the in -edges to node \c n163 /// \brief Function to count the number of the inc-edges to node \c n. 164 /// 165 /// This function counts the number of the inc-edges to node \c n 166 166 /// in the graph. 167 167 template <typename Graph> … … 215 215 // /// \todo We may want to use the "GraphBase" 216 216 // /// interface here... 217 // /// It would not work with the undirected graphs.218 217 template <typename Graph> 219 218 inline typename Graph::Edge findEdge(const Graph &g, … … 265 264 ConEdgeIt& operator++() { 266 265 Parent::operator=(findEdge(graph, graph.source(*this), 266 graph.target(*this), *this)); 267 return *this; 268 } 269 private: 270 const Graph& graph; 271 }; 272 273 template <typename Graph> 274 inline 275 typename enable_if< 276 typename Graph::FindEdgeTag, 277 typename Graph::UndirEdge>::type 278 _findUndirEdge(const Graph &g, 279 typename Graph::Node u, typename Graph::Node v, 280 typename Graph::UndirEdge prev = INVALID) { 281 return g.findUndirEdge(u, v, prev); 282 } 283 284 template <typename Graph> 285 inline typename Graph::UndirEdge 286 _findUndirEdge(Wrap<Graph> w, 287 typename Graph::Node u, 288 typename Graph::Node v, 289 typename Graph::UndirEdge prev = INVALID) { 290 const Graph& g = w.value; 291 if (prev == INVALID) { 292 typename Graph::OutEdgeIt e(g, u); 293 while (e != INVALID && g.target(e) != v) ++e; 294 return e; 295 } else { 296 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e; 297 while (e != INVALID && g.target(e) != v) ++e; 298 return e; 299 } 300 } 301 302 /// \brief Finds an undir edge between two nodes of a graph. 303 /// 304 /// Finds an undir edge from node \c u to node \c v in graph \c g. 305 /// 306 /// If \c prev is \ref INVALID (this is the default value), then 307 /// it finds the first edge from \c u to \c v. Otherwise it looks for 308 /// the next edge from \c u to \c v after \c prev. 309 /// \return The found edge or \ref INVALID if there is no such an edge. 310 /// 311 /// Thus you can iterate through each edge from \c u to \c v as it follows. 312 /// \code 313 /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID; 314 /// e = findUndirEdge(g,u,v,e)) { 315 /// ... 316 /// } 317 /// \endcode 318 // /// \todo We may want to use the "GraphBase" 319 // /// interface here... 320 template <typename Graph> 321 inline typename Graph::UndirEdge 322 findUndirEdge(const Graph &g, 323 typename Graph::Node u, 324 typename Graph::Node v, 325 typename Graph::UndirEdge prev = INVALID) { 326 return _findUndirEdge<Graph>(g, u, v, prev); 327 } 328 329 /// \brief Iterator for iterating on undir edges connected the same nodes. 330 /// 331 /// Iterator for iterating on undir edges connected the same nodes. It is 332 /// higher level interface for the findUndirEdge() function. You can 333 /// use it the following way: 334 /// \code 335 /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 336 /// ... 337 /// } 338 /// \endcode 339 /// 340 /// \author Balazs Dezso 341 template <typename _Graph> 342 class ConUndirEdgeIt : public _Graph::UndirEdge { 343 public: 344 345 typedef _Graph Graph; 346 typedef typename Graph::UndirEdge Parent; 347 348 typedef typename Graph::UndirEdge UndirEdge; 349 typedef typename Graph::Node Node; 350 351 /// \brief Constructor. 352 /// 353 /// Construct a new ConUndirEdgeIt iterating on the edges which 354 /// connects the \c u and \c v node. 355 ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) { 356 Parent::operator=(findUndirEdge(graph, u, v)); 357 } 358 359 /// \brief Constructor. 360 /// 361 /// Construct a new ConUndirEdgeIt which continues the iterating from 362 /// the \c e edge. 363 ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {} 364 365 /// \brief Increment operator. 366 /// 367 /// It increments the iterator and gives back the next edge. 368 ConUndirEdgeIt& operator++() { 369 Parent::operator=(findUndirEdge(graph, graph.source(*this), 267 370 graph.target(*this), *this)); 268 371 return *this; … … 553 656 typedef _Item Key; 554 657 555 typedef True NeedCopy;556 557 658 /// \brief Constructor. 558 659 /// … … 577 678 class InverseMap { 578 679 public: 579 580 typedef True NeedCopy;581 680 582 681 /// \brief Constructor. … … 907 1006 public: 908 1007 909 typedef True NeedCopy;910 911 1008 typedef typename Graph::Node Value; 912 1009 typedef typename Graph::Edge Key; … … 948 1045 public: 949 1046 950 typedef True NeedCopy;951 952 1047 typedef typename Graph::Node Value; 953 1048 typedef typename Graph::Edge Key; … … 989 1084 public: 990 1085 991 typedef True NeedCopy;992 993 1086 typedef typename Graph::Edge Value; 994 1087 typedef typename Graph::UndirEdge Key; … … 1029 1122 class BackwardMap { 1030 1123 public: 1031 typedef True NeedCopy;1032 1124 1033 1125 typedef typename Graph::Edge Value; … … 1297 1389 1298 1390 static int index(int i, int j) { 1299 int m = i > j ? i : j;1300 1391 if (i < j) { 1301 return m * m+ i;1392 return j * j + i; 1302 1393 } else { 1303 return m * m + m+ j;1394 return i * i + i + j; 1304 1395 } 1305 1396 }
Note: See TracChangeset
for help on using the changeset viewer.