351 /// |
351 /// |
352 /// ReverseDigraph can be used for reversing the arcs in a digraph. |
352 /// ReverseDigraph can be used for reversing the arcs in a digraph. |
353 /// It conforms to the \ref concepts::Digraph "Digraph" concept. |
353 /// It conforms to the \ref concepts::Digraph "Digraph" concept. |
354 /// |
354 /// |
355 /// The adapted digraph can also be modified through this adaptor |
355 /// The adapted digraph can also be modified through this adaptor |
356 /// by adding or removing nodes or arcs, unless the \c _Digraph template |
356 /// by adding or removing nodes or arcs, unless the \c GR template |
357 /// parameter is set to be \c const. |
357 /// parameter is set to be \c const. |
358 /// |
358 /// |
359 /// \tparam _Digraph The type of the adapted digraph. |
359 /// \tparam GR The type of the adapted digraph. |
360 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
360 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
361 /// It can also be specified to be \c const. |
361 /// It can also be specified to be \c const. |
362 /// |
362 /// |
363 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
363 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
364 /// digraph are convertible to each other. |
364 /// digraph are convertible to each other. |
365 template<typename _Digraph> |
365 template<typename GR> |
|
366 #ifdef DOXYGEN |
|
367 class ReverseDigraph { |
|
368 #else |
366 class ReverseDigraph : |
369 class ReverseDigraph : |
367 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { |
370 public DigraphAdaptorExtender<ReverseDigraphBase<GR> > { |
368 public: |
371 #endif |
369 typedef _Digraph Digraph; |
372 public: |
370 typedef DigraphAdaptorExtender< |
373 /// The type of the adapted digraph. |
371 ReverseDigraphBase<_Digraph> > Parent; |
374 typedef GR Digraph; |
|
375 typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent; |
372 protected: |
376 protected: |
373 ReverseDigraph() { } |
377 ReverseDigraph() { } |
374 public: |
378 public: |
375 |
379 |
376 /// \brief Constructor |
380 /// \brief Constructor |
384 /// \brief Returns a read-only ReverseDigraph adaptor |
388 /// \brief Returns a read-only ReverseDigraph adaptor |
385 /// |
389 /// |
386 /// This function just returns a read-only \ref ReverseDigraph adaptor. |
390 /// This function just returns a read-only \ref ReverseDigraph adaptor. |
387 /// \ingroup graph_adaptors |
391 /// \ingroup graph_adaptors |
388 /// \relates ReverseDigraph |
392 /// \relates ReverseDigraph |
389 template<typename Digraph> |
393 template<typename GR> |
390 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { |
394 ReverseDigraph<const GR> reverseDigraph(const GR& digraph) { |
391 return ReverseDigraph<const Digraph>(digraph); |
395 return ReverseDigraph<const GR>(digraph); |
392 } |
396 } |
393 |
397 |
394 |
398 |
395 template <typename _Digraph, typename _NodeFilterMap, |
399 template <typename _Digraph, typename _NodeFilterMap, |
396 typename _ArcFilterMap, bool _checked = true> |
400 typename _ArcFilterMap, bool _checked = true> |
694 /// |
698 /// |
695 /// SubDigraph can be used for hiding nodes and arcs in a digraph. |
699 /// SubDigraph can be used for hiding nodes and arcs in a digraph. |
696 /// A \c bool node map and a \c bool arc map must be specified, which |
700 /// A \c bool node map and a \c bool arc map must be specified, which |
697 /// define the filters for nodes and arcs. |
701 /// define the filters for nodes and arcs. |
698 /// Only the nodes and arcs with \c true filter value are |
702 /// Only the nodes and arcs with \c true filter value are |
699 /// shown in the subdigraph. This adaptor conforms to the \ref |
703 /// shown in the subdigraph. The arcs that are incident to hidden |
700 /// concepts::Digraph "Digraph" concept. If the \c _checked parameter |
704 /// nodes are also filtered out. |
701 /// is \c true, then the arcs incident to hidden nodes are also |
705 /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept. |
702 /// filtered out. |
|
703 /// |
706 /// |
704 /// The adapted digraph can also be modified through this adaptor |
707 /// The adapted digraph can also be modified through this adaptor |
705 /// by adding or removing nodes or arcs, unless the \c _Digraph template |
708 /// by adding or removing nodes or arcs, unless the \c GR template |
706 /// parameter is set to be \c const. |
709 /// parameter is set to be \c const. |
707 /// |
710 /// |
708 /// \tparam _Digraph The type of the adapted digraph. |
711 /// \tparam GR The type of the adapted digraph. |
709 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
712 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
710 /// It can also be specified to be \c const. |
713 /// It can also be specified to be \c const. |
711 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the |
714 /// \tparam NF The type of the node filter map. |
712 /// adapted digraph. The default map type is |
715 /// It must be a \c bool (or convertible) node map of the |
713 /// \ref concepts::Digraph::NodeMap "_Digraph::NodeMap<bool>". |
716 /// adapted digraph. The default type is |
714 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the |
717 /// \ref concepts::Digraph::NodeMap "GR::NodeMap<bool>". |
715 /// adapted digraph. The default map type is |
718 /// \tparam AF The type of the arc filter map. |
716 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>". |
719 /// It must be \c bool (or convertible) arc map of the |
717 /// \tparam _checked If this parameter is set to \c false, then the arc |
720 /// adapted digraph. The default type is |
718 /// filtering is not checked with respect to the node filter. |
721 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>". |
719 /// Otherwise, each arc that is incident to a hidden node is automatically |
|
720 /// filtered out. This is the default option. |
|
721 /// |
722 /// |
722 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
723 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
723 /// digraph are convertible to each other. |
724 /// digraph are convertible to each other. |
724 /// |
725 /// |
725 /// \see FilterNodes |
726 /// \see FilterNodes |
726 /// \see FilterArcs |
727 /// \see FilterArcs |
727 #ifdef DOXYGEN |
728 #ifdef DOXYGEN |
728 template<typename _Digraph, |
729 template<typename GR, typename NF, typename AF> |
729 typename _NodeFilterMap, |
730 class SubDigraph { |
730 typename _ArcFilterMap, |
|
731 bool _checked> |
|
732 #else |
731 #else |
733 template<typename _Digraph, |
732 template<typename GR, |
734 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, |
733 typename NF = typename GR::template NodeMap<bool>, |
735 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, |
734 typename AF = typename GR::template ArcMap<bool> > |
736 bool _checked = true> |
735 class SubDigraph : |
|
736 public DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > { |
737 #endif |
737 #endif |
738 class SubDigraph |
|
739 : public DigraphAdaptorExtender< |
|
740 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { |
|
741 public: |
738 public: |
742 /// The type of the adapted digraph. |
739 /// The type of the adapted digraph. |
743 typedef _Digraph Digraph; |
740 typedef GR Digraph; |
744 /// The type of the node filter map. |
741 /// The type of the node filter map. |
745 typedef _NodeFilterMap NodeFilterMap; |
742 typedef NF NodeFilterMap; |
746 /// The type of the arc filter map. |
743 /// The type of the arc filter map. |
747 typedef _ArcFilterMap ArcFilterMap; |
744 typedef AF ArcFilterMap; |
748 |
745 |
749 typedef DigraphAdaptorExtender< |
746 typedef DigraphAdaptorExtender<SubDigraphBase<GR, NF, AF, true> > |
750 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > |
747 Parent; |
751 Parent; |
|
752 |
748 |
753 typedef typename Parent::Node Node; |
749 typedef typename Parent::Node Node; |
754 typedef typename Parent::Arc Arc; |
750 typedef typename Parent::Arc Arc; |
755 |
751 |
756 protected: |
752 protected: |
825 /// \brief Returns a read-only SubDigraph adaptor |
821 /// \brief Returns a read-only SubDigraph adaptor |
826 /// |
822 /// |
827 /// This function just returns a read-only \ref SubDigraph adaptor. |
823 /// This function just returns a read-only \ref SubDigraph adaptor. |
828 /// \ingroup graph_adaptors |
824 /// \ingroup graph_adaptors |
829 /// \relates SubDigraph |
825 /// \relates SubDigraph |
830 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
826 template<typename GR, typename NF, typename AF> |
831 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> |
827 SubDigraph<const GR, NF, AF> |
832 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { |
828 subDigraph(const GR& digraph, |
833 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> |
829 NF& node_filter_map, AF& arc_filter_map) { |
834 (digraph, nfm, afm); |
830 return SubDigraph<const GR, NF, AF> |
|
831 (digraph, node_filter_map, arc_filter_map); |
835 } |
832 } |
836 |
833 |
837 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
834 template<typename GR, typename NF, typename AF> |
838 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> |
835 SubDigraph<const GR, const NF, AF> |
839 subDigraph(const Digraph& digraph, |
836 subDigraph(const GR& digraph, |
840 const NodeFilterMap& nfm, ArcFilterMap& afm) { |
837 const NF& node_filter_map, AF& arc_filter_map) { |
841 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> |
838 return SubDigraph<const GR, const NF, AF> |
842 (digraph, nfm, afm); |
839 (digraph, node_filter_map, arc_filter_map); |
843 } |
840 } |
844 |
841 |
845 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
842 template<typename GR, typename NF, typename AF> |
846 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> |
843 SubDigraph<const GR, NF, const AF> |
847 subDigraph(const Digraph& digraph, |
844 subDigraph(const GR& digraph, |
848 NodeFilterMap& nfm, const ArcFilterMap& afm) { |
845 NF& node_filter_map, const AF& arc_filter_map) { |
849 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> |
846 return SubDigraph<const GR, NF, const AF> |
850 (digraph, nfm, afm); |
847 (digraph, node_filter_map, arc_filter_map); |
851 } |
848 } |
852 |
849 |
853 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> |
850 template<typename GR, typename NF, typename AF> |
854 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> |
851 SubDigraph<const GR, const NF, const AF> |
855 subDigraph(const Digraph& digraph, |
852 subDigraph(const GR& digraph, |
856 const NodeFilterMap& nfm, const ArcFilterMap& afm) { |
853 const NF& node_filter_map, const AF& arc_filter_map) { |
857 return SubDigraph<const Digraph, const NodeFilterMap, |
854 return SubDigraph<const GR, const NF, const AF> |
858 const ArcFilterMap>(digraph, nfm, afm); |
855 (digraph, node_filter_map, arc_filter_map); |
859 } |
856 } |
860 |
857 |
861 |
858 |
862 template <typename _Graph, typename _NodeFilterMap, |
859 template <typename _Graph, typename _NodeFilterMap, |
863 typename _EdgeFilterMap, bool _checked = true> |
860 typename _EdgeFilterMap, bool _checked = true> |
1290 /// |
1287 /// |
1291 /// SubGraph can be used for hiding nodes and edges in a graph. |
1288 /// 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 |
1289 /// A \c bool node map and a \c bool edge map must be specified, which |
1293 /// define the filters for nodes and edges. |
1290 /// define the filters for nodes and edges. |
1294 /// Only the nodes and edges with \c true filter value are |
1291 /// Only the nodes and edges with \c true filter value are |
1295 /// shown in the subgraph. This adaptor conforms to the \ref |
1292 /// shown in the subgraph. The edges that are incident to hidden |
1296 /// concepts::Graph "Graph" concept. If the \c _checked parameter is |
1293 /// nodes are also filtered out. |
1297 /// \c true, then the edges incident to hidden nodes are also |
1294 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. |
1298 /// filtered out. |
|
1299 /// |
1295 /// |
1300 /// The adapted graph can also be modified through this adaptor |
1296 /// The adapted graph can also be modified through this adaptor |
1301 /// by adding or removing nodes or edges, unless the \c _Graph template |
1297 /// by adding or removing nodes or edges, unless the \c GR template |
1302 /// parameter is set to be \c const. |
1298 /// parameter is set to be \c const. |
1303 /// |
1299 /// |
1304 /// \tparam _Graph The type of the adapted graph. |
1300 /// \tparam GR The type of the adapted graph. |
1305 /// It must conform to the \ref concepts::Graph "Graph" concept. |
1301 /// It must conform to the \ref concepts::Graph "Graph" concept. |
1306 /// It can also be specified to be \c const. |
1302 /// It can also be specified to be \c const. |
1307 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the |
1303 /// \tparam NF The type of the node filter map. |
1308 /// adapted graph. The default map type is |
1304 /// It must be a \c bool (or convertible) node map of the |
1309 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>". |
1305 /// adapted graph. The default type is |
1310 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the |
1306 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". |
1311 /// adapted graph. The default map type is |
1307 /// \tparam EF The type of the edge filter map. |
1312 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". |
1308 /// It must be a \c bool (or convertible) edge map of the |
1313 /// \tparam _checked If this parameter is set to \c false, then the edge |
1309 /// adapted graph. The default type is |
1314 /// filtering is not checked with respect to the node filter. |
1310 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". |
1315 /// Otherwise, each edge that is incident to a hidden node is automatically |
|
1316 /// filtered out. This is the default option. |
|
1317 /// |
1311 /// |
1318 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
1312 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
1319 /// adapted graph are convertible to each other. |
1313 /// adapted graph are convertible to each other. |
1320 /// |
1314 /// |
1321 /// \see FilterNodes |
1315 /// \see FilterNodes |
1322 /// \see FilterEdges |
1316 /// \see FilterEdges |
1323 #ifdef DOXYGEN |
1317 #ifdef DOXYGEN |
1324 template<typename _Graph, |
1318 template<typename GR, typename NF, typename EF> |
1325 typename _NodeFilterMap, |
1319 class SubGraph { |
1326 typename _EdgeFilterMap, |
|
1327 bool _checked> |
|
1328 #else |
1320 #else |
1329 template<typename _Graph, |
1321 template<typename GR, |
1330 typename _NodeFilterMap = typename _Graph::template NodeMap<bool>, |
1322 typename NF = typename GR::template NodeMap<bool>, |
1331 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool>, |
1323 typename EF = typename GR::template EdgeMap<bool> > |
1332 bool _checked = true> |
1324 class SubGraph : |
|
1325 public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > { |
1333 #endif |
1326 #endif |
1334 class SubGraph |
|
1335 : public GraphAdaptorExtender< |
|
1336 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > { |
|
1337 public: |
1327 public: |
1338 /// The type of the adapted graph. |
1328 /// The type of the adapted graph. |
1339 typedef _Graph Graph; |
1329 typedef GR Graph; |
1340 /// The type of the node filter map. |
1330 /// The type of the node filter map. |
1341 typedef _NodeFilterMap NodeFilterMap; |
1331 typedef NF NodeFilterMap; |
1342 /// The type of the edge filter map. |
1332 /// The type of the edge filter map. |
1343 typedef _EdgeFilterMap EdgeFilterMap; |
1333 typedef EF EdgeFilterMap; |
1344 |
1334 |
1345 typedef GraphAdaptorExtender< |
1335 typedef GraphAdaptorExtender< SubGraphBase<GR, NF, EF, true> > |
1346 SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, _checked> > Parent; |
1336 Parent; |
1347 |
1337 |
1348 typedef typename Parent::Node Node; |
1338 typedef typename Parent::Node Node; |
1349 typedef typename Parent::Edge Edge; |
1339 typedef typename Parent::Edge Edge; |
1350 |
1340 |
1351 protected: |
1341 protected: |
1420 /// \brief Returns a read-only SubGraph adaptor |
1410 /// \brief Returns a read-only SubGraph adaptor |
1421 /// |
1411 /// |
1422 /// This function just returns a read-only \ref SubGraph adaptor. |
1412 /// This function just returns a read-only \ref SubGraph adaptor. |
1423 /// \ingroup graph_adaptors |
1413 /// \ingroup graph_adaptors |
1424 /// \relates SubGraph |
1414 /// \relates SubGraph |
1425 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
1415 template<typename GR, typename NF, typename EF> |
1426 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> |
1416 SubGraph<const GR, NF, EF> |
1427 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { |
1417 subGraph(const GR& graph, |
1428 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); |
1418 NF& node_filter_map, EF& edge_filter_map) { |
|
1419 return SubGraph<const GR, NF, EF> |
|
1420 (graph, node_filter_map, edge_filter_map); |
1429 } |
1421 } |
1430 |
1422 |
1431 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
1423 template<typename GR, typename NF, typename EF> |
1432 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> |
1424 SubGraph<const GR, const NF, EF> |
1433 subGraph(const Graph& graph, |
1425 subGraph(const GR& graph, |
1434 const NodeFilterMap& nfm, ArcFilterMap& efm) { |
1426 const NF& node_filter_map, EF& edge_filter_map) { |
1435 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> |
1427 return SubGraph<const GR, const NF, EF> |
1436 (graph, nfm, efm); |
1428 (graph, node_filter_map, edge_filter_map); |
1437 } |
1429 } |
1438 |
1430 |
1439 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
1431 template<typename GR, typename NF, typename EF> |
1440 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> |
1432 SubGraph<const GR, NF, const EF> |
1441 subGraph(const Graph& graph, |
1433 subGraph(const GR& graph, |
1442 NodeFilterMap& nfm, const ArcFilterMap& efm) { |
1434 NF& node_filter_map, const EF& edge_filter_map) { |
1443 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> |
1435 return SubGraph<const GR, NF, const EF> |
1444 (graph, nfm, efm); |
1436 (graph, node_filter_map, edge_filter_map); |
1445 } |
1437 } |
1446 |
1438 |
1447 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> |
1439 template<typename GR, typename NF, typename EF> |
1448 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> |
1440 SubGraph<const GR, const NF, const EF> |
1449 subGraph(const Graph& graph, |
1441 subGraph(const GR& graph, |
1450 const NodeFilterMap& nfm, const ArcFilterMap& efm) { |
1442 const NF& node_filter_map, const EF& edge_filter_map) { |
1451 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> |
1443 return SubGraph<const GR, const NF, const EF> |
1452 (graph, nfm, efm); |
1444 (graph, node_filter_map, edge_filter_map); |
1453 } |
1445 } |
1454 |
1446 |
1455 |
1447 |
1456 /// \ingroup graph_adaptors |
1448 /// \ingroup graph_adaptors |
1457 /// |
1449 /// |
1461 /// graph. A \c bool node map must be specified, which defines the filter |
1453 /// graph. A \c bool node map must be specified, which defines the filter |
1462 /// for the nodes. Only the nodes with \c true filter value and the |
1454 /// for the nodes. Only the nodes with \c true filter value and the |
1463 /// arcs/edges incident to nodes both with \c true filter value are shown |
1455 /// arcs/edges incident to nodes both with \c true filter value are shown |
1464 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph |
1456 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph |
1465 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept |
1457 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept |
1466 /// depending on the \c _Graph template parameter. |
1458 /// depending on the \c GR template parameter. |
1467 /// |
1459 /// |
1468 /// The adapted (di)graph can also be modified through this adaptor |
1460 /// The adapted (di)graph can also be modified through this adaptor |
1469 /// by adding or removing nodes or arcs/edges, unless the \c _Graph template |
1461 /// by adding or removing nodes or arcs/edges, unless the \c GR template |
1470 /// parameter is set to be \c const. |
1462 /// parameter is set to be \c const. |
1471 /// |
1463 /// |
1472 /// \tparam _Graph The type of the adapted digraph or graph. |
1464 /// \tparam GR The type of the adapted digraph or graph. |
1473 /// It must conform to the \ref concepts::Digraph "Digraph" concept |
1465 /// It must conform to the \ref concepts::Digraph "Digraph" concept |
1474 /// or the \ref concepts::Graph "Graph" concept. |
1466 /// or the \ref concepts::Graph "Graph" concept. |
1475 /// It can also be specified to be \c const. |
1467 /// It can also be specified to be \c const. |
1476 /// \tparam _NodeFilterMap A \c bool (or convertible) node map of the |
1468 /// \tparam NF The type of the node filter map. |
1477 /// adapted (di)graph. The default map type is |
1469 /// It must be a \c bool (or convertible) node map of the |
1478 /// \ref concepts::Graph::NodeMap "_Graph::NodeMap<bool>". |
1470 /// adapted (di)graph. The default type is |
1479 /// \tparam _checked If this parameter is set to \c false then the arc/edge |
1471 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". |
1480 /// filtering is not checked with respect to the node filter. In this |
|
1481 /// case only isolated nodes can be filtered out from the graph. |
|
1482 /// Otherwise, each arc/edge that is incident to a hidden node is |
|
1483 /// automatically filtered out. This is the default option. |
|
1484 /// |
1472 /// |
1485 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the |
1473 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the |
1486 /// adapted (di)graph are convertible to each other. |
1474 /// adapted (di)graph are convertible to each other. |
1487 #ifdef DOXYGEN |
1475 #ifdef DOXYGEN |
1488 template<typename _Graph, |
1476 template<typename GR, typename NF> |
1489 typename _NodeFilterMap, |
1477 class FilterNodes { |
1490 bool _checked> |
|
1491 #else |
1478 #else |
1492 template<typename _Digraph, |
1479 template<typename GR, |
1493 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, |
1480 typename NF = typename GR::template NodeMap<bool>, |
1494 bool _checked = true, |
|
1495 typename Enable = void> |
1481 typename Enable = void> |
|
1482 class FilterNodes : |
|
1483 public DigraphAdaptorExtender< |
|
1484 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > { |
1496 #endif |
1485 #endif |
1497 class FilterNodes |
1486 public: |
1498 : public SubDigraph<_Digraph, _NodeFilterMap, |
1487 |
1499 ConstMap<typename _Digraph::Arc, bool>, _checked> { |
1488 typedef GR Digraph; |
1500 public: |
1489 typedef NF NodeFilterMap; |
1501 |
1490 |
1502 typedef _Digraph Digraph; |
1491 typedef DigraphAdaptorExtender< |
1503 typedef _NodeFilterMap NodeFilterMap; |
1492 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > |
1504 |
1493 Parent; |
1505 typedef SubDigraph<Digraph, NodeFilterMap, |
|
1506 ConstMap<typename Digraph::Arc, bool>, _checked> |
|
1507 Parent; |
|
1508 |
1494 |
1509 typedef typename Parent::Node Node; |
1495 typedef typename Parent::Node Node; |
1510 |
1496 |
1511 protected: |
1497 protected: |
1512 ConstMap<typename Digraph::Arc, bool> const_true_map; |
1498 ConstMap<typename Digraph::Arc, bool> const_true_map; |
1558 /// It is the same as \ref status() "status(n, true)". |
1541 /// It is the same as \ref status() "status(n, true)". |
1559 void enable(const Node& n) const { Parent::status(n, true); } |
1542 void enable(const Node& n) const { Parent::status(n, true); } |
1560 |
1543 |
1561 }; |
1544 }; |
1562 |
1545 |
1563 template<typename _Graph, typename _NodeFilterMap, bool _checked> |
1546 template<typename GR, typename NF> |
1564 class FilterNodes<_Graph, _NodeFilterMap, _checked, |
1547 class FilterNodes<GR, NF, |
1565 typename enable_if<UndirectedTagIndicator<_Graph> >::type> |
1548 typename enable_if<UndirectedTagIndicator<GR> >::type> : |
1566 : public SubGraph<_Graph, _NodeFilterMap, |
1549 public GraphAdaptorExtender< |
1567 ConstMap<typename _Graph::Edge, bool>, _checked> { |
1550 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > { |
1568 public: |
1551 |
1569 typedef _Graph Graph; |
1552 public: |
1570 typedef _NodeFilterMap NodeFilterMap; |
1553 typedef GR Graph; |
1571 typedef SubGraph<Graph, NodeFilterMap, |
1554 typedef NF NodeFilterMap; |
1572 ConstMap<typename Graph::Edge, bool> > Parent; |
1555 typedef GraphAdaptorExtender< |
|
1556 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > |
|
1557 Parent; |
1573 |
1558 |
1574 typedef typename Parent::Node Node; |
1559 typedef typename Parent::Node Node; |
1575 protected: |
1560 protected: |
1576 ConstMap<typename Graph::Edge, bool> const_true_map; |
1561 ConstMap<typename Graph::Edge, bool> const_true_map; |
1577 |
1562 |
1599 /// \brief Returns a read-only FilterNodes adaptor |
1584 /// \brief Returns a read-only FilterNodes adaptor |
1600 /// |
1585 /// |
1601 /// This function just returns a read-only \ref FilterNodes adaptor. |
1586 /// This function just returns a read-only \ref FilterNodes adaptor. |
1602 /// \ingroup graph_adaptors |
1587 /// \ingroup graph_adaptors |
1603 /// \relates FilterNodes |
1588 /// \relates FilterNodes |
1604 template<typename Digraph, typename NodeFilterMap> |
1589 template<typename GR, typename NF> |
1605 FilterNodes<const Digraph, NodeFilterMap> |
1590 FilterNodes<const GR, NF> |
1606 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { |
1591 filterNodes(const GR& graph, NF& node_filter_map) { |
1607 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); |
1592 return FilterNodes<const GR, NF>(graph, node_filter_map); |
1608 } |
1593 } |
1609 |
1594 |
1610 template<typename Digraph, typename NodeFilterMap> |
1595 template<typename GR, typename NF> |
1611 FilterNodes<const Digraph, const NodeFilterMap> |
1596 FilterNodes<const GR, const NF> |
1612 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) { |
1597 filterNodes(const GR& graph, const NF& node_filter_map) { |
1613 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm); |
1598 return FilterNodes<const GR, const NF>(graph, node_filter_map); |
1614 } |
1599 } |
1615 |
1600 |
1616 /// \ingroup graph_adaptors |
1601 /// \ingroup graph_adaptors |
1617 /// |
1602 /// |
1618 /// \brief Adaptor class for hiding arcs in a digraph. |
1603 /// \brief Adaptor class for hiding arcs in a digraph. |
1622 /// the arcs. Only the arcs with \c true filter value are shown in the |
1607 /// the arcs. Only the arcs with \c true filter value are shown in the |
1623 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph |
1608 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph |
1624 /// "Digraph" concept. |
1609 /// "Digraph" concept. |
1625 /// |
1610 /// |
1626 /// The adapted digraph can also be modified through this adaptor |
1611 /// The adapted digraph can also be modified through this adaptor |
1627 /// by adding or removing nodes or arcs, unless the \c _Digraph template |
1612 /// by adding or removing nodes or arcs, unless the \c GR template |
1628 /// parameter is set to be \c const. |
1613 /// parameter is set to be \c const. |
1629 /// |
1614 /// |
1630 /// \tparam _Digraph The type of the adapted digraph. |
1615 /// \tparam GR The type of the adapted digraph. |
1631 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
1616 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
1632 /// It can also be specified to be \c const. |
1617 /// It can also be specified to be \c const. |
1633 /// \tparam _ArcFilterMap A \c bool (or convertible) arc map of the |
1618 /// \tparam AF The type of the arc filter map. |
1634 /// adapted digraph. The default map type is |
1619 /// It must be a \c bool (or convertible) arc map of the |
1635 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<bool>". |
1620 /// adapted digraph. The default type is |
|
1621 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<bool>". |
1636 /// |
1622 /// |
1637 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
1623 /// \note The \c Node and \c Arc types of this adaptor and the adapted |
1638 /// digraph are convertible to each other. |
1624 /// digraph are convertible to each other. |
1639 #ifdef DOXYGEN |
1625 #ifdef DOXYGEN |
1640 template<typename _Digraph, |
1626 template<typename GR, |
1641 typename _ArcFilterMap> |
1627 typename AF> |
|
1628 class FilterArcs { |
1642 #else |
1629 #else |
1643 template<typename _Digraph, |
1630 template<typename GR, |
1644 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool> > |
1631 typename AF = typename GR::template ArcMap<bool> > |
|
1632 class FilterArcs : |
|
1633 public DigraphAdaptorExtender< |
|
1634 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > { |
1645 #endif |
1635 #endif |
1646 class FilterArcs : |
1636 public: |
1647 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, |
1637 /// The type of the adapted digraph. |
1648 _ArcFilterMap, false> { |
1638 typedef GR Digraph; |
1649 public: |
1639 /// The type of the arc filter map. |
1650 |
1640 typedef AF ArcFilterMap; |
1651 typedef _Digraph Digraph; |
1641 |
1652 typedef _ArcFilterMap ArcFilterMap; |
1642 typedef DigraphAdaptorExtender< |
1653 |
1643 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > |
1654 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, |
1644 Parent; |
1655 ArcFilterMap, false> Parent; |
|
1656 |
1645 |
1657 typedef typename Parent::Arc Arc; |
1646 typedef typename Parent::Arc Arc; |
1658 |
1647 |
1659 protected: |
1648 protected: |
1660 ConstMap<typename Digraph::Node, bool> const_true_map; |
1649 ConstMap<typename Digraph::Node, bool> const_true_map; |
1707 /// \brief Returns a read-only FilterArcs adaptor |
1696 /// \brief Returns a read-only FilterArcs adaptor |
1708 /// |
1697 /// |
1709 /// This function just returns a read-only \ref FilterArcs adaptor. |
1698 /// This function just returns a read-only \ref FilterArcs adaptor. |
1710 /// \ingroup graph_adaptors |
1699 /// \ingroup graph_adaptors |
1711 /// \relates FilterArcs |
1700 /// \relates FilterArcs |
1712 template<typename Digraph, typename ArcFilterMap> |
1701 template<typename GR, typename AF> |
1713 FilterArcs<const Digraph, ArcFilterMap> |
1702 FilterArcs<const GR, AF> |
1714 filterArcs(const Digraph& digraph, ArcFilterMap& afm) { |
1703 filterArcs(const GR& digraph, AF& arc_filter_map) { |
1715 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); |
1704 return FilterArcs<const GR, AF>(digraph, arc_filter_map); |
1716 } |
1705 } |
1717 |
1706 |
1718 template<typename Digraph, typename ArcFilterMap> |
1707 template<typename GR, typename AF> |
1719 FilterArcs<const Digraph, const ArcFilterMap> |
1708 FilterArcs<const GR, const AF> |
1720 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { |
1709 filterArcs(const GR& digraph, const AF& arc_filter_map) { |
1721 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); |
1710 return FilterArcs<const GR, const AF>(digraph, arc_filter_map); |
1722 } |
1711 } |
1723 |
1712 |
1724 /// \ingroup graph_adaptors |
1713 /// \ingroup graph_adaptors |
1725 /// |
1714 /// |
1726 /// \brief Adaptor class for hiding edges in a graph. |
1715 /// \brief Adaptor class for hiding edges in a graph. |
1730 /// the edges. Only the edges with \c true filter value are shown in the |
1719 /// the edges. Only the edges with \c true filter value are shown in the |
1731 /// subgraph. This adaptor conforms to the \ref concepts::Graph |
1720 /// subgraph. This adaptor conforms to the \ref concepts::Graph |
1732 /// "Graph" concept. |
1721 /// "Graph" concept. |
1733 /// |
1722 /// |
1734 /// The adapted graph can also be modified through this adaptor |
1723 /// The adapted graph can also be modified through this adaptor |
1735 /// by adding or removing nodes or edges, unless the \c _Graph template |
1724 /// by adding or removing nodes or edges, unless the \c GR template |
1736 /// parameter is set to be \c const. |
1725 /// parameter is set to be \c const. |
1737 /// |
1726 /// |
1738 /// \tparam _Graph The type of the adapted graph. |
1727 /// \tparam GR The type of the adapted graph. |
1739 /// It must conform to the \ref concepts::Graph "Graph" concept. |
1728 /// It must conform to the \ref concepts::Graph "Graph" concept. |
1740 /// It can also be specified to be \c const. |
1729 /// It can also be specified to be \c const. |
1741 /// \tparam _EdgeFilterMap A \c bool (or convertible) edge map of the |
1730 /// \tparam EF The type of the edge filter map. |
1742 /// adapted graph. The default map type is |
1731 /// It must be a \c bool (or convertible) edge map of the |
1743 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". |
1732 /// adapted graph. The default type is |
|
1733 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". |
1744 /// |
1734 /// |
1745 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
1735 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the |
1746 /// adapted graph are convertible to each other. |
1736 /// adapted graph are convertible to each other. |
1747 #ifdef DOXYGEN |
1737 #ifdef DOXYGEN |
1748 template<typename _Graph, |
1738 template<typename GR, |
1749 typename _EdgeFilterMap> |
1739 typename EF> |
|
1740 class FilterEdges { |
1750 #else |
1741 #else |
1751 template<typename _Graph, |
1742 template<typename GR, |
1752 typename _EdgeFilterMap = typename _Graph::template EdgeMap<bool> > |
1743 typename EF = typename GR::template EdgeMap<bool> > |
|
1744 class FilterEdges : |
|
1745 public GraphAdaptorExtender< |
|
1746 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > { |
1753 #endif |
1747 #endif |
1754 class FilterEdges : |
1748 public: |
1755 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, |
1749 /// The type of the adapted graph. |
1756 _EdgeFilterMap, false> { |
1750 typedef GR Graph; |
1757 public: |
1751 /// The type of the edge filter map. |
1758 typedef _Graph Graph; |
1752 typedef EF EdgeFilterMap; |
1759 typedef _EdgeFilterMap EdgeFilterMap; |
1753 |
1760 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, |
1754 typedef GraphAdaptorExtender< |
1761 EdgeFilterMap, false> Parent; |
1755 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > |
|
1756 Parent; |
|
1757 |
1762 typedef typename Parent::Edge Edge; |
1758 typedef typename Parent::Edge Edge; |
|
1759 |
1763 protected: |
1760 protected: |
1764 ConstMap<typename Graph::Node, bool> const_true_map; |
1761 ConstMap<typename Graph::Node, bool> const_true_map; |
1765 |
1762 |
1766 FilterEdges() : const_true_map(true) { |
1763 FilterEdges() : const_true_map(true) { |
1767 Parent::setNodeFilterMap(const_true_map); |
1764 Parent::setNodeFilterMap(const_true_map); |
1811 /// \brief Returns a read-only FilterEdges adaptor |
1808 /// \brief Returns a read-only FilterEdges adaptor |
1812 /// |
1809 /// |
1813 /// This function just returns a read-only \ref FilterEdges adaptor. |
1810 /// This function just returns a read-only \ref FilterEdges adaptor. |
1814 /// \ingroup graph_adaptors |
1811 /// \ingroup graph_adaptors |
1815 /// \relates FilterEdges |
1812 /// \relates FilterEdges |
1816 template<typename Graph, typename EdgeFilterMap> |
1813 template<typename GR, typename EF> |
1817 FilterEdges<const Graph, EdgeFilterMap> |
1814 FilterEdges<const GR, EF> |
1818 filterEdges(const Graph& graph, EdgeFilterMap& efm) { |
1815 filterEdges(const GR& graph, EF& edge_filter_map) { |
1819 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); |
1816 return FilterEdges<const GR, EF>(graph, edge_filter_map); |
1820 } |
1817 } |
1821 |
1818 |
1822 template<typename Graph, typename EdgeFilterMap> |
1819 template<typename GR, typename EF> |
1823 FilterEdges<const Graph, const EdgeFilterMap> |
1820 FilterEdges<const GR, const EF> |
1824 filterEdges(const Graph& graph, const EdgeFilterMap& efm) { |
1821 filterEdges(const GR& graph, const EF& edge_filter_map) { |
1825 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); |
1822 return FilterEdges<const GR, const EF>(graph, edge_filter_map); |
1826 } |
1823 } |
1827 |
1824 |
1828 |
1825 |
1829 template <typename _Digraph> |
1826 template <typename _Digraph> |
1830 class UndirectorBase { |
1827 class UndirectorBase { |
2224 /// graph. All arcs of the underlying digraph are showed in the |
2221 /// graph. All arcs of the underlying digraph are showed in the |
2225 /// adaptor as an edge (and also as a pair of arcs, of course). |
2222 /// adaptor as an edge (and also as a pair of arcs, of course). |
2226 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. |
2223 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. |
2227 /// |
2224 /// |
2228 /// The adapted digraph can also be modified through this adaptor |
2225 /// The adapted digraph can also be modified through this adaptor |
2229 /// by adding or removing nodes or edges, unless the \c _Digraph template |
2226 /// by adding or removing nodes or edges, unless the \c GR template |
2230 /// parameter is set to be \c const. |
2227 /// parameter is set to be \c const. |
2231 /// |
2228 /// |
2232 /// \tparam _Digraph The type of the adapted digraph. |
2229 /// \tparam GR The type of the adapted digraph. |
2233 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
2230 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
2234 /// It can also be specified to be \c const. |
2231 /// It can also be specified to be \c const. |
2235 /// |
2232 /// |
2236 /// \note The \c Node type of this adaptor and the adapted digraph are |
2233 /// \note The \c Node type of this adaptor and the adapted digraph are |
2237 /// convertible to each other, moreover the \c Edge type of the adaptor |
2234 /// convertible to each other, moreover the \c Edge type of the adaptor |
2238 /// and the \c Arc type of the adapted digraph are also convertible to |
2235 /// and the \c Arc type of the adapted digraph are also convertible to |
2239 /// each other. |
2236 /// each other. |
2240 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type |
2237 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type |
2241 /// of the adapted digraph.) |
2238 /// of the adapted digraph.) |
2242 template<typename _Digraph> |
2239 template<typename GR> |
2243 class Undirector |
2240 #ifdef DOXYGEN |
2244 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { |
2241 class Undirector { |
2245 public: |
2242 #else |
2246 typedef _Digraph Digraph; |
2243 class Undirector : |
2247 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; |
2244 public GraphAdaptorExtender<UndirectorBase<GR> > { |
|
2245 #endif |
|
2246 public: |
|
2247 /// The type of the adapted digraph. |
|
2248 typedef GR Digraph; |
|
2249 typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent; |
2248 protected: |
2250 protected: |
2249 Undirector() { } |
2251 Undirector() { } |
2250 public: |
2252 public: |
2251 |
2253 |
2252 /// \brief Constructor |
2254 /// \brief Constructor |
2253 /// |
2255 /// |
2254 /// Creates an undirected graph from the given digraph. |
2256 /// Creates an undirected graph from the given digraph. |
2255 Undirector(_Digraph& digraph) { |
2257 Undirector(Digraph& digraph) { |
2256 setDigraph(digraph); |
2258 setDigraph(digraph); |
2257 } |
2259 } |
2258 |
2260 |
2259 /// \brief Arc map combined from two original arc maps |
2261 /// \brief Arc map combined from two original arc maps |
2260 /// |
2262 /// |
2261 /// This map adaptor class adapts two arc maps of the underlying |
2263 /// This map adaptor class adapts two arc maps of the underlying |
2262 /// digraph to get an arc map of the undirected graph. |
2264 /// digraph to get an arc map of the undirected graph. |
2263 /// Its value type is inherited from the first arc map type |
2265 /// Its value type is inherited from the first arc map type |
2264 /// (\c %ForwardMap). |
2266 /// (\c %ForwardMap). |
2265 template <typename _ForwardMap, typename _BackwardMap> |
2267 template <typename ForwardMap, typename BackwardMap> |
2266 class CombinedArcMap { |
2268 class CombinedArcMap { |
2267 public: |
2269 public: |
2268 |
|
2269 typedef _ForwardMap ForwardMap; |
|
2270 typedef _BackwardMap BackwardMap; |
|
2271 |
|
2272 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; |
|
2273 |
2270 |
2274 /// The key type of the map |
2271 /// The key type of the map |
2275 typedef typename Parent::Arc Key; |
2272 typedef typename Parent::Arc Key; |
2276 /// The value type of the map |
2273 /// The value type of the map |
2277 typedef typename ForwardMap::Value Value; |
2274 typedef typename ForwardMap::Value Value; |
|
2275 |
|
2276 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; |
2278 |
2277 |
2279 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; |
2278 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; |
2280 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue; |
2279 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue; |
2281 typedef typename MapTraits<ForwardMap>::ReturnValue Reference; |
2280 typedef typename MapTraits<ForwardMap>::ReturnValue Reference; |
2282 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; |
2281 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; |
2531 /// The arcs can be easily reversed by the \c reverseArc() member function |
2529 /// The arcs can be easily reversed by the \c reverseArc() member function |
2532 /// of the adaptor. |
2530 /// of the adaptor. |
2533 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. |
2531 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. |
2534 /// |
2532 /// |
2535 /// The adapted graph can also be modified through this adaptor |
2533 /// The adapted graph can also be modified through this adaptor |
2536 /// by adding or removing nodes or arcs, unless the \c _Graph template |
2534 /// by adding or removing nodes or arcs, unless the \c GR template |
2537 /// parameter is set to be \c const. |
2535 /// parameter is set to be \c const. |
2538 /// |
2536 /// |
2539 /// \tparam _Graph The type of the adapted graph. |
2537 /// \tparam GR The type of the adapted graph. |
2540 /// It must conform to the \ref concepts::Graph "Graph" concept. |
2538 /// It must conform to the \ref concepts::Graph "Graph" concept. |
2541 /// It can also be specified to be \c const. |
2539 /// It can also be specified to be \c const. |
2542 /// \tparam _DirectionMap A \c bool (or convertible) edge map of the |
2540 /// \tparam DM The type of the direction map. |
2543 /// adapted graph. The default map type is |
2541 /// It must be a \c bool (or convertible) edge map of the |
2544 /// \ref concepts::Graph::EdgeMap "_Graph::EdgeMap<bool>". |
2542 /// adapted graph. The default type is |
|
2543 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". |
2545 /// |
2544 /// |
2546 /// \note The \c Node type of this adaptor and the adapted graph are |
2545 /// \note The \c Node type of this adaptor and the adapted graph are |
2547 /// convertible to each other, moreover the \c Arc type of the adaptor |
2546 /// convertible to each other, moreover the \c Arc type of the adaptor |
2548 /// and the \c Edge type of the adapted graph are also convertible to |
2547 /// and the \c Edge type of the adapted graph are also convertible to |
2549 /// each other. |
2548 /// each other. |
2550 #ifdef DOXYGEN |
2549 #ifdef DOXYGEN |
2551 template<typename _Graph, |
2550 template<typename GR, |
2552 typename _DirectionMap> |
2551 typename DM> |
|
2552 class Orienter { |
2553 #else |
2553 #else |
2554 template<typename _Graph, |
2554 template<typename GR, |
2555 typename _DirectionMap = typename _Graph::template EdgeMap<bool> > |
2555 typename DM = typename GR::template EdgeMap<bool> > |
|
2556 class Orienter : |
|
2557 public DigraphAdaptorExtender<OrienterBase<GR, DM> > { |
2556 #endif |
2558 #endif |
2557 class Orienter : |
|
2558 public DigraphAdaptorExtender<OrienterBase<_Graph, _DirectionMap> > { |
|
2559 public: |
2559 public: |
2560 |
2560 |
2561 /// The type of the adapted graph. |
2561 /// The type of the adapted graph. |
2562 typedef _Graph Graph; |
2562 typedef GR Graph; |
2563 /// The type of the direction edge map. |
2563 /// The type of the direction edge map. |
2564 typedef _DirectionMap DirectionMap; |
2564 typedef DM DirectionMap; |
2565 |
2565 |
2566 typedef DigraphAdaptorExtender< |
2566 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent; |
2567 OrienterBase<_Graph, _DirectionMap> > Parent; |
|
2568 typedef typename Parent::Arc Arc; |
2567 typedef typename Parent::Arc Arc; |
2569 protected: |
2568 protected: |
2570 Orienter() { } |
2569 Orienter() { } |
2571 public: |
2570 public: |
2572 |
2571 |
2591 /// \brief Returns a read-only Orienter adaptor |
2590 /// \brief Returns a read-only Orienter adaptor |
2592 /// |
2591 /// |
2593 /// This function just returns a read-only \ref Orienter adaptor. |
2592 /// This function just returns a read-only \ref Orienter adaptor. |
2594 /// \ingroup graph_adaptors |
2593 /// \ingroup graph_adaptors |
2595 /// \relates Orienter |
2594 /// \relates Orienter |
2596 template<typename Graph, typename DirectionMap> |
2595 template<typename GR, typename DM> |
2597 Orienter<const Graph, DirectionMap> |
2596 Orienter<const GR, DM> |
2598 orienter(const Graph& graph, DirectionMap& dm) { |
2597 orienter(const GR& graph, DM& direction_map) { |
2599 return Orienter<const Graph, DirectionMap>(graph, dm); |
2598 return Orienter<const GR, DM>(graph, direction_map); |
2600 } |
2599 } |
2601 |
2600 |
2602 template<typename Graph, typename DirectionMap> |
2601 template<typename GR, typename DM> |
2603 Orienter<const Graph, const DirectionMap> |
2602 Orienter<const GR, const DM> |
2604 orienter(const Graph& graph, const DirectionMap& dm) { |
2603 orienter(const GR& graph, const DM& direction_map) { |
2605 return Orienter<const Graph, const DirectionMap>(graph, dm); |
2604 return Orienter<const GR, const DM>(graph, direction_map); |
2606 } |
2605 } |
2607 |
2606 |
2608 namespace _adaptor_bits { |
2607 namespace _adaptor_bits { |
2609 |
2608 |
2610 template<typename _Digraph, |
2609 template<typename Digraph, |
2611 typename _CapacityMap = typename _Digraph::template ArcMap<int>, |
2610 typename CapacityMap, |
2612 typename _FlowMap = _CapacityMap, |
2611 typename FlowMap, |
2613 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > |
2612 typename Tolerance> |
2614 class ResForwardFilter { |
2613 class ResForwardFilter { |
2615 public: |
2614 public: |
2616 |
|
2617 typedef _Digraph Digraph; |
|
2618 typedef _CapacityMap CapacityMap; |
|
2619 typedef _FlowMap FlowMap; |
|
2620 typedef _Tolerance Tolerance; |
|
2621 |
2615 |
2622 typedef typename Digraph::Arc Key; |
2616 typedef typename Digraph::Arc Key; |
2623 typedef bool Value; |
2617 typedef bool Value; |
2624 |
2618 |
2625 private: |
2619 private: |
2690 /// multiplicities are counted, i.e. the adaptor has exactly |
2679 /// multiplicities are counted, i.e. the adaptor has exactly |
2691 /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel |
2680 /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel |
2692 /// arcs). |
2681 /// arcs). |
2693 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. |
2682 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. |
2694 /// |
2683 /// |
2695 /// \tparam _Digraph The type of the adapted digraph. |
2684 /// \tparam GR The type of the adapted digraph. |
2696 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
2685 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
2697 /// It is implicitly \c const. |
2686 /// It is implicitly \c const. |
2698 /// \tparam _CapacityMap An arc map of some numerical type, which defines |
2687 /// \tparam CM The type of the capacity map. |
|
2688 /// It must be an arc map of some numerical type, which defines |
2699 /// the capacities in the flow problem. It is implicitly \c const. |
2689 /// the capacities in the flow problem. It is implicitly \c const. |
2700 /// The default map type is |
2690 /// The default type is |
2701 /// \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>". |
2691 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
2702 /// \tparam _FlowMap An arc map of some numerical type, which defines |
2692 /// \tparam FM The type of the flow map. |
2703 /// the flow values in the flow problem. |
2693 /// It must be an arc map of some numerical type, which defines |
2704 /// The default map type is \c _CapacityMap. |
2694 /// the flow values in the flow problem. The default type is \c CM. |
2705 /// \tparam _Tolerance Tolerance type for handling inexact computation. |
2695 /// \tparam TL The tolerance type for handling inexact computation. |
2706 /// The default tolerance type depends on the value type of the |
2696 /// The default tolerance type depends on the value type of the |
2707 /// capacity map. |
2697 /// capacity map. |
2708 /// |
2698 /// |
2709 /// \note This adaptor is implemented using Undirector and FilterArcs |
2699 /// \note This adaptor is implemented using Undirector and FilterArcs |
2710 /// adaptors. |
2700 /// adaptors. |
2711 /// |
2701 /// |
2712 /// \note The \c Node type of this adaptor and the adapted digraph are |
2702 /// \note The \c Node type of this adaptor and the adapted digraph are |
2713 /// convertible to each other, moreover the \c Arc type of the adaptor |
2703 /// convertible to each other, moreover the \c Arc type of the adaptor |
2714 /// is convertible to the \c Arc type of the adapted digraph. |
2704 /// is convertible to the \c Arc type of the adapted digraph. |
2715 #ifdef DOXYGEN |
2705 #ifdef DOXYGEN |
2716 template<typename _Digraph, |
2706 template<typename GR, typename CM, typename FM, typename TL> |
2717 typename _CapacityMap, |
|
2718 typename _FlowMap, |
|
2719 typename _Tolerance> |
|
2720 class Residual |
2707 class Residual |
2721 #else |
2708 #else |
2722 template<typename _Digraph, |
2709 template<typename GR, |
2723 typename _CapacityMap = typename _Digraph::template ArcMap<int>, |
2710 typename CM = typename GR::template ArcMap<int>, |
2724 typename _FlowMap = _CapacityMap, |
2711 typename FM = CM, |
2725 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > |
2712 typename TL = Tolerance<typename CM::Value> > |
2726 class Residual : |
2713 class Residual : |
2727 public FilterArcs< |
2714 public FilterArcs< |
2728 Undirector<const _Digraph>, |
2715 Undirector<const GR>, |
2729 typename Undirector<const _Digraph>::template CombinedArcMap< |
2716 typename Undirector<const GR>::template CombinedArcMap< |
2730 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap, |
2717 _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>, |
2731 _FlowMap, _Tolerance>, |
2718 _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > > |
2732 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, |
|
2733 _FlowMap, _Tolerance> > > |
|
2734 #endif |
2719 #endif |
2735 { |
2720 { |
2736 public: |
2721 public: |
2737 |
2722 |
2738 /// The type of the underlying digraph. |
2723 /// The type of the underlying digraph. |
2739 typedef _Digraph Digraph; |
2724 typedef GR Digraph; |
2740 /// The type of the capacity map. |
2725 /// The type of the capacity map. |
2741 typedef _CapacityMap CapacityMap; |
2726 typedef CM CapacityMap; |
2742 /// The type of the flow map. |
2727 /// The type of the flow map. |
2743 typedef _FlowMap FlowMap; |
2728 typedef FM FlowMap; |
2744 typedef _Tolerance Tolerance; |
2729 /// The tolerance type. |
|
2730 typedef TL Tolerance; |
2745 |
2731 |
2746 typedef typename CapacityMap::Value Value; |
2732 typedef typename CapacityMap::Value Value; |
2747 typedef Residual Adaptor; |
2733 typedef Residual Adaptor; |
2748 |
2734 |
2749 protected: |
2735 protected: |
2880 /// \brief Returns a (read-only) Residual adaptor |
2866 /// \brief Returns a (read-only) Residual adaptor |
2881 /// |
2867 /// |
2882 /// This function just returns a (read-only) \ref Residual adaptor. |
2868 /// This function just returns a (read-only) \ref Residual adaptor. |
2883 /// \ingroup graph_adaptors |
2869 /// \ingroup graph_adaptors |
2884 /// \relates Residual |
2870 /// \relates Residual |
2885 template<typename Digraph, typename CapacityMap, typename FlowMap> |
2871 template<typename GR, typename CM, typename FM> |
2886 Residual<Digraph, CapacityMap, FlowMap> |
2872 Residual<GR, CM, FM> residual(const GR& digraph, |
2887 residual(const Digraph& digraph, |
2873 const CM& capacity_map, |
2888 const CapacityMap& capacity, |
2874 FM& flow_map) { |
2889 FlowMap& flow) |
2875 return Residual<GR, CM, FM> (digraph, capacity_map, flow_map); |
2890 { |
|
2891 return Residual<Digraph, CapacityMap, FlowMap> (digraph, capacity, flow); |
|
2892 } |
2876 } |
2893 |
2877 |
2894 |
2878 |
2895 template <typename _Digraph> |
2879 template <typename _Digraph> |
2896 class SplitNodesBase { |
2880 class SplitNodesBase { |
3337 /// capacities directly. |
3321 /// capacities directly. |
3338 /// In this case you can use \c SplitNodes adaptor, and set the node |
3322 /// In this case you can use \c SplitNodes adaptor, and set the node |
3339 /// costs/capacities of the original digraph to the \e bind \e arcs |
3323 /// costs/capacities of the original digraph to the \e bind \e arcs |
3340 /// in the adaptor. |
3324 /// in the adaptor. |
3341 /// |
3325 /// |
3342 /// \tparam _Digraph The type of the adapted digraph. |
3326 /// \tparam GR The type of the adapted digraph. |
3343 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
3327 /// It must conform to the \ref concepts::Digraph "Digraph" concept. |
3344 /// It is implicitly \c const. |
3328 /// It is implicitly \c const. |
3345 /// |
3329 /// |
3346 /// \note The \c Node type of this adaptor is converible to the \c Node |
3330 /// \note The \c Node type of this adaptor is converible to the \c Node |
3347 /// type of the adapted digraph. |
3331 /// type of the adapted digraph. |
3348 template <typename _Digraph> |
3332 template <typename GR> |
|
3333 #ifdef DOXYGEN |
|
3334 class SplitNodes { |
|
3335 #else |
3349 class SplitNodes |
3336 class SplitNodes |
3350 : public DigraphAdaptorExtender<SplitNodesBase<const _Digraph> > { |
3337 : public DigraphAdaptorExtender<SplitNodesBase<const GR> > { |
3351 public: |
3338 #endif |
3352 typedef _Digraph Digraph; |
3339 public: |
3353 typedef DigraphAdaptorExtender<SplitNodesBase<const Digraph> > Parent; |
3340 typedef GR Digraph; |
|
3341 typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent; |
3354 |
3342 |
3355 typedef typename Digraph::Node DigraphNode; |
3343 typedef typename Digraph::Node DigraphNode; |
3356 typedef typename Digraph::Arc DigraphArc; |
3344 typedef typename Digraph::Arc DigraphArc; |
3357 |
3345 |
3358 typedef typename Parent::Node Node; |
3346 typedef typename Parent::Node Node; |
3519 /// original digraph. |
3507 /// original digraph. |
3520 /// |
3508 /// |
3521 /// This map adaptor class adapts an arc map and a node map of the |
3509 /// This map adaptor class adapts an arc map and a node map of the |
3522 /// original digraph to get an arc map of the split digraph. |
3510 /// original digraph to get an arc map of the split digraph. |
3523 /// Its value type is inherited from the original arc map type |
3511 /// Its value type is inherited from the original arc map type |
3524 /// (\c DigraphArcMap). |
3512 /// (\c ArcMap). |
3525 template <typename DigraphArcMap, typename DigraphNodeMap> |
3513 template <typename ArcMap, typename NodeMap> |
3526 class CombinedArcMap { |
3514 class CombinedArcMap { |
3527 public: |
3515 public: |
3528 |
3516 |
3529 /// The key type of the map |
3517 /// The key type of the map |
3530 typedef Arc Key; |
3518 typedef Arc Key; |
3531 /// The value type of the map |
3519 /// The value type of the map |
3532 typedef typename DigraphArcMap::Value Value; |
3520 typedef typename ArcMap::Value Value; |
3533 |
3521 |
3534 typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag |
3522 typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag; |
3535 ReferenceMapTag; |
3523 typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue; |
3536 typedef typename MapTraits<DigraphArcMap>::ReturnValue |
3524 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue; |
3537 ReturnValue; |
3525 typedef typename MapTraits<ArcMap>::ReturnValue Reference; |
3538 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue |
3526 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference; |
3539 ConstReturnValue; |
|
3540 typedef typename MapTraits<DigraphArcMap>::ReturnValue |
|
3541 Reference; |
|
3542 typedef typename MapTraits<DigraphArcMap>::ConstReturnValue |
|
3543 ConstReference; |
|
3544 |
3527 |
3545 /// Constructor |
3528 /// Constructor |
3546 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) |
3529 CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) |
3547 : _arc_map(arc_map), _node_map(node_map) {} |
3530 : _arc_map(arc_map), _node_map(node_map) {} |
3548 |
3531 |
3549 /// Returns the value associated with the given key. |
3532 /// Returns the value associated with the given key. |
3550 Value operator[](const Key& arc) const { |
3533 Value operator[](const Key& arc) const { |
3551 if (Parent::origArc(arc)) { |
3534 if (Parent::origArc(arc)) { |
3572 _node_map.set(arc, val); |
3555 _node_map.set(arc, val); |
3573 } |
3556 } |
3574 } |
3557 } |
3575 |
3558 |
3576 private: |
3559 private: |
3577 DigraphArcMap& _arc_map; |
3560 ArcMap& _arc_map; |
3578 DigraphNodeMap& _node_map; |
3561 NodeMap& _node_map; |
3579 }; |
3562 }; |
3580 |
3563 |
3581 /// \brief Returns a combined arc map |
3564 /// \brief Returns a combined arc map |
3582 /// |
3565 /// |
3583 /// This function just returns a combined arc map. |
3566 /// This function just returns a combined arc map. |
3584 template <typename DigraphArcMap, typename DigraphNodeMap> |
3567 template <typename ArcMap, typename NodeMap> |
3585 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> |
3568 static CombinedArcMap<ArcMap, NodeMap> |
3586 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { |
3569 combinedArcMap(ArcMap& arc_map, NodeMap& node_map) { |
3587 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map); |
3570 return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map); |
3588 } |
3571 } |
3589 |
3572 |
3590 template <typename DigraphArcMap, typename DigraphNodeMap> |
3573 template <typename ArcMap, typename NodeMap> |
3591 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> |
3574 static CombinedArcMap<const ArcMap, NodeMap> |
3592 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { |
3575 combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) { |
3593 return CombinedArcMap<const DigraphArcMap, |
3576 return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map); |
3594 DigraphNodeMap>(arc_map, node_map); |
3577 } |
3595 } |
3578 |
3596 |
3579 template <typename ArcMap, typename NodeMap> |
3597 template <typename DigraphArcMap, typename DigraphNodeMap> |
3580 static CombinedArcMap<ArcMap, const NodeMap> |
3598 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> |
3581 combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) { |
3599 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { |
3582 return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map); |
3600 return CombinedArcMap<DigraphArcMap, |
3583 } |
3601 const DigraphNodeMap>(arc_map, node_map); |
3584 |
3602 } |
3585 template <typename ArcMap, typename NodeMap> |
3603 |
3586 static CombinedArcMap<const ArcMap, const NodeMap> |
3604 template <typename DigraphArcMap, typename DigraphNodeMap> |
3587 combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) { |
3605 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> |
3588 return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map); |
3606 combinedArcMap(const DigraphArcMap& arc_map, |
|
3607 const DigraphNodeMap& node_map) { |
|
3608 return CombinedArcMap<const DigraphArcMap, |
|
3609 const DigraphNodeMap>(arc_map, node_map); |
|
3610 } |
3589 } |
3611 |
3590 |
3612 }; |
3591 }; |
3613 |
3592 |
3614 /// \brief Returns a (read-only) SplitNodes adaptor |
3593 /// \brief Returns a (read-only) SplitNodes adaptor |
3615 /// |
3594 /// |
3616 /// This function just returns a (read-only) \ref SplitNodes adaptor. |
3595 /// This function just returns a (read-only) \ref SplitNodes adaptor. |
3617 /// \ingroup graph_adaptors |
3596 /// \ingroup graph_adaptors |
3618 /// \relates SplitNodes |
3597 /// \relates SplitNodes |
3619 template<typename Digraph> |
3598 template<typename GR> |
3620 SplitNodes<Digraph> |
3599 SplitNodes<GR> |
3621 splitNodes(const Digraph& digraph) { |
3600 splitNodes(const GR& digraph) { |
3622 return SplitNodes<Digraph>(digraph); |
3601 return SplitNodes<GR>(digraph); |
3623 } |
3602 } |
3624 |
3603 |
3625 |
|
3626 } //namespace lemon |
3604 } //namespace lemon |
3627 |
3605 |
3628 #endif //LEMON_ADAPTORS_H |
3606 #endif //LEMON_ADAPTORS_H |