diff --git a/lemon/adaptors.h b/lemon/adaptors.h --- a/lemon/adaptors.h +++ b/lemon/adaptors.h @@ -21,7 +21,7 @@ /// \ingroup graph_adaptors /// \file -/// \brief Several graph adaptors +/// \brief Adaptor classes for digraphs and graphs /// /// This file contains several useful adaptors for digraphs and graphs. @@ -70,21 +70,21 @@ typedef NodeNumTagIndicator NodeNumTag; int nodeNum() const { return _digraph->nodeNum(); } - typedef EdgeNumTagIndicator EdgeNumTag; + typedef ArcNumTagIndicator ArcNumTag; int arcNum() const { return _digraph->arcNum(); } - typedef FindEdgeTagIndicator FindEdgeTag; - Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { + typedef FindArcTagIndicator FindArcTag; + Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { return _digraph->findArc(u, v, prev); } Node addNode() { return _digraph->addNode(); } Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } - void erase(const Node& n) const { _digraph->erase(n); } - void erase(const Arc& a) const { _digraph->erase(a); } - - void clear() const { _digraph->clear(); } + void erase(const Node& n) { _digraph->erase(n); } + void erase(const Arc& a) { _digraph->erase(a); } + + void clear() { _digraph->clear(); } int id(const Node& n) const { return _digraph->id(n); } int id(const Arc& a) const { return _digraph->id(a); } @@ -198,15 +198,21 @@ typedef NodeNumTagIndicator NodeNumTag; int nodeNum() const { return _graph->nodeNum(); } + typedef ArcNumTagIndicator ArcNumTag; + int arcNum() const { return _graph->arcNum(); } + typedef EdgeNumTagIndicator EdgeNumTag; - int arcNum() const { return _graph->arcNum(); } int edgeNum() const { return _graph->edgeNum(); } - typedef FindEdgeTagIndicator FindEdgeTag; - Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { + typedef FindArcTagIndicator FindArcTag; + Arc findArc(const Node& u, const Node& v, + const Arc& prev = INVALID) const { return _graph->findArc(u, v, prev); } - Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { + + typedef FindEdgeTagIndicator FindEdgeTag; + Edge findEdge(const Node& u, const Node& v, + const Edge& prev = INVALID) const { return _graph->findEdge(u, v, prev); } @@ -330,9 +336,9 @@ Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } - typedef FindEdgeTagIndicator FindEdgeTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, - const Arc& prev = INVALID) { + const Arc& prev = INVALID) const { return Parent::findArc(v, u, prev); } @@ -340,41 +346,56 @@ /// \ingroup graph_adaptors /// - /// \brief A digraph adaptor which reverses the orientation of the arcs. + /// \brief Adaptor class for reversing the orientation of the arcs in + /// a digraph. /// - /// ReverseDigraph reverses the arcs in the adapted digraph. The - /// SubDigraph is conform to the \ref concepts::Digraph - /// "Digraph concept". + /// ReverseDigraph can be used for reversing the arcs in a digraph. + /// It conforms to the \ref concepts::Digraph "Digraph" concept. /// - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph - /// "Digraph concept". The type can be specified to be const. - template + /// The adapted digraph can also be modified through this adaptor + /// by adding or removing nodes or arcs, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It can also be specified to be \c const. + /// + /// \note The \c Node and \c Arc types of this adaptor and the adapted + /// digraph are convertible to each other. + template +#ifdef DOXYGEN + class ReverseDigraph { +#else class ReverseDigraph : - public DigraphAdaptorExtender > { + public DigraphAdaptorExtender > { +#endif public: - typedef _Digraph Digraph; - typedef DigraphAdaptorExtender< - ReverseDigraphBase<_Digraph> > Parent; + /// The type of the adapted digraph. + typedef GR Digraph; + typedef DigraphAdaptorExtender > Parent; protected: ReverseDigraph() { } public: /// \brief Constructor /// - /// Creates a reverse digraph adaptor for the given digraph + /// Creates a reverse digraph adaptor for the given digraph. explicit ReverseDigraph(Digraph& digraph) { Parent::setDigraph(digraph); } }; - /// \brief Just gives back a reverse digraph adaptor + /// \brief Returns a read-only ReverseDigraph adaptor /// - /// Just gives back a reverse digraph adaptor - template - ReverseDigraph reverseDigraph(const Digraph& digraph) { - return ReverseDigraph(digraph); + /// This function just returns a read-only \ref ReverseDigraph adaptor. + /// \ingroup graph_adaptors + /// \relates ReverseDigraph + template + ReverseDigraph reverseDigraph(const GR& digraph) { + return ReverseDigraph(digraph); } + template class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { @@ -457,21 +478,18 @@ Parent::nextOut(i); } - void hide(const Node& n) const { _node_filter->set(n, false); } - void hide(const Arc& a) const { _arc_filter->set(a, false); } - - void unHide(const Node& n) const { _node_filter->set(n, true); } - void unHide(const Arc& a) const { _arc_filter->set(a, true); } - - bool hidden(const Node& n) const { return !(*_node_filter)[n]; } - bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; } + void status(const Node& n, bool v) const { _node_filter->set(n, v); } + void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } + + bool status(const Node& n) const { return (*_node_filter)[n]; } + bool status(const Arc& a) const { return (*_arc_filter)[a]; } typedef False NodeNumTag; - typedef False EdgeNumTag; - - typedef FindEdgeTagIndicator FindEdgeTag; + typedef False ArcNumTag; + + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& source, const Node& target, - const Arc& prev = INVALID) { + const Arc& prev = INVALID) const { if (!(*_node_filter)[source] || !(*_node_filter)[target]) { return INVALID; } @@ -600,21 +618,18 @@ while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); } - void hide(const Node& n) const { _node_filter->set(n, false); } - void hide(const Arc& e) const { _arc_filter->set(e, false); } - - void unHide(const Node& n) const { _node_filter->set(n, true); } - void unHide(const Arc& e) const { _arc_filter->set(e, true); } - - bool hidden(const Node& n) const { return !(*_node_filter)[n]; } - bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; } + void status(const Node& n, bool v) const { _node_filter->set(n, v); } + void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } + + bool status(const Node& n) const { return (*_node_filter)[n]; } + bool status(const Arc& a) const { return (*_arc_filter)[a]; } typedef False NodeNumTag; - typedef False EdgeNumTag; - - typedef FindEdgeTagIndicator FindEdgeTag; + typedef False ArcNumTag; + + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& source, const Node& target, - const Arc& prev = INVALID) { + const Arc& prev = INVALID) const { if (!(*_node_filter)[source] || !(*_node_filter)[target]) { return INVALID; } @@ -679,42 +694,57 @@ /// \ingroup graph_adaptors /// - /// \brief An adaptor for hiding nodes and arcs in a digraph + /// \brief Adaptor class for hiding nodes and arcs in a digraph /// - /// SubDigraph hides nodes and arcs in a digraph. A bool node map - /// and a bool arc map must be specified, which define the filters - /// for nodes and arcs. Just the nodes and arcs with true value are - /// shown in the subdigraph. The SubDigraph is conform to the \ref - /// concepts::Digraph "Digraph concept". If the \c _checked parameter - /// is true, then the arcs incident to filtered nodes are also - /// filtered out. + /// SubDigraph can be used for hiding nodes and arcs in a digraph. + /// A \c bool node map and a \c bool arc map must be specified, which + /// define the filters for nodes and arcs. + /// Only the nodes and arcs with \c true filter value are + /// shown in the subdigraph. The arcs that are incident to hidden + /// nodes are also filtered out. + /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept. /// - /// \tparam _Digraph It must be conform to the \ref - /// concepts::Digraph "Digraph concept". The type can be specified - /// to const. - /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. - /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. - /// \tparam _checked If the parameter is false then the arc filtering - /// is not checked with respect to node filter. Otherwise, each arc - /// is automatically filtered, which is incident to a filtered node. + /// The adapted digraph can also be modified through this adaptor + /// by adding or removing nodes or arcs, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It can also be specified to be \c const. + /// \tparam NF The type of the node filter map. + /// It must be a \c bool (or convertible) node map of the + /// adapted digraph. The default type is + /// \ref concepts::Digraph::NodeMap "GR::NodeMap". + /// \tparam AF The type of the arc filter map. + /// It must be \c bool (or convertible) arc map of the + /// adapted digraph. The default type is + /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// + /// \note The \c Node and \c Arc types of this adaptor and the adapted + /// digraph are convertible to each other. /// /// \see FilterNodes /// \see FilterArcs - template, - typename _ArcFilterMap = typename _Digraph::template ArcMap, - bool _checked = true> - class SubDigraph - : public DigraphAdaptorExtender< - SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { +#ifdef DOXYGEN + template + class SubDigraph { +#else + template, + typename AF = typename GR::template ArcMap > + class SubDigraph : + public DigraphAdaptorExtender > { +#endif public: - typedef _Digraph Digraph; - typedef _NodeFilterMap NodeFilterMap; - typedef _ArcFilterMap ArcFilterMap; - - typedef DigraphAdaptorExtender< - SubDigraphBase > - Parent; + /// The type of the adapted digraph. + typedef GR Digraph; + /// The type of the node filter map. + typedef NF NodeFilterMap; + /// The type of the arc filter map. + typedef AF ArcFilterMap; + + typedef DigraphAdaptorExtender > + Parent; typedef typename Parent::Node Node; typedef typename Parent::Arc Arc; @@ -725,8 +755,8 @@ /// \brief Constructor /// - /// Creates a subdigraph for the given digraph with - /// given node and arc map filters. + /// Creates a subdigraph for the given digraph with the + /// given node and arc filter maps. SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, ArcFilterMap& arc_filter) { setDigraph(digraph); @@ -734,88 +764,106 @@ setArcFilterMap(arc_filter); } - /// \brief Hides the node of the graph + /// \brief Sets the status of the given node /// - /// This function hides \c n in the digraph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c n - /// to be false in the corresponding node-map. - void hide(const Node& n) const { Parent::hide(n); } - - /// \brief Hides the arc of the graph + /// This function sets the status of the given node. + /// It is done by simply setting the assigned value of \c n + /// to \c v in the node filter map. + void status(const Node& n, bool v) const { Parent::status(n, v); } + + /// \brief Sets the status of the given arc /// - /// This function hides \c a in the digraph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c a - /// to be false in the corresponding arc-map. - void hide(const Arc& a) const { Parent::hide(a); } - - /// \brief Unhides the node of the graph + /// This function sets the status of the given arc. + /// It is done by simply setting the assigned value of \c a + /// to \c v in the arc filter map. + void status(const Arc& a, bool v) const { Parent::status(a, v); } + + /// \brief Returns the status of the given node /// - /// The value of \c n is set to be true in the node-map which stores - /// hide information. If \c n was hidden previuosly, then it is shown - /// again - void unHide(const Node& n) const { Parent::unHide(n); } - - /// \brief Unhides the arc of the graph + /// This function returns the status of the given node. + /// It is \c true if the given node is enabled (i.e. not hidden). + bool status(const Node& n) const { return Parent::status(n); } + + /// \brief Returns the status of the given arc /// - /// The value of \c a is set to be true in the arc-map which stores - /// hide information. If \c a was hidden previuosly, then it is shown - /// again - void unHide(const Arc& a) const { Parent::unHide(a); } - - /// \brief Returns true if \c n is hidden. + /// This function returns the status of the given arc. + /// It is \c true if the given arc is enabled (i.e. not hidden). + bool status(const Arc& a) const { return Parent::status(a); } + + /// \brief Disables the given node /// - /// Returns true if \c n is hidden. + /// This function disables the given node in the subdigraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(n, false)". + void disable(const Node& n) const { Parent::status(n, false); } + + /// \brief Disables the given arc /// - bool hidden(const Node& n) const { return Parent::hidden(n); } - - /// \brief Returns true if \c a is hidden. + /// This function disables the given arc in the subdigraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(a, false)". + void disable(const Arc& a) const { Parent::status(a, false); } + + /// \brief Enables the given node /// - /// Returns true if \c a is hidden. + /// This function enables the given node in the subdigraph. + /// It is the same as \ref status() "status(n, true)". + void enable(const Node& n) const { Parent::status(n, true); } + + /// \brief Enables the given arc /// - bool hidden(const Arc& a) const { return Parent::hidden(a); } + /// This function enables the given arc in the subdigraph. + /// It is the same as \ref status() "status(a, true)". + void enable(const Arc& a) const { Parent::status(a, true); } }; - /// \brief Just gives back a subdigraph + /// \brief Returns a read-only SubDigraph adaptor /// - /// Just gives back a subdigraph - template - SubDigraph - subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { - return SubDigraph - (digraph, nfm, afm); + /// This function just returns a read-only \ref SubDigraph adaptor. + /// \ingroup graph_adaptors + /// \relates SubDigraph + template + SubDigraph + subDigraph(const GR& digraph, + NF& node_filter_map, AF& arc_filter_map) { + return SubDigraph + (digraph, node_filter_map, arc_filter_map); } - template - SubDigraph - subDigraph(const Digraph& digraph, - const NodeFilterMap& nfm, ArcFilterMap& afm) { - return SubDigraph - (digraph, nfm, afm); + template + SubDigraph + subDigraph(const GR& digraph, + const NF& node_filter_map, AF& arc_filter_map) { + return SubDigraph + (digraph, node_filter_map, arc_filter_map); } - template - SubDigraph - subDigraph(const Digraph& digraph, - NodeFilterMap& nfm, const ArcFilterMap& afm) { - return SubDigraph - (digraph, nfm, afm); + template + SubDigraph + subDigraph(const GR& digraph, + NF& node_filter_map, const AF& arc_filter_map) { + return SubDigraph + (digraph, node_filter_map, arc_filter_map); } - template - SubDigraph - subDigraph(const Digraph& digraph, - const NodeFilterMap& nfm, const ArcFilterMap& afm) { - return SubDigraph(digraph, nfm, afm); + template + SubDigraph + subDigraph(const GR& digraph, + const NF& node_filter_map, const AF& arc_filter_map) { + return SubDigraph + (digraph, node_filter_map, arc_filter_map); } - template + template class SubGraphBase : public GraphAdaptorBase<_Graph> { public: typedef _Graph Graph; + typedef _NodeFilterMap NodeFilterMap; + typedef _EdgeFilterMap EdgeFilterMap; + typedef SubGraphBase Adaptor; typedef GraphAdaptorBase<_Graph> Parent; protected: @@ -925,21 +973,19 @@ Parent::nextInc(i, d); } - void hide(const Node& n) const { _node_filter_map->set(n, false); } - void hide(const Edge& e) const { _edge_filter_map->set(e, false); } - - void unHide(const Node& n) const { _node_filter_map->set(n, true); } - void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } - - bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } - bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } + void status(const Node& n, bool v) const { _node_filter_map->set(n, v); } + void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); } + + bool status(const Node& n) const { return (*_node_filter_map)[n]; } + bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } typedef False NodeNumTag; + typedef False ArcNumTag; typedef False EdgeNumTag; - typedef FindEdgeTagIndicator FindEdgeTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, - const Arc& prev = INVALID) { + const Arc& prev = INVALID) const { if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { return INVALID; } @@ -949,8 +995,10 @@ } return arc; } + + typedef FindEdgeTagIndicator FindEdgeTag; Edge findEdge(const Node& u, const Node& v, - const Edge& prev = INVALID) { + const Edge& prev = INVALID) const { if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { return INVALID; } @@ -1039,11 +1087,14 @@ }; - template - class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> + template + class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> : public GraphAdaptorBase<_Graph> { public: typedef _Graph Graph; + typedef _NodeFilterMap NodeFilterMap; + typedef _EdgeFilterMap EdgeFilterMap; + typedef SubGraphBase Adaptor; typedef GraphAdaptorBase<_Graph> Parent; protected: @@ -1121,29 +1172,29 @@ while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); } - void hide(const Node& n) const { _node_filter_map->set(n, false); } - void hide(const Edge& e) const { _edge_filter_map->set(e, false); } - - void unHide(const Node& n) const { _node_filter_map->set(n, true); } - void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } - - bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } - bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } + void status(const Node& n, bool v) const { _node_filter_map->set(n, v); } + void status(const Edge& e, bool v) const { _edge_filter_map->set(e, v); } + + bool status(const Node& n) const { return (*_node_filter_map)[n]; } + bool status(const Edge& e) const { return (*_edge_filter_map)[e]; } typedef False NodeNumTag; + typedef False ArcNumTag; typedef False EdgeNumTag; - typedef FindEdgeTagIndicator FindEdgeTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, - const Arc& prev = INVALID) { + const Arc& prev = INVALID) const { Arc arc = Parent::findArc(u, v, prev); while (arc != INVALID && !(*_edge_filter_map)[arc]) { arc = Parent::findArc(u, v, arc); } return arc; } + + typedef FindEdgeTagIndicator FindEdgeTag; Edge findEdge(const Node& u, const Node& v, - const Edge& prev = INVALID) { + const Edge& prev = INVALID) const { Edge edge = Parent::findEdge(u, v, prev); while (edge != INVALID && !(*_edge_filter_map)[edge]) { edge = Parent::findEdge(u, v, edge); @@ -1231,37 +1282,58 @@ /// \ingroup graph_adaptors /// - /// \brief A graph adaptor for hiding nodes and edges in an - /// undirected graph. + /// \brief Adaptor class for hiding nodes and edges in an undirected + /// graph. /// - /// SubGraph hides nodes and edges in a graph. A bool node map and a - /// bool edge map must be specified, which define the filters for - /// nodes and edges. Just the nodes and edges with true value are - /// shown in the subgraph. The SubGraph is conform to the \ref - /// concepts::Graph "Graph concept". If the \c _checked parameter is - /// true, then the edges incident to filtered nodes are also - /// filtered out. + /// SubGraph can be used for hiding nodes and edges in a graph. + /// A \c bool node map and a \c bool edge map must be specified, which + /// define the filters for nodes and edges. + /// Only the nodes and edges with \c true filter value are + /// shown in the subgraph. The edges that are incident to hidden + /// nodes are also filtered out. + /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. /// - /// \tparam _Graph It must be conform to the \ref - /// concepts::Graph "Graph concept". The type can be specified - /// to const. - /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. - /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. - /// \tparam _checked If the parameter is false then the edge filtering - /// is not checked with respect to node filter. Otherwise, each edge - /// is automatically filtered, which is incident to a filtered node. + /// The adapted graph can also be modified through this adaptor + /// by adding or removing nodes or edges, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted graph. + /// It must conform to the \ref concepts::Graph "Graph" concept. + /// It can also be specified to be \c const. + /// \tparam NF The type of the node filter map. + /// It must be a \c bool (or convertible) node map of the + /// adapted graph. The default type is + /// \ref concepts::Graph::NodeMap "GR::NodeMap". + /// \tparam EF The type of the edge filter map. + /// It must be a \c bool (or convertible) edge map of the + /// adapted graph. The default type is + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". + /// + /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the + /// adapted graph are convertible to each other. /// /// \see FilterNodes /// \see FilterEdges - template - class SubGraph - : public GraphAdaptorExtender< - SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { +#ifdef DOXYGEN + template + class SubGraph { +#else + template, + typename EF = typename GR::template EdgeMap > + class SubGraph : + public GraphAdaptorExtender > { +#endif public: - typedef _Graph Graph; - typedef GraphAdaptorExtender< - SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; + /// The type of the adapted graph. + typedef GR Graph; + /// The type of the node filter map. + typedef NF NodeFilterMap; + /// The type of the edge filter map. + typedef EF EdgeFilterMap; + + typedef GraphAdaptorExtender< SubGraphBase > + Parent; typedef typename Parent::Node Node; typedef typename Parent::Edge Edge; @@ -1272,132 +1344,153 @@ /// \brief Constructor /// - /// Creates a subgraph for the given graph with given node and - /// edge map filters. - SubGraph(Graph& _graph, NodeFilterMap& node_filter_map, + /// Creates a subgraph for the given graph with the given node + /// and edge filter maps. + SubGraph(Graph& graph, NodeFilterMap& node_filter_map, EdgeFilterMap& edge_filter_map) { - setGraph(_graph); + setGraph(graph); setNodeFilterMap(node_filter_map); setEdgeFilterMap(edge_filter_map); } - /// \brief Hides the node of the graph + /// \brief Sets the status of the given node /// - /// This function hides \c n in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c n - /// to be false in the corresponding node-map. - void hide(const Node& n) const { Parent::hide(n); } - - /// \brief Hides the edge of the graph + /// This function sets the status of the given node. + /// It is done by simply setting the assigned value of \c n + /// to \c v in the node filter map. + void status(const Node& n, bool v) const { Parent::status(n, v); } + + /// \brief Sets the status of the given edge /// - /// This function hides \c e in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c e - /// to be false in the corresponding edge-map. - void hide(const Edge& e) const { Parent::hide(e); } - - /// \brief Unhides the node of the graph + /// This function sets the status of the given edge. + /// It is done by simply setting the assigned value of \c e + /// to \c v in the edge filter map. + void status(const Edge& e, bool v) const { Parent::status(e, v); } + + /// \brief Returns the status of the given node /// - /// The value of \c n is set to be true in the node-map which stores - /// hide information. If \c n was hidden previuosly, then it is shown - /// again - void unHide(const Node& n) const { Parent::unHide(n); } - - /// \brief Unhides the edge of the graph + /// This function returns the status of the given node. + /// It is \c true if the given node is enabled (i.e. not hidden). + bool status(const Node& n) const { return Parent::status(n); } + + /// \brief Returns the status of the given edge /// - /// The value of \c e is set to be true in the edge-map which stores - /// hide information. If \c e was hidden previuosly, then it is shown - /// again - void unHide(const Edge& e) const { Parent::unHide(e); } - - /// \brief Returns true if \c n is hidden. + /// This function returns the status of the given edge. + /// It is \c true if the given edge is enabled (i.e. not hidden). + bool status(const Edge& e) const { return Parent::status(e); } + + /// \brief Disables the given node /// - /// Returns true if \c n is hidden. + /// This function disables the given node in the subdigraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(n, false)". + void disable(const Node& n) const { Parent::status(n, false); } + + /// \brief Disables the given edge /// - bool hidden(const Node& n) const { return Parent::hidden(n); } - - /// \brief Returns true if \c e is hidden. + /// This function disables the given edge in the subgraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(e, false)". + void disable(const Edge& e) const { Parent::status(e, false); } + + /// \brief Enables the given node /// - /// Returns true if \c e is hidden. + /// This function enables the given node in the subdigraph. + /// It is the same as \ref status() "status(n, true)". + void enable(const Node& n) const { Parent::status(n, true); } + + /// \brief Enables the given edge /// - bool hidden(const Edge& e) const { return Parent::hidden(e); } + /// This function enables the given edge in the subgraph. + /// It is the same as \ref status() "status(e, true)". + void enable(const Edge& e) const { Parent::status(e, true); } + }; - /// \brief Just gives back a subgraph + /// \brief Returns a read-only SubGraph adaptor /// - /// Just gives back a subgraph - template - SubGraph - subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { - return SubGraph(graph, nfm, efm); + /// This function just returns a read-only \ref SubGraph adaptor. + /// \ingroup graph_adaptors + /// \relates SubGraph + template + SubGraph + subGraph(const GR& graph, + NF& node_filter_map, EF& edge_filter_map) { + return SubGraph + (graph, node_filter_map, edge_filter_map); } - template - SubGraph - subGraph(const Graph& graph, - const NodeFilterMap& nfm, ArcFilterMap& efm) { - return SubGraph - (graph, nfm, efm); + template + SubGraph + subGraph(const GR& graph, + const NF& node_filter_map, EF& edge_filter_map) { + return SubGraph + (graph, node_filter_map, edge_filter_map); } - template - SubGraph - subGraph(const Graph& graph, - NodeFilterMap& nfm, const ArcFilterMap& efm) { - return SubGraph - (graph, nfm, efm); + template + SubGraph + subGraph(const GR& graph, + NF& node_filter_map, const EF& edge_filter_map) { + return SubGraph + (graph, node_filter_map, edge_filter_map); } - template - SubGraph - subGraph(const Graph& graph, - const NodeFilterMap& nfm, const ArcFilterMap& efm) { - return SubGraph - (graph, nfm, efm); + template + SubGraph + subGraph(const GR& graph, + const NF& node_filter_map, const EF& edge_filter_map) { + return SubGraph + (graph, node_filter_map, edge_filter_map); } + /// \ingroup graph_adaptors /// - /// \brief An adaptor for hiding nodes from a digraph or a graph. + /// \brief Adaptor class for hiding nodes in a digraph or a graph. /// - /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool - /// node map must be specified, which defines the filters for - /// nodes. Just the unfiltered nodes and the arcs or edges incident - /// to unfiltered nodes are shown in the subdigraph or subgraph. The - /// FilterNodes is conform to the \ref concepts::Digraph - /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending - /// on the \c _Digraph template parameter. If the \c _checked - /// parameter is true, then the arc or edges incident to filtered nodes - /// are also filtered out. + /// FilterNodes adaptor can be used for hiding nodes in a digraph or a + /// graph. A \c bool node map must be specified, which defines the filter + /// for the nodes. Only the nodes with \c true filter value and the + /// arcs/edges incident to nodes both with \c true filter value are shown + /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph + /// "Digraph" concept or the \ref concepts::Graph "Graph" concept + /// depending on the \c GR template parameter. /// - /// \tparam _Digraph It must be conform to the \ref - /// concepts::Digraph "Digraph concept" or \ref concepts::Graph - /// "Graph concept". The type can be specified to be const. - /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. - /// \tparam _checked If the parameter is false then the arc or edge - /// filtering is not checked with respect to node filter. In this - /// case just isolated nodes can be filtered out from the - /// graph. + /// The adapted (di)graph can also be modified through this adaptor + /// by adding or removing nodes or arcs/edges, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted digraph or graph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept + /// or the \ref concepts::Graph "Graph" concept. + /// It can also be specified to be \c const. + /// \tparam NF The type of the node filter map. + /// It must be a \c bool (or convertible) node map of the + /// adapted (di)graph. The default type is + /// \ref concepts::Graph::NodeMap "GR::NodeMap". + /// + /// \note The \c Node and Arc/Edge types of this adaptor and the + /// adapted (di)graph are convertible to each other. #ifdef DOXYGEN - template, - bool _checked = true> + template + class FilterNodes { #else - template, - bool _checked = true, + template, typename Enable = void> + class FilterNodes : + public DigraphAdaptorExtender< + SubDigraphBase, true> > { #endif - class FilterNodes - : public SubDigraph<_Digraph, _NodeFilterMap, - ConstMap, _checked> { public: - typedef _Digraph Digraph; - typedef _NodeFilterMap NodeFilterMap; - - typedef SubDigraph, _checked> - Parent; + typedef GR Digraph; + typedef NF NodeFilterMap; + + typedef DigraphAdaptorExtender< + SubDigraphBase, true> > + Parent; typedef typename Parent::Node Node; @@ -1412,47 +1505,56 @@ /// \brief Constructor /// - /// Creates an adaptor for the given digraph or graph with + /// Creates a subgraph for the given digraph or graph with the /// given node filter map. - FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : - Parent(), const_true_map(true) { - Parent::setDigraph(_digraph); + FilterNodes(GR& graph, NodeFilterMap& node_filter) : + Parent(), const_true_map(true) + { + Parent::setDigraph(graph); Parent::setNodeFilterMap(node_filter); Parent::setArcFilterMap(const_true_map); } - /// \brief Hides the node of the graph + /// \brief Sets the status of the given node /// - /// This function hides \c n in the digraph or graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c n - /// to be false in the corresponding node map. - void hide(const Node& n) const { Parent::hide(n); } - - /// \brief Unhides the node of the graph + /// This function sets the status of the given node. + /// It is done by simply setting the assigned value of \c n + /// to \c v in the node filter map. + void status(const Node& n, bool v) const { Parent::status(n, v); } + + /// \brief Returns the status of the given node /// - /// The value of \c n is set to be true in the node-map which stores - /// hide information. If \c n was hidden previuosly, then it is shown - /// again - void unHide(const Node& n) const { Parent::unHide(n); } - - /// \brief Returns true if \c n is hidden. + /// This function returns the status of the given node. + /// It is \c true if the given node is enabled (i.e. not hidden). + bool status(const Node& n) const { return Parent::status(n); } + + /// \brief Disables the given node /// - /// Returns true if \c n is hidden. + /// This function disables the given node, so the iteration + /// jumps over it. + /// It is the same as \ref status() "status(n, false)". + void disable(const Node& n) const { Parent::status(n, false); } + + /// \brief Enables the given node /// - bool hidden(const Node& n) const { return Parent::hidden(n); } + /// This function enables the given node. + /// It is the same as \ref status() "status(n, true)". + void enable(const Node& n) const { Parent::status(n, true); } }; - template - class FilterNodes<_Graph, _NodeFilterMap, _checked, - typename enable_if >::type> - : public SubGraph<_Graph, _NodeFilterMap, - ConstMap, _checked> { + template + class FilterNodes >::type> : + public GraphAdaptorExtender< + SubGraphBase, true> > { + public: - typedef _Graph Graph; - typedef _NodeFilterMap NodeFilterMap; - typedef SubGraph > Parent; + typedef GR Graph; + typedef NF NodeFilterMap; + typedef GraphAdaptorExtender< + SubGraphBase, true> > + Parent; typedef typename Parent::Node Node; protected: @@ -1471,51 +1573,75 @@ Parent::setEdgeFilterMap(const_true_map); } - void hide(const Node& n) const { Parent::hide(n); } - void unHide(const Node& n) const { Parent::unHide(n); } - bool hidden(const Node& n) const { return Parent::hidden(n); } + void status(const Node& n, bool v) const { Parent::status(n, v); } + bool status(const Node& n) const { return Parent::status(n); } + void disable(const Node& n) const { Parent::status(n, false); } + void enable(const Node& n) const { Parent::status(n, true); } }; - /// \brief Just gives back a FilterNodes adaptor + /// \brief Returns a read-only FilterNodes adaptor /// - /// Just gives back a FilterNodes adaptor - template - FilterNodes - filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { - return FilterNodes(digraph, nfm); + /// This function just returns a read-only \ref FilterNodes adaptor. + /// \ingroup graph_adaptors + /// \relates FilterNodes + template + FilterNodes + filterNodes(const GR& graph, NF& node_filter_map) { + return FilterNodes(graph, node_filter_map); } - template - FilterNodes - filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) { - return FilterNodes(digraph, nfm); + template + FilterNodes + filterNodes(const GR& graph, const NF& node_filter_map) { + return FilterNodes(graph, node_filter_map); } /// \ingroup graph_adaptors /// - /// \brief An adaptor for hiding arcs from a digraph. + /// \brief Adaptor class for hiding arcs in a digraph. /// - /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must - /// be specified, which defines the filters for arcs. Just the - /// unfiltered arcs are shown in the subdigraph. The FilterArcs is - /// conform to the \ref concepts::Digraph "Digraph concept". + /// FilterArcs adaptor can be used for hiding arcs in a digraph. + /// A \c bool arc map must be specified, which defines the filter for + /// the arcs. Only the arcs with \c true filter value are shown in the + /// subdigraph. This adaptor conforms to the \ref concepts::Digraph + /// "Digraph" concept. /// - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph - /// "Digraph concept". The type can be specified to be const. - /// \tparam _ArcFilterMap A bool valued arc map of the the adapted - /// graph. - template + /// The adapted digraph can also be modified through this adaptor + /// by adding or removing nodes or arcs, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It can also be specified to be \c const. + /// \tparam AF The type of the arc filter map. + /// It must be a \c bool (or convertible) arc map of the + /// adapted digraph. The default type is + /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// + /// \note The \c Node and \c Arc types of this adaptor and the adapted + /// digraph are convertible to each other. +#ifdef DOXYGEN + template + class FilterArcs { +#else + template > class FilterArcs : - public SubDigraph<_Digraph, ConstMap, - _ArcFilterMap, false> { + public DigraphAdaptorExtender< + SubDigraphBase, AF, false> > { +#endif public: - typedef _Digraph Digraph; - typedef _ArcFilterMap ArcFilterMap; - - typedef SubDigraph, - ArcFilterMap, false> Parent; + /// The type of the adapted digraph. + typedef GR Digraph; + /// The type of the arc filter map. + typedef AF ArcFilterMap; + + typedef DigraphAdaptorExtender< + SubDigraphBase, AF, false> > + Parent; typedef typename Parent::Arc Arc; @@ -1530,8 +1656,8 @@ /// \brief Constructor /// - /// Creates a FilterArcs adaptor for the given graph with - /// given arc map filter. + /// Creates a subdigraph for the given digraph with the given arc + /// filter map. FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) : Parent(), const_true_map(true) { Parent::setDigraph(digraph); @@ -1539,66 +1665,98 @@ Parent::setArcFilterMap(arc_filter); } - /// \brief Hides the arc of the graph + /// \brief Sets the status of the given arc /// - /// This function hides \c a in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c a - /// to be false in the corresponding arc map. - void hide(const Arc& a) const { Parent::hide(a); } - - /// \brief Unhides the arc of the graph + /// This function sets the status of the given arc. + /// It is done by simply setting the assigned value of \c a + /// to \c v in the arc filter map. + void status(const Arc& a, bool v) const { Parent::status(a, v); } + + /// \brief Returns the status of the given arc /// - /// The value of \c a is set to be true in the arc-map which stores - /// hide information. If \c a was hidden previuosly, then it is shown - /// again - void unHide(const Arc& a) const { Parent::unHide(a); } - - /// \brief Returns true if \c a is hidden. + /// This function returns the status of the given arc. + /// It is \c true if the given arc is enabled (i.e. not hidden). + bool status(const Arc& a) const { return Parent::status(a); } + + /// \brief Disables the given arc /// - /// Returns true if \c a is hidden. + /// This function disables the given arc in the subdigraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(a, false)". + void disable(const Arc& a) const { Parent::status(a, false); } + + /// \brief Enables the given arc /// - bool hidden(const Arc& a) const { return Parent::hidden(a); } + /// This function enables the given arc in the subdigraph. + /// It is the same as \ref status() "status(a, true)". + void enable(const Arc& a) const { Parent::status(a, true); } }; - /// \brief Just gives back an FilterArcs adaptor + /// \brief Returns a read-only FilterArcs adaptor /// - /// Just gives back an FilterArcs adaptor - template - FilterArcs - filterArcs(const Digraph& digraph, ArcFilterMap& afm) { - return FilterArcs(digraph, afm); + /// This function just returns a read-only \ref FilterArcs adaptor. + /// \ingroup graph_adaptors + /// \relates FilterArcs + template + FilterArcs + filterArcs(const GR& digraph, AF& arc_filter_map) { + return FilterArcs(digraph, arc_filter_map); } - template - FilterArcs - filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { - return FilterArcs(digraph, afm); + template + FilterArcs + filterArcs(const GR& digraph, const AF& arc_filter_map) { + return FilterArcs(digraph, arc_filter_map); } /// \ingroup graph_adaptors /// - /// \brief An adaptor for hiding edges from a graph. + /// \brief Adaptor class for hiding edges in a graph. /// - /// FilterEdges adaptor hides edges in a digraph. A bool edge map must - /// be specified, which defines the filters for edges. Just the - /// unfiltered edges are shown in the subdigraph. The FilterEdges is - /// conform to the \ref concepts::Graph "Graph concept". + /// FilterEdges adaptor can be used for hiding edges in a graph. + /// A \c bool edge map must be specified, which defines the filter for + /// the edges. Only the edges with \c true filter value are shown in the + /// subgraph. This adaptor conforms to the \ref concepts::Graph + /// "Graph" concept. /// - /// \tparam _Graph It must be conform to the \ref concepts::Graph - /// "Graph concept". The type can be specified to be const. - /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted - /// graph. - template + /// The adapted graph can also be modified through this adaptor + /// by adding or removing nodes or edges, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted graph. + /// It must conform to the \ref concepts::Graph "Graph" concept. + /// It can also be specified to be \c const. + /// \tparam EF The type of the edge filter map. + /// It must be a \c bool (or convertible) edge map of the + /// adapted graph. The default type is + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". + /// + /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the + /// adapted graph are convertible to each other. +#ifdef DOXYGEN + template + class FilterEdges { +#else + template > class FilterEdges : - public SubGraph<_Graph, ConstMap, - _EdgeFilterMap, false> { + public GraphAdaptorExtender< + SubGraphBase, EF, false> > { +#endif public: - typedef _Graph Graph; - typedef _EdgeFilterMap EdgeFilterMap; - typedef SubGraph, - EdgeFilterMap, false> Parent; + /// The type of the adapted graph. + typedef GR Graph; + /// The type of the edge filter map. + typedef EF EdgeFilterMap; + + typedef GraphAdaptorExtender< + SubGraphBase, EF, false> > + Parent; + typedef typename Parent::Edge Edge; + protected: ConstMap const_true_map; @@ -1610,52 +1768,61 @@ /// \brief Constructor /// - /// Creates a FilterEdges adaptor for the given graph with - /// given edge map filters. - FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) : + /// Creates a subgraph for the given graph with the given edge + /// filter map. + FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : Parent(), const_true_map(true) { - Parent::setGraph(_graph); + Parent::setGraph(graph); Parent::setNodeFilterMap(const_true_map); Parent::setEdgeFilterMap(edge_filter_map); } - /// \brief Hides the edge of the graph + /// \brief Sets the status of the given edge /// - /// This function hides \c e in the graph, i.e. the iteration - /// jumps over it. This is done by simply setting the value of \c e - /// to be false in the corresponding edge-map. - void hide(const Edge& e) const { Parent::hide(e); } - - /// \brief Unhides the edge of the graph + /// This function sets the status of the given edge. + /// It is done by simply setting the assigned value of \c e + /// to \c v in the edge filter map. + void status(const Edge& e, bool v) const { Parent::status(e, v); } + + /// \brief Returns the status of the given edge /// - /// The value of \c e is set to be true in the edge-map which stores - /// hide information. If \c e was hidden previuosly, then it is shown - /// again - void unHide(const Edge& e) const { Parent::unHide(e); } - - /// \brief Returns true if \c e is hidden. + /// This function returns the status of the given edge. + /// It is \c true if the given edge is enabled (i.e. not hidden). + bool status(const Edge& e) const { return Parent::status(e); } + + /// \brief Disables the given edge /// - /// Returns true if \c e is hidden. + /// This function disables the given edge in the subgraph, + /// so the iteration jumps over it. + /// It is the same as \ref status() "status(e, false)". + void disable(const Edge& e) const { Parent::status(e, false); } + + /// \brief Enables the given edge /// - bool hidden(const Edge& e) const { return Parent::hidden(e); } + /// This function enables the given edge in the subgraph. + /// It is the same as \ref status() "status(e, true)". + void enable(const Edge& e) const { Parent::status(e, true); } }; - /// \brief Just gives back a FilterEdges adaptor + /// \brief Returns a read-only FilterEdges adaptor /// - /// Just gives back a FilterEdges adaptor - template - FilterEdges - filterEdges(const Graph& graph, EdgeFilterMap& efm) { - return FilterEdges(graph, efm); + /// This function just returns a read-only \ref FilterEdges adaptor. + /// \ingroup graph_adaptors + /// \relates FilterEdges + template + FilterEdges + filterEdges(const GR& graph, EF& edge_filter_map) { + return FilterEdges(graph, edge_filter_map); } - template - FilterEdges - filterEdges(const Graph& graph, const EdgeFilterMap& efm) { - return FilterEdges(graph, efm); + template + FilterEdges + filterEdges(const GR& graph, const EF& edge_filter_map) { + return FilterEdges(graph, edge_filter_map); } + template class UndirectorBase { public: @@ -1695,8 +1862,6 @@ } }; - - void first(Node& n) const { _digraph->first(n); } @@ -1845,12 +2010,15 @@ void clear() { _digraph->clear(); } typedef NodeNumTagIndicator NodeNumTag; - int nodeNum() const { return 2 * _digraph->arcNum(); } - typedef EdgeNumTagIndicator EdgeNumTag; + int nodeNum() const { return _digraph->nodeNum(); } + + typedef ArcNumTagIndicator ArcNumTag; int arcNum() const { return 2 * _digraph->arcNum(); } + + typedef ArcNumTag EdgeNumTag; int edgeNum() const { return _digraph->arcNum(); } - typedef FindEdgeTagIndicator FindEdgeTag; + typedef FindArcTagIndicator FindArcTag; Arc findArc(Node s, Node t, Arc p = INVALID) const { if (p == INVALID) { Edge arc = _digraph->findArc(s, t); @@ -1869,6 +2037,7 @@ return INVALID; } + typedef FindArcTag FindEdgeTag; Edge findEdge(Node s, Node t, Edge p = INVALID) const { if (s != t) { if (p == INVALID) { @@ -1876,7 +2045,7 @@ if (arc != INVALID) return arc; arc = _digraph->findArc(t, s); if (arc != INVALID) return arc; - } else if (_digraph->s(p) == s) { + } else if (_digraph->source(p) == s) { Edge arc = _digraph->findArc(s, t, p); if (arc != INVALID) return arc; arc = _digraph->findArc(t, s); @@ -1905,6 +2074,10 @@ typedef _Value Value; typedef Arc Key; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReference; + typedef typename MapTraits::ReturnValue Reference; ArcMapBase(const Adaptor& adaptor) : _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} @@ -1920,8 +2093,7 @@ } } - typename MapTraits::ConstReturnValue - operator[](const Arc& a) const { + ConstReturnValue operator[](const Arc& a) const { if (direction(a)) { return _forward[a]; } else { @@ -1929,8 +2101,7 @@ } } - typename MapTraits::ReturnValue - operator[](const Arc& a) { + ReturnValue operator[](const Arc& a) { if (direction(a)) { return _forward[a]; } else { @@ -1980,7 +2151,7 @@ typedef _Value Value; typedef SubMapExtender > Parent; - ArcMap(const Adaptor& adaptor) + explicit ArcMap(const Adaptor& adaptor) : Parent(adaptor) {} ArcMap(const Adaptor& adaptor, const Value& value) @@ -2027,6 +2198,9 @@ typedef typename ItemSetTraits::ItemNotifier NodeNotifier; NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } + typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; + EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } + protected: UndirectorBase() : _digraph(0) {} @@ -2041,59 +2215,76 @@ /// \ingroup graph_adaptors /// - /// \brief Undirect the graph + /// \brief Adaptor class for viewing a digraph as an undirected graph. /// - /// This adaptor makes an undirected graph from a directed - /// graph. All arcs of the underlying digraph will be showed in the - /// adaptor as an edge. The Orienter adaptor is conform to the \ref - /// concepts::Graph "Graph concept". + /// Undirector adaptor can be used for viewing a digraph as an undirected + /// graph. All arcs of the underlying digraph are showed in the + /// adaptor as an edge (and also as a pair of arcs, of course). + /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. /// - /// \tparam _Digraph It must be conform to the \ref - /// concepts::Digraph "Digraph concept". The type can be specified - /// to const. - template - class Undirector - : public GraphAdaptorExtender > { + /// The adapted digraph can also be modified through this adaptor + /// by adding or removing nodes or edges, unless the \c GR template + /// parameter is set to be \c const. + /// + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It can also be specified to be \c const. + /// + /// \note The \c Node type of this adaptor and the adapted digraph are + /// convertible to each other, moreover the \c Edge type of the adaptor + /// and the \c Arc type of the adapted digraph are also convertible to + /// each other. + /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type + /// of the adapted digraph.) + template +#ifdef DOXYGEN + class Undirector { +#else + class Undirector : + public GraphAdaptorExtender > { +#endif public: - typedef _Digraph Digraph; - typedef GraphAdaptorExtender > Parent; + /// The type of the adapted digraph. + typedef GR Digraph; + typedef GraphAdaptorExtender > Parent; protected: Undirector() { } public: /// \brief Constructor /// - /// Creates a undirected graph from the given digraph - Undirector(_Digraph& digraph) { + /// Creates an undirected graph from the given digraph. + Undirector(Digraph& digraph) { setDigraph(digraph); } - /// \brief ArcMap combined from two original ArcMap + /// \brief Arc map combined from two original arc maps /// - /// This class adapts two original digraph ArcMap to - /// get an arc map on the undirected graph. - template + /// This map adaptor class adapts two arc maps of the underlying + /// digraph to get an arc map of the undirected graph. + /// Its value type is inherited from the first arc map type + /// (\c %ForwardMap). + template class CombinedArcMap { public: - typedef _ForwardMap ForwardMap; - typedef _BackwardMap BackwardMap; + /// The key type of the map + typedef typename Parent::Arc Key; + /// The value type of the map + typedef typename ForwardMap::Value Value; typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; - typedef typename ForwardMap::Value Value; - typedef typename Parent::Arc Key; - - /// \brief Constructor - /// + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; + /// Constructor CombinedArcMap(ForwardMap& forward, BackwardMap& backward) : _forward(&forward), _backward(&backward) {} - - /// \brief Sets the value associated with a key. - /// - /// Sets the value associated with a key. + /// Sets the value associated with the given key. void set(const Key& e, const Value& a) { if (Parent::direction(e)) { _forward->set(e, a); @@ -2102,11 +2293,8 @@ } } - /// \brief Returns the value associated with a key. - /// - /// Returns the value associated with a key. - typename MapTraits::ConstReturnValue - operator[](const Key& e) const { + /// Returns the value associated with the given key. + ConstReturnValue operator[](const Key& e) const { if (Parent::direction(e)) { return (*_forward)[e]; } else { @@ -2114,11 +2302,8 @@ } } - /// \brief Returns the value associated with a key. - /// - /// Returns the value associated with a key. - typename MapTraits::ReturnValue - operator[](const Key& e) { + /// Returns a reference to the value associated with the given key. + ReturnValue operator[](const Key& e) { if (Parent::direction(e)) { return (*_forward)[e]; } else { @@ -2133,9 +2318,9 @@ }; - /// \brief Just gives back a combined arc map + /// \brief Returns a combined arc map /// - /// Just gives back a combined arc map + /// This function just returns a combined arc map. template static CombinedArcMap combinedArcMap(ForwardMap& forward, BackwardMap& backward) { @@ -2165,15 +2350,17 @@ }; - /// \brief Just gives back an undirected view of the given digraph + /// \brief Returns a read-only Undirector adaptor /// - /// Just gives back an undirected view of the given digraph - template - Undirector - undirector(const Digraph& digraph) { - return Undirector(digraph); + /// This function just returns a read-only \ref Undirector adaptor. + /// \ingroup graph_adaptors + /// \relates Undirector + template + Undirector undirector(const GR& digraph) { + return Undirector(digraph); } + template class OrienterBase { public: @@ -2191,12 +2378,12 @@ void first(Node& i) const { _graph->first(i); } void first(Arc& i) const { _graph->first(i); } void firstIn(Arc& i, const Node& n) const { - bool d; + bool d = true; _graph->firstInc(i, d, n); while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); } void firstOut(Arc& i, const Node& n ) const { - bool d; + bool d = true; _graph->firstInc(i, d, n); while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); } @@ -2224,24 +2411,15 @@ typedef NodeNumTagIndicator NodeNumTag; int nodeNum() const { return _graph->nodeNum(); } - typedef EdgeNumTagIndicator EdgeNumTag; + typedef EdgeNumTagIndicator ArcNumTag; int arcNum() const { return _graph->edgeNum(); } - typedef FindEdgeTagIndicator FindEdgeTag; + typedef FindEdgeTagIndicator FindArcTag; Arc findArc(const Node& u, const Node& v, - const Arc& prev = INVALID) { - Arc arc = prev; - bool d = arc == INVALID ? true : (*_direction)[arc]; - if (d) { + const Arc& prev = INVALID) const { + Arc arc = _graph->findEdge(u, v, prev); + while (arc != INVALID && source(arc) != u) { arc = _graph->findEdge(u, v, arc); - while (arc != INVALID && !(*_direction)[arc]) { - _graph->findEdge(u, v, arc); - } - if (arc != INVALID) return arc; - } - _graph->findEdge(v, u, arc); - while (arc != INVALID && (*_direction)[arc]) { - _graph->findEdge(u, v, arc); } return arc; } @@ -2251,8 +2429,8 @@ } Arc addArc(const Node& u, const Node& v) { - Arc arc = _graph->addArc(u, v); - _direction->set(arc, _graph->source(arc) == u); + Arc arc = _graph->addEdge(u, v); + _direction->set(arc, _graph->u(arc) == u); return arc; } @@ -2343,78 +2521,98 @@ /// \ingroup graph_adaptors /// - /// \brief Orients the edges of the graph to get a digraph + /// \brief Adaptor class for orienting the edges of a graph to get a digraph /// - /// This adaptor orients each edge in the undirected graph. The - /// direction of the arcs stored in an edge node map. The arcs can - /// be easily reverted by the \c reverseArc() member function in the - /// adaptor. The Orienter adaptor is conform to the \ref - /// concepts::Digraph "Digraph concept". + /// Orienter adaptor can be used for orienting the edges of a graph to + /// get a digraph. A \c bool edge map of the underlying graph must be + /// specified, which define the direction of the arcs in the adaptor. + /// The arcs can be easily reversed by the \c reverseArc() member function + /// of the adaptor. + /// This class conforms to the \ref concepts::Digraph "Digraph" concept. /// - /// \tparam _Graph It must be conform to the \ref concepts::Graph - /// "Graph concept". The type can be specified to be const. - /// \tparam _DirectionMap A bool valued edge map of the the adapted - /// graph. + /// The adapted graph can also be modified through this adaptor + /// by adding or removing nodes or arcs, unless the \c GR template + /// parameter is set to be \c const. /// - /// \sa orienter - template > + /// \tparam GR The type of the adapted graph. + /// It must conform to the \ref concepts::Graph "Graph" concept. + /// It can also be specified to be \c const. + /// \tparam DM The type of the direction map. + /// It must be a \c bool (or convertible) edge map of the + /// adapted graph. The default type is + /// \ref concepts::Graph::EdgeMap "GR::EdgeMap". + /// + /// \note The \c Node type of this adaptor and the adapted graph are + /// convertible to each other, moreover the \c Arc type of the adaptor + /// and the \c Edge type of the adapted graph are also convertible to + /// each other. +#ifdef DOXYGEN + template + class Orienter { +#else + template > class Orienter : - public DigraphAdaptorExtender > { + public DigraphAdaptorExtender > { +#endif public: - typedef _Graph Graph; - typedef DigraphAdaptorExtender< - OrienterBase<_Graph, DirectionMap> > Parent; + + /// The type of the adapted graph. + typedef GR Graph; + /// The type of the direction edge map. + typedef DM DirectionMap; + + typedef DigraphAdaptorExtender > Parent; typedef typename Parent::Arc Arc; protected: Orienter() { } public: - /// \brief Constructor of the adaptor + /// \brief Constructor /// - /// Constructor of the adaptor + /// Constructor of the adaptor. Orienter(Graph& graph, DirectionMap& direction) { setGraph(graph); setDirectionMap(direction); } - /// \brief Reverse arc + /// \brief Reverses the given arc /// - /// It reverse the given arc. It simply negate the direction in the map. + /// This function reverses the given arc. + /// It is done by simply negate the assigned value of \c a + /// in the direction map. void reverseArc(const Arc& a) { Parent::reverseArc(a); } }; - /// \brief Just gives back a Orienter + /// \brief Returns a read-only Orienter adaptor /// - /// Just gives back a Orienter - template - Orienter - orienter(const Graph& graph, DirectionMap& dm) { - return Orienter(graph, dm); + /// This function just returns a read-only \ref Orienter adaptor. + /// \ingroup graph_adaptors + /// \relates Orienter + template + Orienter + orienter(const GR& graph, DM& direction_map) { + return Orienter(graph, direction_map); } - template - Orienter - orienter(const Graph& graph, const DirectionMap& dm) { - return Orienter(graph, dm); + template + Orienter + orienter(const GR& graph, const DM& direction_map) { + return Orienter(graph, direction_map); } namespace _adaptor_bits { - template, - typename _FlowMap = _CapacityMap, - typename _Tolerance = Tolerance > + template class ResForwardFilter { public: - typedef _Digraph Digraph; - typedef _CapacityMap CapacityMap; - typedef _FlowMap FlowMap; - typedef _Tolerance Tolerance; - typedef typename Digraph::Arc Key; typedef bool Value; @@ -2434,18 +2632,13 @@ } }; - template, - typename _FlowMap = _CapacityMap, - typename _Tolerance = Tolerance > + template class ResBackwardFilter { public: - typedef _Digraph Digraph; - typedef _CapacityMap CapacityMap; - typedef _FlowMap FlowMap; - typedef _Tolerance Tolerance; - typedef typename Digraph::Arc Key; typedef bool Value; @@ -2470,50 +2663,71 @@ /// \ingroup graph_adaptors /// - /// \brief An adaptor for composing the residual graph for directed + /// \brief Adaptor class for composing the residual digraph for directed /// flow and circulation problems. /// - /// An adaptor for composing the residual graph for directed flow and - /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph - /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, - /// be functions on the arc-set. + /// Residual can be used for composing the \e residual digraph for directed + /// flow and circulation problems. Let \f$ G=(V, A) \f$ be a directed graph + /// and let \f$ F \f$ be a number type. Let \f$ flow, cap: A\to F \f$ be + /// functions on the arcs. + /// This adaptor implements a digraph structure with node set \f$ V \f$ + /// and arc set \f$ A_{forward}\cup A_{backward} \f$, + /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)0\} \f$, i.e. the so + /// called residual digraph. + /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken, + /// multiplicities are counted, i.e. the adaptor has exactly + /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel + /// arcs). + /// This class conforms to the \ref concepts::Digraph "Digraph" concept. /// - /// Then Residual implements the digraph structure with - /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$, - /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$, i.e. the so - /// called residual graph. When we take the union - /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, - /// i.e. if an arc is in both \f$ A_{forward} \f$ and - /// \f$ A_{backward} \f$, then in the adaptor it appears in both - /// orientation. + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It is implicitly \c const. + /// \tparam CM The type of the capacity map. + /// It must be an arc map of some numerical type, which defines + /// the capacities in the flow problem. It is implicitly \c const. + /// The default type is + /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// \tparam FM The type of the flow map. + /// It must be an arc map of some numerical type, which defines + /// the flow values in the flow problem. The default type is \c CM. + /// \tparam TL The tolerance type for handling inexact computation. + /// The default tolerance type depends on the value type of the + /// capacity map. /// - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph - /// "Digraph concept". The type is implicitly const. - /// \tparam _CapacityMap An arc map of some numeric type, it defines - /// the capacities in the flow problem. The map is implicitly const. - /// \tparam _FlowMap An arc map of some numeric type, it defines - /// the capacities in the flow problem. - /// \tparam _Tolerance Handler for inexact computation. - template, - typename _FlowMap = _CapacityMap, - typename _Tolerance = Tolerance > + /// \note This adaptor is implemented using Undirector and FilterArcs + /// adaptors. + /// + /// \note The \c Node type of this adaptor and the adapted digraph are + /// convertible to each other, moreover the \c Arc type of the adaptor + /// is convertible to the \c Arc type of the adapted digraph. +#ifdef DOXYGEN + template + class Residual +#else + template, + typename FM = CM, + typename TL = Tolerance > class Residual : public FilterArcs< - Undirector, - typename Undirector::template CombinedArcMap< - _adaptor_bits::ResForwardFilter, - _adaptor_bits::ResBackwardFilter > > + Undirector, + typename Undirector::template CombinedArcMap< + _adaptor_bits::ResForwardFilter, + _adaptor_bits::ResBackwardFilter > > +#endif { public: - typedef _Digraph Digraph; - typedef _CapacityMap CapacityMap; - typedef _FlowMap FlowMap; - typedef _Tolerance Tolerance; + /// The type of the underlying digraph. + typedef GR Digraph; + /// The type of the capacity map. + typedef CM CapacityMap; + /// The type of the flow map. + typedef FM FlowMap; + /// The tolerance type. + typedef TL Tolerance; typedef typename CapacityMap::Value Value; typedef Residual Adaptor; @@ -2529,7 +2743,7 @@ FlowMap, Tolerance> BackwardFilter; typedef typename Undirected:: - template CombinedArcMap ArcFilter; + template CombinedArcMap ArcFilter; typedef FilterArcs Parent; @@ -2543,10 +2757,10 @@ public: - /// \brief Constructor of the residual digraph. + /// \brief Constructor /// - /// Constructor of the residual graph. The parameters are the digraph, - /// the flow map, the capacity map and a tolerance object. + /// Constructor of the residual digraph adaptor. The parameters are the + /// digraph, the capacity map, the flow map, and a tolerance object. Residual(const Digraph& digraph, const CapacityMap& capacity, FlowMap& flow, const Tolerance& tolerance = Tolerance()) : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), @@ -2560,9 +2774,9 @@ typedef typename Parent::Arc Arc; - /// \brief Gives back the residual capacity of the arc. + /// \brief Returns the residual capacity of the given arc. /// - /// Gives back the residual capacity of the arc. + /// Returns the residual capacity of the given arc. Value residualCapacity(const Arc& a) const { if (Undirected::direction(a)) { return (*_capacity)[a] - (*_flow)[a]; @@ -2571,11 +2785,11 @@ } } - /// \brief Augment on the given arc in the residual graph. + /// \brief Augments on the given arc in the residual digraph. /// - /// Augment on the given arc in the residual graph. It increase - /// or decrease the flow on the original arc depend on the direction - /// of the residual arc. + /// Augments on the given arc in the residual digraph. It increases + /// or decreases the flow value on the original arc according to the + /// direction of the residual arc. void augment(const Arc& a, const Value& v) const { if (Undirected::direction(a)) { _flow->set(a, (*_flow)[a] + v); @@ -2584,59 +2798,84 @@ } } - /// \brief Returns the direction of the arc. + /// \brief Returns \c true if the given residual arc is a forward arc. /// - /// Returns true when the arc is same oriented as the original arc. + /// Returns \c true if the given residual arc has the same orientation + /// as the original arc, i.e. it is a so called forward arc. static bool forward(const Arc& a) { return Undirected::direction(a); } - /// \brief Returns the direction of the arc. + /// \brief Returns \c true if the given residual arc is a backward arc. /// - /// Returns true when the arc is opposite oriented as the original arc. + /// Returns \c true if the given residual arc has the opposite orientation + /// than the original arc, i.e. it is a so called backward arc. static bool backward(const Arc& a) { return !Undirected::direction(a); } - /// \brief Gives back the forward oriented residual arc. + /// \brief Returns the forward oriented residual arc. /// - /// Gives back the forward oriented residual arc. + /// Returns the forward oriented residual arc related to the given + /// arc of the underlying digraph. static Arc forward(const typename Digraph::Arc& a) { return Undirected::direct(a, true); } - /// \brief Gives back the backward oriented residual arc. + /// \brief Returns the backward oriented residual arc. /// - /// Gives back the backward oriented residual arc. + /// Returns the backward oriented residual arc related to the given + /// arc of the underlying digraph. static Arc backward(const typename Digraph::Arc& a) { return Undirected::direct(a, false); } /// \brief Residual capacity map. /// - /// In generic residual graph the residual capacity can be obtained - /// as a map. + /// This map adaptor class can be used for obtaining the residual + /// capacities as an arc map of the residual digraph. + /// Its value type is inherited from the capacity map. class ResidualCapacity { protected: const Adaptor* _adaptor; public: - /// The Key type + /// The key type of the map typedef Arc Key; - /// The Value type - typedef typename _CapacityMap::Value Value; + /// The value type of the map + typedef typename CapacityMap::Value Value; /// Constructor ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} - /// \e + /// Returns the value associated with the given residual arc Value operator[](const Arc& a) const { return _adaptor->residualCapacity(a); } }; + /// \brief Returns a residual capacity map + /// + /// This function just returns a residual capacity map. + ResidualCapacity residualCapacity() const { + return ResidualCapacity(*this); + } + }; + /// \brief Returns a (read-only) Residual adaptor + /// + /// This function just returns a (read-only) \ref Residual adaptor. + /// \ingroup graph_adaptors + /// \relates Residual + template + Residual residual(const GR& digraph, + const CM& capacity_map, + FM& flow_map) { + return Residual (digraph, capacity_map, flow_map); + } + + template class SplitNodesBase { public: @@ -2884,30 +3123,26 @@ } typedef True NodeNumTag; - int nodeNum() const { return 2 * countNodes(*_digraph); } - typedef True EdgeNumTag; + typedef True ArcNumTag; int arcNum() const { return countArcs(*_digraph) + countNodes(*_digraph); } - typedef True FindEdgeTag; + typedef True FindArcTag; Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { - if (inNode(u)) { - if (outNode(v)) { - if (static_cast(u) == - static_cast(v) && prev == INVALID) { - return Arc(u); - } + if (inNode(u) && outNode(v)) { + if (static_cast(u) == + static_cast(v) && prev == INVALID) { + return Arc(u); } - } else { - if (inNode(v)) { - return Arc(::lemon::findArc(*_digraph, u, v, prev)); - } + } + else if (outNode(u) && inNode(v)) { + return Arc(::lemon::findArc(*_digraph, u, v, prev)); } return INVALID; } @@ -2921,6 +3156,11 @@ public: typedef Node Key; typedef _Value Value; + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; NodeMapBase(const Adaptor& adaptor) : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} @@ -2933,14 +3173,12 @@ else {_out_map.set(key, val); } } - typename MapTraits::ReturnValue - operator[](const Node& key) { + ReturnValue operator[](const Node& key) { if (Adaptor::inNode(key)) { return _in_map[key]; } else { return _out_map[key]; } } - typename MapTraits::ConstReturnValue - operator[](const Node& key) const { + ConstReturnValue operator[](const Node& key) const { if (Adaptor::inNode(key)) { return _in_map[key]; } else { return _out_map[key]; } } @@ -2957,6 +3195,11 @@ public: typedef Arc Key; typedef _Value Value; + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; ArcMapBase(const Adaptor& adaptor) : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} @@ -2972,8 +3215,7 @@ } } - typename MapTraits::ReturnValue - operator[](const Arc& key) { + ReturnValue operator[](const Arc& key) { if (Adaptor::origArc(key)) { return _arc_map[key._item.first()]; } else { @@ -2981,8 +3223,7 @@ } } - typename MapTraits::ConstReturnValue - operator[](const Arc& key) const { + ConstReturnValue operator[](const Arc& key) const { if (Adaptor::origArc(key)) { return _arc_map[key._item.first()]; } else { @@ -3063,31 +3304,41 @@ /// \ingroup graph_adaptors /// - /// \brief Split the nodes of a directed graph + /// \brief Adaptor class for splitting the nodes of a digraph. /// - /// The SplitNodes adaptor splits each node into an in-node and an - /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in - /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node - /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the - /// original digraph the new target of the arc will be \f$ u_{in} \f$ - /// and similarly the source of the original \f$ (u, v) \f$ arc - /// will be \f$ u_{out} \f$. The adaptor will add for each node in - /// the original digraph an additional arc which connects - /// \f$ (u_{in}, u_{out}) \f$. + /// SplitNodes adaptor can be used for splitting each node into an + /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor + /// replaces each node \f$ u \f$ in the digraph with two nodes, + /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$. + /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the + /// new target of the arc will be \f$ u_{in} \f$ and similarly the + /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$. + /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$ + /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph. /// - /// The aim of this class is to run algorithm with node costs if the - /// algorithm can use directly just arc costs. In this case we should use - /// a \c SplitNodes and set the node cost of the graph to the - /// bind arc in the adapted graph. + /// The aim of this class is running an algorithm with respect to node + /// costs or capacities if the algorithm considers only arc costs or + /// capacities directly. + /// In this case you can use \c SplitNodes adaptor, and set the node + /// costs/capacities of the original digraph to the \e bind \e arcs + /// in the adaptor. /// - /// \tparam _Digraph It must be conform to the \ref concepts::Digraph - /// "Digraph concept". The type can be specified to be const. - template + /// \tparam GR The type of the adapted digraph. + /// It must conform to the \ref concepts::Digraph "Digraph" concept. + /// It is implicitly \c const. + /// + /// \note The \c Node type of this adaptor is converible to the \c Node + /// type of the adapted digraph. + template +#ifdef DOXYGEN + class SplitNodes { +#else class SplitNodes - : public DigraphAdaptorExtender > { + : public DigraphAdaptorExtender > { +#endif public: - typedef _Digraph Digraph; - typedef DigraphAdaptorExtender > Parent; + typedef GR Digraph; + typedef DigraphAdaptorExtender > Parent; typedef typename Digraph::Node DigraphNode; typedef typename Digraph::Arc DigraphArc; @@ -3095,89 +3346,110 @@ typedef typename Parent::Node Node; typedef typename Parent::Arc Arc; - /// \brief Constructor of the adaptor. + /// \brief Constructor /// /// Constructor of the adaptor. - SplitNodes(Digraph& g) { + SplitNodes(const Digraph& g) { Parent::setDigraph(g); } - /// \brief Returns true when the node is in-node. + /// \brief Returns \c true if the given node is an in-node. /// - /// Returns true when the node is in-node. + /// Returns \c true if the given node is an in-node. static bool inNode(const Node& n) { return Parent::inNode(n); } - /// \brief Returns true when the node is out-node. + /// \brief Returns \c true if the given node is an out-node. /// - /// Returns true when the node is out-node. + /// Returns \c true if the given node is an out-node. static bool outNode(const Node& n) { return Parent::outNode(n); } - /// \brief Returns true when the arc is arc in the original digraph. + /// \brief Returns \c true if the given arc is an original arc. /// - /// Returns true when the arc is arc in the original digraph. + /// Returns \c true if the given arc is one of the arcs in the + /// original digraph. static bool origArc(const Arc& a) { return Parent::origArc(a); } - /// \brief Returns true when the arc binds an in-node and an out-node. + /// \brief Returns \c true if the given arc is a bind arc. /// - /// Returns true when the arc binds an in-node and an out-node. + /// Returns \c true if the given arc is a bind arc, i.e. it connects + /// an in-node and an out-node. static bool bindArc(const Arc& a) { return Parent::bindArc(a); } - /// \brief Gives back the in-node created from the \c node. + /// \brief Returns the in-node created from the given original node. /// - /// Gives back the in-node created from the \c node. + /// Returns the in-node created from the given original node. static Node inNode(const DigraphNode& n) { return Parent::inNode(n); } - /// \brief Gives back the out-node created from the \c node. + /// \brief Returns the out-node created from the given original node. /// - /// Gives back the out-node created from the \c node. + /// Returns the out-node created from the given original node. static Node outNode(const DigraphNode& n) { return Parent::outNode(n); } - /// \brief Gives back the arc binds the two part of the node. + /// \brief Returns the bind arc that corresponds to the given + /// original node. /// - /// Gives back the arc binds the two part of the node. + /// Returns the bind arc in the adaptor that corresponds to the given + /// original node, i.e. the arc connecting the in-node and out-node + /// of \c n. static Arc arc(const DigraphNode& n) { return Parent::arc(n); } - /// \brief Gives back the arc of the original arc. + /// \brief Returns the arc that corresponds to the given original arc. /// - /// Gives back the arc of the original arc. + /// Returns the arc in the adaptor that corresponds to the given + /// original arc. static Arc arc(const DigraphArc& a) { return Parent::arc(a); } - /// \brief NodeMap combined from two original NodeMap + /// \brief Node map combined from two original node maps /// - /// This class adapt two of the original digraph NodeMap to - /// get a node map on the adapted digraph. + /// This map adaptor class adapts two node maps of the original digraph + /// to get a node map of the split digraph. + /// Its value type is inherited from the first node map type + /// (\c InNodeMap). template class CombinedNodeMap { public: + /// The key type of the map typedef Node Key; + /// The value type of the map typedef typename InNodeMap::Value Value; - /// \brief Constructor - /// - /// Constructor. + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; + + /// Constructor CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) : _in_map(in_map), _out_map(out_map) {} - /// \brief The subscript operator. - /// - /// The subscript operator. + /// Returns the value associated with the given key. + Value operator[](const Key& key) const { + if (Parent::inNode(key)) { + return _in_map[key]; + } else { + return _out_map[key]; + } + } + + /// Returns a reference to the value associated with the given key. Value& operator[](const Key& key) { if (Parent::inNode(key)) { return _in_map[key]; @@ -3186,20 +3458,7 @@ } } - /// \brief The const subscript operator. - /// - /// The const subscript operator. - Value operator[](const Key& key) const { - if (Parent::inNode(key)) { - return _in_map[key]; - } else { - return _out_map[key]; - } - } - - /// \brief The setter function of the map. - /// - /// The setter function of the map. + /// Sets the value associated with the given key. void set(const Key& key, const Value& value) { if (Parent::inNode(key)) { _in_map.set(key, value); @@ -3216,9 +3475,9 @@ }; - /// \brief Just gives back a combined node map + /// \brief Returns a combined node map /// - /// Just gives back a combined node map + /// This function just returns a combined node map. template static CombinedNodeMap combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { @@ -3244,26 +3503,51 @@ const OutNodeMap>(in_map, out_map); } - /// \brief ArcMap combined from an original ArcMap and a NodeMap + /// \brief Arc map combined from an arc map and a node map of the + /// original digraph. /// - /// This class adapt an original ArcMap and a NodeMap to get an - /// arc map on the adapted digraph - template + /// This map adaptor class adapts an arc map and a node map of the + /// original digraph to get an arc map of the split digraph. + /// Its value type is inherited from the original arc map type + /// (\c ArcMap). + template class CombinedArcMap { public: + /// The key type of the map typedef Arc Key; - typedef typename DigraphArcMap::Value Value; - - /// \brief Constructor - /// - /// Constructor. - CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) + /// The value type of the map + typedef typename ArcMap::Value Value; + + typedef typename MapTraits::ReferenceMapTag ReferenceMapTag; + typedef typename MapTraits::ReturnValue ReturnValue; + typedef typename MapTraits::ConstReturnValue ConstReturnValue; + typedef typename MapTraits::ReturnValue Reference; + typedef typename MapTraits::ConstReturnValue ConstReference; + + /// Constructor + CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) : _arc_map(arc_map), _node_map(node_map) {} - /// \brief The subscript operator. - /// - /// The subscript operator. + /// Returns the value associated with the given key. + Value operator[](const Key& arc) const { + if (Parent::origArc(arc)) { + return _arc_map[arc]; + } else { + return _node_map[arc]; + } + } + + /// Returns a reference to the value associated with the given key. + Value& operator[](const Key& arc) { + if (Parent::origArc(arc)) { + return _arc_map[arc]; + } else { + return _node_map[arc]; + } + } + + /// Sets the value associated with the given key. void set(const Arc& arc, const Value& val) { if (Parent::origArc(arc)) { _arc_map.set(arc, val); @@ -3272,76 +3556,51 @@ } } - /// \brief The const subscript operator. - /// - /// The const subscript operator. - Value operator[](const Key& arc) const { - if (Parent::origArc(arc)) { - return _arc_map[arc]; - } else { - return _node_map[arc]; - } - } - - /// \brief The const subscript operator. - /// - /// The const subscript operator. - Value& operator[](const Key& arc) { - if (Parent::origArc(arc)) { - return _arc_map[arc]; - } else { - return _node_map[arc]; - } - } - private: - DigraphArcMap& _arc_map; - DigraphNodeMap& _node_map; + ArcMap& _arc_map; + NodeMap& _node_map; }; - /// \brief Just gives back a combined arc map + /// \brief Returns a combined arc map /// - /// Just gives back a combined arc map - template - static CombinedArcMap - combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { - return CombinedArcMap(arc_map, node_map); + /// This function just returns a combined arc map. + template + static CombinedArcMap + combinedArcMap(ArcMap& arc_map, NodeMap& node_map) { + return CombinedArcMap(arc_map, node_map); } - template - static CombinedArcMap - combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { - return CombinedArcMap(arc_map, node_map); + template + static CombinedArcMap + combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) { + return CombinedArcMap(arc_map, node_map); } - template - static CombinedArcMap - combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { - return CombinedArcMap(arc_map, node_map); + template + static CombinedArcMap + combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) { + return CombinedArcMap(arc_map, node_map); } - template - static CombinedArcMap - combinedArcMap(const DigraphArcMap& arc_map, - const DigraphNodeMap& node_map) { - return CombinedArcMap(arc_map, node_map); + template + static CombinedArcMap + combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) { + return CombinedArcMap(arc_map, node_map); } }; - /// \brief Just gives back a node splitter + /// \brief Returns a (read-only) SplitNodes adaptor /// - /// Just gives back a node splitter - template - SplitNodes - splitNodes(const Digraph& digraph) { - return SplitNodes(digraph); + /// This function just returns a (read-only) \ref SplitNodes adaptor. + /// \ingroup graph_adaptors + /// \relates SplitNodes + template + SplitNodes + splitNodes(const GR& digraph) { + return SplitNodes(digraph); } - } //namespace lemon #endif //LEMON_ADAPTORS_H