Changeset 431:4b6112235fad in lemon
 Timestamp:
 11/30/08 19:00:30 (12 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/digraph_adaptor.h
r430 r431 24 24 ///\brief Several digraph adaptors. 25 25 /// 26 ///This file contains several useful digraph adaptor functions.26 ///This file contains several useful digraph adaptor classes. 27 27 28 28 #include <lemon/core.h> … … 39 39 namespace lemon { 40 40 41 ///\brief Base type for the Digraph Adaptors42 ///43 ///Base type for the Digraph Adaptors44 ///45 ///This is the base type for most of LEMON digraph adaptors. This46 ///class implements a trivial digraph adaptor i.e. it only wraps the47 ///functions and types of the digraph. The purpose of this class is48 ///to make easier implementing digraph adaptors. E.g. if an adaptor49 ///is considered which differs from the wrapped digraph only in some50 ///of its functions or types, then it can be derived from51 ///DigraphAdaptor, and only the differences should be implemented.52 41 template<typename _Digraph> 53 42 class DigraphAdaptorBase { … … 167 156 }; 168 157 169 ///\ingroup graph_adaptors170 ///171 ///\brief Trivial Digraph Adaptor172 ///173 /// This class is an adaptor which does not change the adapted174 /// digraph. It can be used only to test the digraph adaptors.175 template <typename _Digraph>176 class DigraphAdaptor :177 public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {178 public:179 typedef _Digraph Digraph;180 typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;181 protected:182 DigraphAdaptor() : Parent() { }183 184 public:185 explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }186 };187 188 /// \brief Just gives back a digraph adaptor189 ///190 /// Just gives back a digraph adaptor which191 /// should be provide original digraph192 template<typename Digraph>193 DigraphAdaptor<const Digraph>194 digraphAdaptor(const Digraph& digraph) {195 return DigraphAdaptor<const Digraph>(digraph);196 }197 198 158 199 159 template <typename _Digraph> … … 232 192 /// If \c g is defined as 233 193 ///\code 234 /// ListDigraph g;194 /// ListDigraph dg; 235 195 ///\endcode 236 196 /// then 237 197 ///\code 238 /// RevDigraphAdaptor<ListDigraph> ga(g);198 /// RevDigraphAdaptor<ListDigraph> dga(dg); 239 199 ///\endcode 240 /// implements the digraph obtained from \c g by200 /// implements the digraph obtained from \c dg by 241 201 /// reversing the orientation of its arcs. 242 202 /// 243 /// A good example of using RevDigraphAdaptor is to decide that the 244 /// directed graph is wheter strongly connected or not. If from one 245 /// node each node is reachable and from each node is reachable this 246 /// node then and just then the digraph is strongly 247 /// connected. Instead of this condition we use a little bit 248 /// different. From one node each node ahould be reachable in the 249 /// digraph and in the reversed digraph. Now this condition can be 250 /// checked with the Dfs algorithm class and the RevDigraphAdaptor 251 /// algorithm class. 252 /// 253 /// And look at the code: 254 /// 203 /// A good example of using RevDigraphAdaptor is to decide whether 204 /// the directed graph is strongly connected or not. The digraph is 205 /// strongly connected iff each node is reachable from one node and 206 /// this node is reachable from the others. Instead of this 207 /// condition we use a slightly different, from one node each node 208 /// is reachable both in the digraph and the reversed digraph. Now 209 /// this condition can be checked with the Dfs algorithm and the 210 /// RevDigraphAdaptor class. 211 /// 212 /// The implementation: 255 213 ///\code 256 214 /// bool stronglyConnected(const Digraph& digraph) { … … 285 243 RevDigraphAdaptor() { } 286 244 public: 245 246 /// \brief Constructor 247 /// 248 /// Creates a reverse graph adaptor for the given digraph 287 249 explicit RevDigraphAdaptor(Digraph& digraph) { 288 250 Parent::setDigraph(digraph); … … 375 337 } 376 338 377 ///\e378 379 /// This function hides \c n in the digraph, i.e. the iteration380 /// jumps over it. This is done by simply setting the value of \c n381 /// to be false in the corresponding nodemap.382 339 void hide(const Node& n) const { _node_filter>set(n, false); } 383 384 ///\e385 386 /// This function hides \c a in the digraph, i.e. the iteration387 /// jumps over it. This is done by simply setting the value of \c a388 /// to be false in the corresponding arcmap.389 340 void hide(const Arc& a) const { _arc_filter>set(a, false); } 390 341 391 ///\e 392 393 /// The value of \c n is set to be true in the nodemap which stores 394 /// hide information. If \c n was hidden previuosly, then it is shown 395 /// again 396 void unHide(const Node& n) const { _node_filter>set(n, true); } 397 398 ///\e 399 400 /// The value of \c a is set to be true in the arcmap which stores 401 /// hide information. If \c a was hidden previuosly, then it is shown 402 /// again 342 void unHide(const Node& n) const { _node_filter>set(n, true); } 403 343 void unHide(const Arc& a) const { _arc_filter>set(a, true); } 404 344 405 /// Returns true if \c n is hidden.406 407 ///\e408 ///409 345 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 410 411 /// Returns true if \c a is hidden.412 413 ///\e414 ///415 346 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; } 416 347 … … 549 480 } 550 481 551 ///\e552 553 /// This function hides \c n in the digraph, i.e. the iteration554 /// jumps over it. This is done by simply setting the value of \c n555 /// to be false in the corresponding nodemap.556 482 void hide(const Node& n) const { _node_filter>set(n, false); } 557 558 ///\e559 560 /// This function hides \c e in the digraph, i.e. the iteration561 /// jumps over it. This is done by simply setting the value of \c e562 /// to be false in the corresponding arcmap.563 483 void hide(const Arc& e) const { _arc_filter>set(e, false); } 564 484 565 ///\e 566 567 /// The value of \c n is set to be true in the nodemap which stores 568 /// hide information. If \c n was hidden previuosly, then it is shown 569 /// again 570 void unHide(const Node& n) const { _node_filter>set(n, true); } 571 572 ///\e 573 574 /// The value of \c e is set to be true in the arcmap which stores 575 /// hide information. If \c e was hidden previuosly, then it is shown 576 /// again 485 void unHide(const Node& n) const { _node_filter>set(n, true); } 577 486 void unHide(const Arc& e) const { _arc_filter>set(e, true); } 578 487 579 /// Returns true if \c n is hidden.580 581 ///\e582 ///583 488 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 584 585 /// Returns true if \c n is hidden.586 587 ///\e588 ///589 489 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; } 590 490 … … 662 562 /// 663 563 /// SubDigraphAdaptor shows the digraph with filtered nodeset and 664 /// arcset. If the \c checked parameter is true then it filters the arcset 665 /// to do not get invalid arcs without source or target. 666 /// Let \f$ G=(V, A) \f$ be a directed digraph 667 /// and suppose that the digraph instance \c g of type ListDigraph 668 /// implements \f$ G \f$. 669 /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be boolvalued functions resp. 670 /// on the nodeset and arcset. 671 /// SubDigraphAdaptor<...>::NodeIt iterates 672 /// on the nodeset \f$ \{v\in V : b_V(v)=true\} \f$ and 673 /// SubDigraphAdaptor<...>::ArcIt iterates 674 /// on the arcset \f$ \{e\in A : b_A(e)=true\} \f$. Similarly, 675 /// SubDigraphAdaptor<...>::OutArcIt and 676 /// SubDigraphAdaptor<...>::InArcIt iterates 677 /// only on arcs leaving and entering a specific node which have true value. 564 /// arcset. If the \c checked parameter is true then it filters the arcset 565 /// respect to the source and target. 678 566 /// 679 /// If the \c checked template parameter is false then we have to680 /// no te that the nodeiterator cares only the filter onthe681 /// nodeset, and the arciterator cares only the filter on the682 /// arcset. This way the arcmap should filter all arcs which's683 /// source or target isfiltered by the nodefilter.567 /// If the \c checked template parameter is false then the 568 /// nodeiterator cares only the filter on the nodeset, and the 569 /// arciterator cares only the filter on the arcset. Therefore 570 /// the arcmap have to filter all arcs which's source or target is 571 /// filtered by the nodefilter. 684 572 ///\code 685 573 /// typedef ListDigraph Digraph; … … 694 582 /// BoolArcMap am(g, true); 695 583 /// am.set(a, false); 696 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> Sub GA;697 /// Sub GA ga(g, nm, am);698 /// for (Sub GA::NodeIt n(ga); n!=INVALID; ++n)584 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA; 585 /// SubDGA ga(g, nm, am); 586 /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n) 699 587 /// std::cout << g.id(n) << std::endl; 700 /// std::cout << ":)" << std::endl; 701 /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a) 588 /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a) 702 589 /// std::cout << g.id(a) << std::endl; 703 590 ///\endcode … … 705 592 ///\code 706 593 /// 1 707 /// :)708 594 /// 1 709 595 ///\endcode 710 /// Note that \c n is of type \c Sub GA::NodeIt, but it can be converted to596 /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to 711 597 /// \c Digraph::Node that is why \c g.id(n) can be applied. 712 598 /// … … 729 615 Parent; 730 616 617 typedef typename Parent::Node Node; 618 typedef typename Parent::Arc Arc; 619 731 620 protected: 732 621 SubDigraphAdaptor() { } 733 622 public: 734 623 624 /// \brief Constructor 625 /// 626 /// Creates a subdigraphadaptor for the given digraph with 627 /// given node and arc map filters. 735 628 SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter, 736 629 ArcFilterMap& arc_filter) { … … 740 633 } 741 634 635 /// \brief Hides the node of the graph 636 /// 637 /// This function hides \c n in the digraph, i.e. the iteration 638 /// jumps over it. This is done by simply setting the value of \c n 639 /// to be false in the corresponding nodemap. 640 void hide(const Node& n) const { Parent::hide(n); } 641 642 /// \brief Hides the arc of the graph 643 /// 644 /// This function hides \c a in the digraph, i.e. the iteration 645 /// jumps over it. This is done by simply setting the value of \c a 646 /// to be false in the corresponding arcmap. 647 void hide(const Arc& a) const { Parent::hide(a); } 648 649 /// \brief Unhides the node of the graph 650 /// 651 /// The value of \c n is set to be true in the nodemap which stores 652 /// hide information. If \c n was hidden previuosly, then it is shown 653 /// again 654 void unHide(const Node& n) const { Parent::unHide(n); } 655 656 /// \brief Unhides the arc of the graph 657 /// 658 /// The value of \c a is set to be true in the arcmap which stores 659 /// hide information. If \c a was hidden previuosly, then it is shown 660 /// again 661 void unHide(const Arc& a) const { Parent::unHide(a); } 662 663 /// \brief Returns true if \c n is hidden. 664 /// 665 /// Returns true if \c n is hidden. 666 /// 667 bool hidden(const Node& n) const { return Parent::hidden(n); } 668 669 /// \brief Returns true if \c a is hidden. 670 /// 671 /// Returns true if \c a is hidden. 672 /// 673 bool hidden(const Arc& a) const { return Parent::hidden(a); } 674 742 675 }; 743 676 744 /// \brief Just gives back a sub digraphadaptor745 /// 746 /// Just gives back a sub digraphadaptor677 /// \brief Just gives back a subdigraphadaptor 678 /// 679 /// Just gives back a subdigraphadaptor 747 680 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 748 681 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap> … … 775 708 return SubDigraphAdaptor<const Digraph, const NodeFilterMap, 776 709 const ArcFilterMap>(digraph, nfm, afm); 710 777 711 } 778 712 … … 803 737 Parent; 804 738 739 typedef typename Parent::Node Node; 740 805 741 protected: 806 742 ConstMap<typename Digraph::Arc, bool> const_true_map; … … 812 748 public: 813 749 750 /// \brief Constructor 751 /// 752 /// Creates a nodesubdigraphadaptor for the given digraph with 753 /// given node map filter. 814 754 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) : 815 755 Parent(), const_true_map(true) { … … 819 759 } 820 760 761 /// \brief Hides the node of the graph 762 /// 763 /// This function hides \c n in the digraph, i.e. the iteration 764 /// jumps over it. This is done by simply setting the value of \c n 765 /// to be false in the corresponding nodemap. 766 void hide(const Node& n) const { Parent::hide(n); } 767 768 /// \brief Unhides the node of the graph 769 /// 770 /// The value of \c n is set to be true in the nodemap which stores 771 /// hide information. If \c n was hidden previuosly, then it is shown 772 /// again 773 void unHide(const Node& n) const { Parent::unHide(n); } 774 775 /// \brief Returns true if \c n is hidden. 776 /// 777 /// Returns true if \c n is hidden. 778 /// 779 bool hidden(const Node& n) const { return Parent::hidden(n); } 780 821 781 }; 822 782 823 783 824 /// \brief Just gives back a \c NodeSubDigraphAdaptor825 /// 826 /// Just gives back a \c NodeSubDigraphAdaptor784 /// \brief Just gives back a nodesubdigraph adaptor 785 /// 786 /// Just gives back a nodesubdigraph adaptor 827 787 template<typename Digraph, typename NodeFilterMap> 828 788 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap> … … 847 807 ///in the problem of searching a maximum number of arcdisjoint 848 808 ///shortest paths between two nodes \c s and \c t. Shortest here 849 ///means being shortest w.r.t. nonnegative arclengths. Note that 850 ///the comprehension of the presented solution need's some 851 ///elementary knowlarc from combinatorial optimization. 809 ///means being shortest with respect to nonnegative 810 ///arclengths. Note that the comprehension of the presented 811 ///solution need's some elementary knowledge from combinatorial 812 ///optimization. 852 813 /// 853 814 ///If a single shortest path is to be searched between \c s and \c … … 869 830 /// 870 831 ///\dot 871 ///di digraph lemon_dot_example {832 ///digraph lemon_dot_example { 872 833 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 873 834 ///n0 [ label="0 (s)" ]; … … 975 936 typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>, 976 937 ArcFilterMap, false> Parent; 938 939 typedef typename Parent::Arc Arc; 940 977 941 protected: 978 942 ConstMap<typename Digraph::Node, bool> const_true_map; … … 984 948 public: 985 949 950 /// \brief Constructor 951 /// 952 /// Creates a arcsubdigraphadaptor for the given digraph with 953 /// given arc map filter. 986 954 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter) 987 955 : Parent(), const_true_map(true) { … … 991 959 } 992 960 961 /// \brief Hides the arc of the graph 962 /// 963 /// This function hides \c a in the digraph, i.e. the iteration 964 /// jumps over it. This is done by simply setting the value of \c a 965 /// to be false in the corresponding arcmap. 966 void hide(const Arc& a) const { Parent::hide(a); } 967 968 /// \brief Unhides the arc of the graph 969 /// 970 /// The value of \c a is set to be true in the arcmap which stores 971 /// hide information. If \c a was hidden previuosly, then it is shown 972 /// again 973 void unHide(const Arc& a) const { Parent::unHide(a); } 974 975 /// \brief Returns true if \c a is hidden. 976 /// 977 /// Returns true if \c a is hidden. 978 /// 979 bool hidden(const Arc& a) const { return Parent::hidden(a); } 980 993 981 }; 994 982 995 /// \brief Just gives back an arc subdigraph adaptor996 /// 997 /// Just gives back an arc subdigraph adaptor983 /// \brief Just gives back an arcsubdigraph adaptor 984 /// 985 /// Just gives back an arcsubdigraph adaptor 998 986 template<typename Digraph, typename ArcFilterMap> 999 987 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap> … … 1394 1382 ///\ingroup graph_adaptors 1395 1383 /// 1396 /// \brief A ngraph is made from a directed digraph by an adaptor1384 /// \brief A graph is made from a directed digraph by an adaptor 1397 1385 /// 1398 1386 /// This adaptor makes an undirected graph from a directed 1399 /// digraph. All arc of the underlying will be showed in the adaptor1400 /// a s an edge. Let's see an informal example about using1401 /// this adaptor :1387 /// graph. All arc of the underlying digraph will be showed in the 1388 /// adaptor as an edge. Let's see an informal example about using 1389 /// this adaptor. 1402 1390 /// 1403 1391 /// There is a network of the streets of a town. Of course there are … … 1803 1791 }; 1804 1792 1805 /// \brief Base class for split digraph adaptor1806 ///1807 /// Base class of split digraph adaptor. In most case you do not need to1808 /// use it directly but the documented member functions of this class can1809 /// be used with the SplitDigraphAdaptor class.1810 /// \sa SplitDigraphAdaptor1811 1793 template <typename _Digraph> 1812 1794 class SplitDigraphAdaptorBase { … … 2023 2005 } 2024 2006 2025 /// \brief Returns true when the node is innode.2026 ///2027 /// Returns true when the node is innode.2028 2007 static bool inNode(const Node& n) { 2029 2008 return n._in; 2030 2009 } 2031 2010 2032 /// \brief Returns true when the node is outnode.2033 ///2034 /// Returns true when the node is outnode.2035 2011 static bool outNode(const Node& n) { 2036 2012 return !n._in; 2037 2013 } 2038 2014 2039 /// \brief Returns true when the arc is arc in the original digraph.2040 ///2041 /// Returns true when the arc is arc in the original digraph.2042 2015 static bool origArc(const Arc& e) { 2043 2016 return e._item.firstState(); 2044 2017 } 2045 2018 2046 /// \brief Returns true when the arc binds an innode and an outnode.2047 ///2048 /// Returns true when the arc binds an innode and an outnode.2049 2019 static bool bindArc(const Arc& e) { 2050 2020 return e._item.secondState(); 2051 2021 } 2052 2022 2053 /// \brief Gives back the innode created from the \c node.2054 ///2055 /// Gives back the innode created from the \c node.2056 2023 static Node inNode(const DigraphNode& n) { 2057 2024 return Node(n, true); 2058 2025 } 2059 2026 2060 /// \brief Gives back the outnode created from the \c node.2061 ///2062 /// Gives back the outnode created from the \c node.2063 2027 static Node outNode(const DigraphNode& n) { 2064 2028 return Node(n, false); 2065 2029 } 2066 2030 2067 /// \brief Gives back the arc binds the two part of the node.2068 ///2069 /// Gives back the arc binds the two part of the node.2070 2031 static Arc arc(const DigraphNode& n) { 2071 2032 return Arc(n); 2072 2033 } 2073 2034 2074 /// \brief Gives back the arc of the original arc.2075 ///2076 /// Gives back the arc of the original arc.2077 2035 static Arc arc(const DigraphArc& e) { 2078 2036 return Arc(e); … … 2276 2234 /// bind arc in the adapted digraph. 2277 2235 /// 2278 /// By example a maximum flow algoritm can compute how many arc2236 /// For example a maximum flow algorithm can compute how many arc 2279 2237 /// disjoint paths are in the digraph. But we would like to know how 2280 2238 /// many node disjoint paths are in the digraph. First we have to … … 2331 2289 typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent; 2332 2290 2291 typedef typename Digraph::Node DigraphNode; 2292 typedef typename Digraph::Arc DigraphArc; 2293 2333 2294 typedef typename Parent::Node Node; 2334 2295 typedef typename Parent::Arc Arc; … … 2339 2300 SplitDigraphAdaptor(Digraph& g) { 2340 2301 Parent::setDigraph(g); 2302 } 2303 2304 /// \brief Returns true when the node is innode. 2305 /// 2306 /// Returns true when the node is innode. 2307 static bool inNode(const Node& n) { 2308 return Parent::inNode(n); 2309 } 2310 2311 /// \brief Returns true when the node is outnode. 2312 /// 2313 /// Returns true when the node is outnode. 2314 static bool outNode(const Node& n) { 2315 return Parent::outNode(n); 2316 } 2317 2318 /// \brief Returns true when the arc is arc in the original digraph. 2319 /// 2320 /// Returns true when the arc is arc in the original digraph. 2321 static bool origArc(const Arc& a) { 2322 return Parent::origArc(a); 2323 } 2324 2325 /// \brief Returns true when the arc binds an innode and an outnode. 2326 /// 2327 /// Returns true when the arc binds an innode and an outnode. 2328 static bool bindArc(const Arc& a) { 2329 return Parent::bindArc(a); 2330 } 2331 2332 /// \brief Gives back the innode created from the \c node. 2333 /// 2334 /// Gives back the innode created from the \c node. 2335 static Node inNode(const DigraphNode& n) { 2336 return Parent::inNode(n); 2337 } 2338 2339 /// \brief Gives back the outnode created from the \c node. 2340 /// 2341 /// Gives back the outnode created from the \c node. 2342 static Node outNode(const DigraphNode& n) { 2343 return Parent::outNode(n); 2344 } 2345 2346 /// \brief Gives back the arc binds the two part of the node. 2347 /// 2348 /// Gives back the arc binds the two part of the node. 2349 static Arc arc(const DigraphNode& n) { 2350 return Parent::arc(n); 2351 } 2352 2353 /// \brief Gives back the arc of the original arc. 2354 /// 2355 /// Gives back the arc of the original arc. 2356 static Arc arc(const DigraphArc& a) { 2357 return Parent::arc(a); 2341 2358 } 2342 2359 
lemon/graph_adaptor.h
r430 r431 32 32 namespace lemon { 33 33 34 /// \brief Base type for the Graph Adaptors35 ///36 /// This is the base type for most of LEMON graph adaptors.37 /// This class implements a trivial graph adaptor i.e. it only wraps the38 /// functions and types of the graph. The purpose of this class is to39 /// make easier implementing graph adaptors. E.g. if an adaptor is40 /// considered which differs from the wrapped graph only in some of its41 /// functions or types, then it can be derived from GraphAdaptor, and only42 /// the differences should be implemented.43 34 template<typename _Graph> 44 35 class GraphAdaptorBase { … … 196 187 }; 197 188 198 /// \ingroup graph_adaptors199 ///200 /// \brief Trivial graph adaptor201 ///202 /// This class is an adaptor which does not change the adapted undirected203 /// graph. It can be used only to test the graph adaptors.204 template <typename _Graph>205 class GraphAdaptor206 : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {207 public:208 typedef _Graph Graph;209 typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;210 protected:211 GraphAdaptor() : Parent() {}212 213 public:214 explicit GraphAdaptor(Graph& graph) { setGraph(graph); }215 };216 217 189 template <typename _Graph, typename NodeFilterMap, 218 190 typename EdgeFilterMap, bool checked = true> … … 319 291 } 320 292 321 /// \brief Hide the given node in the graph.322 ///323 /// This function hides \c n in the graph, i.e. the iteration324 /// jumps over it. This is done by simply setting the value of \c n325 /// to be false in the corresponding nodemap.326 293 void hide(const Node& n) const { _node_filter_map>set(n, false); } 327 328 /// \brief Hide the given edge in the graph.329 ///330 /// This function hides \c e in the graph, i.e. the iteration331 /// jumps over it. This is done by simply setting the value of \c e332 /// to be false in the corresponding edgemap.333 294 void hide(const Edge& e) const { _edge_filter_map>set(e, false); } 334 295 335 /// \brief Unhide the given node in the graph. 336 /// 337 /// The value of \c n is set to be true in the nodemap which stores 338 /// hide information. If \c n was hidden previuosly, then it is shown 339 /// again 340 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 341 342 /// \brief Hide the given edge in the graph. 343 /// 344 /// The value of \c e is set to be true in the edgemap which stores 345 /// hide information. If \c e was hidden previuosly, then it is shown 346 /// again 296 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 347 297 void unHide(const Edge& e) const { _edge_filter_map>set(e, true); } 348 298 349 /// \brief Returns true if \c n is hidden.350 ///351 /// Returns true if \c n is hidden.352 299 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 353 354 /// \brief Returns true if \c e is hidden.355 ///356 /// Returns true if \c e is hidden.357 300 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 358 301 … … 544 487 } 545 488 546 /// \brief Hide the given node in the graph.547 ///548 /// This function hides \c n in the graph, i.e. the iteration549 /// jumps over it. This is done by simply setting the value of \c n550 /// to be false in the corresponding nodemap.551 489 void hide(const Node& n) const { _node_filter_map>set(n, false); } 552 553 /// \brief Hide the given edge in the graph.554 ///555 /// This function hides \c e in the graph, i.e. the iteration556 /// jumps over it. This is done by simply setting the value of \c e557 /// to be false in the corresponding edgemap.558 490 void hide(const Edge& e) const { _edge_filter_map>set(e, false); } 559 491 560 /// \brief Unhide the given node in the graph. 561 /// 562 /// The value of \c n is set to be true in the nodemap which stores 563 /// hide information. If \c n was hidden previuosly, then it is shown 564 /// again 565 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 566 567 /// \brief Hide the given edge in the graph. 568 /// 569 /// The value of \c e is set to be true in the edgemap which stores 570 /// hide information. If \c e was hidden previuosly, then it is shown 571 /// again 492 void unHide(const Node& n) const { _node_filter_map>set(n, true); } 572 493 void unHide(const Edge& e) const { _edge_filter_map>set(e, true); } 573 494 574 /// \brief Returns true if \c n is hidden.575 ///576 /// Returns true if \c n is hidden.577 495 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 578 579 /// \brief Returns true if \c e is hidden.580 ///581 /// Returns true if \c e is hidden.582 496 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 583 497 … … 683 597 /// \ingroup graph_adaptors 684 598 /// 685 /// \brief A graph adaptor for hiding nodes and arcs from an599 /// \brief A graph adaptor for hiding nodes and edges from an 686 600 /// undirected graph. 687 601 /// … … 705 619 typedef GraphAdaptorExtender< 706 620 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 621 622 typedef typename Parent::Node Node; 623 typedef typename Parent::Edge Edge; 624 707 625 protected: 708 626 SubGraphAdaptor() { } 709 627 public: 628 629 /// \brief Constructor 630 /// 631 /// Creates a subgraphadaptor for the given graph with 632 /// given node and edge map filters. 710 633 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, 711 634 EdgeFilterMap& edge_filter_map) { … … 714 637 setEdgeFilterMap(edge_filter_map); 715 638 } 639 640 /// \brief Hides the node of the graph 641 /// 642 /// This function hides \c n in the digraph, i.e. the iteration 643 /// jumps over it. This is done by simply setting the value of \c n 644 /// to be false in the corresponding nodemap. 645 void hide(const Node& n) const { Parent::hide(n); } 646 647 /// \brief Hides the edge of the graph 648 /// 649 /// This function hides \c e in the digraph, i.e. the iteration 650 /// jumps over it. This is done by simply setting the value of \c e 651 /// to be false in the corresponding edgemap. 652 void hide(const Edge& e) const { Parent::hide(e); } 653 654 /// \brief Unhides the node of the graph 655 /// 656 /// The value of \c n is set to be true in the nodemap which stores 657 /// hide information. If \c n was hidden previuosly, then it is shown 658 /// again 659 void unHide(const Node& n) const { Parent::unHide(n); } 660 661 /// \brief Unhides the edge of the graph 662 /// 663 /// The value of \c e is set to be true in the edgemap which stores 664 /// hide information. If \c e was hidden previuosly, then it is shown 665 /// again 666 void unHide(const Edge& e) const { Parent::unHide(e); } 667 668 /// \brief Returns true if \c n is hidden. 669 /// 670 /// Returns true if \c n is hidden. 671 /// 672 bool hidden(const Node& n) const { return Parent::hidden(n); } 673 674 /// \brief Returns true if \c e is hidden. 675 /// 676 /// Returns true if \c e is hidden. 677 /// 678 bool hidden(const Edge& e) const { return Parent::hidden(e); } 716 679 }; 717 680 681 /// \brief Just gives back a subgraph adaptor 682 /// 683 /// Just gives back a subgraph adaptor 718 684 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 719 685 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap> … … 766 732 typedef SubGraphAdaptor<Graph, NodeFilterMap, 767 733 ConstMap<typename Graph::Edge, bool> > Parent; 734 735 typedef typename Parent::Node Node; 768 736 protected: 769 737 ConstMap<typename Graph::Edge, bool> const_true_map; … … 774 742 775 743 public: 744 745 /// \brief Constructor 746 /// 747 /// Creates a nodesubgraphadaptor for the given graph with 748 /// given node map filters. 776 749 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : 777 750 Parent(), const_true_map(true) { … … 780 753 Parent::setEdgeFilterMap(const_true_map); 781 754 } 755 756 /// \brief Hides the node of the graph 757 /// 758 /// This function hides \c n in the digraph, i.e. the iteration 759 /// jumps over it. This is done by simply setting the value of \c n 760 /// to be false in the corresponding nodemap. 761 void hide(const Node& n) const { Parent::hide(n); } 762 763 /// \brief Unhides the node of the graph 764 /// 765 /// The value of \c n is set to be true in the nodemap which stores 766 /// hide information. If \c n was hidden previuosly, then it is shown 767 /// again 768 void unHide(const Node& n) const { Parent::unHide(n); } 769 770 /// \brief Returns true if \c n is hidden. 771 /// 772 /// Returns true if \c n is hidden. 773 /// 774 bool hidden(const Node& n) const { return Parent::hidden(n); } 775 782 776 }; 783 777 778 /// \brief Just gives back a nodesubgraph adaptor 779 /// 780 /// Just gives back a nodesubgraph adaptor 784 781 template<typename Graph, typename NodeFilterMap> 785 782 NodeSubGraphAdaptor<const Graph, NodeFilterMap> … … 814 811 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 815 812 EdgeFilterMap, false> Parent; 813 typedef typename Parent::Edge Edge; 816 814 protected: 817 815 ConstMap<typename Graph::Node, bool> const_true_map; … … 823 821 public: 824 822 823 /// \brief Constructor 824 /// 825 /// Creates a edgesubgraphadaptor for the given graph with 826 /// given node map filters. 825 827 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) : 826 828 Parent(), const_true_map(true) { … … 830 832 } 831 833 834 /// \brief Hides the edge of the graph 835 /// 836 /// This function hides \c e in the digraph, i.e. the iteration 837 /// jumps over it. This is done by simply setting the value of \c e 838 /// to be false in the corresponding edgemap. 839 void hide(const Edge& e) const { Parent::hide(e); } 840 841 /// \brief Unhides the edge of the graph 842 /// 843 /// The value of \c e is set to be true in the edgemap which stores 844 /// hide information. If \c e was hidden previuosly, then it is shown 845 /// again 846 void unHide(const Edge& e) const { Parent::unHide(e); } 847 848 /// \brief Returns true if \c e is hidden. 849 /// 850 /// Returns true if \c e is hidden. 851 /// 852 bool hidden(const Edge& e) const { return Parent::hidden(e); } 853 832 854 }; 833 855 856 /// \brief Just gives back an edgesubgraph adaptor 857 /// 858 /// Just gives back an edgesubgraph adaptor 834 859 template<typename Graph, typename EdgeFilterMap> 835 860 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap> … … 844 869 } 845 870 846 /// \brief Base of direct graph adaptor847 ///848 /// Base class of the direct graph adaptor. All public member849 /// of this class can be used with the DirGraphAdaptor too.850 /// \sa DirGraphAdaptor851 871 template <typename _Graph, typename _DirectionMap> 852 872 class DirGraphAdaptorBase { … … 1104 1124 typedef DigraphAdaptorExtender< 1105 1125 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent; 1126 typedef typename Parent::Arc Arc; 1106 1127 protected: 1107 1128 DirGraphAdaptor() { } … … 1114 1135 setGraph(graph); 1115 1136 setDirectionMap(direction); 1137 } 1138 1139 /// \brief Reverse arc 1140 /// 1141 /// It reverse the given arc. It simply negate the direction in the map. 1142 void reverseArc(const Arc& a) { 1143 Parent::reverseArc(a); 1116 1144 } 1117 1145 }; 
test/graph_adaptor_test.cc
r430 r431 38 38 using namespace lemon; 39 39 40 void checkDigraphAdaptor() {41 checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();42 43 typedef ListDigraph Digraph;44 typedef DigraphAdaptor<Digraph> Adaptor;45 46 Digraph digraph;47 Adaptor adaptor(digraph);48 49 Digraph::Node n1 = digraph.addNode();50 Digraph::Node n2 = digraph.addNode();51 Digraph::Node n3 = digraph.addNode();52 53 Digraph::Arc a1 = digraph.addArc(n1, n2);54 Digraph::Arc a2 = digraph.addArc(n1, n3);55 Digraph::Arc a3 = digraph.addArc(n2, n3);56 57 checkGraphNodeList(adaptor, 3);58 checkGraphArcList(adaptor, 3);59 checkGraphConArcList(adaptor, 3);60 61 checkGraphOutArcList(adaptor, n1, 2);62 checkGraphOutArcList(adaptor, n2, 1);63 checkGraphOutArcList(adaptor, n3, 0);64 65 checkGraphInArcList(adaptor, n1, 0);66 checkGraphInArcList(adaptor, n2, 1);67 checkGraphInArcList(adaptor, n3, 2);68 69 checkNodeIds(adaptor);70 checkArcIds(adaptor);71 72 checkGraphNodeMap(adaptor);73 checkGraphArcMap(adaptor);74 }75 76 40 void checkRevDigraphAdaptor() { 77 41 checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >(); … … 586 550 } 587 551 588 void checkGraphAdaptor() {589 checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();590 591 typedef ListGraph Graph;592 typedef GraphAdaptor<Graph> Adaptor;593 594 Graph graph;595 Adaptor adaptor(graph);596 597 Graph::Node n1 = graph.addNode();598 Graph::Node n2 = graph.addNode();599 Graph::Node n3 = graph.addNode();600 Graph::Node n4 = graph.addNode();601 602 Graph::Edge a1 = graph.addEdge(n1, n2);603 Graph::Edge a2 = graph.addEdge(n1, n3);604 Graph::Edge a3 = graph.addEdge(n2, n3);605 Graph::Edge a4 = graph.addEdge(n3, n4);606 607 checkGraphNodeList(adaptor, 4);608 checkGraphArcList(adaptor, 8);609 checkGraphEdgeList(adaptor, 4);610 checkGraphConArcList(adaptor, 8);611 checkGraphConEdgeList(adaptor, 4);612 613 checkGraphOutArcList(adaptor, n1, 2);614 checkGraphOutArcList(adaptor, n2, 2);615 checkGraphOutArcList(adaptor, n3, 3);616 checkGraphOutArcList(adaptor, n4, 1);617 618 checkGraphInArcList(adaptor, n1, 2);619 checkGraphInArcList(adaptor, n2, 2);620 checkGraphInArcList(adaptor, n3, 3);621 checkGraphInArcList(adaptor, n4, 1);622 623 checkGraphIncEdgeList(adaptor, n1, 2);624 checkGraphIncEdgeList(adaptor, n2, 2);625 checkGraphIncEdgeList(adaptor, n3, 3);626 checkGraphIncEdgeList(adaptor, n4, 1);627 628 629 checkNodeIds(adaptor);630 checkArcIds(adaptor);631 checkEdgeIds(adaptor);632 633 checkGraphNodeMap(adaptor);634 checkGraphArcMap(adaptor);635 checkGraphEdgeMap(adaptor);636 }637 638 552 void checkSubGraphAdaptor() { 639 553 checkConcept<concepts::Graph, … … 1054 968 int main(int, const char **) { 1055 969 1056 checkDigraphAdaptor();1057 970 checkRevDigraphAdaptor(); 1058 971 checkSubDigraphAdaptor(); … … 1063 976 checkSplitDigraphAdaptor(); 1064 977 1065 checkGraphAdaptor();1066 978 checkSubGraphAdaptor(); 1067 979 checkNodeSubGraphAdaptor();
Note: See TracChangeset
for help on using the changeset viewer.