Changeset 919:6153d9cf78c6 in lemon-0.x for src/hugo/smart_graph.h
- Timestamp:
- 09/29/04 16:02:14 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1230
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/smart_graph.h
r916 r919 28 28 29 29 #include <hugo/array_map.h> 30 #include <hugo/sym_map.h> 31 30 32 #include <hugo/map_registry.h> 31 33 … … 297 299 }; 298 300 299 300 301 class SymSmartGraph : public SmartGraph {302 typedef SmartGraph Parent;303 public:304 305 typedef SymSmartGraph Graph;306 307 typedef SmartGraph::Node Node;308 typedef SmartGraph::NodeIt NodeIt;309 310 class SymEdge;311 class SymEdgeIt;312 313 class Edge;314 class EdgeIt;315 class OutEdgeIt;316 class InEdgeIt;317 318 template <typename Value>319 class NodeMap : public Parent::NodeMap<Value> {320 public:321 NodeMap(const SymSmartGraph& g)322 : SymSmartGraph::Parent::NodeMap<Value>(g) {}323 NodeMap(const SymSmartGraph& g, Value v)324 : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}325 template<typename TT>326 NodeMap(const NodeMap<TT>& copy)327 : SymSmartGraph::Parent::NodeMap<Value>(copy) { }328 };329 330 template <typename Value>331 class SymEdgeMap : public Parent::EdgeMap<Value> {332 public:333 typedef SymEdge KeyType;334 335 SymEdgeMap(const SymSmartGraph& g)336 : SymSmartGraph::Parent::EdgeMap<Value>(g) {}337 SymEdgeMap(const SymSmartGraph& g, Value v)338 : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}339 template<typename TT>340 SymEdgeMap(const SymEdgeMap<TT>& copy)341 : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }342 343 };344 345 // Create edge map registry.346 CREATE_EDGE_MAP_REGISTRY;347 // Create edge maps.348 CREATE_EDGE_MAP(ArrayMap);349 350 class Edge {351 friend class SymSmartGraph;352 friend class SymSmartGraph::EdgeIt;353 friend class SymSmartGraph::OutEdgeIt;354 friend class SymSmartGraph::InEdgeIt;355 356 protected:357 int id;358 359 Edge(int pid) { id = pid; }360 361 public:362 /// An Edge with id \c n.363 364 Edge() { }365 Edge (Invalid) { id = -1; }366 367 operator SymEdge(){ return SymEdge(id >> 1);}368 369 bool operator==(const Edge i) const {return id == i.id;}370 bool operator!=(const Edge i) const {return id != i.id;}371 bool operator<(const Edge i) const {return id < i.id;}372 // ///Validity check373 // operator bool() { return n!=-1; }374 };375 376 class SymEdge : public SmartGraph::Edge {377 friend class SymSmartGraph;378 friend class SymSmartGraph::Edge;379 typedef SmartGraph::Edge Parent;380 381 protected:382 SymEdge(int pid) : Parent(pid) {}383 public:384 385 SymEdge() { }386 SymEdge(const SmartGraph::Edge& i) : Parent(i) {}387 SymEdge (Invalid) : Parent(INVALID) {}388 389 };390 391 class OutEdgeIt {392 Parent::OutEdgeIt out;393 Parent::InEdgeIt in;394 public:395 OutEdgeIt() {}396 OutEdgeIt(const SymSmartGraph& g, Edge e) {397 if ((e.id & 1) == 0) {398 out = Parent::OutEdgeIt(g, SymEdge(e));399 in = Parent::InEdgeIt(g, g.tail(e));400 } else {401 out = Parent::OutEdgeIt(INVALID);402 in = Parent::InEdgeIt(g, SymEdge(e));403 }404 }405 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }406 407 OutEdgeIt(const SymSmartGraph& g, const Node v)408 : out(g, v), in(g, v) {}409 OutEdgeIt &operator++() {410 if (out != INVALID) {411 ++out;412 } else {413 ++in;414 }415 return *this;416 }417 418 operator Edge() const {419 if (out == INVALID && in == INVALID) return INVALID;420 return out != INVALID ? forward(out) : backward(in);421 }422 423 bool operator==(const Edge i) const {return Edge(*this) == i;}424 bool operator!=(const Edge i) const {return Edge(*this) != i;}425 bool operator<(const Edge i) const {return Edge(*this) < i;}426 };427 428 class InEdgeIt {429 Parent::OutEdgeIt out;430 Parent::InEdgeIt in;431 public:432 InEdgeIt() {}433 InEdgeIt(const SymSmartGraph& g, Edge e) {434 if ((e.id & 1) == 0) {435 out = Parent::OutEdgeIt(g, SymEdge(e));436 in = Parent::InEdgeIt(g, g.tail(e));437 } else {438 out = Parent::OutEdgeIt(INVALID);439 in = Parent::InEdgeIt(g, SymEdge(e));440 }441 }442 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }443 444 InEdgeIt(const SymSmartGraph& g, const Node v)445 : out(g, v), in(g, v) {}446 447 InEdgeIt &operator++() {448 if (out != INVALID) {449 ++out;450 } else {451 ++in;452 }453 return *this;454 }455 456 operator Edge() const {457 if (out == INVALID && in == INVALID) return INVALID;458 return out != INVALID ? backward(out) : forward(in);459 }460 461 bool operator==(const Edge i) const {return Edge(*this) == i;}462 bool operator!=(const Edge i) const {return Edge(*this) != i;}463 bool operator<(const Edge i) const {return Edge(*this) < i;}464 };465 466 class SymEdgeIt : public Parent::EdgeIt {467 468 public:469 SymEdgeIt() {}470 471 SymEdgeIt(const SymSmartGraph& g)472 : SymSmartGraph::Parent::EdgeIt(g) {}473 474 SymEdgeIt(const SymSmartGraph& g, SymEdge e)475 : SymSmartGraph::Parent::EdgeIt(g, e) {}476 477 SymEdgeIt(Invalid i)478 : SymSmartGraph::Parent::EdgeIt(INVALID) {}479 480 SymEdgeIt& operator++() {481 SymSmartGraph::Parent::EdgeIt::operator++();482 return *this;483 }484 485 operator SymEdge() const {486 return SymEdge487 (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));488 }489 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}490 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}491 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}492 };493 494 class EdgeIt {495 SymEdgeIt it;496 bool fw;497 public:498 EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}499 EdgeIt (Invalid i) : it(i) { }500 EdgeIt(const SymSmartGraph& g, Edge e)501 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }502 EdgeIt() { }503 EdgeIt& operator++() {504 fw = !fw;505 if (fw) ++it;506 return *this;507 }508 operator Edge() const {509 if (it == INVALID) return INVALID;510 return fw ? forward(it) : backward(it);511 }512 bool operator==(const Edge i) const {return Edge(*this) == i;}513 bool operator!=(const Edge i) const {return Edge(*this) != i;}514 bool operator<(const Edge i) const {return Edge(*this) < i;}515 516 };517 518 ///Number of nodes.519 int nodeNum() const { return Parent::nodeNum(); }520 ///Number of edges.521 int edgeNum() const { return 2*Parent::edgeNum(); }522 ///Number of symmetric edges.523 int symEdgeNum() const { return Parent::edgeNum(); }524 525 /// Maximum node ID.526 527 /// Maximum node ID.528 ///\sa id(Node)529 int maxNodeId() const { return Parent::maxNodeId(); }530 /// Maximum edge ID.531 532 /// Maximum edge ID.533 ///\sa id(Edge)534 int maxEdgeId() const { return 2*Parent::maxEdgeId(); }535 /// Maximum symmetric edge ID.536 537 /// Maximum symmetric edge ID.538 ///\sa id(SymEdge)539 int maxSymEdgeId() const { return Parent::maxEdgeId(); }540 541 542 Node tail(Edge e) const {543 return (e.id & 1) == 0 ?544 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));545 }546 547 Node head(Edge e) const {548 return (e.id & 1) == 0 ?549 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));550 }551 552 Node tail(SymEdge e) const {553 return Parent::tail(e);554 }555 556 Node head(SymEdge e) const {557 return Parent::head(e);558 }559 560 NodeIt& first(NodeIt& v) const {561 v=NodeIt(*this); return v; }562 EdgeIt& first(EdgeIt& e) const {563 e=EdgeIt(*this); return e; }564 SymEdgeIt& first(SymEdgeIt& e) const {565 e=SymEdgeIt(*this); return e; }566 OutEdgeIt& first(OutEdgeIt& e, const Node v) const {567 e=OutEdgeIt(*this,v); return e; }568 InEdgeIt& first(InEdgeIt& e, const Node v) const {569 e=InEdgeIt(*this,v); return e; }570 571 /// Node ID.572 573 /// The ID of a valid Node is a nonnegative integer not greater than574 /// \ref maxNodeId(). The range of the ID's is not surely continuous575 /// and the greatest node ID can be actually less then \ref maxNodeId().576 ///577 /// The ID of the \ref INVALID node is -1.578 ///\return The ID of the node \c v.579 static int id(Node v) { return Parent::id(v); }580 /// Edge ID.581 582 /// The ID of a valid Edge is a nonnegative integer not greater than583 /// \ref maxEdgeId(). The range of the ID's is not surely continuous584 /// and the greatest edge ID can be actually less then \ref maxEdgeId().585 ///586 /// The ID of the \ref INVALID edge is -1.587 ///\return The ID of the edge \c e.588 static int id(Edge e) { return e.id; }589 590 /// The ID of a valid SymEdge is a nonnegative integer not greater than591 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous592 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().593 ///594 /// The ID of the \ref INVALID symmetric edge is -1.595 ///\return The ID of the edge \c e.596 static int id(SymEdge e) { return Parent::id(e); }597 598 /// Adds a new node to the graph.599 600 /// \warning It adds the new node to the front of the list.601 /// (i.e. the lastly added node becomes the first.)602 Node addNode() {603 return Parent::addNode();604 }605 606 SymEdge addEdge(Node u, Node v) {607 SymEdge se = Parent::addEdge(u, v);608 edge_maps.add(forward(se));609 edge_maps.add(backward(se));610 return se;611 }612 613 /// Finds an edge between two nodes.614 615 /// Finds an edge from node \c u to node \c v.616 ///617 /// If \c prev is \ref INVALID (this is the default value), then618 /// It finds the first edge from \c u to \c v. Otherwise it looks for619 /// the next edge from \c u to \c v after \c prev.620 /// \return The found edge or INVALID if there is no such an edge.621 Edge findEdge(Node u, Node v, Edge prev = INVALID)622 {623 if (prev == INVALID || id(prev) & 1 == 0) {624 SymEdge se = Parent::findEdge(u, v, SymEdge(prev));625 if (se != INVALID) return forward(se);626 } else {627 SymEdge se = Parent::findEdge(v, u, SymEdge(prev));628 if (se != INVALID) return backward(se);629 }630 return INVALID;631 }632 633 // /// Finds an symmetric edge between two nodes.634 635 // /// Finds an symmetric edge from node \c u to node \c v.636 // ///637 // /// If \c prev is \ref INVALID (this is the default value), then638 // /// It finds the first edge from \c u to \c v. Otherwise it looks for639 // /// the next edge from \c u to \c v after \c prev.640 // /// \return The found edge or INVALID if there is no such an edge.641 642 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)643 // {644 // if (prev == INVALID || id(prev) & 1 == 0) {645 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev));646 // if (se != INVALID) return se;647 // } else {648 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev));649 // if (se != INVALID) return se;650 // }651 // return INVALID;652 // }653 654 public:655 656 void clear() {657 edge_maps.clear();658 Parent::clear();659 }660 661 static Edge opposite(Edge e) {662 return Edge(id(e) ^ 1);663 }664 665 static Edge forward(SymEdge e) {666 return Edge(id(e) << 1);667 }668 669 static Edge backward(SymEdge e) {670 return Edge((id(e) << 1) | 1);671 }672 673 };674 301 ///Graph for bidirectional edges. 675 302 … … 692 319 //\sa SmartGraph. 693 320 694 /*class SymSmartGraph : public SmartGraph321 class SymSmartGraph : public SmartGraph 695 322 { 696 323 public: … … 727 354 728 355 729 };*/356 }; 730 357 731 358 /// @}
Note: See TracChangeset
for help on using the changeset viewer.