1.1 --- a/lemon/graph_adaptor.h Sun Nov 30 18:57:18 2008 +0100
1.2 +++ b/lemon/graph_adaptor.h Sun Nov 30 19:00:30 2008 +0100
1.3 @@ -31,15 +31,6 @@
1.4
1.5 namespace lemon {
1.6
1.7 - /// \brief Base type for the Graph Adaptors
1.8 - ///
1.9 - /// This is the base type for most of LEMON graph adaptors.
1.10 - /// This class implements a trivial graph adaptor i.e. it only wraps the
1.11 - /// functions and types of the graph. The purpose of this class is to
1.12 - /// make easier implementing graph adaptors. E.g. if an adaptor is
1.13 - /// considered which differs from the wrapped graph only in some of its
1.14 - /// functions or types, then it can be derived from GraphAdaptor, and only
1.15 - /// the differences should be implemented.
1.16 template<typename _Graph>
1.17 class GraphAdaptorBase {
1.18 public:
1.19 @@ -195,25 +186,6 @@
1.20
1.21 };
1.22
1.23 - /// \ingroup graph_adaptors
1.24 - ///
1.25 - /// \brief Trivial graph adaptor
1.26 - ///
1.27 - /// This class is an adaptor which does not change the adapted undirected
1.28 - /// graph. It can be used only to test the graph adaptors.
1.29 - template <typename _Graph>
1.30 - class GraphAdaptor
1.31 - : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
1.32 - public:
1.33 - typedef _Graph Graph;
1.34 - typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
1.35 - protected:
1.36 - GraphAdaptor() : Parent() {}
1.37 -
1.38 - public:
1.39 - explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
1.40 - };
1.41 -
1.42 template <typename _Graph, typename NodeFilterMap,
1.43 typename EdgeFilterMap, bool checked = true>
1.44 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1.45 @@ -318,42 +290,13 @@
1.46 || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d);
1.47 }
1.48
1.49 - /// \brief Hide the given node in the graph.
1.50 - ///
1.51 - /// This function hides \c n in the graph, i.e. the iteration
1.52 - /// jumps over it. This is done by simply setting the value of \c n
1.53 - /// to be false in the corresponding node-map.
1.54 void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.55 -
1.56 - /// \brief Hide the given edge in the graph.
1.57 - ///
1.58 - /// This function hides \c e in the graph, i.e. the iteration
1.59 - /// jumps over it. This is done by simply setting the value of \c e
1.60 - /// to be false in the corresponding edge-map.
1.61 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.62
1.63 - /// \brief Unhide the given node in the graph.
1.64 - ///
1.65 - /// The value of \c n is set to be true in the node-map which stores
1.66 - /// hide information. If \c n was hidden previuosly, then it is shown
1.67 - /// again
1.68 - void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.69 -
1.70 - /// \brief Hide the given edge in the graph.
1.71 - ///
1.72 - /// The value of \c e is set to be true in the edge-map which stores
1.73 - /// hide information. If \c e was hidden previuosly, then it is shown
1.74 - /// again
1.75 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.76 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.77
1.78 - /// \brief Returns true if \c n is hidden.
1.79 - ///
1.80 - /// Returns true if \c n is hidden.
1.81 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.82 -
1.83 - /// \brief Returns true if \c e is hidden.
1.84 - ///
1.85 - /// Returns true if \c e is hidden.
1.86 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.87
1.88 typedef False NodeNumTag;
1.89 @@ -543,42 +486,13 @@
1.90 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d);
1.91 }
1.92
1.93 - /// \brief Hide the given node in the graph.
1.94 - ///
1.95 - /// This function hides \c n in the graph, i.e. the iteration
1.96 - /// jumps over it. This is done by simply setting the value of \c n
1.97 - /// to be false in the corresponding node-map.
1.98 void hide(const Node& n) const { _node_filter_map->set(n, false); }
1.99 -
1.100 - /// \brief Hide the given edge in the graph.
1.101 - ///
1.102 - /// This function hides \c e in the graph, i.e. the iteration
1.103 - /// jumps over it. This is done by simply setting the value of \c e
1.104 - /// to be false in the corresponding edge-map.
1.105 void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
1.106
1.107 - /// \brief Unhide the given node in the graph.
1.108 - ///
1.109 - /// The value of \c n is set to be true in the node-map which stores
1.110 - /// hide information. If \c n was hidden previuosly, then it is shown
1.111 - /// again
1.112 - void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.113 -
1.114 - /// \brief Hide the given edge in the graph.
1.115 - ///
1.116 - /// The value of \c e is set to be true in the edge-map which stores
1.117 - /// hide information. If \c e was hidden previuosly, then it is shown
1.118 - /// again
1.119 + void unHide(const Node& n) const { _node_filter_map->set(n, true); }
1.120 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
1.121
1.122 - /// \brief Returns true if \c n is hidden.
1.123 - ///
1.124 - /// Returns true if \c n is hidden.
1.125 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
1.126 -
1.127 - /// \brief Returns true if \c e is hidden.
1.128 - ///
1.129 - /// Returns true if \c e is hidden.
1.130 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
1.131
1.132 typedef False NodeNumTag;
1.133 @@ -682,7 +596,7 @@
1.134
1.135 /// \ingroup graph_adaptors
1.136 ///
1.137 - /// \brief A graph adaptor for hiding nodes and arcs from an
1.138 + /// \brief A graph adaptor for hiding nodes and edges from an
1.139 /// undirected graph.
1.140 ///
1.141 /// SubGraphAdaptor shows the graph with filtered node-set and
1.142 @@ -704,17 +618,69 @@
1.143 typedef _Graph Graph;
1.144 typedef GraphAdaptorExtender<
1.145 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
1.146 +
1.147 + typedef typename Parent::Node Node;
1.148 + typedef typename Parent::Edge Edge;
1.149 +
1.150 protected:
1.151 SubGraphAdaptor() { }
1.152 public:
1.153 +
1.154 + /// \brief Constructor
1.155 + ///
1.156 + /// Creates a sub-graph-adaptor for the given graph with
1.157 + /// given node and edge map filters.
1.158 SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
1.159 EdgeFilterMap& edge_filter_map) {
1.160 setGraph(_graph);
1.161 setNodeFilterMap(node_filter_map);
1.162 setEdgeFilterMap(edge_filter_map);
1.163 }
1.164 +
1.165 + /// \brief Hides the node of the graph
1.166 + ///
1.167 + /// This function hides \c n in the digraph, i.e. the iteration
1.168 + /// jumps over it. This is done by simply setting the value of \c n
1.169 + /// to be false in the corresponding node-map.
1.170 + void hide(const Node& n) const { Parent::hide(n); }
1.171 +
1.172 + /// \brief Hides the edge of the graph
1.173 + ///
1.174 + /// This function hides \c e in the digraph, i.e. the iteration
1.175 + /// jumps over it. This is done by simply setting the value of \c e
1.176 + /// to be false in the corresponding edge-map.
1.177 + void hide(const Edge& e) const { Parent::hide(e); }
1.178 +
1.179 + /// \brief Unhides the node of the graph
1.180 + ///
1.181 + /// The value of \c n is set to be true in the node-map which stores
1.182 + /// hide information. If \c n was hidden previuosly, then it is shown
1.183 + /// again
1.184 + void unHide(const Node& n) const { Parent::unHide(n); }
1.185 +
1.186 + /// \brief Unhides the edge of the graph
1.187 + ///
1.188 + /// The value of \c e is set to be true in the edge-map which stores
1.189 + /// hide information. If \c e was hidden previuosly, then it is shown
1.190 + /// again
1.191 + void unHide(const Edge& e) const { Parent::unHide(e); }
1.192 +
1.193 + /// \brief Returns true if \c n is hidden.
1.194 + ///
1.195 + /// Returns true if \c n is hidden.
1.196 + ///
1.197 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.198 +
1.199 + /// \brief Returns true if \c e is hidden.
1.200 + ///
1.201 + /// Returns true if \c e is hidden.
1.202 + ///
1.203 + bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.204 };
1.205
1.206 + /// \brief Just gives back a sub-graph adaptor
1.207 + ///
1.208 + /// Just gives back a sub-graph adaptor
1.209 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
1.210 SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
1.211 subGraphAdaptor(const Graph& graph,
1.212 @@ -765,6 +731,8 @@
1.213 typedef _NodeFilterMap NodeFilterMap;
1.214 typedef SubGraphAdaptor<Graph, NodeFilterMap,
1.215 ConstMap<typename Graph::Edge, bool> > Parent;
1.216 +
1.217 + typedef typename Parent::Node Node;
1.218 protected:
1.219 ConstMap<typename Graph::Edge, bool> const_true_map;
1.220
1.221 @@ -773,14 +741,43 @@
1.222 }
1.223
1.224 public:
1.225 +
1.226 + /// \brief Constructor
1.227 + ///
1.228 + /// Creates a node-sub-graph-adaptor for the given graph with
1.229 + /// given node map filters.
1.230 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
1.231 Parent(), const_true_map(true) {
1.232 Parent::setGraph(_graph);
1.233 Parent::setNodeFilterMap(node_filter_map);
1.234 Parent::setEdgeFilterMap(const_true_map);
1.235 }
1.236 +
1.237 + /// \brief Hides the node of the graph
1.238 + ///
1.239 + /// This function hides \c n in the digraph, i.e. the iteration
1.240 + /// jumps over it. This is done by simply setting the value of \c n
1.241 + /// to be false in the corresponding node-map.
1.242 + void hide(const Node& n) const { Parent::hide(n); }
1.243 +
1.244 + /// \brief Unhides the node of the graph
1.245 + ///
1.246 + /// The value of \c n is set to be true in the node-map which stores
1.247 + /// hide information. If \c n was hidden previuosly, then it is shown
1.248 + /// again
1.249 + void unHide(const Node& n) const { Parent::unHide(n); }
1.250 +
1.251 + /// \brief Returns true if \c n is hidden.
1.252 + ///
1.253 + /// Returns true if \c n is hidden.
1.254 + ///
1.255 + bool hidden(const Node& n) const { return Parent::hidden(n); }
1.256 +
1.257 };
1.258
1.259 + /// \brief Just gives back a node-sub-graph adaptor
1.260 + ///
1.261 + /// Just gives back a node-sub-graph adaptor
1.262 template<typename Graph, typename NodeFilterMap>
1.263 NodeSubGraphAdaptor<const Graph, NodeFilterMap>
1.264 nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {
1.265 @@ -813,6 +810,7 @@
1.266 typedef _EdgeFilterMap EdgeFilterMap;
1.267 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
1.268 EdgeFilterMap, false> Parent;
1.269 + typedef typename Parent::Edge Edge;
1.270 protected:
1.271 ConstMap<typename Graph::Node, bool> const_true_map;
1.272
1.273 @@ -822,6 +820,10 @@
1.274
1.275 public:
1.276
1.277 + /// \brief Constructor
1.278 + ///
1.279 + /// Creates a edge-sub-graph-adaptor for the given graph with
1.280 + /// given node map filters.
1.281 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
1.282 Parent(), const_true_map(true) {
1.283 Parent::setGraph(_graph);
1.284 @@ -829,8 +831,31 @@
1.285 Parent::setEdgeFilterMap(edge_filter_map);
1.286 }
1.287
1.288 + /// \brief Hides the edge of the graph
1.289 + ///
1.290 + /// This function hides \c e in the digraph, i.e. the iteration
1.291 + /// jumps over it. This is done by simply setting the value of \c e
1.292 + /// to be false in the corresponding edge-map.
1.293 + void hide(const Edge& e) const { Parent::hide(e); }
1.294 +
1.295 + /// \brief Unhides the edge of the graph
1.296 + ///
1.297 + /// The value of \c e is set to be true in the edge-map which stores
1.298 + /// hide information. If \c e was hidden previuosly, then it is shown
1.299 + /// again
1.300 + void unHide(const Edge& e) const { Parent::unHide(e); }
1.301 +
1.302 + /// \brief Returns true if \c e is hidden.
1.303 + ///
1.304 + /// Returns true if \c e is hidden.
1.305 + ///
1.306 + bool hidden(const Edge& e) const { return Parent::hidden(e); }
1.307 +
1.308 };
1.309
1.310 + /// \brief Just gives back an edge-sub-graph adaptor
1.311 + ///
1.312 + /// Just gives back an edge-sub-graph adaptor
1.313 template<typename Graph, typename EdgeFilterMap>
1.314 EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
1.315 edgeSubGraphAdaptor(const Graph& graph, EdgeFilterMap& efm) {
1.316 @@ -843,11 +868,6 @@
1.317 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1.318 }
1.319
1.320 - /// \brief Base of direct graph adaptor
1.321 - ///
1.322 - /// Base class of the direct graph adaptor. All public member
1.323 - /// of this class can be used with the DirGraphAdaptor too.
1.324 - /// \sa DirGraphAdaptor
1.325 template <typename _Graph, typename _DirectionMap>
1.326 class DirGraphAdaptorBase {
1.327 public:
1.328 @@ -1103,6 +1123,7 @@
1.329 typedef _Graph Graph;
1.330 typedef DigraphAdaptorExtender<
1.331 DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
1.332 + typedef typename Parent::Arc Arc;
1.333 protected:
1.334 DirGraphAdaptor() { }
1.335 public:
1.336 @@ -1114,6 +1135,13 @@
1.337 setGraph(graph);
1.338 setDirectionMap(direction);
1.339 }
1.340 +
1.341 + /// \brief Reverse arc
1.342 + ///
1.343 + /// It reverse the given arc. It simply negate the direction in the map.
1.344 + void reverseArc(const Arc& a) {
1.345 + Parent::reverseArc(a);
1.346 + }
1.347 };
1.348
1.349 /// \brief Just gives back a DirGraphAdaptor