Changeset 451:fbd6e04acf44 in lemon1.2 for lemon/adaptors.h
 Timestamp:
 01/09/09 12:54:27 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/adaptors.h
r450 r451 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.