Changeset 1128:426a704d7483 in lemon
- Timestamp:
- 01/20/12 19:23:48 (13 years ago)
- Branch:
- default
- Parents:
- 1124:b1744d7bdb47 (diff), 1125:b873350e6258 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r1111 r1128 67 67 # C4996: 'function': was declared deprecated 68 68 ELSE() 69 SET(CXX_WARNING "-Wall -W")69 SET(CXX_WARNING "-Wall") 70 70 ENDIF() 71 71 ENDIF() … … 74 74 SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}") 75 75 76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb " CACHE STRING76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING 77 77 "Flags used by the C++ compiler during maintainer builds." 78 78 FORCE ) 79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror " CACHE STRING79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING 80 80 "Flags used by the C compiler during maintainer builds." 81 81 FORCE ) -
CMakeLists.txt
r1125 r1128 125 125 ADD_SUBDIRECTORY(lemon) 126 126 IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR}) 127 ADD_SUBDIRECTORY(contrib) 127 128 ADD_SUBDIRECTORY(demo) 128 129 ADD_SUBDIRECTORY(tools) -
lemon/bfs.h
r956 r1127 1252 1252 } 1253 1253 _Visitor& visitor; 1254 Constraints() {} 1254 1255 }; 1255 1256 }; -
lemon/bfs.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the shortest paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 88 ///Instantiates a \c ReachedMap. … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 103 ///Instantiates a \c DistMap. … … 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref BfsDefaultTraits 127 ///"BfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 123 130 #ifdef DOXYGEN 124 131 template <typename GR, … … 226 233 ///\ref named-templ-param "Named parameter" for setting 227 234 ///\c PredMap type. 228 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 229 236 template <class T> 230 237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > { … … 246 253 ///\ref named-templ-param "Named parameter" for setting 247 254 ///\c DistMap type. 248 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 249 256 template <class T> 250 257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > { … … 266 273 ///\ref named-templ-param "Named parameter" for setting 267 274 ///\c ReachedMap type. 268 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 275 ///It must conform to 276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 269 277 template <class T> 270 278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > { … … 286 294 ///\ref named-templ-param "Named parameter" for setting 287 295 ///\c ProcessedMap type. 288 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 289 297 template <class T> 290 298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > { … … 414 422 ///The simplest way to execute the BFS algorithm is to use one of the 415 423 ///member functions called \ref run(Node) "run()".\n 416 ///If you need more control on the execution, firstyou have to call417 ///\ref init() , then you can add several source nodes with424 ///If you need better control on the execution, you have to call 425 ///\ref init() first, then you can add several source nodes with 418 426 ///\ref addSource(). Finally the actual path computation can be 419 427 ///performed with one of the \ref start() functions. … … 701 709 ///Runs the algorithm to visit all nodes in the digraph. 702 710 703 ///This method runs the %BFS algorithm in order to 704 ///compute the shortest path to each node. 705 /// 706 ///The algorithm computes 707 ///- the shortest path tree (forest), 708 ///- the distance of each node from the root(s). 711 ///This method runs the %BFS algorithm in order to visit all nodes 712 ///in the digraph. 709 713 /// 710 714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 738 742 ///@{ 739 743 740 ///The shortest path to anode.741 742 ///Returns the shortest path to a node.744 ///The shortest path to the given node. 745 746 ///Returns the shortest path to the given node from the root(s). 743 747 /// 744 748 ///\warning \c t should be reached from the root(s). … … 748 752 Path path(Node t) const { return Path(*G, *_pred, t); } 749 753 750 ///The distance of anode from the root(s).751 752 ///Returns the distance of anode from the root(s).754 ///The distance of the given node from the root(s). 755 756 ///Returns the distance of the given node from the root(s). 753 757 /// 754 758 ///\warning If node \c v is not reached from the root(s), then … … 759 763 int dist(Node v) const { return (*_dist)[v]; } 760 764 761 ///Returns the 'previous arc' of the shortest path tree for a node. 762 765 ///\brief Returns the 'previous arc' of the shortest path tree for 766 ///the given node. 767 /// 763 768 ///This function returns the 'previous arc' of the shortest path 764 769 ///tree for the node \c v, i.e. it returns the last arc of a … … 767 772 /// 768 773 ///The shortest path tree used here is equal to the shortest path 769 ///tree used in \ref predNode() .774 ///tree used in \ref predNode() and \ref predMap(). 770 775 /// 771 776 ///\pre Either \ref run(Node) "run()" or \ref init() … … 773 778 Arc predArc(Node v) const { return (*_pred)[v];} 774 779 775 ///Returns the 'previous node' of the shortest path tree for a node. 776 780 ///\brief Returns the 'previous node' of the shortest path tree for 781 ///the given node. 782 /// 777 783 ///This function returns the 'previous node' of the shortest path 778 784 ///tree for the node \c v, i.e. it returns the last but one node 779 /// froma shortest path from a root to \c v. It is \c INVALID785 ///of a shortest path from a root to \c v. It is \c INVALID 780 786 ///if \c v is not reached from the root(s) or if \c v is a root. 781 787 /// 782 788 ///The shortest path tree used here is equal to the shortest path 783 ///tree used in \ref predArc() .789 ///tree used in \ref predArc() and \ref predMap(). 784 790 /// 785 791 ///\pre Either \ref run(Node) "run()" or \ref init() … … 802 808 /// 803 809 ///Returns a const reference to the node map that stores the predecessor 804 ///arcs, which form the shortest path tree .810 ///arcs, which form the shortest path tree (forest). 805 811 /// 806 812 ///\pre Either \ref run(Node) "run()" or \ref init() … … 808 814 const PredMap &predMap() const { return *_pred;} 809 815 810 ///Checks if anode is reached from the root(s).816 ///Checks if the given node is reached from the root(s). 811 817 812 818 ///Returns \c true if \c v is reached from the root(s). … … 834 840 ///The type of the map that stores the predecessor 835 841 ///arcs of the shortest paths. 836 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.842 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 837 843 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 838 844 ///Instantiates a PredMap. … … 849 855 850 856 ///The type of the map that indicates which nodes are processed. 851 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.852 ///By default it is a NullMap.857 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 858 ///By default, it is a NullMap. 853 859 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 854 860 ///Instantiates a ProcessedMap. … … 869 875 870 876 ///The type of the map that indicates which nodes are reached. 871 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 877 ///It must conform to 878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 872 879 typedef typename Digraph::template NodeMap<bool> ReachedMap; 873 880 ///Instantiates a ReachedMap. … … 884 891 885 892 ///The type of the map that stores the distances of the nodes. 886 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.893 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 887 894 typedef typename Digraph::template NodeMap<int> DistMap; 888 895 ///Instantiates a DistMap. … … 899 906 900 907 ///The type of the shortest paths. 901 ///It must meetthe \ref concepts::Path "Path" concept.908 ///It must conform to the \ref concepts::Path "Path" concept. 902 909 typedef lemon::Path<Digraph> Path; 903 910 }; … … 905 912 /// Default traits class used by BfsWizard 906 913 907 /// To make it easier to use Bfs algorithm 908 /// we have created a wizard class. 909 /// This \ref BfsWizard class needs default traits, 910 /// as well as the \ref Bfs class. 911 /// The \ref BfsWizardBase is a class to be the default traits of the 912 /// \ref BfsWizard class. 914 /// Default traits class used by BfsWizard. 915 /// \tparam GR The type of the digraph. 913 916 template<class GR> 914 917 class BfsWizardBase : public BfsWizardDefaultTraits<GR> … … 938 941 /// Constructor. 939 942 940 /// This constructor does not require parameters, thereforeit initiates943 /// This constructor does not require parameters, it initiates 941 944 /// all of the attributes to \c 0. 942 945 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 963 966 /// This class should only be used through the \ref bfs() function, 964 967 /// which makes it easier to use the algorithm. 968 /// 969 /// \tparam TR The traits class that defines various types used by the 970 /// algorithm. 965 971 template<class TR> 966 972 class BfsWizard : public TR … … 968 974 typedef TR Base; 969 975 970 ///The type of the digraph the algorithm runs on.971 976 typedef typename TR::Digraph Digraph; 972 977 … … 976 981 typedef typename Digraph::OutArcIt OutArcIt; 977 982 978 ///\brief The type of the map that stores the predecessor979 ///arcs of the shortest paths.980 983 typedef typename TR::PredMap PredMap; 981 ///\brief The type of the map that stores the distances of the nodes.982 984 typedef typename TR::DistMap DistMap; 983 ///\brief The type of the map that indicates which nodes are reached.984 985 typedef typename TR::ReachedMap ReachedMap; 985 ///\brief The type of the map that indicates which nodes are processed.986 986 typedef typename TR::ProcessedMap ProcessedMap; 987 ///The type of the shortest paths988 987 typedef typename TR::Path Path; 989 988 … … 1055 1054 ///Runs BFS algorithm to visit all nodes in the digraph. 1056 1055 1057 ///This method runs BFS algorithm in order to compute1058 /// the shortest path to each node.1056 ///This method runs BFS algorithm in order to visit all nodes 1057 ///in the digraph. 1059 1058 void run() 1060 1059 { … … 1068 1067 SetPredMapBase(const TR &b) : TR(b) {} 1069 1068 }; 1070 ///\brief \ref named-func-param "Named parameter" 1071 ///for setting PredMap object. 1072 /// 1073 ///\ref named-func-param "Named parameter" 1074 ///for setting PredMap object. 1069 1070 ///\brief \ref named-templ-param "Named parameter" for setting 1071 ///the predecessor map. 1072 /// 1073 ///\ref named-templ-param "Named parameter" function for setting 1074 ///the map that stores the predecessor arcs of the nodes. 1075 1075 template<class T> 1076 1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1086 1086 SetReachedMapBase(const TR &b) : TR(b) {} 1087 1087 }; 1088 ///\brief \ref named-func-param "Named parameter" 1089 ///for setting ReachedMap object. 1090 /// 1091 /// \ref named-func-param "Named parameter" 1092 ///for setting ReachedMap object. 1088 1089 ///\brief \ref named-templ-param "Named parameter" for setting 1090 ///the reached map. 1091 /// 1092 ///\ref named-templ-param "Named parameter" function for setting 1093 ///the map that indicates which nodes are reached. 1093 1094 template<class T> 1094 1095 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1104 1105 SetDistMapBase(const TR &b) : TR(b) {} 1105 1106 }; 1106 ///\brief \ref named-func-param "Named parameter" 1107 ///for setting DistMap object. 1108 /// 1109 /// \ref named-func-param "Named parameter" 1110 ///for setting DistMap object. 1107 1108 ///\brief \ref named-templ-param "Named parameter" for setting 1109 ///the distance map. 1110 /// 1111 ///\ref named-templ-param "Named parameter" function for setting 1112 ///the map that stores the distances of the nodes calculated 1113 ///by the algorithm. 1111 1114 template<class T> 1112 1115 BfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1122 1125 SetProcessedMapBase(const TR &b) : TR(b) {} 1123 1126 }; 1124 ///\brief \ref named-func-param "Named parameter" 1125 ///for setting ProcessedMap object. 1126 /// 1127 /// \ref named-func-param "Named parameter" 1128 ///for setting ProcessedMap object. 1127 1128 ///\brief \ref named-func-param "Named parameter" for setting 1129 ///the processed map. 1130 /// 1131 ///\ref named-templ-param "Named parameter" function for setting 1132 ///the map that indicates which nodes are processed. 1129 1133 template<class T> 1130 1134 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1266 1270 /// 1267 1271 /// The type of the map that indicates which nodes are reached. 1268 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1272 /// It must conform to 1273 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1269 1274 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1270 1275 … … 1304 1309 /// does not observe the BFS events. If you want to observe the BFS 1305 1310 /// events, you should implement your own visitor class. 1306 /// \tparam TR T raits class to set various datatypes used by the1307 /// algorithm. The default traits class is1308 /// \ref BfsVisitDefaultTraits"BfsVisitDefaultTraits<GR>".1309 /// See \ref BfsVisitDefaultTraits for the documentation of1310 /// a BFS visit traits class.1311 /// \tparam TR The traits class that defines various types used by the 1312 /// algorithm. By default, it is \ref BfsVisitDefaultTraits 1313 /// "BfsVisitDefaultTraits<GR>". 1314 /// In most cases, this parameter should not be set directly, 1315 /// consider to use the named template parameters instead. 1311 1316 #ifdef DOXYGEN 1312 1317 template <typename GR, typename VS, typename TR> … … 1427 1432 /// The simplest way to execute the BFS algorithm is to use one of the 1428 1433 /// member functions called \ref run(Node) "run()".\n 1429 /// If you need more control on the execution, firstyou have to call1430 /// \ref init() , then you can add several source nodes with1434 /// If you need better control on the execution, you have to call 1435 /// \ref init() first, then you can add several source nodes with 1431 1436 /// \ref addSource(). Finally the actual path computation can be 1432 1437 /// performed with one of the \ref start() functions. … … 1700 1705 /// \brief Runs the algorithm to visit all nodes in the digraph. 1701 1706 /// 1702 /// This method runs the %BFS algorithm in order to 1703 /// compute the shortest path to each node. 1704 /// 1705 /// The algorithm computes 1706 /// - the shortest path tree (forest), 1707 /// - the distance of each node from the root(s). 1707 /// This method runs the %BFS algorithm in order to visit all nodes 1708 /// in the digraph. 1708 1709 /// 1709 1710 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code. … … 1737 1738 ///@{ 1738 1739 1739 /// \brief Checks if anode is reached from the root(s).1740 /// \brief Checks if the given node is reached from the root(s). 1740 1741 /// 1741 1742 /// Returns \c true if \c v is reached from the root(s). -
lemon/concepts/graph_components.h
r956 r1127 116 116 const _GraphItem &ia; 117 117 const _GraphItem &ib; 118 Constraints() {} 118 119 }; 119 120 }; … … 175 176 176 177 const _Digraph& digraph; 178 Constraints() {} 177 179 }; 178 180 }; … … 291 293 292 294 const _Graph& graph; 295 Constraints() {} 293 296 }; 294 297 … … 370 373 371 374 const _Digraph& digraph; 375 Constraints() {} 372 376 }; 373 377 }; … … 422 426 423 427 const _Graph& graph; 428 Constraints() {} 424 429 }; 425 430 }; … … 499 504 } 500 505 const GR& g; 506 Constraints() {} 501 507 }; 502 508 }; … … 587 593 const Base& node; 588 594 const GR& graph; 595 Constraints() {} 589 596 }; 590 597 }; … … 763 770 764 771 const _Digraph& digraph; 772 Constraints() {} 765 773 }; 766 774 }; … … 887 895 888 896 const _Graph& graph; 897 Constraints() {} 889 898 }; 890 899 }; … … 944 953 945 954 const _Digraph& digraph; 955 Constraints() {} 946 956 }; 947 957 }; … … 985 995 986 996 const _Graph& graph; 997 Constraints() {} 987 998 }; 988 999 }; … … 1062 1073 const GR &g; 1063 1074 const typename GraphMap::Value &t; 1075 Constraints() {} 1064 1076 }; 1065 1077 … … 1200 1212 1201 1213 const _Digraph& digraph; 1214 Constraints() {} 1202 1215 }; 1203 1216 }; … … 1285 1298 1286 1299 const _Graph& graph; 1300 Constraints() {} 1287 1301 }; 1288 1302 }; … … 1329 1343 1330 1344 _Digraph& digraph; 1345 Constraints() {} 1331 1346 }; 1332 1347 }; … … 1373 1388 1374 1389 _Graph& graph; 1390 Constraints() {} 1375 1391 }; 1376 1392 }; … … 1412 1428 1413 1429 _Digraph& digraph; 1430 Constraints() {} 1414 1431 }; 1415 1432 }; … … 1451 1468 1452 1469 _Graph& graph; 1470 Constraints() {} 1453 1471 }; 1454 1472 }; … … 1479 1497 1480 1498 _Digraph& digraph; 1499 Constraints() {} 1481 1500 }; 1482 1501 }; … … 1507 1526 1508 1527 _Graph& graph; 1528 Constraints() {} 1509 1529 }; 1510 1530 }; -
lemon/concepts/graph_components.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 19 19 ///\ingroup graph_concepts 20 20 ///\file 21 ///\brief The concept of graph components.21 ///\brief The concepts of graph components. 22 22 23 23 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H … … 39 39 /// \note This class is a template class so that we can use it to 40 40 /// create graph skeleton classes. The reason for this is that \c Node 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 41 /// and \c Arc (or \c Edge) types should \e not derive from the same 42 42 /// base class. For \c Node you should instantiate it with character 43 43 /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. … … 90 90 /// 91 91 /// This operator defines an ordering of the items. 92 /// It makes possible to use graph item types as key types in 92 /// It makes possible to use graph item types as key types in 93 93 /// associative containers (e.g. \c std::map). 94 94 /// 95 /// \note This operator only ha veto define some strict ordering of95 /// \note This operator only has to define some strict ordering of 96 96 /// the items; this order has nothing to do with the iteration 97 97 /// ordering of the items. … … 124 124 /// This class describes the base interface of directed graph types. 125 125 /// All digraph %concepts have to conform to this class. 126 /// It just provides types for nodes and arcs and functions 126 /// It just provides types for nodes and arcs and functions 127 127 /// to get the source and the target nodes of arcs. 128 128 class BaseDigraphComponent { … … 432 432 /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. 433 433 /// 434 /// This class describes the concept of \c NodeIt, \c ArcIt and 434 /// This class describes the concept of \c NodeIt, \c ArcIt and 435 435 /// \c EdgeIt subtypes of digraph and graph types. 436 436 template <typename GR, typename Item> … … 472 472 /// next item. 473 473 GraphItemIt& operator++() { return *this; } 474 474 475 475 /// \brief Equality operator 476 476 /// … … 508 508 }; 509 509 510 /// \brief Concept class for \c InArcIt, \c OutArcIt and 510 /// \brief Concept class for \c InArcIt, \c OutArcIt and 511 511 /// \c IncEdgeIt types. 512 512 /// 513 /// This class describes the concept of \c InArcIt, \c OutArcIt 513 /// This class describes the concept of \c InArcIt, \c OutArcIt 514 514 /// and \c IncEdgeIt subtypes of digraph and graph types. 515 515 /// 516 516 /// \note Since these iterator classes do not inherit from the same 517 517 /// base class, there is an additional template parameter (selector) 518 /// \c sel. For \c InArcIt you should instantiate it with character 518 /// \c sel. For \c InArcIt you should instantiate it with character 519 519 /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. 520 520 template <typename GR, … … 537 537 GraphIncIt(const GraphIncIt& it) : Item(it) {} 538 538 539 /// \brief Constructor that sets the iterator to the first 539 /// \brief Constructor that sets the iterator to the first 540 540 /// incoming or outgoing arc. 541 541 /// 542 /// Constructor that sets the iterator to the first arc 542 /// Constructor that sets the iterator to the first arc 543 543 /// incoming to or outgoing from the given node. 544 544 explicit GraphIncIt(const GR&, const Base&) {} … … 813 813 /// \brief Return the first edge incident to the given node. 814 814 /// 815 /// This function gives back the first edge incident to the given 815 /// This function gives back the first edge incident to the given 816 816 /// node. The bool parameter gives back the direction for which the 817 /// source node of the directed arc representing the edge is the 817 /// source node of the directed arc representing the edge is the 818 818 /// given node. 819 819 void firstInc(Edge&, bool&, const Node&) const {} … … 822 822 /// given node. 823 823 /// 824 /// This function gives back the next edge incident to the given 824 /// This function gives back the next edge incident to the given 825 825 /// node. The bool parameter should be used as \c firstInc() use it. 826 826 void nextInc(Edge&, bool&) const {} … … 1002 1002 /// 1003 1003 /// This class describes the concept of standard graph maps, i.e. 1004 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1004 /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 1005 1005 /// graph types, which can be used for associating data to graph items. 1006 1006 /// The standard graph maps must conform to the ReferenceMap concept. … … 1057 1057 _Map m1(g); 1058 1058 _Map m2(g,t); 1059 1059 1060 1060 // Copy constructor 1061 1061 // _Map m3(m); … … 1081 1081 /// 1082 1082 /// This class describes the interface of mappable directed graphs. 1083 /// It extends \ref BaseDigraphComponent with the standard digraph 1083 /// It extends \ref BaseDigraphComponent with the standard digraph 1084 1084 /// map classes, namely \c NodeMap and \c ArcMap. 1085 1085 /// This concept is part of the Digraph concept. … … 1219 1219 /// 1220 1220 /// This class describes the interface of mappable undirected graphs. 1221 /// It extends \ref MappableDigraphComponent with the standard graph 1221 /// It extends \ref MappableDigraphComponent with the standard graph 1222 1222 /// map class for edges (\c EdgeMap). 1223 1223 /// This concept is part of the Graph concept. … … 1305 1305 /// 1306 1306 /// This class describes the interface of extendable directed graphs. 1307 /// It extends \ref BaseDigraphComponent with functions for adding 1307 /// It extends \ref BaseDigraphComponent with functions for adding 1308 1308 /// nodes and arcs to the digraph. 1309 1309 /// This concept requires \ref AlterableDigraphComponent. … … 1350 1350 /// 1351 1351 /// This class describes the interface of extendable undirected graphs. 1352 /// It extends \ref BaseGraphComponent with functions for adding 1352 /// It extends \ref BaseGraphComponent with functions for adding 1353 1353 /// nodes and edges to the graph. 1354 1354 /// This concept requires \ref AlterableGraphComponent. … … 1395 1395 /// 1396 1396 /// This class describes the interface of erasable directed graphs. 1397 /// It extends \ref BaseDigraphComponent with functions for removing 1397 /// It extends \ref BaseDigraphComponent with functions for removing 1398 1398 /// nodes and arcs from the digraph. 1399 1399 /// This concept requires \ref AlterableDigraphComponent. … … 1408 1408 /// \brief Erase a node from the digraph. 1409 1409 /// 1410 /// This function erases the given node from the digraph and all arcs 1410 /// This function erases the given node from the digraph and all arcs 1411 1411 /// connected to the node. 1412 1412 void erase(const Node&) {} … … 1435 1435 /// 1436 1436 /// This class describes the interface of erasable undirected graphs. 1437 /// It extends \ref BaseGraphComponent with functions for removing 1437 /// It extends \ref BaseGraphComponent with functions for removing 1438 1438 /// nodes and edges from the graph. 1439 1439 /// This concept requires \ref AlterableGraphComponent. -
lemon/concepts/heap.h
r956 r1127 315 315 _Heap& heap; 316 316 ItemIntMap& map; 317 Constraints() {} 317 318 }; 318 319 }; -
lemon/concepts/heap.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 17 17 */ 18 18 19 #ifndef LEMON_CONCEPTS_HEAP_H 20 #define LEMON_CONCEPTS_HEAP_H 21 19 22 ///\ingroup concept 20 23 ///\file 21 24 ///\brief The concept of heaps. 22 25 23 #ifndef LEMON_CONCEPTS_HEAP_H24 #define LEMON_CONCEPTS_HEAP_H25 26 26 #include <lemon/core.h> 27 27 #include <lemon/concept_check.h> … … 36 36 /// \brief The heap concept. 37 37 /// 38 /// Concept class describing the main interface of heaps. A \e heap 39 /// is a data structure for storing items with specified values called 40 /// \e priorities in such a way that finding the item with minimum 41 /// priority is efficient. In a heap one can change the priority of an 42 /// item, add or erase an item, etc. 38 /// This concept class describes the main interface of heaps. 39 /// The various \ref heaps "heap structures" are efficient 40 /// implementations of the abstract data type \e priority \e queue. 41 /// They store items with specified values called \e priorities 42 /// in such a way that finding and removing the item with minimum 43 /// priority are efficient. The basic operations are adding and 44 /// erasing items, changing the priority of an item, etc. 43 45 /// 44 /// \tparam PR Type of the priority of the items. 45 /// \tparam IM A read and writable item map with int values, used 46 /// Heaps are crucial in several algorithms, such as Dijkstra and Prim. 47 /// Any class that conforms to this concept can be used easily in such 48 /// algorithms. 49 /// 50 /// \tparam PR Type of the priorities of the items. 51 /// \tparam IM A read-writable item map with \c int values, used 46 52 /// internally to handle the cross references. 47 /// \tparam C omp A functor class for the ordering ofthe priorities.53 /// \tparam CMP A functor class for comparing the priorities. 48 54 /// The default is \c std::less<PR>. 49 55 #ifdef DOXYGEN 50 template <typename PR, typename IM, typename C omp = std::less<PR>>51 #else 52 template <typename PR, typename IM >56 template <typename PR, typename IM, typename CMP> 57 #else 58 template <typename PR, typename IM, typename CMP = std::less<PR> > 53 59 #endif 54 60 class Heap { … … 65 71 /// 66 72 /// Each item has a state associated to it. It can be "in heap", 67 /// "pre heap" or "post heap". The later two are indifferent 68 /// from the point of view of the heap, but may be useful for 69 /// the user. 73 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 /// heap's point of view, but may be useful to the user. 70 75 /// 71 76 /// The item-int map must be initialized in such way that it assigns … … 73 78 enum State { 74 79 IN_HEAP = 0, ///< = 0. The "in heap" state constant. 75 PRE_HEAP = -1, ///< = -1. The "pre 76 POST_HEAP = -2 ///< = -2. The "post 80 PRE_HEAP = -1, ///< = -1. The "pre-heap" state constant. 81 POST_HEAP = -2 ///< = -2. The "post-heap" state constant. 77 82 }; 78 83 79 /// \brief The constructor.80 /// 81 /// The constructor.84 /// \brief Constructor. 85 /// 86 /// Constructor. 82 87 /// \param map A map that assigns \c int values to keys of type 83 88 /// \c Item. It is used internally by the heap implementations to 84 89 /// handle the cross references. The assigned value must be 85 /// \c PRE_HEAP (<tt>-1</tt>) for every item. 90 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 91 #ifdef DOXYGEN 86 92 explicit Heap(ItemIntMap &map) {} 93 #else 94 explicit Heap(ItemIntMap&) {} 95 #endif 96 97 /// \brief Constructor. 98 /// 99 /// Constructor. 100 /// \param map A map that assigns \c int values to keys of type 101 /// \c Item. It is used internally by the heap implementations to 102 /// handle the cross references. The assigned value must be 103 /// \c PRE_HEAP (<tt>-1</tt>) for each item. 104 /// \param comp The function object used for comparing the priorities. 105 #ifdef DOXYGEN 106 explicit Heap(ItemIntMap &map, const CMP &comp) {} 107 #else 108 explicit Heap(ItemIntMap&, const CMP&) {} 109 #endif 87 110 88 111 /// \brief The number of items stored in the heap. 89 112 /// 90 /// Returns the number of items stored in the heap.113 /// This function returns the number of items stored in the heap. 91 114 int size() const { return 0; } 92 115 93 /// \brief Check sif the heap is empty.94 /// 95 /// Returns \c true if the heap is empty.116 /// \brief Check if the heap is empty. 117 /// 118 /// This function returns \c true if the heap is empty. 96 119 bool empty() const { return false; } 97 120 98 /// \brief Makes the heap empty. 99 /// 100 /// Makes the heap empty. 101 void clear(); 102 103 /// \brief Inserts an item into the heap with the given priority. 104 /// 105 /// Inserts the given item into the heap with the given priority. 121 /// \brief Make the heap empty. 122 /// 123 /// This functon makes the heap empty. 124 /// It does not change the cross reference map. If you want to reuse 125 /// a heap that is not surely empty, you should first clear it and 126 /// then you should set the cross reference map to \c PRE_HEAP 127 /// for each item. 128 void clear() {} 129 130 /// \brief Insert an item into the heap with the given priority. 131 /// 132 /// This function inserts the given item into the heap with the 133 /// given priority. 106 134 /// \param i The item to insert. 107 135 /// \param p The priority of the item. 136 /// \pre \e i must not be stored in the heap. 137 #ifdef DOXYGEN 108 138 void push(const Item &i, const Prio &p) {} 109 110 /// \brief Returns the item having minimum priority. 111 /// 112 /// Returns the item having minimum priority. 139 #else 140 void push(const Item&, const Prio&) {} 141 #endif 142 143 /// \brief Return the item having minimum priority. 144 /// 145 /// This function returns the item having minimum priority. 113 146 /// \pre The heap must be non-empty. 114 Item top() const { }147 Item top() const { return Item(); } 115 148 116 149 /// \brief The minimum priority. 117 150 /// 118 /// Returns the minimum priority.151 /// This function returns the minimum priority. 119 152 /// \pre The heap must be non-empty. 120 Prio prio() const { }121 122 /// \brief Remove sthe item having minimum priority.123 /// 124 /// Removes the item having minimum priority.153 Prio prio() const { return Prio(); } 154 155 /// \brief Remove the item having minimum priority. 156 /// 157 /// This function removes the item having minimum priority. 125 158 /// \pre The heap must be non-empty. 126 159 void pop() {} 127 160 128 /// \brief Removes an item from the heap. 129 /// 130 /// Removes the given item from the heap if it is already stored. 161 /// \brief Remove the given item from the heap. 162 /// 163 /// This function removes the given item from the heap if it is 164 /// already stored. 131 165 /// \param i The item to delete. 166 /// \pre \e i must be in the heap. 167 #ifdef DOXYGEN 132 168 void erase(const Item &i) {} 133 134 /// \brief The priority of an item. 135 /// 136 /// Returns the priority of the given item. 137 /// \param i The item. 138 /// \pre \c i must be in the heap. 169 #else 170 void erase(const Item&) {} 171 #endif 172 173 /// \brief The priority of the given item. 174 /// 175 /// This function returns the priority of the given item. 176 /// \param i The item. 177 /// \pre \e i must be in the heap. 178 #ifdef DOXYGEN 139 179 Prio operator[](const Item &i) const {} 140 141 /// \brief Sets the priority of an item or inserts it, if it is 180 #else 181 Prio operator[](const Item&) const { return Prio(); } 182 #endif 183 184 /// \brief Set the priority of an item or insert it, if it is 142 185 /// not stored in the heap. 143 186 /// 144 187 /// This method sets the priority of the given item if it is 145 /// already stored in the heap. 146 /// Otherwise it inserts the given itemwith the given priority.188 /// already stored in the heap. Otherwise it inserts the given 189 /// item into the heap with the given priority. 147 190 /// 148 191 /// \param i The item. 149 192 /// \param p The priority. 193 #ifdef DOXYGEN 150 194 void set(const Item &i, const Prio &p) {} 151 152 /// \brief Decreases the priority of an item to the given value. 153 /// 154 /// Decreases the priority of an item to the given value. 195 #else 196 void set(const Item&, const Prio&) {} 197 #endif 198 199 /// \brief Decrease the priority of an item to the given value. 200 /// 201 /// This function decreases the priority of an item to the given value. 155 202 /// \param i The item. 156 203 /// \param p The priority. 157 /// \pre \c i must be stored in the heap with priority at least \c p. 204 /// \pre \e i must be stored in the heap with priority at least \e p. 205 #ifdef DOXYGEN 158 206 void decrease(const Item &i, const Prio &p) {} 159 160 /// \brief Increases the priority of an item to the given value. 161 /// 162 /// Increases the priority of an item to the given value. 207 #else 208 void decrease(const Item&, const Prio&) {} 209 #endif 210 211 /// \brief Increase the priority of an item to the given value. 212 /// 213 /// This function increases the priority of an item to the given value. 163 214 /// \param i The item. 164 215 /// \param p The priority. 165 /// \pre \c i must be stored in the heap with priority at most \c p. 216 /// \pre \e i must be stored in the heap with priority at most \e p. 217 #ifdef DOXYGEN 166 218 void increase(const Item &i, const Prio &p) {} 167 168 /// \brief Returns if an item is in, has already been in, or has 169 /// never been in the heap. 219 #else 220 void increase(const Item&, const Prio&) {} 221 #endif 222 223 /// \brief Return the state of an item. 170 224 /// 171 225 /// This method returns \c PRE_HEAP if the given item has never … … 175 229 /// to the heap again. 176 230 /// \param i The item. 231 #ifdef DOXYGEN 177 232 State state(const Item &i) const {} 178 179 /// \brief Sets the state of an item in the heap. 180 /// 181 /// Sets the state of the given item in the heap. It can be used 182 /// to manually clear the heap when it is important to achive the 183 /// better time complexity. 233 #else 234 State state(const Item&) const { return PRE_HEAP; } 235 #endif 236 237 /// \brief Set the state of an item in the heap. 238 /// 239 /// This function sets the state of the given item in the heap. 240 /// It can be used to manually clear the heap when it is important 241 /// to achive better time complexity. 184 242 /// \param i The item. 185 243 /// \param st The state. It should not be \c IN_HEAP. 244 #ifdef DOXYGEN 186 245 void state(const Item& i, State st) {} 246 #else 247 void state(const Item&, State) {} 248 #endif 187 249 188 250 -
lemon/concepts/path.h
r832 r1127 169 169 } 170 170 _Path& p; 171 PathDumperConstraints() {} 171 172 }; 172 173 … … 194 195 } 195 196 _Path& p; 197 PathDumperConstraints() {} 196 198 }; 197 199 -
lemon/concepts/path.h
r1125 r1127 19 19 ///\ingroup concept 20 20 ///\file 21 ///\brief Classes for representing paths in digraphs.21 ///\brief The concept of paths 22 22 /// 23 23 … … 39 39 /// A skeleton structure for representing directed paths in a 40 40 /// digraph. 41 /// In a sense, a path can be treated as a list of arcs. 42 /// LEMON path types just store this list. As a consequence, they cannot 43 /// enumerate the nodes on the path directly and a zero length path 44 /// cannot store its source node. 45 /// 46 /// The arcs of a path should be stored in the order of their directions, 47 /// i.e. the target node of each arc should be the same as the source 48 /// node of the next arc. This consistency could be checked using 49 /// \ref checkPath(). 50 /// The source and target nodes of a (consistent) path can be obtained 51 /// using \ref pathSource() and \ref pathTarget(). 52 /// 53 /// A path can be constructed from another path of any type using the 54 /// copy constructor or the assignment operator. 55 /// 41 56 /// \tparam GR The digraph type in which the path is. 42 ///43 /// In a sense, the path can be treated as a list of arcs. The44 /// lemon path type stores just this list. As a consequence it45 /// cannot enumerate the nodes in the path and the zero length46 /// paths cannot store the source.47 ///48 57 template <typename GR> 49 58 class Path { … … 60 69 Path() {} 61 70 62 /// \brief Template co nstructor71 /// \brief Template copy constructor 63 72 template <typename CPath> 64 73 Path(const CPath& cpath) {} 65 74 66 /// \brief Template assigment 75 /// \brief Template assigment operator 67 76 template <typename CPath> 68 77 Path& operator=(const CPath& cpath) { … … 71 80 } 72 81 73 /// Length of the path ie. the number of arcs in the path.82 /// Length of the path, i.e. the number of arcs on the path. 74 83 int length() const { return 0;} 75 84 … … 80 89 void clear() {} 81 90 82 /// \brief LEMON style iterator for path arcs91 /// \brief LEMON style iterator for enumerating the arcs of a path. 83 92 /// 84 /// This class is used to iterate on the arcs of the paths.93 /// LEMON style iterator class for enumerating the arcs of a path. 85 94 class ArcIt { 86 95 public: … … 89 98 /// Invalid constructor 90 99 ArcIt(Invalid) {} 91 /// Constructor for first arc100 /// Sets the iterator to the first arc of the given path 92 101 ArcIt(const Path &) {} 93 102 94 /// Conversion to Arc103 /// Conversion to \c Arc 95 104 operator Arc() const { return INVALID; } 96 105 … … 195 204 /// 196 205 /// A skeleton structure for path dumpers. The path dumpers are 197 /// the generalization of the paths. The path dumpers can 198 /// enumerate the arcs of the path wheter in forward or in 199 /// backward order. In most time these classes are not used 200 /// directly rather it used to assign a dumped class to a real 201 /// path type. 206 /// the generalization of the paths, they can enumerate the arcs 207 /// of the path either in forward or in backward order. 208 /// These classes are typically not used directly, they are rather 209 /// used to be assigned to a real path type. 202 210 /// 203 211 /// The main purpose of this concept is that the shortest path 204 /// algorithms can enumerate easily the arcs in reverse order. 205 /// If we would like to give back a real path from these 206 /// algorithms then we should create a temporarly path object. In 207 /// LEMON such algorithms gives back a path dumper what can 208 /// assigned to a real path and the dumpers can be implemented as 212 /// algorithms can enumerate the arcs easily in reverse order. 213 /// In LEMON, such algorithms give back a (reverse) path dumper that 214 /// can be assigned to a real path. The dumpers can be implemented as 209 215 /// an adaptor class to the predecessor map. 210 216 /// 211 217 /// \tparam GR The digraph type in which the path is. 212 ///213 /// The paths can be constructed from any path type by a214 /// template constructor or a template assignment operator.215 218 template <typename GR> 216 219 class PathDumper { … … 222 225 typedef typename Digraph::Arc Arc; 223 226 224 /// Length of the path ie. the number of arcs in the path.227 /// Length of the path, i.e. the number of arcs on the path. 225 228 int length() const { return 0;} 226 229 … … 230 233 /// \brief Forward or reverse dumping 231 234 /// 232 /// If the RevPathTag is defined and true then reverse dumping 233 /// is provided in the path dumper. In this case instead of the 234 /// ArcIt the RevArcIt iterator should be implemented in the 235 /// dumper. 235 /// If this tag is defined to be \c True, then reverse dumping 236 /// is provided in the path dumper. In this case, \c RevArcIt 237 /// iterator should be implemented instead of \c ArcIt iterator. 236 238 typedef False RevPathTag; 237 239 238 /// \brief LEMON style iterator for path arcs240 /// \brief LEMON style iterator for enumerating the arcs of a path. 239 241 /// 240 /// This class is used to iterate on the arcs of the paths.242 /// LEMON style iterator class for enumerating the arcs of a path. 241 243 class ArcIt { 242 244 public: … … 245 247 /// Invalid constructor 246 248 ArcIt(Invalid) {} 247 /// Constructor for first arc249 /// Sets the iterator to the first arc of the given path 248 250 ArcIt(const PathDumper&) {} 249 251 250 /// Conversion to Arc252 /// Conversion to \c Arc 251 253 operator Arc() const { return INVALID; } 252 254 … … 263 265 }; 264 266 265 /// \brief LEMON style iterator for path arcs 267 /// \brief LEMON style iterator for enumerating the arcs of a path 268 /// in reverse direction. 266 269 /// 267 /// This class is used to iterate on the arcs of the paths in268 /// reverse direction.270 /// LEMON style iterator class for enumerating the arcs of a path 271 /// in reverse direction. 269 272 class RevArcIt { 270 273 public: … … 273 276 /// Invalid constructor 274 277 RevArcIt(Invalid) {} 275 /// Constructor for first arc278 /// Sets the iterator to the last arc of the given path 276 279 RevArcIt(const PathDumper &) {} 277 280 278 /// Conversion to Arc281 /// Conversion to \c Arc 279 282 operator Arc() const { return INVALID; } 280 283 -
lemon/dfs.h
r1110 r1127 1194 1194 } 1195 1195 _Visitor& visitor; 1196 Constraints() {} 1196 1197 }; 1197 1198 }; -
lemon/dfs.h
r1125 r1127 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 88 ///Instantiates a \c ReachedMap. … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 103 ///Instantiates a \c DistMap. … … 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref DfsDefaultTraits 127 ///"DfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 123 130 #ifdef DOXYGEN 124 131 template <typename GR, … … 225 232 ///\ref named-templ-param "Named parameter" for setting 226 233 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 235 template <class T> 229 236 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 252 ///\ref named-templ-param "Named parameter" for setting 246 253 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 255 template <class T> 249 256 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 272 ///\ref named-templ-param "Named parameter" for setting 266 273 ///\c ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 274 ///It must conform to 275 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 276 template <class T> 269 277 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 293 ///\ref named-templ-param "Named parameter" for setting 286 294 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.295 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 296 template <class T> 289 297 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 420 ///The simplest way to execute the DFS algorithm is to use one of the 413 421 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, firstyou have to call415 ///\ref init() , then you can add a source node with \ref addSource()422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add a source node with \ref addSource() 416 424 ///and perform the actual computation with \ref start(). 417 425 ///This procedure can be repeated if there are nodes that have not … … 633 641 ///Runs the algorithm to visit all nodes in the digraph. 634 642 635 ///This method runs the %DFS algorithm in order to compute the 636 ///%DFS path to each node. 637 /// 638 ///The algorithm computes 639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 643 ///This method runs the %DFS algorithm in order to visit all nodes 644 ///in the digraph. 641 645 /// 642 646 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 670 674 ///@{ 671 675 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.676 ///The DFS path to the given node. 677 678 ///Returns the DFS path to the given node from the root(s). 675 679 /// 676 680 ///\warning \c t should be reached from the root(s). … … 680 684 Path path(Node t) const { return Path(*G, *_pred, t); } 681 685 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).686 ///The distance of the given node from the root(s). 687 688 ///Returns the distance of the given node from the root(s). 685 689 /// 686 690 ///\warning If node \c v is not reached from the root(s), then … … 691 695 int dist(Node v) const { return (*_dist)[v]; } 692 696 693 ///Returns the 'previous arc' of the %DFS tree for anode.697 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 698 695 699 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 703 /// 700 704 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .705 ///\ref predNode() and \ref predMap(). 702 706 /// 703 707 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 709 Arc predArc(Node v) const { return (*_pred)[v];} 706 710 707 ///Returns the 'previous node' of the %DFS tree .711 ///Returns the 'previous node' of the %DFS tree for the given node. 708 712 709 713 ///This function returns the 'previous node' of the %DFS 710 714 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID715 ///of a %DFS path from a root to \c v. It is \c INVALID 712 716 ///if \c v is not reached from the root(s) or if \c v is a root. 713 717 /// 714 718 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .719 ///\ref predArc() and \ref predMap(). 716 720 /// 717 721 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 738 /// 735 739 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .740 ///arcs, which form the DFS tree (forest). 737 741 /// 738 742 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 744 const PredMap &predMap() const { return *_pred;} 741 745 742 ///Checks if anode is reached from the root(s).746 ///Checks if the given node. node is reached from the root(s). 743 747 744 748 ///Returns \c true if \c v is reached from the root(s). … … 766 770 ///The type of the map that stores the predecessor 767 771 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.772 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 773 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 774 ///Instantiates a PredMap. … … 781 785 782 786 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///By default it is a NullMap.787 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 788 ///By default, it is a NullMap. 785 789 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 790 ///Instantiates a ProcessedMap. … … 801 805 802 806 ///The type of the map that indicates which nodes are reached. 803 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 807 ///It must conform to 808 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 809 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 810 ///Instantiates a ReachedMap. … … 816 821 817 822 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.823 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 824 typedef typename Digraph::template NodeMap<int> DistMap; 820 825 ///Instantiates a DistMap. … … 831 836 832 837 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.838 ///It must conform to the \ref concepts::Path "Path" concept. 834 839 typedef lemon::Path<Digraph> Path; 835 840 }; … … 837 842 /// Default traits class used by DfsWizard 838 843 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 844 /// Default traits class used by DfsWizard. 845 /// \tparam GR The type of the digraph. 845 846 template<class GR> 846 847 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 871 /// Constructor. 871 872 872 /// This constructor does not require parameters, thereforeit initiates873 /// This constructor does not require parameters, it initiates 873 874 /// all of the attributes to \c 0. 874 875 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 895 896 /// This class should only be used through the \ref dfs() function, 896 897 /// which makes it easier to use the algorithm. 898 /// 899 /// \tparam TR The traits class that defines various types used by the 900 /// algorithm. 897 901 template<class TR> 898 902 class DfsWizard : public TR … … 900 904 typedef TR Base; 901 905 902 ///The type of the digraph the algorithm runs on.903 906 typedef typename TR::Digraph Digraph; 904 907 … … 908 911 typedef typename Digraph::OutArcIt OutArcIt; 909 912 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 913 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 914 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 915 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 916 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 917 typedef typename TR::Path Path; 921 918 … … 987 984 ///Runs DFS algorithm to visit all nodes in the digraph. 988 985 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.986 ///This method runs DFS algorithm in order to visit all nodes 987 ///in the digraph. 991 988 void run() 992 989 { … … 1000 997 SetPredMapBase(const TR &b) : TR(b) {} 1001 998 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 999 1000 ///\brief \ref named-templ-param "Named parameter" for setting 1001 ///the predecessor map. 1002 /// 1003 ///\ref named-templ-param "Named parameter" function for setting 1004 ///the map that stores the predecessor arcs of the nodes. 1007 1005 template<class T> 1008 1006 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1016 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1017 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1018 1019 ///\brief \ref named-templ-param "Named parameter" for setting 1020 ///the reached map. 1021 /// 1022 ///\ref named-templ-param "Named parameter" function for setting 1023 ///the map that indicates which nodes are reached. 1025 1024 template<class T> 1026 1025 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1035 SetDistMapBase(const TR &b) : TR(b) {} 1037 1036 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1037 1038 ///\brief \ref named-templ-param "Named parameter" for setting 1039 ///the distance map. 1040 /// 1041 ///\ref named-templ-param "Named parameter" function for setting 1042 ///the map that stores the distances of the nodes calculated 1043 ///by the algorithm. 1043 1044 template<class T> 1044 1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1055 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1056 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1057 1058 ///\brief \ref named-func-param "Named parameter" for setting 1059 ///the processed map. 1060 /// 1061 ///\ref named-templ-param "Named parameter" function for setting 1062 ///the map that indicates which nodes are processed. 1061 1063 template<class T> 1062 1064 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1210 1212 /// 1211 1213 /// The type of the map that indicates which nodes are reached. 1212 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1214 /// It must conform to the 1215 /// \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1213 1216 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1214 1217 … … 1248 1251 /// does not observe the DFS events. If you want to observe the DFS 1249 1252 /// events, you should implement your own visitor class. 1250 /// \tparam TR T raits class to set various datatypes used by the1251 /// algorithm. The default traits class is1252 /// \ref DfsVisitDefaultTraits"DfsVisitDefaultTraits<GR>".1253 /// See \ref DfsVisitDefaultTraits for the documentation of1254 /// a DFS visit traits class.1253 /// \tparam TR The traits class that defines various types used by the 1254 /// algorithm. By default, it is \ref DfsVisitDefaultTraits 1255 /// "DfsVisitDefaultTraits<GR>". 1256 /// In most cases, this parameter should not be set directly, 1257 /// consider to use the named template parameters instead. 1255 1258 #ifdef DOXYGEN 1256 1259 template <typename GR, typename VS, typename TR> … … 1371 1374 /// The simplest way to execute the DFS algorithm is to use one of the 1372 1375 /// member functions called \ref run(Node) "run()".\n 1373 /// If you need more control on the execution, firstyou have to call1374 /// \ref init() , then you can add a source node with \ref addSource()1376 /// If you need better control on the execution, you have to call 1377 /// \ref init() first, then you can add a source node with \ref addSource() 1375 1378 /// and perform the actual computation with \ref start(). 1376 1379 /// This procedure can be repeated if there are nodes that have not … … 1585 1588 /// \brief Runs the algorithm to visit all nodes in the digraph. 1586 1589 1587 /// This method runs the %DFS algorithm in order to 1588 /// compute the %DFS path to each node. 1589 /// 1590 /// The algorithm computes 1591 /// - the %DFS tree (forest), 1592 /// - the distance of each node from the root(s) in the %DFS tree. 1590 /// This method runs the %DFS algorithm in order to visit all nodes 1591 /// in the digraph. 1593 1592 /// 1594 1593 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1622 1621 ///@{ 1623 1622 1624 /// \brief Checks if anode is reached from the root(s).1623 /// \brief Checks if the given node is reached from the root(s). 1625 1624 /// 1626 1625 /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset
for help on using the changeset viewer.