Changeset 1909:2d806130e700 in lemon0.x for lemon/graph_utils.h
 Timestamp:
 01/26/06 16:42:13 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2484
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r1875 r1909 72 72 ///This \c \#define creates the same convenience typedefs as defined by 73 73 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates 74 ///\c U ndirEdge, \c UndirEdgeIt, \c IncEdgeIt,75 ///\c BoolU ndirEdgeMap, \c IntUndirEdgeMap, \c DoubleUndirEdgeMap.74 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt, 75 ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap. 76 76 /// 77 77 ///\note If \c G it a template parameter, it should be used in this way. … … 84 84 #define UNDIRGRAPH_TYPEDEFS(Graph) \ 85 85 GRAPH_TYPEDEFS(Graph) \ 86 typedef Graph:: U ndirEdge UndirEdge; \87 typedef Graph:: U ndirEdgeIt UndirEdgeIt; \86 typedef Graph:: UEdge UEdge; \ 87 typedef Graph:: UEdgeIt UEdgeIt; \ 88 88 typedef Graph:: IncEdgeIt IncEdgeIt; 89 // typedef Graph::template U ndirEdgeMap<bool> BoolUndirEdgeMap;90 // typedef Graph::template U ndirEdgeMap<int> IntUndirEdgeMap;91 // typedef Graph::template U ndirEdgeMap<double> DoubleUndirEdgeMap;89 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap; 90 // typedef Graph::template UEdgeMap<int> IntUEdgeMap; 91 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap; 92 92 93 93 … … 163 163 inline 164 164 typename enable_if<typename Graph::EdgeNumTag, int>::type 165 _countU ndirEdges(const Graph &g) {166 return g.u ndirEdgeNum();167 } 168 169 template <typename Graph> 170 inline int _countU ndirEdges(Wrap<Graph> w) {171 return countItems<Graph, typename Graph::U ndirEdgeIt>(w.value);165 _countUEdges(const Graph &g) { 166 return g.uEdgeNum(); 167 } 168 169 template <typename Graph> 170 inline int _countUEdges(Wrap<Graph> w) { 171 return countItems<Graph, typename Graph::UEdgeIt>(w.value); 172 172 } 173 173 … … 179 179 180 180 template <typename Graph> 181 inline int countU ndirEdges(const Graph& g) {182 return _countU ndirEdges<Graph>(g);181 inline int countUEdges(const Graph& g) { 182 return _countUEdges<Graph>(g); 183 183 } 184 184 … … 326 326 typename enable_if< 327 327 typename Graph::FindEdgeTag, 328 typename Graph::U ndirEdge>::type329 _findU ndirEdge(const Graph &g,328 typename Graph::UEdge>::type 329 _findUEdge(const Graph &g, 330 330 typename Graph::Node u, typename Graph::Node v, 331 typename Graph::U ndirEdge prev = INVALID) {332 return g.findU ndirEdge(u, v, prev);333 } 334 335 template <typename Graph> 336 inline typename Graph::U ndirEdge337 _findU ndirEdge(Wrap<Graph> w,331 typename Graph::UEdge prev = INVALID) { 332 return g.findUEdge(u, v, prev); 333 } 334 335 template <typename Graph> 336 inline typename Graph::UEdge 337 _findUEdge(Wrap<Graph> w, 338 338 typename Graph::Node u, 339 339 typename Graph::Node v, 340 typename Graph::U ndirEdge prev = INVALID) {340 typename Graph::UEdge prev = INVALID) { 341 341 const Graph& g = w.value; 342 342 if (prev == INVALID) { … … 351 351 } 352 352 353 /// \brief Finds an u ndiredge between two nodes of a graph.354 /// 355 /// Finds an u ndiredge from node \c u to node \c v in graph \c g.353 /// \brief Finds an uedge between two nodes of a graph. 354 /// 355 /// Finds an uedge from node \c u to node \c v in graph \c g. 356 356 /// 357 357 /// If \c prev is \ref INVALID (this is the default value), then … … 362 362 /// Thus you can iterate through each edge from \c u to \c v as it follows. 363 363 /// \code 364 /// for(U ndirEdge e = findUndirEdge(g,u,v); e != INVALID;365 /// e = findU ndirEdge(g,u,v,e)) {364 /// for(UEdge e = findUEdge(g,u,v); e != INVALID; 365 /// e = findUEdge(g,u,v,e)) { 366 366 /// ... 367 367 /// } … … 370 370 // /// interface here... 371 371 template <typename Graph> 372 inline typename Graph::U ndirEdge373 findU ndirEdge(const Graph &g,372 inline typename Graph::UEdge 373 findUEdge(const Graph &g, 374 374 typename Graph::Node u, 375 375 typename Graph::Node v, 376 typename Graph::U ndirEdge prev = INVALID) {377 return _findU ndirEdge<Graph>(g, u, v, prev);378 } 379 380 /// \brief Iterator for iterating on u ndiredges connected the same nodes.381 /// 382 /// Iterator for iterating on u ndiredges connected the same nodes. It is383 /// higher level interface for the findU ndirEdge() function. You can376 typename Graph::UEdge prev = INVALID) { 377 return _findUEdge<Graph>(g, u, v, prev); 378 } 379 380 /// \brief Iterator for iterating on uedges connected the same nodes. 381 /// 382 /// Iterator for iterating on uedges connected the same nodes. It is 383 /// higher level interface for the findUEdge() function. You can 384 384 /// use it the following way: 385 385 /// \code 386 /// for (ConU ndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {386 /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 387 387 /// ... 388 388 /// } … … 391 391 /// \author Balazs Dezso 392 392 template <typename _Graph> 393 class ConU ndirEdgeIt : public _Graph::UndirEdge {393 class ConUEdgeIt : public _Graph::UEdge { 394 394 public: 395 395 396 396 typedef _Graph Graph; 397 typedef typename Graph::U ndirEdge Parent;398 399 typedef typename Graph::U ndirEdge UndirEdge;397 typedef typename Graph::UEdge Parent; 398 399 typedef typename Graph::UEdge UEdge; 400 400 typedef typename Graph::Node Node; 401 401 402 402 /// \brief Constructor. 403 403 /// 404 /// Construct a new ConU ndirEdgeIt iterating on the edges which404 /// Construct a new ConUEdgeIt iterating on the edges which 405 405 /// connects the \c u and \c v node. 406 ConU ndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {407 Parent::operator=(findU ndirEdge(graph, u, v));406 ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) { 407 Parent::operator=(findUEdge(graph, u, v)); 408 408 } 409 409 410 410 /// \brief Constructor. 411 411 /// 412 /// Construct a new ConU ndirEdgeIt which continues the iterating from412 /// Construct a new ConUEdgeIt which continues the iterating from 413 413 /// the \c e edge. 414 ConU ndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}414 ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {} 415 415 416 416 /// \brief Increment operator. 417 417 /// 418 418 /// It increments the iterator and gives back the next edge. 419 ConU ndirEdgeIt& operator++() {420 Parent::operator=(findU ndirEdge(graph, graph.source(*this),419 ConUEdgeIt& operator++() { 420 Parent::operator=(findUEdge(graph, graph.source(*this), 421 421 graph.target(*this), *this)); 422 422 return *this; … … 597 597 /// 598 598 /// Class to copy an undirected graph to an other graph (duplicate a graph). 599 /// The simplest way of using it is through the \c copyU ndirGraph() function.599 /// The simplest way of using it is through the \c copyUGraph() function. 600 600 template <typename Target, typename Source> 601 class U ndirGraphCopy {601 class UGraphCopy { 602 602 public: 603 603 typedef typename Source::Node Node; … … 605 605 typedef typename Source::Edge Edge; 606 606 typedef typename Source::EdgeIt EdgeIt; 607 typedef typename Source::U ndirEdge UndirEdge;608 typedef typename Source::U ndirEdgeIt UndirEdgeIt;607 typedef typename Source::UEdge UEdge; 608 typedef typename Source::UEdgeIt UEdgeIt; 609 609 610 610 typedef typename Source:: … … 612 612 613 613 typedef typename Source:: 614 template U ndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;614 template UEdgeMap<typename Target::UEdge> UEdgeRefMap; 615 615 616 616 private: 617 617 618 618 struct EdgeRefMap { 619 EdgeRefMap(U ndirGraphCopy& _gc) : gc(_gc) {}619 EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {} 620 620 typedef typename Source::Edge Key; 621 621 typedef typename Target::Edge Value; 622 622 623 623 Value operator[](const Key& key) { 624 return gc.target.direct(gc.u ndirEdgeRef[key],624 return gc.target.direct(gc.uEdgeRef[key], 625 625 gc.target.direction(key)); 626 626 } 627 627 628 U ndirGraphCopy& gc;628 UGraphCopy& gc; 629 629 }; 630 630 631 631 public: 632 632 633 /// \brief Constructor for the U ndirGraphCopy.633 /// \brief Constructor for the UGraphCopy. 634 634 /// 635 635 /// It copies the content of the \c _source graph into the 636 636 /// \c _target graph. It creates also two references, one beetween 637 637 /// the two nodeset and one beetween the two edgesets. 638 U ndirGraphCopy(Target& _target, const Source& _source)638 UGraphCopy(Target& _target, const Source& _source) 639 639 : source(_source), target(_target), 640 nodeRefMap(_source), edgeRefMap(*this), u ndirEdgeRefMap(_source) {640 nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) { 641 641 for (NodeIt it(source); it != INVALID; ++it) { 642 642 nodeRefMap[it] = target.addNode(); 643 643 } 644 for (U ndirEdgeIt it(source); it != INVALID; ++it) {645 u ndirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],644 for (UEdgeIt it(source); it != INVALID; ++it) { 645 uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 646 646 nodeRefMap[source.target(it)]); 647 647 } … … 652 652 /// Copies the node references into the given map. 653 653 template <typename NodeRef> 654 const U ndirGraphCopy& nodeRef(NodeRef& map) const {654 const UGraphCopy& nodeRef(NodeRef& map) const { 655 655 for (NodeIt it(source); it != INVALID; ++it) { 656 656 map.set(it, nodeRefMap[it]); … … 663 663 /// Reverse and copies the node references into the given map. 664 664 template <typename NodeRef> 665 const U ndirGraphCopy& nodeCrossRef(NodeRef& map) const {665 const UGraphCopy& nodeCrossRef(NodeRef& map) const { 666 666 for (NodeIt it(source); it != INVALID; ++it) { 667 667 map.set(nodeRefMap[it], it); … … 674 674 /// Copies the edge references into the given map. 675 675 template <typename EdgeRef> 676 const U ndirGraphCopy& edgeRef(EdgeRef& map) const {676 const UGraphCopy& edgeRef(EdgeRef& map) const { 677 677 for (EdgeIt it(source); it != INVALID; ++it) { 678 678 map.set(edgeRefMap[it], it); … … 686 686 /// Reverse and copies the undirected edge references into the given map. 687 687 template <typename EdgeRef> 688 const U ndirGraphCopy& edgeCrossRef(EdgeRef& map) const {688 const UGraphCopy& edgeCrossRef(EdgeRef& map) const { 689 689 for (EdgeIt it(source); it != INVALID; ++it) { 690 690 map.set(it, edgeRefMap[it]); … … 697 697 /// Copies the undirected edge references into the given map. 698 698 template <typename EdgeRef> 699 const U ndirGraphCopy& undirEdgeRef(EdgeRef& map) const {700 for (U ndirEdgeIt it(source); it != INVALID; ++it) {701 map.set(it, u ndirEdgeRefMap[it]);699 const UGraphCopy& uEdgeRef(EdgeRef& map) const { 700 for (UEdgeIt it(source); it != INVALID; ++it) { 701 map.set(it, uEdgeRefMap[it]); 702 702 } 703 703 return *this; … … 709 709 /// Reverse and copies the undirected edge references into the given map. 710 710 template <typename EdgeRef> 711 const U ndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {712 for (U ndirEdgeIt it(source); it != INVALID; ++it) {713 map.set(u ndirEdgeRefMap[it], it);711 const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const { 712 for (UEdgeIt it(source); it != INVALID; ++it) { 713 map.set(uEdgeRefMap[it], it); 714 714 } 715 715 return *this; … … 723 723 /// type. 724 724 template <typename TargetMap, typename SourceMap> 725 const U ndirGraphCopy& nodeMap(TargetMap& tMap,725 const UGraphCopy& nodeMap(TargetMap& tMap, 726 726 const SourceMap& sMap) const { 727 727 copyMap(tMap, sMap, NodeIt(source), nodeRefMap); … … 736 736 /// type. 737 737 template <typename TargetMap, typename SourceMap> 738 const U ndirGraphCopy& edgeMap(TargetMap& tMap,738 const UGraphCopy& edgeMap(TargetMap& tMap, 739 739 const SourceMap& sMap) const { 740 740 copyMap(tMap, sMap, EdgeIt(source), edgeRefMap); … … 749 749 /// type. 750 750 template <typename TargetMap, typename SourceMap> 751 const U ndirGraphCopy& undirEdgeMap(TargetMap& tMap,751 const UGraphCopy& uEdgeMap(TargetMap& tMap, 752 752 const SourceMap& sMap) const { 753 copyMap(tMap, sMap, U ndirEdgeIt(source), undirEdgeRefMap);753 copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap); 754 754 return *this; 755 755 } … … 769 769 } 770 770 771 /// \brief Gives back the stored u ndiredge references.772 /// 773 /// Gives back the stored u ndiredge references.774 const U ndirEdgeRefMap& undirEdgeRef() const {775 return u ndirEdgeRefMap;771 /// \brief Gives back the stored uedge references. 772 /// 773 /// Gives back the stored uedge references. 774 const UEdgeRefMap& uEdgeRef() const { 775 return uEdgeRefMap; 776 776 } 777 777 … … 785 785 NodeRefMap nodeRefMap; 786 786 EdgeRefMap edgeRefMap; 787 U ndirEdgeRefMap undirEdgeRefMap;787 UEdgeRefMap uEdgeRefMap; 788 788 }; 789 789 … … 802 802 /// edges. 803 803 template <typename Target, typename Source> 804 U ndirGraphCopy<Target, Source>805 copyU ndirGraph(Target& target, const Source& source) {806 return U ndirGraphCopy<Target, Source>(target, source);804 UGraphCopy<Target, Source> 805 copyUGraph(Target& target, const Source& source) { 806 return UGraphCopy<Target, Source>(target, source); 807 807 } 808 808 … … 906 906 typedef _Graph Graph; 907 907 908 /// The key type of InvertableMap (Node, Edge, U ndirEdge).908 /// The key type of InvertableMap (Node, Edge, UEdge). 909 909 typedef typename _Map::Key Key; 910 910 /// The value type of the InvertableMap. … … 1037 1037 /// \param _Graph The graph class the \c DescriptorMap belongs to. 1038 1038 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or 1039 /// U ndirEdge.1039 /// UEdge. 1040 1040 #ifndef DOXYGEN 1041 1041 /// \param _Map A ReadWriteMap mapping from the item type to integer. … … 1056 1056 typedef _Graph Graph; 1057 1057 1058 /// The key type of DescriptorMap (Node, Edge, U ndirEdge).1058 /// The key type of DescriptorMap (Node, Edge, UEdge). 1059 1059 typedef typename _Map::Key Key; 1060 1060 /// The value type of DescriptorMap. … … 1297 1297 1298 1298 typedef typename Graph::Edge Value; 1299 typedef typename Graph::U ndirEdge Key;1299 typedef typename Graph::UEdge Key; 1300 1300 1301 1301 /// \brief Constructor … … 1336 1336 1337 1337 typedef typename Graph::Edge Value; 1338 typedef typename Graph::U ndirEdge Key;1338 typedef typename Graph::UEdge Key; 1339 1339 1340 1340 /// \brief Constructor
Note: See TracChangeset
for help on using the changeset viewer.