Changeset 474:fbd6e04acf44 in lemon
 Timestamp:
 01/09/09 12:54:27 (13 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r434 r474 63 63 64 64 /** 65 @defgroup graph_adaptors Adaptor Classes for graphs65 @defgroup graph_adaptors Adaptor Classes for Graphs 66 66 @ingroup graphs 67 \brief This group contains several adaptor classes for digraphs and graphs 67 \brief Adaptor classes for digraphs and graphs 68 69 This group contains several useful adaptor classes for digraphs and graphs. 68 70 69 71 The main parts of LEMON are the different graph structures, generic 70 graph algorithms, graph concepts which couple these, and graph72 graph algorithms, graph concepts, which couple them, and graph 71 73 adaptors. While the previous notions are more or less clear, the 72 74 latter one needs further explanation. Graph adaptors are graph classes … … 74 76 75 77 A short example makes this much clearer. Suppose that we have an 76 instance \c g of a directed graph type say ListDigraph and an algorithm78 instance \c g of a directed graph type, say ListDigraph and an algorithm 77 79 \code 78 80 template <typename Digraph> … … 82 84 (in time or in memory usage) to copy \c g with the reversed 83 85 arcs. In this case, an adaptor class is used, which (according 84 to LEMON digraph concepts) works as a digraph. The adaptor uses the85 original digraph structure and digraph operations when methods of the 86 reversed oriented graph are called. This means that the adaptor have 87 minor memory usage, and do not perform sophisticated algorithmic86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. 87 The adaptor uses the original digraph structure and digraph operations when 88 methods of the reversed oriented graph are called. This means that the adaptor 89 have minor memory usage, and do not perform sophisticated algorithmic 88 90 actions. The purpose of it is to give a tool for the cases when a 89 91 graph have to be used in a specific alteration. If this alteration is 90 obtained by a usual construction like filtering the arcset or92 obtained by a usual construction like filtering the node or the arc set or 91 93 considering a new orientation, then an adaptor is worthwhile to use. 92 94 To come back to the reverse oriented graph, in this situation … … 97 99 \code 98 100 ListDigraph g; 99 ReverseDigraph<List Graph> rg(g);101 ReverseDigraph<ListDigraph> rg(g); 100 102 int result = algorithm(rg); 101 103 \endcode 102 After running the algorithm, the originalgraph \c g is untouched.103 This techniques give srise to an elegant code, and based on stable104 During running the algorithm, the original digraph \c g is untouched. 105 This techniques give rise to an elegant code, and based on stable 104 106 graph adaptors, complex algorithms can be implemented easily. 105 107 106 In flow, circulation and bipartitematching problems, the residual108 In flow, circulation and matching problems, the residual 107 109 graph is of particular importance. Combining an adaptor implementing 108 this , shortest path algorithms andminimum mean cycle algorithms,110 this with shortest path algorithms or minimum mean cycle algorithms, 109 111 a range of weighted and cardinality optimization algorithms can be 110 112 obtained. For other examples, the interested user is referred to the … … 113 115 The behavior of graph adaptors can be very different. Some of them keep 114 116 capabilities of the original graph while in other cases this would be 115 meaningless. This means that the concepts that they are models of depend 116 on the graph adaptor, and the wrapped graph(s). 117 If an arc of \c rg is deleted, this is carried out by deleting the 118 corresponding arc of \c g, thus the adaptor modifies the original graph. 119 120 But for a residual graph, this operation has no sense. 117 meaningless. This means that the concepts that they meet depend 118 on the graph adaptor, and the wrapped graph. 119 For example, if an arc of a reversed digraph is deleted, this is carried 120 out by deleting the corresponding arc of the original digraph, thus the 121 adaptor modifies the original digraph. 122 However in case of a residual digraph, this operation has no sense. 123 121 124 Let us stand one more example here to simplify your work. 122 Rev GraphAdaptorhas constructor125 ReverseDigraph has constructor 123 126 \code 124 127 ReverseDigraph(Digraph& digraph); 125 128 \endcode 126 This means that in a situation, when a <tt>const ListDigraph&</tt>129 This means that in a situation, when a <tt>const %ListDigraph&</tt> 127 130 reference to a graph is given, then it have to be instantiated with 128 <tt>Digraph=const ListDigraph</tt>.131 <tt>Digraph=const %ListDigraph</tt>. 129 132 \code 130 133 int algorithm1(const ListDigraph& g) { 131 Rev GraphAdaptor<const ListDigraph> rg(g);134 ReverseDigraph<const ListDigraph> rg(g); 132 135 return algorithm2(rg); 133 136 } 
lemon/adaptors.h
r473 r474 22 22 /// \ingroup graph_adaptors 23 23 /// \file 24 /// \brief Several graph adaptors24 /// \brief Adaptor classes for digraphs and graphs 25 25 /// 26 26 /// This file contains several useful adaptors for digraphs and graphs. … … 347 347 /// \ingroup graph_adaptors 348 348 /// 349 /// \brief A digraph adaptor which reverses the orientation of the arcs. 350 /// 351 /// ReverseDigraph reverses the arcs in the adapted digraph. The 352 /// SubDigraph is conform to the \ref concepts::Digraph 353 /// "Digraph concept". 354 /// 355 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 356 /// "Digraph concept". The type can be specified to be const. 349 /// \brief Adaptor class for reversing the orientation of the arcs in 350 /// a digraph. 351 /// 352 /// ReverseDigraph can be used for reversing the arcs in a digraph. 353 /// It conforms to the \ref concepts::Digraph "Digraph" concept. 354 /// 355 /// The adapted digraph can also be modified through this adaptor 356 /// by adding or removing nodes or arcs, unless the \c _Digraph template 357 /// parameter is set to be \c const. 358 /// 359 /// \tparam _Digraph The type of the adapted digraph. 360 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 361 /// It can also be specified to be \c const. 362 /// 363 /// \note The \c Node and \c Arc types of this adaptor and the adapted 364 /// digraph are convertible to each other. 357 365 template<typename _Digraph> 358 366 class ReverseDigraph : … … 368 376 /// \brief Constructor 369 377 /// 370 /// Creates a reverse digraph adaptor for the given digraph 378 /// Creates a reverse digraph adaptor for the given digraph. 371 379 explicit ReverseDigraph(Digraph& digraph) { 372 380 Parent::setDigraph(digraph); … … 374 382 }; 375 383 376 /// \brief Just gives back a reverse digraph adaptor 377 /// 378 /// Just gives back a reverse digraph adaptor 384 /// \brief Returns a readonly ReverseDigraph adaptor 385 /// 386 /// This function just returns a readonly \ref ReverseDigraph adaptor. 387 /// \ingroup graph_adaptors 388 /// \relates ReverseDigraph 379 389 template<typename Digraph> 380 390 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 381 391 return ReverseDigraph<const Digraph>(digraph); 382 392 } 393 383 394 384 395 template <typename _Digraph, typename _NodeFilterMap, … … 686 697 /// \ingroup graph_adaptors 687 698 /// 688 /// \brief An adaptor for hiding nodes and arcs in a digraph 689 /// 690 /// SubDigraph hides nodes and arcs in a digraph. A bool node map 691 /// and a bool arc map must be specified, which define the filters 692 /// for nodes and arcs. Just the nodes and arcs with true value are 693 /// shown in the subdigraph. The SubDigraph is conform to the \ref 694 /// concepts::Digraph "Digraph concept". If the \c _checked parameter 695 /// is true, then the arcs incident to filtered nodes are also 699 /// \brief Adaptor class for hiding nodes and arcs in a digraph 700 /// 701 /// SubDigraph can be used for hiding nodes and arcs in a digraph. 702 /// A \c bool node map and a \c bool arc map must be specified, which 703 /// define the filters for nodes and arcs. 704 /// Only the nodes and arcs with \c true filter value are 705 /// shown in the subdigraph. This adaptor conforms to the \ref 706 /// concepts::Digraph "Digraph" concept. If the \c _checked parameter 707 /// is \c true, then the arcs incident to hidden nodes are also 696 708 /// filtered out. 697 709 /// 698 /// \tparam _Digraph It must be conform to the \ref 699 /// concepts::Digraph "Digraph concept". The type can be specified 700 /// to const. 701 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. 702 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. 703 /// \tparam _checked If the parameter is false then the arc filtering 704 /// is not checked with respect to node filter. Otherwise, each arc 705 /// is automatically filtered, which is incident to a filtered node. 710 /// The adapted digraph can also be modified through this adaptor 711 /// by adding or removing nodes or arcs, unless the \c _Digraph template 712 /// parameter is set to be \c const. 713 /// 714 /// \tparam _Digraph The type of the adapted digraph. 715 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 716 /// It can also be specified to be \c const. 717 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the 718 /// adapted digraph. The default map type is 719 /// \ref concepts::Digraph::NodeMap "_Digraph::NodeMap<bool>". 720 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the 721 /// adapted digraph. The default map type is 722 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>". 723 /// \tparam _checked If this parameter is set to \c false, then the arc 724 /// filtering is not checked with respect to the node filter. 725 /// Otherwise, each arc that is incident to a hidden node is automatically 726 /// filtered out. This is the default option. 727 /// 728 /// \note The \c Node and \c Arc types of this adaptor and the adapted 729 /// digraph are convertible to each other. 706 730 /// 707 731 /// \see FilterNodes 708 732 /// \see FilterArcs 733 #ifdef DOXYGEN 734 template<typename _Digraph, 735 typename _NodeFilterMap, 736 typename _ArcFilterMap, 737 bool _checked> 738 #else 709 739 template<typename _Digraph, 710 740 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 711 741 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 712 742 bool _checked = true> 743 #endif 713 744 class SubDigraph 714 745 : public DigraphAdaptorExtender< 715 746 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { 716 747 public: 748 /// The type of the adapted digraph. 717 749 typedef _Digraph Digraph; 750 /// The type of the node filter map. 718 751 typedef _NodeFilterMap NodeFilterMap; 752 /// The type of the arc filter map. 719 753 typedef _ArcFilterMap ArcFilterMap; 720 754 721 755 typedef DigraphAdaptorExtender< 722 SubDigraphBase< Digraph, NodeFilterMap,ArcFilterMap, _checked> >756 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > 723 757 Parent; 724 758 … … 732 766 /// \brief Constructor 733 767 /// 734 /// Creates a subdigraph for the given digraph with 735 /// given node and arc map filters.768 /// Creates a subdigraph for the given digraph with the 769 /// given node and arc filter maps. 736 770 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 737 771 ArcFilterMap& arc_filter) { … … 741 775 } 742 776 743 /// \brief Hides the node of the graph 744 /// 745 /// This function hides \c n in the digraph, i.e. the iteration 746 /// jumps over it. This is done by simply setting the value of \c n 747 /// to be false in the corresponding nodemap. 777 /// \brief Hides the given node 778 /// 779 /// This function hides the given node in the subdigraph, 780 /// i.e. the iteration jumps over it. 781 /// It is done by simply setting the assigned value of \c n 782 /// to be \c false in the node filter map. 748 783 void hide(const Node& n) const { Parent::hide(n); } 749 784 750 /// \brief Hides the arc of the graph 751 /// 752 /// This function hides \c a in the digraph, i.e. the iteration 753 /// jumps over it. This is done by simply setting the value of \c a 754 /// to be false in the corresponding arcmap. 785 /// \brief Hides the given arc 786 /// 787 /// This function hides the given arc in the subdigraph, 788 /// i.e. the iteration jumps over it. 789 /// It is done by simply setting the assigned value of \c a 790 /// to be \c false in the arc filter map. 755 791 void hide(const Arc& a) const { Parent::hide(a); } 756 792 757 /// \brief Unhides the node of the graph758 /// 759 /// Th e value of \c n is set to be true in the nodemap which stores760 /// hide information. If \c n was hidden previuosly, then it is shown761 /// again793 /// \brief Shows the given node 794 /// 795 /// This function shows the given node in the subdigraph. 796 /// It is done by simply setting the assigned value of \c n 797 /// to be \c true in the node filter map. 762 798 void unHide(const Node& n) const { Parent::unHide(n); } 763 799 764 /// \brief Unhides the arc of the graph765 /// 766 /// Th e value of \c a is set to be true in the arcmap which stores767 /// hide information. If \c a was hidden previuosly, then it is shown768 /// again800 /// \brief Shows the given arc 801 /// 802 /// This function shows the given arc in the subdigraph. 803 /// It is done by simply setting the assigned value of \c a 804 /// to be \c true in the arc filter map. 769 805 void unHide(const Arc& a) const { Parent::unHide(a); } 770 806 771 /// \brief Returns true if \c n is hidden. 772 /// 773 /// Returns true if \c n is hidden. 774 /// 807 /// \brief Returns \c true if the given node is hidden. 808 /// 809 /// This function returns \c true if the given node is hidden. 775 810 bool hidden(const Node& n) const { return Parent::hidden(n); } 776 811 777 /// \brief Returns true if \c a is hidden. 778 /// 779 /// Returns true if \c a is hidden. 780 /// 812 /// \brief Returns \c true if the given arc is hidden. 813 /// 814 /// This function returns \c true if the given arc is hidden. 781 815 bool hidden(const Arc& a) const { return Parent::hidden(a); } 782 816 783 817 }; 784 818 785 /// \brief Just gives back a subdigraph 786 /// 787 /// Just gives back a subdigraph 819 /// \brief Returns a readonly SubDigraph adaptor 820 /// 821 /// This function just returns a readonly \ref SubDigraph adaptor. 822 /// \ingroup graph_adaptors 823 /// \relates SubDigraph 788 824 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 789 825 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> … … 1250 1286 /// \ingroup graph_adaptors 1251 1287 /// 1252 /// \brief A graph adaptor for hiding nodes and edges in an 1253 /// undirected graph. 1254 /// 1255 /// SubGraph hides nodes and edges in a graph. A bool node map and a 1256 /// bool edge map must be specified, which define the filters for 1257 /// nodes and edges. Just the nodes and edges with true value are 1258 /// shown in the subgraph. The SubGraph is conform to the \ref 1259 /// concepts::Graph "Graph concept". If the \c _checked parameter is 1260 /// true, then the edges incident to filtered nodes are also 1288 /// \brief Adaptor class for hiding nodes and edges in an undirected 1289 /// graph. 1290 /// 1291 /// SubGraph can be used for hiding nodes and edges in a graph. 1292 /// A \c bool node map and a \c bool edge map must be specified, which 1293 /// define the filters for nodes and edges. 1294 /// Only the nodes and edges with \c true filter value are 1295 /// shown in the subgraph. This adaptor conforms to the \ref 1296 /// concepts::Graph "Graph" concept. If the \c _checked parameter is 1297 /// \c true, then the edges incident to hidden nodes are also 1261 1298 /// filtered out. 1262 1299 /// 1263 /// \tparam _Graph It must be conform to the \ref 1264 /// concepts::Graph "Graph concept". The type can be specified 1265 /// to const. 1266 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1267 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. 1268 /// \tparam _checked If the parameter is false then the edge filtering 1269 /// is not checked with respect to node filter. Otherwise, each edge 1270 /// is automatically filtered, which is incident to a filtered node. 1300 /// The adapted graph can also be modified through this adaptor 1301 /// by adding or removing nodes or edges, unless the \c _Graph template 1302 /// parameter is set to be \c const. 1303 /// 1304 /// \tparam _Graph The type of the adapted graph. 1305 /// It must conform to the \ref concepts::Graph "Graph" concept. 1306 /// It can also be specified to be \c const. 1307 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the 1308 /// adapted graph. The default map type is 1309 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>". 1310 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the 1311 /// adapted graph. The default map type is 1312 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". 1313 /// \tparam _checked If this parameter is set to \c false, then the edge 1314 /// filtering is not checked with respect to the node filter. 1315 /// Otherwise, each edge that is incident to a hidden node is automatically 1316 /// filtered out. This is the default option. 1317 /// 1318 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1319 /// adapted graph are convertible to each other. 1271 1320 /// 1272 1321 /// \see FilterNodes 1273 1322 /// \see FilterEdges 1274 template<typename _Graph, typename NodeFilterMap, 1275 typename EdgeFilterMap, bool _checked = true> 1323 #ifdef DOXYGEN 1324 template<typename _Graph, 1325 typename _NodeFilterMap, 1326 typename _EdgeFilterMap, 1327 bool _checked> 1328 #else 1329 template<typename _Graph, 1330 typename _NodeFilterMap = typename _Graph::template NodeMap<bool>, 1331 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>, 1332 bool _checked = true> 1333 #endif 1276 1334 class SubGraph 1277 1335 : public GraphAdaptorExtender< 1278 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { 1279 public: 1336 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > { 1337 public: 1338 /// The type of the adapted graph. 1280 1339 typedef _Graph Graph; 1340 /// The type of the node filter map. 1341 typedef _NodeFilterMap NodeFilterMap; 1342 /// The type of the edge filter map. 1343 typedef _EdgeFilterMap EdgeFilterMap; 1344 1281 1345 typedef GraphAdaptorExtender< 1282 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;1346 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent; 1283 1347 1284 1348 typedef typename Parent::Node Node; … … 1291 1355 /// \brief Constructor 1292 1356 /// 1293 /// Creates a subgraph for the given graph with given node and1294 /// edge map filters.1295 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map,1357 /// Creates a subgraph for the given graph with the given node 1358 /// and edge filter maps. 1359 SubGraph(Graph& graph, NodeFilterMap& node_filter_map, 1296 1360 EdgeFilterMap& edge_filter_map) { 1297 setGraph( _graph);1361 setGraph(graph); 1298 1362 setNodeFilterMap(node_filter_map); 1299 1363 setEdgeFilterMap(edge_filter_map); 1300 1364 } 1301 1365 1302 /// \brief Hides the node of the graph 1303 /// 1304 /// This function hides \c n in the graph, i.e. the iteration 1305 /// jumps over it. This is done by simply setting the value of \c n 1306 /// to be false in the corresponding nodemap. 1366 /// \brief Hides the given node 1367 /// 1368 /// This function hides the given node in the subgraph, 1369 /// i.e. the iteration jumps over it. 1370 /// It is done by simply setting the assigned value of \c n 1371 /// to be \c false in the node filter map. 1307 1372 void hide(const Node& n) const { Parent::hide(n); } 1308 1373 1309 /// \brief Hides the edge of the graph 1310 /// 1311 /// This function hides \c e in the graph, i.e. the iteration 1312 /// jumps over it. This is done by simply setting the value of \c e 1313 /// to be false in the corresponding edgemap. 1374 /// \brief Hides the given edge 1375 /// 1376 /// This function hides the given edge in the subgraph, 1377 /// i.e. the iteration jumps over it. 1378 /// It is done by simply setting the assigned value of \c e 1379 /// to be \c false in the edge filter map. 1314 1380 void hide(const Edge& e) const { Parent::hide(e); } 1315 1381 1316 /// \brief Unhides the node of the graph1317 /// 1318 /// Th e value of \c n is set to be true in the nodemap which stores1319 /// hide information. If \c n was hidden previuosly, then it is shown1320 /// again1382 /// \brief Shows the given node 1383 /// 1384 /// This function shows the given node in the subgraph. 1385 /// It is done by simply setting the assigned value of \c n 1386 /// to be \c true in the node filter map. 1321 1387 void unHide(const Node& n) const { Parent::unHide(n); } 1322 1388 1323 /// \brief Unhides the edge of the graph1324 /// 1325 /// Th e value of \c e is set to be true in the edgemap which stores1326 /// hide information. If \c e was hidden previuosly, then it is shown1327 /// again1389 /// \brief Shows the given edge 1390 /// 1391 /// This function shows the given edge in the subgraph. 1392 /// It is done by simply setting the assigned value of \c e 1393 /// to be \c true in the edge filter map. 1328 1394 void unHide(const Edge& e) const { Parent::unHide(e); } 1329 1395 1330 /// \brief Returns true if \c n is hidden. 1331 /// 1332 /// Returns true if \c n is hidden. 1333 /// 1396 /// \brief Returns \c true if the given node is hidden. 1397 /// 1398 /// This function returns \c true if the given node is hidden. 1334 1399 bool hidden(const Node& n) const { return Parent::hidden(n); } 1335 1400 1336 /// \brief Returns true if \c e is hidden. 1337 /// 1338 /// Returns true if \c e is hidden. 1339 /// 1401 /// \brief Returns \c true if the given edge is hidden. 1402 /// 1403 /// This function returns \c true if the given edge is hidden. 1340 1404 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1341 1405 }; 1342 1406 1343 /// \brief Just gives back a subgraph 1344 /// 1345 /// Just gives back a subgraph 1407 /// \brief Returns a readonly SubGraph adaptor 1408 /// 1409 /// This function just returns a readonly \ref SubGraph adaptor. 1410 /// \ingroup graph_adaptors 1411 /// \relates SubGraph 1346 1412 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1347 1413 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> … … 1374 1440 } 1375 1441 1442 1376 1443 /// \ingroup graph_adaptors 1377 1444 /// 1378 /// \brief An adaptor for hiding nodes from a digraph or a graph. 1379 /// 1380 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 1381 /// node map must be specified, which defines the filters for 1382 /// nodes. Just the unfiltered nodes and the arcs or edges incident 1383 /// to unfiltered nodes are shown in the subdigraph or subgraph. The 1384 /// FilterNodes is conform to the \ref concepts::Digraph 1385 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 1386 /// on the \c _Digraph template parameter. If the \c _checked 1387 /// parameter is true, then the arc or edges incident to filtered nodes 1388 /// are also filtered out. 1389 /// 1390 /// \tparam _Digraph It must be conform to the \ref 1391 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 1392 /// "Graph concept". The type can be specified to be const. 1393 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1394 /// \tparam _checked If the parameter is false then the arc or edge 1395 /// filtering is not checked with respect to node filter. In this 1396 /// case just isolated nodes can be filtered out from the 1397 /// graph. 1445 /// \brief Adaptor class for hiding nodes in a digraph or a graph. 1446 /// 1447 /// FilterNodes adaptor can be used for hiding nodes in a digraph or a 1448 /// graph. A \c bool node map must be specified, which defines the filter 1449 /// for the nodes. Only the nodes with \c true filter value and the 1450 /// arcs/edges incident to nodes both with \c true filter value are shown 1451 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph 1452 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept 1453 /// depending on the \c _Graph template parameter. 1454 /// 1455 /// The adapted (di)graph can also be modified through this adaptor 1456 /// by adding or removing nodes or arcs/edges, unless the \c _Graph template 1457 /// parameter is set to be \c const. 1458 /// 1459 /// \tparam _Graph The type of the adapted digraph or graph. 1460 /// It must conform to the \ref concepts::Digraph "Digraph" concept 1461 /// or the \ref concepts::Graph "Graph" concept. 1462 /// It can also be specified to be \c const. 1463 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the 1464 /// adapted (di)graph. The default map type is 1465 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>". 1466 /// \tparam _checked If this parameter is set to \c false then the arc/edge 1467 /// filtering is not checked with respect to the node filter. In this 1468 /// case only isolated nodes can be filtered out from the graph. 1469 /// Otherwise, each arc/edge that is incident to a hidden node is 1470 /// automatically filtered out. This is the default option. 1471 /// 1472 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the 1473 /// adapted (di)graph are convertible to each other. 1398 1474 #ifdef DOXYGEN 1399 template<typename _ Digraph,1400 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>,1401 bool _checked = true>1475 template<typename _Graph, 1476 typename _NodeFilterMap, 1477 bool _checked> 1402 1478 #else 1403 1479 template<typename _Digraph, … … 1431 1507 /// \brief Constructor 1432 1508 /// 1433 /// Creates a n adaptor for the given digraph or graph with1509 /// Creates a subgraph for the given digraph or graph with the 1434 1510 /// given node filter map. 1435 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 1511 #ifdef DOXYGEN 1512 FilterNodes(_Graph& graph, _NodeFilterMap& node_filter) : 1513 #else 1514 FilterNodes(Digraph& graph, NodeFilterMap& node_filter) : 1515 #endif 1436 1516 Parent(), const_true_map(true) { 1437 Parent::setDigraph( _digraph);1517 Parent::setDigraph(graph); 1438 1518 Parent::setNodeFilterMap(node_filter); 1439 1519 Parent::setArcFilterMap(const_true_map); 1440 1520 } 1441 1521 1442 /// \brief Hides the node of the graph 1443 /// 1444 /// This function hides \c n in the digraph or graph, i.e. the iteration 1445 /// jumps over it. This is done by simply setting the value of \c n 1446 /// to be false in the corresponding node map. 1522 /// \brief Hides the given node 1523 /// 1524 /// This function hides the given node in the subgraph, 1525 /// i.e. the iteration jumps over it. 1526 /// It is done by simply setting the assigned value of \c n 1527 /// to be \c false in the node filter map. 1447 1528 void hide(const Node& n) const { Parent::hide(n); } 1448 1529 1449 /// \brief Unhides the node of the graph1450 /// 1451 /// Th e value of \c n is set to be true in the nodemap which stores1452 /// hide information. If \c n was hidden previuosly, then it is shown1453 /// again1530 /// \brief Shows the given node 1531 /// 1532 /// This function shows the given node in the subgraph. 1533 /// It is done by simply setting the assigned value of \c n 1534 /// to be \c true in the node filter map. 1454 1535 void unHide(const Node& n) const { Parent::unHide(n); } 1455 1536 1456 /// \brief Returns true if \c n is hidden. 1457 /// 1458 /// Returns true if \c n is hidden. 1459 /// 1537 /// \brief Returns \c true if the given node is hidden. 1538 /// 1539 /// This function returns \c true if the given node is hidden. 1460 1540 bool hidden(const Node& n) const { return Parent::hidden(n); } 1461 1541 … … 1497 1577 1498 1578 1499 /// \brief Just gives back a FilterNodes adaptor 1500 /// 1501 /// Just gives back a FilterNodes adaptor 1579 /// \brief Returns a readonly FilterNodes adaptor 1580 /// 1581 /// This function just returns a readonly \ref FilterNodes adaptor. 1582 /// \ingroup graph_adaptors 1583 /// \relates FilterNodes 1502 1584 template<typename Digraph, typename NodeFilterMap> 1503 1585 FilterNodes<const Digraph, NodeFilterMap> … … 1514 1596 /// \ingroup graph_adaptors 1515 1597 /// 1516 /// \brief An adaptor for hiding arcs from a digraph. 1517 /// 1518 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 1519 /// be specified, which defines the filters for arcs. Just the 1520 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 1521 /// conform to the \ref concepts::Digraph "Digraph concept". 1522 /// 1523 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 1524 /// "Digraph concept". The type can be specified to be const. 1525 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 1526 /// graph. 1527 template<typename _Digraph, typename _ArcFilterMap> 1598 /// \brief Adaptor class for hiding arcs in a digraph. 1599 /// 1600 /// FilterArcs adaptor can be used for hiding arcs in a digraph. 1601 /// A \c bool arc map must be specified, which defines the filter for 1602 /// the arcs. Only the arcs with \c true filter value are shown in the 1603 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph 1604 /// "Digraph" concept. 1605 /// 1606 /// The adapted digraph can also be modified through this adaptor 1607 /// by adding or removing nodes or arcs, unless the \c _Digraph template 1608 /// parameter is set to be \c const. 1609 /// 1610 /// \tparam _Digraph The type of the adapted digraph. 1611 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 1612 /// It can also be specified to be \c const. 1613 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the 1614 /// adapted digraph. The default map type is 1615 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>". 1616 /// 1617 /// \note The \c Node and \c Arc types of this adaptor and the adapted 1618 /// digraph are convertible to each other. 1619 #ifdef DOXYGEN 1620 template<typename _Digraph, 1621 typename _ArcFilterMap> 1622 #else 1623 template<typename _Digraph, 1624 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> > 1625 #endif 1528 1626 class FilterArcs : 1529 1627 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 1530 1628 _ArcFilterMap, false> { 1531 1629 public: 1630 1532 1631 typedef _Digraph Digraph; 1533 1632 typedef _ArcFilterMap ArcFilterMap; … … 1549 1648 /// \brief Constructor 1550 1649 /// 1551 /// Creates a FilterArcs adaptor for the given graph with1552 /// given arc map filter.1650 /// Creates a subdigraph for the given digraph with the given arc 1651 /// filter map. 1553 1652 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1554 1653 : Parent(), const_true_map(true) { … … 1558 1657 } 1559 1658 1560 /// \brief Hides the arc of the graph 1561 /// 1562 /// This function hides \c a in the graph, i.e. the iteration 1563 /// jumps over it. This is done by simply setting the value of \c a 1564 /// to be false in the corresponding arc map. 1659 /// \brief Hides the given arc 1660 /// 1661 /// This function hides the given arc in the subdigraph, 1662 /// i.e. the iteration jumps over it. 1663 /// It is done by simply setting the assigned value of \c a 1664 /// to be \c false in the arc filter map. 1565 1665 void hide(const Arc& a) const { Parent::hide(a); } 1566 1666 1567 /// \brief Unhides the arc of the graph1568 /// 1569 /// Th e value of \c a is set to be true in the arcmap which stores1570 /// hide information. If \c a was hidden previuosly, then it is shown1571 /// again1667 /// \brief Shows the given arc 1668 /// 1669 /// This function shows the given arc in the subdigraph. 1670 /// It is done by simply setting the assigned value of \c a 1671 /// to be \c true in the arc filter map. 1572 1672 void unHide(const Arc& a) const { Parent::unHide(a); } 1573 1673 1574 /// \brief Returns true if \c a is hidden. 1575 /// 1576 /// Returns true if \c a is hidden. 1577 /// 1674 /// \brief Returns \c true if the given arc is hidden. 1675 /// 1676 /// This function returns \c true if the given arc is hidden. 1578 1677 bool hidden(const Arc& a) const { return Parent::hidden(a); } 1579 1678 1580 1679 }; 1581 1680 1582 /// \brief Just gives back an FilterArcs adaptor 1583 /// 1584 /// Just gives back an FilterArcs adaptor 1681 /// \brief Returns a readonly FilterArcs adaptor 1682 /// 1683 /// This function just returns a readonly \ref FilterArcs adaptor. 1684 /// \ingroup graph_adaptors 1685 /// \relates FilterArcs 1585 1686 template<typename Digraph, typename ArcFilterMap> 1586 1687 FilterArcs<const Digraph, ArcFilterMap> … … 1597 1698 /// \ingroup graph_adaptors 1598 1699 /// 1599 /// \brief An adaptor for hiding edges from a graph. 1600 /// 1601 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 1602 /// be specified, which defines the filters for edges. Just the 1603 /// unfiltered edges are shown in the subdigraph. The FilterEdges is 1604 /// conform to the \ref concepts::Graph "Graph concept". 1605 /// 1606 /// \tparam _Graph It must be conform to the \ref concepts::Graph 1607 /// "Graph concept". The type can be specified to be const. 1608 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 1609 /// graph. 1610 template<typename _Graph, typename _EdgeFilterMap> 1700 /// \brief Adaptor class for hiding edges in a graph. 1701 /// 1702 /// FilterEdges adaptor can be used for hiding edges in a graph. 1703 /// A \c bool edge map must be specified, which defines the filter for 1704 /// the edges. Only the edges with \c true filter value are shown in the 1705 /// subgraph. This adaptor conforms to the \ref concepts::Graph 1706 /// "Graph" concept. 1707 /// 1708 /// The adapted graph can also be modified through this adaptor 1709 /// by adding or removing nodes or edges, unless the \c _Graph template 1710 /// parameter is set to be \c const. 1711 /// 1712 /// \tparam _Graph The type of the adapted graph. 1713 /// It must conform to the \ref concepts::Graph "Graph" concept. 1714 /// It can also be specified to be \c const. 1715 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the 1716 /// adapted graph. The default map type is 1717 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". 1718 /// 1719 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1720 /// adapted graph are convertible to each other. 1721 #ifdef DOXYGEN 1722 template<typename _Graph, 1723 typename _EdgeFilterMap> 1724 #else 1725 template<typename _Graph, 1726 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> > 1727 #endif 1611 1728 class FilterEdges : 1612 1729 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, … … 1629 1746 /// \brief Constructor 1630 1747 /// 1631 /// Creates a FilterEdges adaptor for the given graph with1632 /// given edge map filters.1633 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) :1748 /// Creates a subgraph for the given graph with the given edge 1749 /// filter map. 1750 FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : 1634 1751 Parent(), const_true_map(true) { 1635 Parent::setGraph( _graph);1752 Parent::setGraph(graph); 1636 1753 Parent::setNodeFilterMap(const_true_map); 1637 1754 Parent::setEdgeFilterMap(edge_filter_map); 1638 1755 } 1639 1756 1640 /// \brief Hides the edge of the graph 1641 /// 1642 /// This function hides \c e in the graph, i.e. the iteration 1643 /// jumps over it. This is done by simply setting the value of \c e 1644 /// to be false in the corresponding edgemap. 1757 /// \brief Hides the given edge 1758 /// 1759 /// This function hides the given edge in the subgraph, 1760 /// i.e. the iteration jumps over it. 1761 /// It is done by simply setting the assigned value of \c e 1762 /// to be \c false in the edge filter map. 1645 1763 void hide(const Edge& e) const { Parent::hide(e); } 1646 1764 1647 /// \brief Unhides the edge of the graph1648 /// 1649 /// Th e value of \c e is set to be true in the edgemap which stores1650 /// hide information. If \c e was hidden previuosly, then it is shown1651 /// again1765 /// \brief Shows the given edge 1766 /// 1767 /// This function shows the given edge in the subgraph. 1768 /// It is done by simply setting the assigned value of \c e 1769 /// to be \c true in the edge filter map. 1652 1770 void unHide(const Edge& e) const { Parent::unHide(e); } 1653 1771 1654 /// \brief Returns true if \c e is hidden. 1655 /// 1656 /// Returns true if \c e is hidden. 1657 /// 1772 /// \brief Returns \c true if the given edge is hidden. 1773 /// 1774 /// This function returns \c true if the given edge is hidden. 1658 1775 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1659 1776 1660 1777 }; 1661 1778 1662 /// \brief Just gives back a FilterEdges adaptor 1663 /// 1664 /// Just gives back a FilterEdges adaptor 1779 /// \brief Returns a readonly FilterEdges adaptor 1780 /// 1781 /// This function just returns a readonly \ref FilterEdges adaptor. 1782 /// \ingroup graph_adaptors 1783 /// \relates FilterEdges 1665 1784 template<typename Graph, typename EdgeFilterMap> 1666 1785 FilterEdges<const Graph, EdgeFilterMap> … … 1675 1794 } 1676 1795 1796 1677 1797 template <typename _Digraph> 1678 1798 class UndirectorBase { … … 1713 1833 } 1714 1834 }; 1715 1716 1717 1835 1718 1836 void first(Node& n) const { … … 2069 2187 /// \ingroup graph_adaptors 2070 2188 /// 2071 /// \brief Undirect the graph 2072 /// 2073 /// This adaptor makes an undirected graph from a directed 2074 /// graph. All arcs of the underlying digraph will be showed in the 2075 /// adaptor as an edge. The Orienter adaptor is conform to the \ref 2076 /// concepts::Graph "Graph concept". 2077 /// 2078 /// \tparam _Digraph It must be conform to the \ref 2079 /// concepts::Digraph "Digraph concept". The type can be specified 2080 /// to const. 2189 /// \brief Adaptor class for viewing a digraph as an undirected graph. 2190 /// 2191 /// Undirector adaptor can be used for viewing a digraph as an undirected 2192 /// graph. All arcs of the underlying digraph are showed in the 2193 /// adaptor as an edge (and also as a pair of arcs, of course). 2194 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. 2195 /// 2196 /// The adapted digraph can also be modified through this adaptor 2197 /// by adding or removing nodes or edges, unless the \c _Digraph template 2198 /// parameter is set to be \c const. 2199 /// 2200 /// \tparam _Digraph The type of the adapted digraph. 2201 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2202 /// It can also be specified to be \c const. 2203 /// 2204 /// \note The \c Node type of this adaptor and the adapted digraph are 2205 /// convertible to each other, moreover the \c Edge type of the adaptor 2206 /// and the \c Arc type of the adapted digraph are also convertible to 2207 /// each other. 2208 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type 2209 /// of the adapted digraph.) 2081 2210 template<typename _Digraph> 2082 2211 class Undirector … … 2091 2220 /// \brief Constructor 2092 2221 /// 2093 /// Creates a undirected graph from the given digraph2222 /// Creates an undirected graph from the given digraph. 2094 2223 Undirector(_Digraph& digraph) { 2095 2224 setDigraph(digraph); 2096 2225 } 2097 2226 2098 /// \brief ArcMap combined from two original ArcMap 2099 /// 2100 /// This class adapts two original digraph ArcMap to 2101 /// get an arc map on the undirected graph. 2227 /// \brief Arc map combined from two original arc maps 2228 /// 2229 /// This map adaptor class adapts two arc maps of the underlying 2230 /// digraph to get an arc map of the undirected graph. 2231 /// Its value type is inherited from the first arc map type 2232 /// (\c %ForwardMap). 2102 2233 template <typename _ForwardMap, typename _BackwardMap> 2103 2234 class CombinedArcMap { … … 2109 2240 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 2110 2241 2242 /// The key type of the map 2243 typedef typename Parent::Arc Key; 2244 /// The value type of the map 2111 2245 typedef typename ForwardMap::Value Value; 2112 typedef typename Parent::Arc Key;2113 2246 2114 2247 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; … … 2117 2250 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; 2118 2251 2119 /// \brief Constructor2120 ///2121 2252 /// Constructor 2122 2253 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2123 2254 : _forward(&forward), _backward(&backward) {} 2124 2255 2125 2126 /// \brief Sets the value associated with a key. 2127 /// 2128 /// Sets the value associated with a key. 2256 /// Sets the value associated with the given key. 2129 2257 void set(const Key& e, const Value& a) { 2130 2258 if (Parent::direction(e)) { … … 2135 2263 } 2136 2264 2137 /// \brief Returns the value associated with a key. 2138 /// 2139 /// Returns the value associated with a key. 2265 /// Returns the value associated with the given key. 2140 2266 ConstReturnValue operator[](const Key& e) const { 2141 2267 if (Parent::direction(e)) { … … 2146 2272 } 2147 2273 2148 /// \brief Returns the value associated with a key. 2149 /// 2150 /// Returns the value associated with a key. 2274 /// Returns a reference to the value associated with the given key. 2151 2275 ReturnValue operator[](const Key& e) { 2152 2276 if (Parent::direction(e)) { … … 2164 2288 }; 2165 2289 2166 /// \brief Just gives backa combined arc map2167 /// 2168 /// Just gives back a combined arc map2290 /// \brief Returns a combined arc map 2291 /// 2292 /// This function just returns a combined arc map. 2169 2293 template <typename ForwardMap, typename BackwardMap> 2170 2294 static CombinedArcMap<ForwardMap, BackwardMap> … … 2196 2320 }; 2197 2321 2198 /// \brief Just gives back an undirected view of the given digraph 2199 /// 2200 /// Just gives back an undirected view of the given digraph 2322 /// \brief Returns a readonly Undirector adaptor 2323 /// 2324 /// This function just returns a readonly \ref Undirector adaptor. 2325 /// \ingroup graph_adaptors 2326 /// \relates Undirector 2201 2327 template<typename Digraph> 2202 2328 Undirector<const Digraph> … … 2204 2330 return Undirector<const Digraph>(digraph); 2205 2331 } 2332 2206 2333 2207 2334 template <typename _Graph, typename _DirectionMap> … … 2365 2492 /// \ingroup graph_adaptors 2366 2493 /// 2367 /// \brief Orients the edges of the graph to get a digraph 2368 /// 2369 /// This adaptor orients each edge in the undirected graph. The 2370 /// direction of the arcs stored in an edge node map. The arcs can 2371 /// be easily reverted by the \c reverseArc() member function in the 2372 /// adaptor. The Orienter adaptor is conform to the \ref 2373 /// concepts::Digraph "Digraph concept". 2374 /// 2375 /// \tparam _Graph It must be conform to the \ref concepts::Graph 2376 /// "Graph concept". The type can be specified to be const. 2377 /// \tparam _DirectionMap A bool valued edge map of the the adapted 2378 /// graph. 2379 /// 2380 /// \sa orienter 2494 /// \brief Adaptor class for orienting the edges of a graph to get a digraph 2495 /// 2496 /// Orienter adaptor can be used for orienting the edges of a graph to 2497 /// get a digraph. A \c bool edge map of the underlying graph must be 2498 /// specified, which define the direction of the arcs in the adaptor. 2499 /// The arcs can be easily reversed by the \c reverseArc() member function 2500 /// of the adaptor. 2501 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2502 /// 2503 /// The adapted graph can also be modified through this adaptor 2504 /// by adding or removing nodes or arcs, unless the \c _Graph template 2505 /// parameter is set to be \c const. 2506 /// 2507 /// \tparam _Graph The type of the adapted graph. 2508 /// It must conform to the \ref concepts::Graph "Graph" concept. 2509 /// It can also be specified to be \c const. 2510 /// \tparam _DirectionMap A \c bool (or convertible) edge map of the 2511 /// adapted graph. The default map type is 2512 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". 2513 /// 2514 /// \note The \c Node type of this adaptor and the adapted graph are 2515 /// convertible to each other, moreover the \c Arc type of the adaptor 2516 /// and the \c Edge type of the adapted graph are also convertible to 2517 /// each other. 2518 #ifdef DOXYGEN 2381 2519 template<typename _Graph, 2382 typename DirectionMap = typename _Graph::template EdgeMap<bool> > 2520 typename _DirectionMap> 2521 #else 2522 template<typename _Graph, 2523 typename _DirectionMap = typename _Graph::template EdgeMap<bool> > 2524 #endif 2383 2525 class Orienter : 2384 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2385 public: 2526 public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > { 2527 public: 2528 2529 /// The type of the adapted graph. 2386 2530 typedef _Graph Graph; 2531 /// The type of the direction edge map. 2532 typedef _DirectionMap DirectionMap; 2533 2387 2534 typedef DigraphAdaptorExtender< 2388 OrienterBase<_Graph, DirectionMap> > Parent;2535 OrienterBase<_Graph, _DirectionMap> > Parent; 2389 2536 typedef typename Parent::Arc Arc; 2390 2537 protected: … … 2392 2539 public: 2393 2540 2394 /// \brief Constructor of the adaptor2395 /// 2396 /// Constructor of the adaptor 2541 /// \brief Constructor 2542 /// 2543 /// Constructor of the adaptor. 2397 2544 Orienter(Graph& graph, DirectionMap& direction) { 2398 2545 setGraph(graph); … … 2400 2547 } 2401 2548 2402 /// \brief Reverse arc 2403 /// 2404 /// It reverse the given arc. It simply negate the direction in the map. 2549 /// \brief Reverses the given arc 2550 /// 2551 /// This function reverses the given arc. 2552 /// It is done by simply negate the assigned value of \c a 2553 /// in the direction map. 2405 2554 void reverseArc(const Arc& a) { 2406 2555 Parent::reverseArc(a); … … 2408 2557 }; 2409 2558 2410 /// \brief Just gives back a Orienter 2411 /// 2412 /// Just gives back a Orienter 2559 /// \brief Returns a readonly Orienter adaptor 2560 /// 2561 /// This function just returns a readonly \ref Orienter adaptor. 2562 /// \ingroup graph_adaptors 2563 /// \relates Orienter 2413 2564 template<typename Graph, typename DirectionMap> 2414 2565 Orienter<const Graph, DirectionMap> … … 2492 2643 /// \ingroup graph_adaptors 2493 2644 /// 2494 /// \brief A n adaptor for composing the residualgraph for directed2645 /// \brief Adaptor class for composing the residual digraph for directed 2495 2646 /// flow and circulation problems. 2496 2647 /// 2497 /// An adaptor for composing the residual graph for directed flow and 2498 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2499 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, 2500 /// be functions on the arcset. 2501 /// 2502 /// Then Residual implements the digraph structure with 2503 /// nodeset \f$ V \f$ and arcset \f$ A_{forward}\cup A_{backward} \f$, 2504 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 2505 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so 2506 /// called residual graph. When we take the union 2507 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, 2508 /// i.e. if an arc is in both \f$ A_{forward} \f$ and 2509 /// \f$ A_{backward} \f$, then in the adaptor it appears in both 2510 /// orientation. 2511 /// 2512 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 2513 /// "Digraph concept". The type is implicitly const. 2514 /// \tparam _CapacityMap An arc map of some numeric type, it defines 2515 /// the capacities in the flow problem. The map is implicitly const. 2516 /// \tparam _FlowMap An arc map of some numeric type, it defines 2517 /// the capacities in the flow problem. 2518 /// \tparam _Tolerance Handler for inexact computation. 2648 /// Residual can be used for composing the \e residual digraph for directed 2649 /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2650 /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be 2651 /// functions on the arcs. 2652 /// This adaptor implements a digraph structure with node set \f$ V \f$ 2653 /// and arc set \f$ A_{forward}\cup A_{backward} \f$, 2654 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and 2655 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so 2656 /// called residual digraph. 2657 /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken, 2658 /// multiplicities are counted, i.e. the adaptor has exactly 2659 /// \f$ A_{forward} + A_{backward}\f$ arcs (it may have parallel 2660 /// arcs). 2661 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2662 /// 2663 /// \tparam _Digraph The type of the adapted digraph. 2664 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2665 /// It is implicitly \c const. 2666 /// \tparam _CapacityMap An arc map of some numerical type, which defines 2667 /// the capacities in the flow problem. It is implicitly \c const. 2668 /// The default map type is 2669 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". 2670 /// \tparam _FlowMap An arc map of some numerical type, which defines 2671 /// the flow values in the flow problem. 2672 /// The default map type is \c _CapacityMap. 2673 /// \tparam _Tolerance Tolerance type for handling inexact computation. 2674 /// The default tolerance type depends on the value type of the 2675 /// capacity map. 2676 /// 2677 /// \note This adaptor is implemented using Undirector and FilterArcs 2678 /// adaptors. 2679 /// 2680 /// \note The \c Node type of this adaptor and the adapted digraph are 2681 /// convertible to each other, moreover the \c Arc type of the adaptor 2682 /// is convertible to the \c Arc type of the adapted digraph. 2683 #ifdef DOXYGEN 2684 template<typename _Digraph, 2685 typename _CapacityMap, 2686 typename _FlowMap, 2687 typename _Tolerance> 2688 class Residual 2689 #else 2519 2690 template<typename _Digraph, 2520 2691 typename _CapacityMap = typename _Digraph::template ArcMap<int>, … … 2529 2700 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, 2530 2701 _FlowMap, _Tolerance> > > 2702 #endif 2531 2703 { 2532 2704 public: 2533 2705 2706 /// The type of the underlying digraph. 2534 2707 typedef _Digraph Digraph; 2708 /// The type of the capacity map. 2535 2709 typedef _CapacityMap CapacityMap; 2710 /// The type of the flow map. 2536 2711 typedef _FlowMap FlowMap; 2537 2712 typedef _Tolerance Tolerance; … … 2565 2740 public: 2566 2741 2567 /// \brief Constructor of the residual digraph.2568 /// 2569 /// Constructor of the residual graph. The parameters are the digraph,2570 /// the flow map, the capacity mapand a tolerance object.2742 /// \brief Constructor 2743 /// 2744 /// Constructor of the residual digraph adaptor. The parameters are the 2745 /// digraph, the capacity map, the flow map, and a tolerance object. 2571 2746 Residual(const Digraph& digraph, const CapacityMap& capacity, 2572 2747 FlowMap& flow, const Tolerance& tolerance = Tolerance()) … … 2582 2757 typedef typename Parent::Arc Arc; 2583 2758 2584 /// \brief Gives back the residual capacity of thearc.2585 /// 2586 /// Gives back the residual capacity of thearc.2759 /// \brief Returns the residual capacity of the given arc. 2760 /// 2761 /// Returns the residual capacity of the given arc. 2587 2762 Value residualCapacity(const Arc& a) const { 2588 2763 if (Undirected::direction(a)) { … … 2593 2768 } 2594 2769 2595 /// \brief Augment on the given arc in the residual graph.2596 /// 2597 /// Augment on the given arc in the residual graph. It increase2598 /// or decrease the flow on the original arc depend on the direction2599 /// of the residual arc.2770 /// \brief Augment on the given arc in the residual digraph. 2771 /// 2772 /// Augment on the given arc in the residual digraph. It increases 2773 /// or decreases the flow value on the original arc according to the 2774 /// direction of the residual arc. 2600 2775 void augment(const Arc& a, const Value& v) const { 2601 2776 if (Undirected::direction(a)) { … … 2606 2781 } 2607 2782 2608 /// \brief Returns the direction of the arc. 2609 /// 2610 /// Returns true when the arc is same oriented as the original arc. 2783 /// \brief Returns \c true if the given residual arc is a forward arc. 2784 /// 2785 /// Returns \c true if the given residual arc has the same orientation 2786 /// as the original arc, i.e. it is a so called forward arc. 2611 2787 static bool forward(const Arc& a) { 2612 2788 return Undirected::direction(a); 2613 2789 } 2614 2790 2615 /// \brief Returns the direction of the arc. 2616 /// 2617 /// Returns true when the arc is opposite oriented as the original arc. 2791 /// \brief Returns \c true if the given residual arc is a backward arc. 2792 /// 2793 /// Returns \c true if the given residual arc has the opposite orientation 2794 /// than the original arc, i.e. it is a so called backward arc. 2618 2795 static bool backward(const Arc& a) { 2619 2796 return !Undirected::direction(a); 2620 2797 } 2621 2798 2622 /// \brief Gives back the forward oriented residual arc. 2623 /// 2624 /// Gives back the forward oriented residual arc. 2799 /// \brief Returns the forward oriented residual arc. 2800 /// 2801 /// Returns the forward oriented residual arc related to the given 2802 /// arc of the underlying digraph. 2625 2803 static Arc forward(const typename Digraph::Arc& a) { 2626 2804 return Undirected::direct(a, true); 2627 2805 } 2628 2806 2629 /// \brief Gives back the backward oriented residual arc. 2630 /// 2631 /// Gives back the backward oriented residual arc. 2807 /// \brief Returns the backward oriented residual arc. 2808 /// 2809 /// Returns the backward oriented residual arc related to the given 2810 /// arc of the underlying digraph. 2632 2811 static Arc backward(const typename Digraph::Arc& a) { 2633 2812 return Undirected::direct(a, false); … … 2636 2815 /// \brief Residual capacity map. 2637 2816 /// 2638 /// In generic residual graph the residual capacity can be obtained 2639 /// as a map. 2817 /// This map adaptor class can be used for obtaining the residual 2818 /// capacities as an arc map of the residual digraph. 2819 /// Its value type is inherited from the capacity map. 2640 2820 class ResidualCapacity { 2641 2821 protected: 2642 2822 const Adaptor* _adaptor; 2643 2823 public: 2644 /// The Key type2824 /// The key type of the map 2645 2825 typedef Arc Key; 2646 /// The Value type2826 /// The value type of the map 2647 2827 typedef typename _CapacityMap::Value Value; 2648 2828 … … 2650 2830 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2651 2831 2652 /// \e2832 /// Returns the value associated with the given residual arc 2653 2833 Value operator[](const Arc& a) const { 2654 2834 return _adaptor>residualCapacity(a); … … 3109 3289 /// \ingroup graph_adaptors 3110 3290 /// 3111 /// \brief Split the nodes of a directed graph 3112 /// 3113 /// The SplitNodes adaptor splits each node into an innode and an 3114 /// outnode. Formaly, the adaptor replaces each \f$ u \f$ node in 3115 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node 3116 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the 3117 /// original digraph the new target of the arc will be \f$ u_{in} \f$ 3118 /// and similarly the source of the original \f$ (u, v) \f$ arc 3119 /// will be \f$ u_{out} \f$. The adaptor will add for each node in 3120 /// the original digraph an additional arc which connects 3121 /// \f$ (u_{in}, u_{out}) \f$. 3122 /// 3123 /// The aim of this class is to run algorithm with node costs if the 3124 /// algorithm can use directly just arc costs. In this case we should use 3125 /// a \c SplitNodes and set the node cost of the graph to the 3126 /// bind arc in the adapted graph. 3127 /// 3128 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3129 /// "Digraph concept". The type can be specified to be const. 3291 /// \brief Adaptor class for splitting the nodes of a digraph. 3292 /// 3293 /// SplitNodes adaptor can be used for splitting each node into an 3294 /// \e innode and an \e outnode in a digraph. Formaly, the adaptor 3295 /// replaces each node \f$ u \f$ in the digraph with two nodes, 3296 /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$. 3297 /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the 3298 /// new target of the arc will be \f$ u_{in} \f$ and similarly the 3299 /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$. 3300 /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$ 3301 /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph. 3302 /// 3303 /// The aim of this class is running an algorithm with respect to node 3304 /// costs or capacities if the algorithm considers only arc costs or 3305 /// capacities directly. 3306 /// In this case you can use \c SplitNodes adaptor, and set the node 3307 /// costs/capacities of the original digraph to the \e bind \e arcs 3308 /// in the adaptor. 3309 /// 3310 /// \tparam _Digraph The type of the adapted digraph. 3311 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 3312 /// It is implicitly \c const. 3313 /// 3314 /// \note The \c Node type of this adaptor is converible to the \c Node 3315 /// type of the adapted digraph. 3130 3316 template <typename _Digraph> 3131 3317 class SplitNodes … … 3141 3327 typedef typename Parent::Arc Arc; 3142 3328 3143 /// \brief Constructor of the adaptor.3329 /// \brief Constructor 3144 3330 /// 3145 3331 /// Constructor of the adaptor. … … 3148 3334 } 3149 3335 3150 /// \brief Returns true when the node isinnode.3151 /// 3152 /// Returns true when the node isinnode.3336 /// \brief Returns \c true if the given node is an innode. 3337 /// 3338 /// Returns \c true if the given node is an innode. 3153 3339 static bool inNode(const Node& n) { 3154 3340 return Parent::inNode(n); 3155 3341 } 3156 3342 3157 /// \brief Returns true when the node isoutnode.3158 /// 3159 /// Returns true when the node isoutnode.3343 /// \brief Returns \c true if the given node is an outnode. 3344 /// 3345 /// Returns \c true if the given node is an outnode. 3160 3346 static bool outNode(const Node& n) { 3161 3347 return Parent::outNode(n); 3162 3348 } 3163 3349 3164 /// \brief Returns true when the arc is arc in the original digraph. 3165 /// 3166 /// Returns true when the arc is arc in the original digraph. 3350 /// \brief Returns \c true if the given arc is an original arc. 3351 /// 3352 /// Returns \c true if the given arc is one of the arcs in the 3353 /// original digraph. 3167 3354 static bool origArc(const Arc& a) { 3168 3355 return Parent::origArc(a); 3169 3356 } 3170 3357 3171 /// \brief Returns true when the arc binds an innode and an outnode. 3172 /// 3173 /// Returns true when the arc binds an innode and an outnode. 3358 /// \brief Returns \c true if the given arc is a bind arc. 3359 /// 3360 /// Returns \c true if the given arc is a bind arc, i.e. it connects 3361 /// an innode and an outnode. 3174 3362 static bool bindArc(const Arc& a) { 3175 3363 return Parent::bindArc(a); 3176 3364 } 3177 3365 3178 /// \brief Gives back the innode created from the \cnode.3179 /// 3180 /// Gives back the innode created from the \cnode.3366 /// \brief Returns the innode created from the given original node. 3367 /// 3368 /// Returns the innode created from the given original node. 3181 3369 static Node inNode(const DigraphNode& n) { 3182 3370 return Parent::inNode(n); 3183 3371 } 3184 3372 3185 /// \brief Gives back the outnode created from the \cnode.3186 /// 3187 /// Gives back the outnode created from the \cnode.3373 /// \brief Returns the outnode created from the given original node. 3374 /// 3375 /// Returns the outnode created from the given original node. 3188 3376 static Node outNode(const DigraphNode& n) { 3189 3377 return Parent::outNode(n); 3190 3378 } 3191 3379 3192 /// \brief Gives back the arc binds the two part of the node. 3193 /// 3194 /// Gives back the arc binds the two part of the node. 3380 /// \brief Returns the bind arc that corresponds to the given 3381 /// original node. 3382 /// 3383 /// Returns the bind arc in the adaptor that corresponds to the given 3384 /// original node, i.e. the arc connecting the innode and outnode 3385 /// of \c n. 3195 3386 static Arc arc(const DigraphNode& n) { 3196 3387 return Parent::arc(n); 3197 3388 } 3198 3389 3199 /// \brief Gives back the arc of the original arc. 3200 /// 3201 /// Gives back the arc of the original arc. 3390 /// \brief Returns the arc that corresponds to the given original arc. 3391 /// 3392 /// Returns the arc in the adaptor that corresponds to the given 3393 /// original arc. 3202 3394 static Arc arc(const DigraphArc& a) { 3203 3395 return Parent::arc(a); 3204 3396 } 3205 3397 3206 /// \brief NodeMap combined from two original NodeMap 3207 /// 3208 /// This class adapt two of the original digraph NodeMap to 3209 /// get a node map on the adapted digraph. 3398 /// \brief Node map combined from two original node maps 3399 /// 3400 /// This map adaptor class adapts two node maps of the original digraph 3401 /// to get a node map of the split digraph. 3402 /// Its value type is inherited from the first node map type 3403 /// (\c InNodeMap). 3210 3404 template <typename InNodeMap, typename OutNodeMap> 3211 3405 class CombinedNodeMap { 3212 3406 public: 3213 3407 3408 /// The key type of the map 3214 3409 typedef Node Key; 3410 /// The value type of the map 3215 3411 typedef typename InNodeMap::Value Value; 3216 3412 … … 3221 3417 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference; 3222 3418 3223 /// \brief Constructor 3224 /// 3225 /// Constructor. 3419 /// Constructor 3226 3420 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3227 3421 : _in_map(in_map), _out_map(out_map) {} 3228 3422 3229 /// \brief The subscript operator. 3230 /// 3231 /// The subscript operator. 3423 /// Returns the value associated with the given key. 3424 Value operator[](const Key& key) const { 3425 if (Parent::inNode(key)) { 3426 return _in_map[key]; 3427 } else { 3428 return _out_map[key]; 3429 } 3430 } 3431 3432 /// Returns a reference to the value associated with the given key. 3232 3433 Value& operator[](const Key& key) { 3233 3434 if (Parent::inNode(key)) { … … 3238 3439 } 3239 3440 3240 /// \brief The const subscript operator. 3241 /// 3242 /// The const subscript operator. 3243 Value operator[](const Key& key) const { 3244 if (Parent::inNode(key)) { 3245 return _in_map[key]; 3246 } else { 3247 return _out_map[key]; 3248 } 3249 } 3250 3251 /// \brief The setter function of the map. 3252 /// 3253 /// The setter function of the map. 3441 /// Sets the value associated with the given key. 3254 3442 void set(const Key& key, const Value& value) { 3255 3443 if (Parent::inNode(key)) { … … 3268 3456 3269 3457 3270 /// \brief Just gives backa combined node map3271 /// 3272 /// Just gives back a combined node map3458 /// \brief Returns a combined node map 3459 /// 3460 /// This function just returns a combined node map. 3273 3461 template <typename InNodeMap, typename OutNodeMap> 3274 3462 static CombinedNodeMap<InNodeMap, OutNodeMap> … … 3296 3484 } 3297 3485 3298 /// \brief ArcMap combined from an original ArcMap and a NodeMap 3299 /// 3300 /// This class adapt an original ArcMap and a NodeMap to get an 3301 /// arc map on the adapted digraph 3486 /// \brief Arc map combined from an arc map and a node map of the 3487 /// original digraph. 3488 /// 3489 /// This map adaptor class adapts an arc map and a node map of the 3490 /// original digraph to get an arc map of the split digraph. 3491 /// Its value type is inherited from the original arc map type 3492 /// (\c DigraphArcMap). 3302 3493 template <typename DigraphArcMap, typename DigraphNodeMap> 3303 3494 class CombinedArcMap { 3304 3495 public: 3305 3496 3497 /// The key type of the map 3306 3498 typedef Arc Key; 3499 /// The value type of the map 3307 3500 typedef typename DigraphArcMap::Value Value; 3308 3501 … … 3318 3511 ConstReference; 3319 3512 3320 /// \brief Constructor 3321 /// 3322 /// Constructor. 3513 /// Constructor 3323 3514 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3324 3515 : _arc_map(arc_map), _node_map(node_map) {} 3325 3516 3326 /// \brief The subscript operator. 3327 /// 3328 /// The subscript operator. 3517 /// Returns the value associated with the given key. 3518 Value operator[](const Key& arc) const { 3519 if (Parent::origArc(arc)) { 3520 return _arc_map[arc]; 3521 } else { 3522 return _node_map[arc]; 3523 } 3524 } 3525 3526 /// Returns a reference to the value associated with the given key. 3527 Value& operator[](const Key& arc) { 3528 if (Parent::origArc(arc)) { 3529 return _arc_map[arc]; 3530 } else { 3531 return _node_map[arc]; 3532 } 3533 } 3534 3535 /// Sets the value associated with the given key. 3329 3536 void set(const Arc& arc, const Value& val) { 3330 3537 if (Parent::origArc(arc)) { … … 3335 3542 } 3336 3543 3337 /// \brief The const subscript operator.3338 ///3339 /// The const subscript operator.3340 Value operator[](const Key& arc) const {3341 if (Parent::origArc(arc)) {3342 return _arc_map[arc];3343 } else {3344 return _node_map[arc];3345 }3346 }3347 3348 /// \brief The const subscript operator.3349 ///3350 /// The const subscript operator.3351 Value& operator[](const Key& arc) {3352 if (Parent::origArc(arc)) {3353 return _arc_map[arc];3354 } else {3355 return _node_map[arc];3356 }3357 }3358 3359 3544 private: 3360 3545 DigraphArcMap& _arc_map; … … 3362 3547 }; 3363 3548 3364 /// \brief Just gives backa combined arc map3365 /// 3366 /// Just gives back a combined arc map3549 /// \brief Returns a combined arc map 3550 /// 3551 /// This function just returns a combined arc map. 3367 3552 template <typename DigraphArcMap, typename DigraphNodeMap> 3368 3553 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> … … 3395 3580 }; 3396 3581 3397 /// \brief Just gives back a node splitter 3398 /// 3399 /// Just gives back a node splitter 3582 /// \brief Returns a (readonly) SplitNodes adaptor 3583 /// 3584 /// This function just returns a (readonly) \ref SplitNodes adaptor. 3585 /// \ingroup graph_adaptors 3586 /// \relates SplitNodes 3400 3587 template<typename Digraph> 3401 3588 SplitNodes<Digraph>
Note: See TracChangeset
for help on using the changeset viewer.