Changes in / [642:16d7255a6849:647:0ba8dfce7259] in lemon
- Files:
-
- 6 edited
-
lemon/gomory_hu.h (modified) (14 diffs)
-
lemon/hao_orlin.h (modified) (12 diffs)
-
lemon/lgf_reader.h (modified) (27 diffs)
-
lemon/lgf_writer.h (modified) (28 diffs)
-
test/gomory_hu_test.cc (modified) (4 diffs)
-
test/hao_orlin_test.cc (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/gomory_hu.h
r628 r643 43 43 /// between these nodes. Moreover the components obtained by removing 44 44 /// this edge from the tree determine the corresponding minimum cut. 45 ///46 45 /// Therefore once this tree is computed, the minimum cut between any pair 47 46 /// of nodes can easily be obtained. 48 47 /// 49 48 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with 50 /// the \ref Preflow algorithm), therefore the algorithm has 51 /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a 52 /// rooted Gomory-Hu tree, its structure and the weights can be obtained 53 /// by \c predNode(), \c predValue() and \c rootDist(). 54 /// 55 /// The members \c minCutMap() and \c minCutValue() calculate 49 /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall 50 /// time complexity. It calculates a rooted Gomory-Hu tree. 51 /// The structure of the tree and the edge weights can be 52 /// obtained using \c predNode(), \c predValue() and \c rootDist(). 53 /// The functions \c minCutMap() and \c minCutValue() calculate 56 54 /// the minimum cut and the minimum cut value between any two nodes 57 55 /// in the graph. You can also list (iterate on) the nodes and the … … 59 57 /// 60 58 /// \tparam GR The type of the undirected graph the algorithm runs on. 61 /// \tparam CAP The type of the edge map describing the edge capacities.62 /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.59 /// \tparam CAP The type of the edge map containing the capacities. 60 /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 63 61 #ifdef DOXYGEN 64 62 template <typename GR, … … 71 69 public: 72 70 73 /// The graph type 71 /// The graph type of the algorithm 74 72 typedef GR Graph; 75 /// The type of the edge capacity map73 /// The capacity map type of the algorithm 76 74 typedef CAP Capacity; 77 75 /// The value type of capacities … … 118 116 /// \brief Constructor 119 117 /// 120 /// Constructor 118 /// Constructor. 121 119 /// \param graph The undirected graph the algorithm runs on. 122 120 /// \param capacity The edge capacity map. … … 131 129 /// \brief Destructor 132 130 /// 133 /// Destructor 131 /// Destructor. 134 132 ~GomoryHu() { 135 133 destroyStructures(); … … 216 214 ///The results of the algorithm can be obtained using these 217 215 ///functions.\n 218 ///\ref run() "run()"should be called before using them.\n216 ///\ref run() should be called before using them.\n 219 217 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. 220 218 … … 223 221 /// \brief Return the predecessor node in the Gomory-Hu tree. 224 222 /// 225 /// This function returns the predecessor node in the Gomory-Hu tree. 226 /// If the node is 227 /// the root of the Gomory-Hu tree, then it returns \c INVALID. 228 Node predNode(const Node& node) { 223 /// This function returns the predecessor node of the given node 224 /// in the Gomory-Hu tree. 225 /// If \c node is the root of the tree, then it returns \c INVALID. 226 /// 227 /// \pre \ref run() must be called before using this function. 228 Node predNode(const Node& node) const { 229 229 return (*_pred)[node]; 230 }231 232 /// \brief Return the distance from the root node in the Gomory-Hu tree.233 ///234 /// This function returns the distance of \c node from the root node235 /// in the Gomory-Hu tree.236 int rootDist(const Node& node) {237 return (*_order)[node];238 230 } 239 231 … … 241 233 /// Gomory-Hu tree. 242 234 /// 243 /// This function returns the weight of the predecessor edge in the 244 /// Gomory-Hu tree. If the node is the root, the result is undefined. 245 Value predValue(const Node& node) { 235 /// This function returns the weight of the predecessor edge of the 236 /// given node in the Gomory-Hu tree. 237 /// If \c node is the root of the tree, the result is undefined. 238 /// 239 /// \pre \ref run() must be called before using this function. 240 Value predValue(const Node& node) const { 246 241 return (*_weight)[node]; 247 242 } 248 243 244 /// \brief Return the distance from the root node in the Gomory-Hu tree. 245 /// 246 /// This function returns the distance of the given node from the root 247 /// node in the Gomory-Hu tree. 248 /// 249 /// \pre \ref run() must be called before using this function. 250 int rootDist(const Node& node) const { 251 return (*_order)[node]; 252 } 253 249 254 /// \brief Return the minimum cut value between two nodes 250 255 /// 251 /// This function returns the minimum cut value between two nodes. The 252 /// algorithm finds the nearest common ancestor in the Gomory-Hu 253 /// tree and calculates the minimum weight edge on the paths to 254 /// the ancestor. 256 /// This function returns the minimum cut value between the nodes 257 /// \c s and \c t. 258 /// It finds the nearest common ancestor of the given nodes in the 259 /// Gomory-Hu tree and calculates the minimum weight edge on the 260 /// paths to the ancestor. 261 /// 262 /// \pre \ref run() must be called before using this function. 255 263 Value minCutValue(const Node& s, const Node& t) const { 256 264 Node sn = s, tn = t; … … 275 283 /// \c s to \c true and the other nodes to \c false. 276 284 /// 277 /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. 285 /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt. 286 /// 287 /// \param s The base node. 288 /// \param t The node you want to separate from node \c s. 289 /// \param cutMap The cut will be returned in this map. 290 /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap 291 /// "ReadWriteMap" on the graph nodes. 292 /// 293 /// \return The value of the minimum cut between \c s and \c t. 294 /// 295 /// \pre \ref run() must be called before using this function. 278 296 template <typename CutMap> 279 Value minCutMap(const Node& s, ///< The base node.297 Value minCutMap(const Node& s, ///< 280 298 const Node& t, 281 ///< The node you want to separate from node \c s.299 ///< 282 300 CutMap& cutMap 283 ///< The cut will be returned in this map. 284 /// It must be a \c bool (or convertible) 285 /// \ref concepts::ReadWriteMap "ReadWriteMap" 286 /// on the graph nodes. 301 ///< 287 302 ) const { 288 303 Node sn = s, tn = t; … … 339 354 340 355 /// This iterator class lists the nodes of a minimum cut found by 341 /// GomoryHu. Before using it, you must allocate a GomoryHu class ,356 /// GomoryHu. Before using it, you must allocate a GomoryHu class 342 357 /// and call its \ref GomoryHu::run() "run()" method. 343 358 /// … … 436 451 437 452 /// This iterator class lists the edges of a minimum cut found by 438 /// GomoryHu. Before using it, you must allocate a GomoryHu class ,453 /// GomoryHu. Before using it, you must allocate a GomoryHu class 439 454 /// and call its \ref GomoryHu::run() "run()" method. 440 455 /// … … 448 463 /// value+=capacities[e]; 449 464 /// \endcode 450 /// the result will be the same as it isreturned by451 /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" 465 /// The result will be the same as the value returned by 466 /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)". 452 467 class MinCutEdgeIt 453 468 { … … 469 484 470 485 public: 486 /// Constructor 487 488 /// Constructor. 489 /// 471 490 MinCutEdgeIt(GomoryHu const &gomory, 472 491 ///< The GomoryHu class. You must call its … … 479 498 ///< If it is \c true (default) then the listed arcs 480 499 /// will be oriented from the 481 /// thenodes of the component containing \c s,500 /// nodes of the component containing \c s, 482 501 /// otherwise they will be oriented in the opposite 483 502 /// direction. -
lemon/hao_orlin.h
r628 r644 32 32 /// \brief Implementation of the Hao-Orlin algorithm. 33 33 /// 34 /// Implementation of the Hao-Orlin algorithm class for testing network35 /// reliability.34 /// Implementation of the Hao-Orlin algorithm for finding a minimum cut 35 /// in a digraph. 36 36 37 37 namespace lemon { … … 39 39 /// \ingroup min_cut 40 40 /// 41 /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.41 /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph. 42 42 /// 43 /// Hao-Orlin calculates a minimum cut in a directed graph 44 /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and 43 /// This class implements the Hao-Orlin algorithm for finding a minimum 44 /// value cut in a directed graph \f$D=(V,A)\f$. 45 /// It takes a fixed node \f$ source \in V \f$ and 45 46 /// consists of two phases: in the first phase it determines a 46 47 /// minimum cut with \f$ source \f$ on the source-side (i.e. a set 47 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal 48 /// out-degree) and in the second phase it determines a minimum cut48 /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing 49 /// capacity) and in the second phase it determines a minimum cut 49 50 /// with \f$ source \f$ on the sink-side (i.e. a set 50 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal 51 /// out-degree). Obviously, the smaller of these two cuts will be a51 /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing 52 /// capacity). Obviously, the smaller of these two cuts will be a 52 53 /// minimum cut of \f$ D \f$. The algorithm is a modified 53 /// p ush-relabel preflow algorithm and our implementation calculates54 /// preflow push-relabel algorithm. Our implementation calculates 54 55 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the 55 56 /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The 56 /// purpose of such algorithm is testing network reliability. For an 57 /// undirected graph you can run just the first phase of the 58 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki 59 /// which solves the undirected problem in 60 /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the 61 /// NagamochiIbaraki algorithm class. 57 /// purpose of such algorithm is e.g. testing network reliability. 62 58 /// 63 /// \param GR The digraph class the algorithm runs on. 64 /// \param CAP An arc map of capacities which can be any numreric type. 65 /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 66 /// \param TOL Tolerance class for handling inexact computations. The 59 /// For an undirected graph you can run just the first phase of the 60 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, 61 /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ 62 /// time. It is implemented in the NagamochiIbaraki algorithm class. 63 /// 64 /// \tparam GR The type of the digraph the algorithm runs on. 65 /// \tparam CAP The type of the arc map containing the capacities, 66 /// which can be any numreric type. The default map type is 67 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 68 /// \tparam TOL Tolerance class for handling inexact computations. The 67 69 /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". 68 70 #ifdef DOXYGEN … … 74 76 #endif 75 77 class HaoOrlin { 78 public: 79 80 /// The digraph type of the algorithm 81 typedef GR Digraph; 82 /// The capacity map type of the algorithm 83 typedef CAP CapacityMap; 84 /// The tolerance type of the algorithm 85 typedef TOL Tolerance; 86 76 87 private: 77 88 78 typedef GR Digraph;79 typedef CAP CapacityMap;80 typedef TOL Tolerance;81 82 89 typedef typename CapacityMap::Value Value; 83 90 84 TEMPLATE_ GRAPH_TYPEDEFS(Digraph);91 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 85 92 86 93 const Digraph& _graph; … … 220 227 for (NodeIt n(_graph); n != INVALID; ++n) { 221 228 (*_excess)[n] = 0; 229 (*_source_set)[n] = false; 222 230 } 223 231 … … 519 527 for (NodeIt n(_graph); n != INVALID; ++n) { 520 528 (*_excess)[n] = 0; 529 (*_source_set)[n] = false; 521 530 } 522 531 … … 816 825 public: 817 826 818 /// \name Execution control827 /// \name Execution Control 819 828 /// The simplest way to execute the algorithm is to use 820 829 /// one of the member functions called \ref run(). 821 830 /// \n 822 /// If you need morecontrol on the execution,823 /// first you must call \ref init(), then the \ref calculateIn() or824 /// \ref calculateOut() functions.831 /// If you need better control on the execution, 832 /// you have to call one of the \ref init() functions first, then 833 /// \ref calculateOut() and/or \ref calculateIn(). 825 834 826 835 /// @{ 827 836 828 /// \brief Initializes the internal data structures. 829 /// 830 /// Initializes the internal data structures. It creates 831 /// the maps, residual graph adaptors and some bucket structures 832 /// for the algorithm. 837 /// \brief Initialize the internal data structures. 838 /// 839 /// This function initializes the internal data structures. It creates 840 /// the maps and some bucket structures for the algorithm. 841 /// The first node is used as the source node for the push-relabel 842 /// algorithm. 833 843 void init() { 834 844 init(NodeIt(_graph)); 835 845 } 836 846 837 /// \brief Initialize sthe internal data structures.838 /// 839 /// Initializes the internal data structures. It creates840 /// the maps , residual graph adaptor and some bucket structures841 /// for the algorithm. Node \c source is used asthe push-relabel842 /// algorithm 's source.847 /// \brief Initialize the internal data structures. 848 /// 849 /// This function initializes the internal data structures. It creates 850 /// the maps and some bucket structures for the algorithm. 851 /// The given node is used as the source node for the push-relabel 852 /// algorithm. 843 853 void init(const Node& source) { 844 854 _source = source; … … 880 890 881 891 882 /// \brief Calculate sa minimum cut with \f$ source \f$ on the892 /// \brief Calculate a minimum cut with \f$ source \f$ on the 883 893 /// source-side. 884 894 /// 885 /// Calculates a minimum cut with \f$ source \f$ on the895 /// This function calculates a minimum cut with \f$ source \f$ on the 886 896 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with 887 /// \f$ source \in X \f$ and minimal out-degree). 897 /// \f$ source \in X \f$ and minimal outgoing capacity). 898 /// 899 /// \pre \ref init() must be called before using this function. 888 900 void calculateOut() { 889 901 findMinCutOut(); 890 902 } 891 903 892 /// \brief Calculates a minimum cut with \f$ source \f$ on the 893 /// target-side. 894 /// 895 /// Calculates a minimum cut with \f$ source \f$ on the 896 /// target-side (i.e. a set \f$ X\subsetneq V \f$ with 897 /// \f$ source \in X \f$ and minimal out-degree). 904 /// \brief Calculate a minimum cut with \f$ source \f$ on the 905 /// sink-side. 906 /// 907 /// This function calculates a minimum cut with \f$ source \f$ on the 908 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with 909 /// \f$ source \notin X \f$ and minimal outgoing capacity). 910 /// 911 /// \pre \ref init() must be called before using this function. 898 912 void calculateIn() { 899 913 findMinCutIn(); … … 901 915 902 916 903 /// \brief Run sthe algorithm.904 /// 905 /// Runs the algorithm. It finds nodes \c source and \c target906 /// arbitrarily and then calls \ref init(), \ref calculateOut()917 /// \brief Run the algorithm. 918 /// 919 /// This function runs the algorithm. It finds nodes \c source and 920 /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() 907 921 /// and \ref calculateIn(). 908 922 void run() { … … 912 926 } 913 927 914 /// \brief Run sthe algorithm.915 /// 916 /// Runs the algorithm. It uses the given \c source node, finds a917 /// proper \c target and then calls the \ref init(), \ref918 /// calculateOut() and \ref calculateIn().928 /// \brief Run the algorithm. 929 /// 930 /// This function runs the algorithm. It uses the given \c source node, 931 /// finds a proper \c target node and then calls the \ref init(), 932 /// \ref calculateOut() and \ref calculateIn(). 919 933 void run(const Node& s) { 920 934 init(s); … … 927 941 /// \name Query Functions 928 942 /// The result of the %HaoOrlin algorithm 929 /// can be obtained using these functions. 930 /// \n 931 /// Before using these functions, either \ref run(), \ref 932 /// calculateOut() or \ref calculateIn() must be called. 943 /// can be obtained using these functions.\n 944 /// \ref run(), \ref calculateOut() or \ref calculateIn() 945 /// should be called before using them. 933 946 934 947 /// @{ 935 948 936 /// \brief Returns the value of the minimum value cut. 937 /// 938 /// Returns the value of the minimum value cut. 949 /// \brief Return the value of the minimum cut. 950 /// 951 /// This function returns the value of the minimum cut. 952 /// 953 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 954 /// must be called before using this function. 939 955 Value minCutValue() const { 940 956 return _min_cut; … … 942 958 943 959 944 /// \brief Returns a minimum cut. 945 /// 946 /// Sets \c nodeMap to the characteristic vector of a minimum 947 /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ 948 /// with minimal out-degree (i.e. \c nodeMap will be true exactly 949 /// for the nodes of \f$ X \f$). \pre nodeMap should be a 950 /// bool-valued node-map. 951 template <typename NodeMap> 952 Value minCutMap(NodeMap& nodeMap) const { 960 /// \brief Return a minimum cut. 961 /// 962 /// This function sets \c cutMap to the characteristic vector of a 963 /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$ 964 /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly 965 /// for the nodes of \f$ X \f$). 966 /// 967 /// \param cutMap A \ref concepts::WriteMap "writable" node map with 968 /// \c bool (or convertible) value type. 969 /// 970 /// \return The value of the minimum cut. 971 /// 972 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() 973 /// must be called before using this function. 974 template <typename CutMap> 975 Value minCutMap(CutMap& cutMap) const { 953 976 for (NodeIt it(_graph); it != INVALID; ++it) { 954 nodeMap.set(it, (*_min_cut_map)[it]);977 cutMap.set(it, (*_min_cut_map)[it]); 955 978 } 956 979 return _min_cut; … … 961 984 }; //class HaoOrlin 962 985 963 964 986 } //namespace lemon 965 987 -
lemon/lgf_reader.h
r631 r646 102 102 }; 103 103 104 template <typename _G raph, bool _dir, typename _Map,104 template <typename _GR, bool _dir, typename _Map, 105 105 typename _Converter = DefaultConverter<typename _Map::Value> > 106 class GraphArcMapStorage : public MapStorageBase<typename _G raph::Edge> {106 class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> { 107 107 public: 108 108 typedef _Map Map; 109 109 typedef _Converter Converter; 110 typedef _G raph Graph;111 typedef typename G raph::Edge Item;110 typedef _GR GR; 111 typedef typename GR::Edge Item; 112 112 static const bool dir = _dir; 113 113 114 114 private: 115 const G raph& _graph;115 const GR& _graph; 116 116 Map& _map; 117 117 Converter _converter; 118 118 119 119 public: 120 GraphArcMapStorage(const G raph& graph, Map& map,120 GraphArcMapStorage(const GR& graph, Map& map, 121 121 const Converter& converter = Converter()) 122 122 : _graph(graph), _map(map), _converter(converter) {} … … 174 174 }; 175 175 176 template <typename G raph>176 template <typename GR> 177 177 struct GraphArcLookUpConverter { 178 const G raph& _graph;179 const std::map<std::string, typename G raph::Edge>& _map;180 181 GraphArcLookUpConverter(const G raph& graph,178 const GR& _graph; 179 const std::map<std::string, typename GR::Edge>& _map; 180 181 GraphArcLookUpConverter(const GR& graph, 182 182 const std::map<std::string, 183 typename G raph::Edge>& map)183 typename GR::Edge>& map) 184 184 : _graph(graph), _map(map) {} 185 185 186 typename G raph::Arc operator()(const std::string& str) {186 typename GR::Arc operator()(const std::string& str) { 187 187 if (str.empty() || (str[0] != '+' && str[0] != '-')) { 188 188 throw FormatError("Item must start with '+' or '-'"); 189 189 } 190 typename std::map<std::string, typename G raph::Edge>190 typename std::map<std::string, typename GR::Edge> 191 191 ::const_iterator it = _map.find(str.substr(1)); 192 192 if (it == _map.end()) { … … 388 388 } 389 389 390 template <typename D igraph>390 template <typename DGR> 391 391 class DigraphReader; 392 392 393 template <typename Digraph> 394 DigraphReader<Digraph> digraphReader(Digraph& digraph, 395 std::istream& is = std::cin); 396 template <typename Digraph> 397 DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn); 398 template <typename Digraph> 399 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn); 393 template <typename TDGR> 394 DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin); 395 template <typename TDGR> 396 DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn); 397 template <typename TDGR> 398 DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn); 400 399 401 400 /// \ingroup lemon_io … … 420 419 /// 421 420 ///\code 422 /// DigraphReader<D igraph>(digraph, std::cin).421 /// DigraphReader<DGR>(digraph, std::cin). 423 422 /// nodeMap("coordinates", coord_map). 424 423 /// arcMap("capacity", cap_map). … … 449 448 /// a single pass, because the arcs are not constructed when the node 450 449 /// maps are read. 451 template <typename GR>450 template <typename DGR> 452 451 class DigraphReader { 453 452 public: 454 453 455 typedef GR Digraph;454 typedef DGR Digraph; 456 455 457 456 private: 458 457 459 TEMPLATE_DIGRAPH_TYPEDEFS(D igraph);458 TEMPLATE_DIGRAPH_TYPEDEFS(DGR); 460 459 461 460 std::istream* _is; … … 463 462 std::string _filename; 464 463 465 D igraph& _digraph;464 DGR& _digraph; 466 465 467 466 std::string _nodes_caption; … … 501 500 /// Construct a directed graph reader, which reads from the given 502 501 /// input stream. 503 DigraphReader(D igraph& digraph, std::istream& is = std::cin)502 DigraphReader(DGR& digraph, std::istream& is = std::cin) 504 503 : _is(&is), local_is(false), _digraph(digraph), 505 504 _use_nodes(false), _use_arcs(false), … … 510 509 /// Construct a directed graph reader, which reads from the given 511 510 /// file. 512 DigraphReader(D igraph& digraph, const std::string& fn)511 DigraphReader(DGR& digraph, const std::string& fn) 513 512 : _is(new std::ifstream(fn.c_str())), local_is(true), 514 513 _filename(fn), _digraph(digraph), … … 525 524 /// Construct a directed graph reader, which reads from the given 526 525 /// file. 527 DigraphReader(D igraph& digraph, const char* fn)526 DigraphReader(DGR& digraph, const char* fn) 528 527 : _is(new std::ifstream(fn)), local_is(true), 529 528 _filename(fn), _digraph(digraph), … … 561 560 private: 562 561 563 template <typename DGR>564 friend DigraphReader< DGR> digraphReader(DGR& digraph, std::istream& is);565 template <typename DGR>566 friend DigraphReader< DGR> digraphReader(DGR& digraph,567 const std::string& fn);568 template <typename DGR>569 friend DigraphReader< DGR> digraphReader(DGR& digraph, const char *fn);562 template <typename TDGR> 563 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is); 564 template <typename TDGR> 565 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 566 const std::string& fn); 567 template <typename TDGR> 568 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn); 570 569 571 570 DigraphReader(DigraphReader& other) … … 1189 1188 1190 1189 }; 1190 1191 /// \ingroup lemon_io 1192 /// 1193 /// \brief Return a \ref DigraphReader class 1194 /// 1195 /// This function just returns a \ref DigraphReader class. 1196 /// 1197 /// With this function a digraph can be read from an 1198 /// \ref lgf-format "LGF" file or input stream with several maps and 1199 /// attributes. For example, there is network flow problem on a 1200 /// digraph, i.e. a digraph with a \e capacity map on the arcs and 1201 /// \e source and \e target nodes. This digraph can be read with the 1202 /// following code: 1203 /// 1204 ///\code 1205 ///ListDigraph digraph; 1206 ///ListDigraph::ArcMap<int> cm(digraph); 1207 ///ListDigraph::Node src, trg; 1208 ///digraphReader(digraph, std::cin). 1209 /// arcMap("capacity", cap). 1210 /// node("source", src). 1211 /// node("target", trg). 1212 /// run(); 1213 ///\endcode 1214 /// 1215 /// For a complete documentation, please see the \ref DigraphReader 1216 /// class documentation. 1217 /// \warning Don't forget to put the \ref DigraphReader::run() "run()" 1218 /// to the end of the parameter list. 1219 /// \relates DigraphReader 1220 /// \sa digraphReader(TDGR& digraph, const std::string& fn) 1221 /// \sa digraphReader(TDGR& digraph, const char* fn) 1222 template <typename TDGR> 1223 DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) { 1224 DigraphReader<TDGR> tmp(digraph, is); 1225 return tmp; 1226 } 1191 1227 1192 1228 /// \brief Return a \ref DigraphReader class … … 1194 1230 /// This function just returns a \ref DigraphReader class. 1195 1231 /// \relates DigraphReader 1196 template <typename Digraph> 1197 DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) { 1198 DigraphReader<Digraph> tmp(digraph, is); 1232 /// \sa digraphReader(TDGR& digraph, std::istream& is) 1233 template <typename TDGR> 1234 DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) { 1235 DigraphReader<TDGR> tmp(digraph, fn); 1199 1236 return tmp; 1200 1237 } … … 1204 1241 /// This function just returns a \ref DigraphReader class. 1205 1242 /// \relates DigraphReader 1206 template <typename Digraph>1207 DigraphReader<Digraph> digraphReader(Digraph& digraph,1208 const std::string&fn) {1209 DigraphReader< Digraph> tmp(digraph, fn);1243 /// \sa digraphReader(TDGR& digraph, std::istream& is) 1244 template <typename TDGR> 1245 DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) { 1246 DigraphReader<TDGR> tmp(digraph, fn); 1210 1247 return tmp; 1211 1248 } 1212 1249 1213 /// \brief Return a \ref DigraphReader class 1214 /// 1215 /// This function just returns a \ref DigraphReader class. 1216 /// \relates DigraphReader 1217 template <typename Digraph> 1218 DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) { 1219 DigraphReader<Digraph> tmp(digraph, fn); 1220 return tmp; 1221 } 1222 1223 template <typename Graph> 1250 template <typename GR> 1224 1251 class GraphReader; 1225 1252 1226 template <typename Graph> 1227 GraphReader<Graph> graphReader(Graph& graph, 1228 std::istream& is = std::cin); 1229 template <typename Graph> 1230 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn); 1231 template <typename Graph> 1232 GraphReader<Graph> graphReader(Graph& graph, const char *fn); 1253 template <typename TGR> 1254 GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin); 1255 template <typename TGR> 1256 GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1257 template <typename TGR> 1258 GraphReader<TGR> graphReader(TGR& graph, const char *fn); 1233 1259 1234 1260 /// \ingroup lemon_io … … 1255 1281 private: 1256 1282 1257 TEMPLATE_GRAPH_TYPEDEFS(G raph);1283 TEMPLATE_GRAPH_TYPEDEFS(GR); 1258 1284 1259 1285 std::istream* _is; … … 1261 1287 std::string _filename; 1262 1288 1263 G raph& _graph;1289 GR& _graph; 1264 1290 1265 1291 std::string _nodes_caption; … … 1299 1325 /// Construct an undirected graph reader, which reads from the given 1300 1326 /// input stream. 1301 GraphReader(G raph& graph, std::istream& is = std::cin)1327 GraphReader(GR& graph, std::istream& is = std::cin) 1302 1328 : _is(&is), local_is(false), _graph(graph), 1303 1329 _use_nodes(false), _use_edges(false), … … 1308 1334 /// Construct an undirected graph reader, which reads from the given 1309 1335 /// file. 1310 GraphReader(G raph& graph, const std::string& fn)1336 GraphReader(GR& graph, const std::string& fn) 1311 1337 : _is(new std::ifstream(fn.c_str())), local_is(true), 1312 1338 _filename(fn), _graph(graph), … … 1323 1349 /// Construct an undirected graph reader, which reads from the given 1324 1350 /// file. 1325 GraphReader(G raph& graph, const char* fn)1351 GraphReader(GR& graph, const char* fn) 1326 1352 : _is(new std::ifstream(fn)), local_is(true), 1327 1353 _filename(fn), _graph(graph), … … 1358 1384 1359 1385 private: 1360 template <typename Graph>1361 friend GraphReader< Graph> graphReader(Graph& graph, std::istream& is);1362 template <typename Graph>1363 friend GraphReader< Graph> graphReader(Graph& graph, const std::string& fn);1364 template <typename Graph>1365 friend GraphReader< Graph> graphReader(Graph& graph, const char *fn);1386 template <typename TGR> 1387 friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is); 1388 template <typename TGR> 1389 friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1390 template <typename TGR> 1391 friend GraphReader<TGR> graphReader(TGR& graph, const char *fn); 1366 1392 1367 1393 GraphReader(GraphReader& other) … … 1455 1481 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1456 1482 _reader_bits::MapStorageBase<Edge>* backward_storage = 1457 new _reader_bits::GraphArcMapStorage<G raph, false, Map>(_graph, map);1483 new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map); 1458 1484 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 1459 1485 return *this; … … 1469 1495 checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>(); 1470 1496 _reader_bits::MapStorageBase<Edge>* forward_storage = 1471 new _reader_bits::GraphArcMapStorage<G raph, true, Map, Converter>1497 new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter> 1472 1498 (_graph, map, converter); 1473 1499 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1474 1500 _reader_bits::MapStorageBase<Edge>* backward_storage = 1475 new _reader_bits::GraphArcMapStorage<G raph, false, Map, Converter>1501 new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter> 1476 1502 (_graph, map, converter); 1477 1503 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); … … 1531 1557 /// Add an arc reading rule to reader. 1532 1558 GraphReader& arc(const std::string& caption, Arc& arc) { 1533 typedef _reader_bits::GraphArcLookUpConverter<G raph> Converter;1559 typedef _reader_bits::GraphArcLookUpConverter<GR> Converter; 1534 1560 Converter converter(_graph, _edge_index); 1535 1561 _reader_bits::ValueStorageBase* storage = … … 2034 2060 }; 2035 2061 2062 /// \ingroup lemon_io 2063 /// 2064 /// \brief Return a \ref GraphReader class 2065 /// 2066 /// This function just returns a \ref GraphReader class. 2067 /// 2068 /// With this function a graph can be read from an 2069 /// \ref lgf-format "LGF" file or input stream with several maps and 2070 /// attributes. For example, there is weighted matching problem on a 2071 /// graph, i.e. a graph with a \e weight map on the edges. This 2072 /// graph can be read with the following code: 2073 /// 2074 ///\code 2075 ///ListGraph graph; 2076 ///ListGraph::EdgeMap<int> weight(graph); 2077 ///graphReader(graph, std::cin). 2078 /// edgeMap("weight", weight). 2079 /// run(); 2080 ///\endcode 2081 /// 2082 /// For a complete documentation, please see the \ref GraphReader 2083 /// class documentation. 2084 /// \warning Don't forget to put the \ref GraphReader::run() "run()" 2085 /// to the end of the parameter list. 2086 /// \relates GraphReader 2087 /// \sa graphReader(TGR& graph, const std::string& fn) 2088 /// \sa graphReader(TGR& graph, const char* fn) 2089 template <typename TGR> 2090 GraphReader<TGR> graphReader(TGR& graph, std::istream& is) { 2091 GraphReader<TGR> tmp(graph, is); 2092 return tmp; 2093 } 2094 2036 2095 /// \brief Return a \ref GraphReader class 2037 2096 /// 2038 2097 /// This function just returns a \ref GraphReader class. 2039 2098 /// \relates GraphReader 2040 template <typename Graph> 2041 GraphReader<Graph> graphReader(Graph& graph, std::istream& is) { 2042 GraphReader<Graph> tmp(graph, is); 2099 /// \sa graphReader(TGR& graph, std::istream& is) 2100 template <typename TGR> 2101 GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) { 2102 GraphReader<TGR> tmp(graph, fn); 2043 2103 return tmp; 2044 2104 } … … 2048 2108 /// This function just returns a \ref GraphReader class. 2049 2109 /// \relates GraphReader 2050 template <typename Graph> 2051 GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) { 2052 GraphReader<Graph> tmp(graph, fn); 2053 return tmp; 2054 } 2055 2056 /// \brief Return a \ref GraphReader class 2057 /// 2058 /// This function just returns a \ref GraphReader class. 2059 /// \relates GraphReader 2060 template <typename Graph> 2061 GraphReader<Graph> graphReader(Graph& graph, const char* fn) { 2062 GraphReader<Graph> tmp(graph, fn); 2110 /// \sa graphReader(TGR& graph, std::istream& is) 2111 template <typename TGR> 2112 GraphReader<TGR> graphReader(TGR& graph, const char* fn) { 2113 GraphReader<TGR> tmp(graph, fn); 2063 2114 return tmp; 2064 2115 } … … 2317 2368 }; 2318 2369 2370 /// \ingroup lemon_io 2371 /// 2319 2372 /// \brief Return a \ref SectionReader class 2320 2373 /// 2321 2374 /// This function just returns a \ref SectionReader class. 2375 /// 2376 /// Please see SectionReader documentation about the custom section 2377 /// input. 2378 /// 2322 2379 /// \relates SectionReader 2380 /// \sa sectionReader(const std::string& fn) 2381 /// \sa sectionReader(const char *fn) 2323 2382 inline SectionReader sectionReader(std::istream& is) { 2324 2383 SectionReader tmp(is); … … 2330 2389 /// This function just returns a \ref SectionReader class. 2331 2390 /// \relates SectionReader 2391 /// \sa sectionReader(std::istream& is) 2332 2392 inline SectionReader sectionReader(const std::string& fn) { 2333 2393 SectionReader tmp(fn); … … 2339 2399 /// This function just returns a \ref SectionReader class. 2340 2400 /// \relates SectionReader 2401 /// \sa sectionReader(std::istream& is) 2341 2402 inline SectionReader sectionReader(const char* fn) { 2342 2403 SectionReader tmp(fn); -
lemon/lgf_writer.h
r631 r646 348 348 } 349 349 350 template <typename D igraph>350 template <typename DGR> 351 351 class DigraphWriter; 352 352 353 template <typename Digraph> 354 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph, 355 std::ostream& os = std::cout); 356 template <typename Digraph> 357 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph, 358 const std::string& fn); 359 360 template <typename Digraph> 361 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph, 362 const char* fn); 353 template <typename TDGR> 354 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 355 std::ostream& os = std::cout); 356 template <typename TDGR> 357 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const std::string& fn); 358 359 template <typename TDGR> 360 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn); 363 361 364 362 … … 382 380 /// 383 381 ///\code 384 /// DigraphWriter<D igraph>(digraph, std::cout).382 /// DigraphWriter<DGR>(digraph, std::cout). 385 383 /// nodeMap("coordinates", coord_map). 386 384 /// nodeMap("size", size). … … 407 405 /// the \c ostream() function, hence the second pass can append its 408 406 /// output to the output of the first pass. 409 template <typename GR>407 template <typename DGR> 410 408 class DigraphWriter { 411 409 public: 412 410 413 typedef GR Digraph;414 TEMPLATE_DIGRAPH_TYPEDEFS(D igraph);411 typedef DGR Digraph; 412 TEMPLATE_DIGRAPH_TYPEDEFS(DGR); 415 413 416 414 private: … … 420 418 bool local_os; 421 419 422 const D igraph& _digraph;420 const DGR& _digraph; 423 421 424 422 std::string _nodes_caption; … … 452 450 /// Construct a directed graph writer, which writes to the given 453 451 /// output stream. 454 DigraphWriter(const D igraph& digraph, std::ostream& os = std::cout)452 DigraphWriter(const DGR& digraph, std::ostream& os = std::cout) 455 453 : _os(&os), local_os(false), _digraph(digraph), 456 454 _skip_nodes(false), _skip_arcs(false) {} … … 460 458 /// Construct a directed graph writer, which writes to the given 461 459 /// output file. 462 DigraphWriter(const D igraph& digraph, const std::string& fn)460 DigraphWriter(const DGR& digraph, const std::string& fn) 463 461 : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph), 464 462 _skip_nodes(false), _skip_arcs(false) { … … 473 471 /// Construct a directed graph writer, which writes to the given 474 472 /// output file. 475 DigraphWriter(const D igraph& digraph, const char* fn)473 DigraphWriter(const DGR& digraph, const char* fn) 476 474 : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph), 477 475 _skip_nodes(false), _skip_arcs(false) { … … 506 504 private: 507 505 508 template <typename DGR>509 friend DigraphWriter< DGR> digraphWriter(constDGR& digraph,510 std::ostream& os);511 template <typename DGR>512 friend DigraphWriter< DGR> digraphWriter(constDGR& digraph,513 const std::string& fn);514 template <typename DGR>515 friend DigraphWriter< DGR> digraphWriter(constDGR& digraph,516 const char *fn);506 template <typename TDGR> 507 friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 508 std::ostream& os); 509 template <typename TDGR> 510 friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 511 const std::string& fn); 512 template <typename TDGR> 513 friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 514 const char *fn); 517 515 518 516 DigraphWriter(DigraphWriter& other) … … 725 723 726 724 if (label == 0) { 727 IdMap<D igraph, Node> id_map(_digraph);728 _writer_bits::MapLess<IdMap<D igraph, Node> > id_less(id_map);725 IdMap<DGR, Node> id_map(_digraph); 726 _writer_bits::MapLess<IdMap<DGR, Node> > id_less(id_map); 729 727 std::sort(nodes.begin(), nodes.end(), id_less); 730 728 } else { … … 810 808 811 809 if (label == 0) { 812 IdMap<D igraph, Arc> id_map(_digraph);813 _writer_bits::MapLess<IdMap<D igraph, Arc> > id_less(id_map);810 IdMap<DGR, Arc> id_map(_digraph); 811 _writer_bits::MapLess<IdMap<DGR, Arc> > id_less(id_map); 814 812 std::sort(arcs.begin(), arcs.end(), id_less); 815 813 } else { … … 916 914 }; 917 915 916 /// \ingroup lemon_io 917 /// 918 /// \brief Return a \ref DigraphWriter class 919 /// 920 /// This function just returns a \ref DigraphWriter class. 921 /// 922 /// With this function a digraph can be write to a file or output 923 /// stream in \ref lgf-format "LGF" format with several maps and 924 /// attributes. For example, with the following code a network flow 925 /// problem can be written to the standard output, i.e. a digraph 926 /// with a \e capacity map on the arcs and \e source and \e target 927 /// nodes: 928 /// 929 ///\code 930 ///ListDigraph digraph; 931 ///ListDigraph::ArcMap<int> cap(digraph); 932 ///ListDigraph::Node src, trg; 933 /// // Setting the capacity map and source and target nodes 934 ///digraphWriter(digraph, std::cout). 935 /// arcMap("capacity", cap). 936 /// node("source", src). 937 /// node("target", trg). 938 /// run(); 939 ///\endcode 940 /// 941 /// For a complete documentation, please see the \ref DigraphWriter 942 /// class documentation. 943 /// \warning Don't forget to put the \ref DigraphWriter::run() "run()" 944 /// to the end of the parameter list. 945 /// \relates DigraphWriter 946 /// \sa digraphWriter(const TDGR& digraph, const std::string& fn) 947 /// \sa digraphWriter(const TDGR& digraph, const char* fn) 948 template <typename TDGR> 949 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, std::ostream& os) { 950 DigraphWriter<TDGR> tmp(digraph, os); 951 return tmp; 952 } 953 918 954 /// \brief Return a \ref DigraphWriter class 919 955 /// 920 956 /// This function just returns a \ref DigraphWriter class. 921 957 /// \relates DigraphWriter 922 template <typename Digraph> 923 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph, 924 std::ostream& os) { 925 DigraphWriter<Digraph> tmp(digraph, os); 958 /// \sa digraphWriter(const TDGR& digraph, std::ostream& os) 959 template <typename TDGR> 960 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, 961 const std::string& fn) { 962 DigraphWriter<TDGR> tmp(digraph, fn); 926 963 return tmp; 927 964 } … … 931 968 /// This function just returns a \ref DigraphWriter class. 932 969 /// \relates DigraphWriter 933 template <typename Digraph>934 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,935 const std::string&fn) {936 DigraphWriter< Digraph> tmp(digraph, fn);970 /// \sa digraphWriter(const TDGR& digraph, std::ostream& os) 971 template <typename TDGR> 972 DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn) { 973 DigraphWriter<TDGR> tmp(digraph, fn); 937 974 return tmp; 938 975 } 939 976 940 /// \brief Return a \ref DigraphWriter class 941 /// 942 /// This function just returns a \ref DigraphWriter class. 943 /// \relates DigraphWriter 944 template <typename Digraph> 945 DigraphWriter<Digraph> digraphWriter(const Digraph& digraph, 946 const char* fn) { 947 DigraphWriter<Digraph> tmp(digraph, fn); 948 return tmp; 949 } 950 951 template <typename Graph> 977 template <typename GR> 952 978 class GraphWriter; 953 979 954 template <typename Graph> 955 GraphWriter<Graph> graphWriter(const Graph& graph, 956 std::ostream& os = std::cout); 957 template <typename Graph> 958 GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn); 959 template <typename Graph> 960 GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn); 980 template <typename TGR> 981 GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os = std::cout); 982 template <typename TGR> 983 GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn); 984 template <typename TGR> 985 GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn); 961 986 962 987 /// \ingroup lemon_io … … 980 1005 981 1006 typedef GR Graph; 982 TEMPLATE_GRAPH_TYPEDEFS(G raph);1007 TEMPLATE_GRAPH_TYPEDEFS(GR); 983 1008 984 1009 private: … … 988 1013 bool local_os; 989 1014 990 const G raph& _graph;1015 const GR& _graph; 991 1016 992 1017 std::string _nodes_caption; … … 1020 1045 /// Construct a directed graph writer, which writes to the given 1021 1046 /// output stream. 1022 GraphWriter(const G raph& graph, std::ostream& os = std::cout)1047 GraphWriter(const GR& graph, std::ostream& os = std::cout) 1023 1048 : _os(&os), local_os(false), _graph(graph), 1024 1049 _skip_nodes(false), _skip_edges(false) {} … … 1028 1053 /// Construct a directed graph writer, which writes to the given 1029 1054 /// output file. 1030 GraphWriter(const G raph& graph, const std::string& fn)1055 GraphWriter(const GR& graph, const std::string& fn) 1031 1056 : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph), 1032 1057 _skip_nodes(false), _skip_edges(false) { … … 1041 1066 /// Construct a directed graph writer, which writes to the given 1042 1067 /// output file. 1043 GraphWriter(const G raph& graph, const char* fn)1068 GraphWriter(const GR& graph, const char* fn) 1044 1069 : _os(new std::ofstream(fn)), local_os(true), _graph(graph), 1045 1070 _skip_nodes(false), _skip_edges(false) { … … 1074 1099 private: 1075 1100 1076 template <typename Graph> 1077 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1078 std::ostream& os); 1079 template <typename Graph> 1080 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1081 const std::string& fn); 1082 template <typename Graph> 1083 friend GraphWriter<Graph> graphWriter(const Graph& graph, 1084 const char *fn); 1101 template <typename TGR> 1102 friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os); 1103 template <typename TGR> 1104 friend GraphWriter<TGR> graphWriter(const TGR& graph, 1105 const std::string& fn); 1106 template <typename TGR> 1107 friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn); 1085 1108 1086 1109 GraphWriter(GraphWriter& other) … … 1169 1192 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); 1170 1193 _writer_bits::MapStorageBase<Edge>* forward_storage = 1171 new _writer_bits::GraphArcMapStorage<G raph, true, Map>(_graph, map);1194 new _writer_bits::GraphArcMapStorage<GR, true, Map>(_graph, map); 1172 1195 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1173 1196 _writer_bits::MapStorageBase<Edge>* backward_storage = 1174 new _writer_bits::GraphArcMapStorage<G raph, false, Map>(_graph, map);1197 new _writer_bits::GraphArcMapStorage<GR, false, Map>(_graph, map); 1175 1198 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); 1176 1199 return *this; … … 1186 1209 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); 1187 1210 _writer_bits::MapStorageBase<Edge>* forward_storage = 1188 new _writer_bits::GraphArcMapStorage<G raph, true, Map, Converter>1211 new _writer_bits::GraphArcMapStorage<GR, true, Map, Converter> 1189 1212 (_graph, map, converter); 1190 1213 _edge_maps.push_back(std::make_pair('+' + caption, forward_storage)); 1191 1214 _writer_bits::MapStorageBase<Edge>* backward_storage = 1192 new _writer_bits::GraphArcMapStorage<G raph, false, Map, Converter>1215 new _writer_bits::GraphArcMapStorage<GR, false, Map, Converter> 1193 1216 (_graph, map, converter); 1194 1217 _edge_maps.push_back(std::make_pair('-' + caption, backward_storage)); … … 1248 1271 /// Add an arc writing rule to writer. 1249 1272 GraphWriter& arc(const std::string& caption, const Arc& arc) { 1250 typedef _writer_bits::GraphArcLookUpConverter<G raph> Converter;1273 typedef _writer_bits::GraphArcLookUpConverter<GR> Converter; 1251 1274 Converter converter(_graph, _edge_index); 1252 1275 _writer_bits::ValueStorageBase* storage = … … 1339 1362 1340 1363 if (label == 0) { 1341 IdMap<G raph, Node> id_map(_graph);1342 _writer_bits::MapLess<IdMap<G raph, Node> > id_less(id_map);1364 IdMap<GR, Node> id_map(_graph); 1365 _writer_bits::MapLess<IdMap<GR, Node> > id_less(id_map); 1343 1366 std::sort(nodes.begin(), nodes.end(), id_less); 1344 1367 } else { … … 1424 1447 1425 1448 if (label == 0) { 1426 IdMap<G raph, Edge> id_map(_graph);1427 _writer_bits::MapLess<IdMap<G raph, Edge> > id_less(id_map);1449 IdMap<GR, Edge> id_map(_graph); 1450 _writer_bits::MapLess<IdMap<GR, Edge> > id_less(id_map); 1428 1451 std::sort(edges.begin(), edges.end(), id_less); 1429 1452 } else { … … 1530 1553 }; 1531 1554 1555 /// \ingroup lemon_io 1556 /// 1557 /// \brief Return a \ref GraphWriter class 1558 /// 1559 /// This function just returns a \ref GraphWriter class. 1560 /// 1561 /// With this function a graph can be write to a file or output 1562 /// stream in \ref lgf-format "LGF" format with several maps and 1563 /// attributes. For example, with the following code a weighted 1564 /// matching problem can be written to the standard output, i.e. a 1565 /// graph with a \e weight map on the edges: 1566 /// 1567 ///\code 1568 ///ListGraph graph; 1569 ///ListGraph::EdgeMap<int> weight(graph); 1570 /// // Setting the weight map 1571 ///graphWriter(graph, std::cout). 1572 /// edgeMap("weight", weight). 1573 /// run(); 1574 ///\endcode 1575 /// 1576 /// For a complete documentation, please see the \ref GraphWriter 1577 /// class documentation. 1578 /// \warning Don't forget to put the \ref GraphWriter::run() "run()" 1579 /// to the end of the parameter list. 1580 /// \relates GraphWriter 1581 /// \sa graphWriter(const TGR& graph, const std::string& fn) 1582 /// \sa graphWriter(const TGR& graph, const char* fn) 1583 template <typename TGR> 1584 GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os) { 1585 GraphWriter<TGR> tmp(graph, os); 1586 return tmp; 1587 } 1588 1532 1589 /// \brief Return a \ref GraphWriter class 1533 1590 /// 1534 1591 /// This function just returns a \ref GraphWriter class. 1535 1592 /// \relates GraphWriter 1536 template <typename Graph>1537 GraphWriter<Graph> graphWriter(const Graph& graph,1538 std::ostream& os) {1539 GraphWriter< Graph> tmp(graph, os);1593 /// \sa graphWriter(const TGR& graph, std::ostream& os) 1594 template <typename TGR> 1595 GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn) { 1596 GraphWriter<TGR> tmp(graph, fn); 1540 1597 return tmp; 1541 1598 } … … 1545 1602 /// This function just returns a \ref GraphWriter class. 1546 1603 /// \relates GraphWriter 1547 template <typename Graph> 1548 GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) { 1549 GraphWriter<Graph> tmp(graph, fn); 1550 return tmp; 1551 } 1552 1553 /// \brief Return a \ref GraphWriter class 1554 /// 1555 /// This function just returns a \ref GraphWriter class. 1556 /// \relates GraphWriter 1557 template <typename Graph> 1558 GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) { 1559 GraphWriter<Graph> tmp(graph, fn); 1604 /// \sa graphWriter(const TGR& graph, std::ostream& os) 1605 template <typename TGR> 1606 GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) { 1607 GraphWriter<TGR> tmp(graph, fn); 1560 1608 return tmp; 1561 1609 } … … 1747 1795 }; 1748 1796 1797 /// \ingroup lemon_io 1798 /// 1749 1799 /// \brief Return a \ref SectionWriter class 1750 1800 /// 1751 1801 /// This function just returns a \ref SectionWriter class. 1802 /// 1803 /// Please see SectionWriter documentation about the custom section 1804 /// output. 1805 /// 1752 1806 /// \relates SectionWriter 1807 /// \sa sectionWriter(const std::string& fn) 1808 /// \sa sectionWriter(const char *fn) 1753 1809 inline SectionWriter sectionWriter(std::ostream& os) { 1754 1810 SectionWriter tmp(os); … … 1760 1816 /// This function just returns a \ref SectionWriter class. 1761 1817 /// \relates SectionWriter 1818 /// \sa sectionWriter(std::ostream& os) 1762 1819 inline SectionWriter sectionWriter(const std::string& fn) { 1763 1820 SectionWriter tmp(fn); … … 1769 1826 /// This function just returns a \ref SectionWriter class. 1770 1827 /// \relates SectionWriter 1828 /// \sa sectionWriter(std::ostream& os) 1771 1829 inline SectionWriter sectionWriter(const char* fn) { 1772 1830 SectionWriter tmp(fn); -
test/gomory_hu_test.cc
r593 r643 3 3 #include "test_tools.h" 4 4 #include <lemon/smart_graph.h> 5 #include <lemon/concepts/graph.h> 6 #include <lemon/concepts/maps.h> 5 7 #include <lemon/lgf_reader.h> 6 8 #include <lemon/gomory_hu.h> … … 33 35 "target 3\n"; 34 36 37 void checkGomoryHuCompile() 38 { 39 typedef int Value; 40 typedef concepts::Graph Graph; 41 42 typedef Graph::Node Node; 43 typedef Graph::Edge Edge; 44 typedef concepts::ReadMap<Edge, Value> CapMap; 45 typedef concepts::ReadWriteMap<Node, bool> CutMap; 46 47 Graph g; 48 Node n; 49 CapMap cap; 50 CutMap cut; 51 Value v; 52 int d; 53 54 GomoryHu<Graph, CapMap> gh_test(g, cap); 55 const GomoryHu<Graph, CapMap>& 56 const_gh_test = gh_test; 57 58 gh_test.run(); 59 60 n = const_gh_test.predNode(n); 61 v = const_gh_test.predValue(n); 62 d = const_gh_test.rootDist(n); 63 v = const_gh_test.minCutValue(n, n); 64 v = const_gh_test.minCutMap(n, n, cut); 65 } 66 35 67 GRAPH_TYPEDEFS(Graph); 36 68 typedef Graph::EdgeMap<int> IntEdgeMap; … … 71 103 ght.minCutMap(u, v, cm); 72 104 check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); 73 check(cm[u] != cm[v], "Wrong cut 3");74 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");105 check(cm[u] != cm[v], "Wrong cut 2"); 106 check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); 75 107 76 108 int sum=0; … … 85 117 sum++; 86 118 check(sum == countNodes(graph), "Problem with MinCutNodeIt"); 87 88 119 } 89 120 } -
test/hao_orlin_test.cc
r463 r644 20 20 21 21 #include <lemon/smart_graph.h> 22 #include <lemon/adaptors.h> 23 #include <lemon/concepts/digraph.h> 24 #include <lemon/concepts/maps.h> 25 #include <lemon/lgf_reader.h> 22 26 #include <lemon/hao_orlin.h> 23 27 24 #include <lemon/lgf_reader.h>25 28 #include "test_tools.h" 26 29 … … 38 41 "5\n" 39 42 "@edges\n" 40 " label capacity\n" 41 "0 1 0 2\n" 42 "1 2 1 2\n" 43 "2 0 2 2\n" 44 "3 4 3 2\n" 45 "4 5 4 2\n" 46 "5 3 5 2\n" 47 "2 3 6 3\n"; 43 " cap1 cap2 cap3\n" 44 "0 1 1 1 1 \n" 45 "0 2 2 2 4 \n" 46 "1 2 4 4 4 \n" 47 "3 4 1 1 1 \n" 48 "3 5 2 2 4 \n" 49 "4 5 4 4 4 \n" 50 "5 4 4 4 4 \n" 51 "2 3 1 6 6 \n" 52 "4 0 1 6 6 \n"; 53 54 void checkHaoOrlinCompile() 55 { 56 typedef int Value; 57 typedef concepts::Digraph Digraph; 58 59 typedef Digraph::Node Node; 60 typedef Digraph::Arc Arc; 61 typedef concepts::ReadMap<Arc, Value> CapMap; 62 typedef concepts::WriteMap<Node, bool> CutMap; 63 64 Digraph g; 65 Node n; 66 CapMap cap; 67 CutMap cut; 68 Value v; 69 70 HaoOrlin<Digraph, CapMap> ho_test(g, cap); 71 const HaoOrlin<Digraph, CapMap>& 72 const_ho_test = ho_test; 73 74 ho_test.init(); 75 ho_test.init(n); 76 ho_test.calculateOut(); 77 ho_test.calculateIn(); 78 ho_test.run(); 79 ho_test.run(n); 80 81 v = const_ho_test.minCutValue(); 82 v = const_ho_test.minCutMap(cut); 83 } 84 85 template <typename Graph, typename CapMap, typename CutMap> 86 typename CapMap::Value 87 cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) 88 { 89 typename CapMap::Value sum = 0; 90 for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { 91 if (cut[graph.source(a)] && !cut[graph.target(a)]) 92 sum += cap[a]; 93 } 94 return sum; 95 } 48 96 49 97 int main() { 50 SmartGraph graph; 51 SmartGraph::EdgeMap<int> capacity(graph); 98 SmartDigraph graph; 99 SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph); 100 SmartDigraph::NodeMap<bool> cut(graph); 52 101 53 istringstream lgfs(lgf); 54 graphReader(graph, lgfs). 55 edgeMap("capacity", capacity).run(); 102 istringstream input(lgf); 103 digraphReader(graph, input) 104 .arcMap("cap1", cap1) 105 .arcMap("cap2", cap2) 106 .arcMap("cap3", cap3) 107 .run(); 56 108 57 HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity); 58 ho.run(); 109 { 110 HaoOrlin<SmartDigraph> ho(graph, cap1); 111 ho.run(); 112 ho.minCutMap(cut); 113 114 check(ho.minCutValue() == 1, "Wrong cut value"); 115 check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); 116 } 117 { 118 HaoOrlin<SmartDigraph> ho(graph, cap2); 119 ho.run(); 120 ho.minCutMap(cut); 59 121 60 check(ho.minCutValue() == 3, "Wrong cut value"); 122 check(ho.minCutValue() == 1, "Wrong cut value"); 123 check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); 124 } 125 { 126 HaoOrlin<SmartDigraph> ho(graph, cap3); 127 ho.run(); 128 ho.minCutMap(cut); 129 130 check(ho.minCutValue() == 1, "Wrong cut value"); 131 check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); 132 } 133 134 typedef Undirector<SmartDigraph> UGraph; 135 UGraph ugraph(graph); 136 137 { 138 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1); 139 ho.run(); 140 ho.minCutMap(cut); 141 142 check(ho.minCutValue() == 2, "Wrong cut value"); 143 check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); 144 } 145 { 146 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2); 147 ho.run(); 148 ho.minCutMap(cut); 149 150 check(ho.minCutValue() == 5, "Wrong cut value"); 151 check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); 152 } 153 { 154 HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3); 155 ho.run(); 156 ho.minCutMap(cut); 157 158 check(ho.minCutValue() == 5, "Wrong cut value"); 159 check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); 160 } 61 161 62 162 return 0;
Note: See TracChangeset
for help on using the changeset viewer.
