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