lemon-0.x: comparison src/lemon/graph

equal deleted inserted replaced

-:7826d4e0f002
+:43cedfab4b92
 /* -*- C++ -*-
-* src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
+* src/lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */
-#ifndef LEMON_GRAPH_WRAPPER_H
+#ifndef LEMON_GRAPH_ADAPTOR_H
-#define LEMON_GRAPH_WRAPPER_H
+#define LEMON_GRAPH_ADAPTOR_H
-///\ingroup gwrappers
+///\ingroup graph_adaptors
 ///\file
-///\brief Several graph wrappers.
+///\brief Several graph adaptors.
 ///
-///This file contains several useful graph wrapper functions.
+///This file contains several useful graph adaptor functions.
 ///
 ///\author Marton Makai
 #include <lemon/invalid.h>
 #include <lemon/maps.h>
 #include <lemon/bits/undir_graph_extender.h>
 #include <iostream>
 namespace lemon {
-// Graph wrappers
+// Graph adaptors
 /*!
-\addtogroup gwrappers
+\addtogroup graph_adaptors
 @{
 */
 /*!
-Base type for the Graph Wrappers
+Base type for the Graph Adaptors
-\warning Graph wrappers are in even more experimental state than the other
+\warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.
-This is the base type for most of LEMON graph wrappers.
+This is the base type for most of LEMON graph adaptors.
-This class implements a trivial graph wrapper i.e. it only wraps the
+This class implements a trivial graph adaptor i.e. it only wraps the
 functions and types of the graph. The purpose of this class is to
-make easier implementing graph wrappers. E.g. if a wrapper is
+make easier implementing graph adaptors. E.g. if an adaptor is
 considered which differs from the wrapped graph only in some of its
-functions or types, then it can be derived from GraphWrapper, and only the
+functions or types, then it can be derived from GraphAdaptor, and only the
 differences should be implemented.
 \author Marton Makai
 */
 template<typename _Graph>
-class GraphWrapperBase {
+class GraphAdaptorBase {
 public:
 typedef _Graph Graph;
 /// \todo Is it needed?
 typedef Graph BaseGraph;
 typedef Graph ParentGraph;
 protected:
 Graph* graph;
-GraphWrapperBase() : graph(0) { }
+GraphAdaptorBase() : graph(0) { }
 void setGraph(Graph& _graph) { graph=&_graph; }
 public:
-GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
+GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
 typedef typename Graph::Node Node;
 typedef typename Graph::Edge Edge;
 void first(Node& i) const { graph->first(i); }
 template <typename _Value>
 class NodeMap : public _Graph::template NodeMap<_Value> {
 public:
 typedef typename _Graph::template NodeMap<_Value> Parent;
-NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
+NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
-NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
+NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
 : Parent(*gw.graph, value) { }
 };
 template <typename _Value>
 class EdgeMap : public _Graph::template EdgeMap<_Value> {
 public:
 typedef typename _Graph::template EdgeMap<_Value> Parent;
-EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
+EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
-EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
+EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
 : Parent(*gw.graph, value) { }
 };
 };
 template <typename _Graph>
-class GraphWrapper :
+class GraphAdaptor :
-public IterableGraphExtender<GraphWrapperBase<_Graph> > {
+public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
 public:
 typedef _Graph Graph;
-typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
+typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
 protected:
-GraphWrapper() : Parent() { }
+GraphAdaptor() : Parent() { }
 public:
-GraphWrapper(Graph& _graph) { setGraph(_graph); }
+GraphAdaptor(Graph& _graph) { setGraph(_graph); }
 };
 template <typename _Graph>
-class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
+class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
 public:
 typedef _Graph Graph;
-typedef GraphWrapperBase<_Graph> Parent;
+typedef GraphAdaptorBase<_Graph> Parent;
 protected:
-RevGraphWrapperBase() : Parent() { }
+RevGraphAdaptorBase() : Parent() { }
 public:
 typedef typename Parent::Node Node;
 typedef typename Parent::Edge Edge;
 //    using Parent::first;
 Node source(const Edge& e) const { return Parent::target(e); }
 Node target(const Edge& e) const { return Parent::source(e); }
 };
-/// A graph wrapper which reverses the orientation of the edges.
+/// A graph adaptor which reverses the orientation of the edges.
-///\warning Graph wrappers are in even more experimental state than the other
+///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 /// Let \f$G=(V, A)\f$ be a directed graph and
 /// suppose that a graph instange \c g of type
 /// \c ListGraph implements \f$G\f$.
 /// ListGraph g;
 /// \endcode
 /// For each directed edge
 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
 /// reversing its orientation.
-/// Then RevGraphWrapper implements the graph structure with node-set
+/// Then RevGraphAdaptor implements the graph structure with node-set
 /// \f$V\f$ and edge-set
 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
 /// reversing the orientation of its edges. The following code shows how
 /// such an instance can be constructed.
 /// \code
-/// RevGraphWrapper<ListGraph> gw(g);
+/// RevGraphAdaptor<ListGraph> gw(g);
 /// \endcode
 ///\author Marton Makai
 template<typename _Graph>
-class RevGraphWrapper :
+class RevGraphAdaptor :
-public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
+public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
 public:
 typedef _Graph Graph;
 typedef IterableGraphExtender<
-RevGraphWrapperBase<_Graph> > Parent;
+RevGraphAdaptorBase<_Graph> > Parent;
 protected:
-RevGraphWrapper() { }
+RevGraphAdaptor() { }
 public:
-RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
+RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
 };
 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
-class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
+class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
 public:
 typedef _Graph Graph;
-typedef GraphWrapperBase<_Graph> Parent;
+typedef GraphAdaptorBase<_Graph> Parent;
 protected:
 NodeFilterMap* node_filter_map;
 EdgeFilterMap* edge_filter_map;
-SubGraphWrapperBase() : Parent(),
+SubGraphAdaptorBase() : Parent(),
 			    node_filter_map(0), edge_filter_map(0) { }
 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
 node_filter_map=&_node_filter_map;
 }
 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
 edge_filter_map=&_edge_filter_map;
 }
 public:
-//     SubGraphWrapperBase(Graph& _graph,
+//     SubGraphAdaptorBase(Graph& _graph,
 // 			NodeFilterMap& _node_filter_map,
 // 			EdgeFilterMap& _edge_filter_map) :
 //       Parent(&_graph),
 //       node_filter_map(&node_filter_map),
 //       edge_filter_map(&edge_filter_map) { }
 }
 };
-/*! \brief A graph wrapper for hiding nodes and edges from a graph.
+/*! \brief A graph adaptor for hiding nodes and edges from a graph.
-\warning Graph wrappers are in even more experimental state than the other
+\warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.
-SubGraphWrapper shows the graph with filtered node-set and
+SubGraphAdaptor shows the graph with filtered node-set and
 edge-set.
 Let \f$G=(V, A)\f$ be a directed graph
 and suppose that the graph instance \c g of type ListGraph implements
 \f$G\f$.
 Let moreover \f$b_V\f$ and
 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
-SubGraphWrapper<...>::NodeIt iterates
+SubGraphAdaptor<...>::NodeIt iterates
 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
-SubGraphWrapper<...>::EdgeIt iterates
+SubGraphAdaptor<...>::EdgeIt iterates
 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
-SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates
+SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
 only on edges leaving and entering a specific node which have true value.
 We have to note that this does not mean that an
 induced subgraph is obtained, the node-iterator cares only the filter
 on the node-set, and the edge-iterators care only the filter on the
 Node f=g.addEdge(v, u); //edge of id 1
 Graph::NodeMap<bool> nm(g, true);
 nm.set(u, false);
 Graph::EdgeMap<bool> em(g, true);
 em.set(e, false);
-typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
+typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
 SubGW gw(g, nm, em);
 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
 std::cout << ":-)" << std::endl;
 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
 \endcode
 1
 \endcode
 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
 \c Graph::Node that is why \c g.id(n) can be applied.
-For other examples see also the documentation of NodeSubGraphWrapper and
+For other examples see also the documentation of NodeSubGraphAdaptor and
-EdgeSubGraphWrapper.
+EdgeSubGraphAdaptor.
 \author Marton Makai
 */
 template<typename _Graph, typename NodeFilterMap,
 	   typename EdgeFilterMap>
-class SubGraphWrapper :
+class SubGraphAdaptor :
 public IterableGraphExtender<
-SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
+SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
 public:
 typedef _Graph Graph;
 typedef IterableGraphExtender<
-SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
+SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
 protected:
-SubGraphWrapper() { }
+SubGraphAdaptor() { }
 public:
-SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
+SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
 		    EdgeFilterMap& _edge_filter_map) {
 setGraph(_graph);
 setNodeFilterMap(_node_filter_map);
 setEdgeFilterMap(_edge_filter_map);
 }
 };
-/*! \brief A wrapper for hiding nodes from a graph.
+/*! \brief An adaptor for hiding nodes from a graph.
-\warning Graph wrappers are in even more experimental state than the other
+\warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.
-A wrapper for hiding nodes from a graph.
+An adaptor for hiding nodes from a graph.
-This wrapper specializes SubGraphWrapper in the way that only the node-set
+This adaptor specializes SubGraphAdaptor in the way that only the node-set
 can be filtered. Note that this does not mean of considering induced
 subgraph, the edge-iterators consider the original edge-set.
 \author Marton Makai
 */
 template<typename Graph, typename NodeFilterMap>
-class NodeSubGraphWrapper :
+class NodeSubGraphAdaptor :
-public SubGraphWrapper<Graph, NodeFilterMap,
+public SubGraphAdaptor<Graph, NodeFilterMap,
 			   ConstMap<typename Graph::Edge,bool> > {
 public:
-typedef SubGraphWrapper<Graph, NodeFilterMap,
+typedef SubGraphAdaptor<Graph, NodeFilterMap,
 			    ConstMap<typename Graph::Edge,bool> > Parent;
 protected:
 ConstMap<typename Graph::Edge, bool> const_true_map;
 public:
-NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
+NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
 Parent(), const_true_map(true) {
 Parent::setGraph(_graph);
 Parent::setNodeFilterMap(_node_filter_map);
 Parent::setEdgeFilterMap(const_true_map);
 }
 };
-/*! \brief A wrapper for hiding edges from a graph.
+/*! \brief An adaptor for hiding edges from a graph.
-\warning Graph wrappers are in even more experimental state than the other
+\warning Graph adaptors are in even more experimental state than the other
 parts of the lib. Use them at you own risk.
-A wrapper for hiding edges from a graph.
+An adaptor for hiding edges from a graph.
-This wrapper specializes SubGraphWrapper in the way that only the edge-set
+This adaptor specializes SubGraphAdaptor in the way that only the edge-set
-can be filtered. The usefulness of this wrapper is demonstrated in the
+can be filtered. The usefulness of this adaptor is demonstrated in the
 problem of searching a maximum number of edge-disjoint shortest paths
 between
 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
 non-negative edge-lengths. Note that
 the comprehension of the presented solution
 \code
 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
 TightEdgeFilter;
 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
-typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
+typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
 SubGW gw(g, tight_edge_filter);
 \endcode
 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
 with a max flow algorithm Preflow.
 \code
 \endcode
 \author Marton Makai
 */
 template<typename Graph, typename EdgeFilterMap>
-class EdgeSubGraphWrapper :
+class EdgeSubGraphAdaptor :
-public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
+public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
 			   EdgeFilterMap> {
 public:
-typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
+typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
 			    EdgeFilterMap> Parent;
 protected:
 ConstMap<typename Graph::Node, bool> const_true_map;
 public:
-EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
+EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
 Parent(), const_true_map(true) {
 Parent::setGraph(_graph);
 Parent::setNodeFilterMap(const_true_map);
 Parent::setEdgeFilterMap(_edge_filter_map);
 }
 };
 template <typename _Graph>
-class UndirGraphWrapperBase :
+class UndirGraphAdaptorBase :
-public UndirGraphExtender<GraphWrapperBase<_Graph> > {
+public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
 public:
 typedef _Graph Graph;
-typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
+typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
 protected:
-UndirGraphWrapperBase() : Parent() { }
+UndirGraphAdaptorBase() : Parent() { }
 public:
 typedef typename Parent::UndirEdge UndirEdge;
 typedef typename Parent::Edge Edge;
 /// \bug Why cant an edge say that it is forward or not???
 /// By this, a pointer to the graph have to be stored
 /// The implementation
 template <typename T>
 class EdgeMap {
 protected:
-const UndirGraphWrapperBase<_Graph>* g;
+const UndirGraphAdaptorBase<_Graph>* g;
 template <typename TT> friend class EdgeMap;
 typename _Graph::template EdgeMap<T> forward_map, backward_map;
 public:
 typedef T Value;
 typedef Edge Key;
-EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
+EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
-EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g),
+EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
 void set(Edge e, T a) {
 	if (g->forward(e))
 	  forward_map.set(e, a);
 typename _Graph::template EdgeMap<T> map;
 public:
 typedef T Value;
 typedef UndirEdge Key;
-UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) :
+UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
 	map(*(g.graph)) { }
-UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) :
+UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
 	map(*(g.graph), a) { }
 void set(UndirEdge e, T a) {
 	map.set(e, a);
 }
 }
 };
 };
-/// \brief An undirected graph is made from a directed graph by a wrapper
+/// \brief An undirected graph is made from a directed graph by an adaptor
 ///
 /// Undocumented, untested!!!
 /// If somebody knows nice demo application, let's polulate it.
 ///
 /// \author Marton Makai
 template<typename _Graph>
-class UndirGraphWrapper :
+class UndirGraphAdaptor :
 public IterableUndirGraphExtender<
-UndirGraphWrapperBase<_Graph> > {
+UndirGraphAdaptorBase<_Graph> > {
 public:
 typedef _Graph Graph;
 typedef IterableUndirGraphExtender<
-UndirGraphWrapperBase<_Graph> > Parent;
+UndirGraphAdaptorBase<_Graph> > Parent;
 protected:
-UndirGraphWrapper() { }
+UndirGraphAdaptor() { }
 public:
-UndirGraphWrapper(_Graph& _graph) {
+UndirGraphAdaptor(_Graph& _graph) {
 setGraph(_graph);
 }
 };
 template <typename _Graph,
 	    typename ForwardFilterMap, typename BackwardFilterMap>
-class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
+class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
 public:
 typedef _Graph Graph;
-typedef GraphWrapperBase<_Graph> Parent;
+typedef GraphAdaptorBase<_Graph> Parent;
 protected:
 ForwardFilterMap* forward_filter;
 BackwardFilterMap* backward_filter;
-SubBidirGraphWrapperBase() : Parent(),
+SubBidirGraphAdaptorBase() : Parent(),
 				 forward_filter(0), backward_filter(0) { }
 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
 forward_filter=&_forward_filter;
 }
 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
 backward_filter=&_backward_filter;
 }
 public:
-//     SubGraphWrapperBase(Graph& _graph,
+//     SubGraphAdaptorBase(Graph& _graph,
 // 			NodeFilterMap& _node_filter_map,
 // 			EdgeFilterMap& _edge_filter_map) :
 //       Parent(&_graph),
 //       node_filter_map(&node_filter_map),
 //       edge_filter_map(&edge_filter_map) { }
 typedef typename Parent::Node Node;
 typedef typename _Graph::Edge GraphEdge;
 template <typename T> class EdgeMap;
-/// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
+/// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
 /// _Graph::Edge. It contains an extra bool flag which is true
 /// if and only if the
 /// edge is the backward version of the original edge.
 class Edge : public _Graph::Edge {
-friend class SubBidirGraphWrapperBase<
+friend class SubBidirGraphAdaptorBase<
 	Graph, ForwardFilterMap, BackwardFilterMap>;
 template<typename T> friend class EdgeMap;
 protected:
 bool backward; //true, iff backward
 public:
 bool forward(const Edge& e) const { return !e.backward; }
 bool backward(const Edge& e) const { return e.backward; }
 template <typename T>
-/// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
+/// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
 /// _Graph::EdgeMap one for the forward edges and
 /// one for the backward edges.
 class EdgeMap {
 template <typename TT> friend class EdgeMap;
 typename _Graph::template EdgeMap<T> forward_map, backward_map;
 public:
 typedef T Value;
 typedef Edge Key;
-EdgeMap(const SubBidirGraphWrapperBase<_Graph,
+EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
 	      ForwardFilterMap, BackwardFilterMap>& g) :
 	forward_map(*(g.graph)), backward_map(*(g.graph)) { }
-EdgeMap(const SubBidirGraphWrapperBase<_Graph,
+EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
 	      ForwardFilterMap, BackwardFilterMap>& g, T a) :
 	forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
 void set(Edge e, T a) {
 	if (!e.backward)
 };
 };
-///\brief A wrapper for composing a subgraph of a
+///\brief An adaptor for composing a subgraph of a
 /// bidirected graph made from a directed one.
 ///
-/// A wrapper for composing a subgraph of a
+/// An adaptor for composing a subgraph of a
 /// bidirected graph made from a directed one.
 ///
-///\warning Graph wrappers are in even more experimental state than the other
+///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
 /// reversing its orientation. We are given moreover two bool valued
 /// maps on the edge-set,
 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
-/// SubBidirGraphWrapper implements the graph structure with node-set
+/// SubBidirGraphAdaptor implements the graph structure with node-set
 /// \f$V\f$ and edge-set
 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
 /// The purpose of writing + instead of union is because parallel
 /// edges can arise. (Similarly, antiparallel edges also can arise).
 /// In other words, a subgraph of the bidirected graph obtained, which
 /// is given by orienting the edges of the original graph in both directions.
 /// As the oppositely directed edges are logically different,
 /// the maps are able to attach different values for them.
 ///
-/// An example for such a construction is \c RevGraphWrapper where the
+/// An example for such a construction is \c RevGraphAdaptor where the
 /// forward_filter is everywhere false and the backward_filter is
 /// everywhere true. We note that for sake of efficiency,
-/// \c RevGraphWrapper is implemented in a different way.
+/// \c RevGraphAdaptor is implemented in a different way.
-/// But BidirGraphWrapper is obtained from
+/// But BidirGraphAdaptor is obtained from
-/// SubBidirGraphWrapper by considering everywhere true
+/// SubBidirGraphAdaptor by considering everywhere true
 /// valued maps both for forward_filter and backward_filter.
 ///
-/// The most important application of SubBidirGraphWrapper
+/// The most important application of SubBidirGraphAdaptor
-/// is ResGraphWrapper, which stands for the residual graph in directed
+/// is ResGraphAdaptor, which stands for the residual graph in directed
 /// flow and circulation problems.
-/// As wrappers usually, the SubBidirGraphWrapper implements the
+/// As adaptors usually, the SubBidirGraphAdaptor implements the
 /// above mentioned graph structure without its physical storage,
 /// that is the whole stuff is stored in constant memory.
 template<typename _Graph,
 	   typename ForwardFilterMap, typename BackwardFilterMap>
-class SubBidirGraphWrapper :
+class SubBidirGraphAdaptor :
 public IterableGraphExtender<
-SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
+SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
 public:
 typedef _Graph Graph;
 typedef IterableGraphExtender<
-SubBidirGraphWrapperBase<
+SubBidirGraphAdaptorBase<
 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
 protected:
-SubBidirGraphWrapper() { }
+SubBidirGraphAdaptor() { }
 public:
-SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
+SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
 			 BackwardFilterMap& _backward_filter) {
 setGraph(_graph);
 setForwardFilterMap(_forward_filter);
 setBackwardFilterMap(_backward_filter);
 }
 };
-///\brief A wrapper for composing bidirected graph from a directed one.
+///\brief An adaptor for composing bidirected graph from a directed one.
 ///
-///\warning Graph wrappers are in even more experimental state than the other
+///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
-/// A wrapper for composing bidirected graph from a directed one.
+/// An adaptor for composing bidirected graph from a directed one.
 /// A bidirected graph is composed over the directed one without physical
 /// storage. As the oppositely directed edges are logically different ones
 /// the maps are able to attach different values for them.
 template<typename Graph>
-class BidirGraphWrapper :
+class BidirGraphAdaptor :
-public SubBidirGraphWrapper<
+public SubBidirGraphAdaptor<
 Graph,
 ConstMap<typename Graph::Edge, bool>,
 ConstMap<typename Graph::Edge, bool> > {
 public:
-typedef  SubBidirGraphWrapper<
+typedef  SubBidirGraphAdaptor<
 Graph,
 ConstMap<typename Graph::Edge, bool>,
 ConstMap<typename Graph::Edge, bool> > Parent;
 protected:
 ConstMap<typename Graph::Edge, bool> cm;
-BidirGraphWrapper() : Parent(), cm(true) {
+BidirGraphAdaptor() : Parent(), cm(true) {
 Parent::setForwardFilterMap(cm);
 Parent::setBackwardFilterMap(cm);
 }
 public:
-BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
+BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
 Parent::setGraph(_graph);
 Parent::setForwardFilterMap(cm);
 Parent::setBackwardFilterMap(cm);
 }
 int edgeNum() const {
 return 2*this->graph->edgeNum();
 }
-//    KEEP_MAPS(Parent, BidirGraphWrapper);
+//    KEEP_MAPS(Parent, BidirGraphAdaptor);
 };
 template<typename Graph, typename Number,
 	   typename CapacityMap, typename FlowMap>
 return (Number(0) < Number((*flow)[e]));
 }
 };
-/*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
+/*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
-A wrapper for composing the residual graph 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 edge-set.
-In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
+In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
 and \f$c\f$ for a capacity function.
 Suppose that a graph instange \c g of type
 \c ListGraph implements \f$G\f$.
 \code
 ListGraph g;
 \endcode
-Then RevGraphWrapper implements the graph structure with node-set
+Then RevGraphAdaptor implements the graph structure with node-set
 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
 \f$A_{backward}=\{vu : 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$,
 multilicities are counted, i.e. if an edge is in both
-\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
+\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
 appears twice.
 The following code shows how
 such an instance can be constructed.
 \code
 typedef ListGraph Graph;
 Graph::EdgeMap<int> f(g);
 Graph::EdgeMap<int> c(g);
-ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
+ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
 \endcode
 \author Marton Makai
 */
 template<typename Graph, typename Number,
 	   typename CapacityMap, typename FlowMap>
-class ResGraphWrapper :
+class ResGraphAdaptor :
-public SubBidirGraphWrapper<
+public SubBidirGraphAdaptor<
 Graph,
 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
 public:
-typedef SubBidirGraphWrapper<
+typedef SubBidirGraphAdaptor<
 Graph,
 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
 protected:
 const CapacityMap* capacity;
 FlowMap* flow;
 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
-ResGraphWrapper() : Parent(),
+ResGraphAdaptor() : Parent(),
 			capacity(0), flow(0) { }
 void setCapacityMap(const CapacityMap& _capacity) {
 capacity=&_capacity;
 forward_filter.setCapacity(_capacity);
 backward_filter.setCapacity(_capacity);
 flow=&_flow;
 forward_filter.setFlow(_flow);
 backward_filter.setFlow(_flow);
 }
 public:
-ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
+ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
 		       FlowMap& _flow) :
 Parent(), capacity(&_capacity), flow(&_flow),
 forward_filter(/*_graph,*/ _capacity, _flow),
 backward_filter(/*_graph,*/ _capacity, _flow) {
 Parent::setGraph(_graph);
 ///
 /// In generic residual graphs the residual capacity can be obtained
 /// as a map.
 class ResCap {
 protected:
-const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
+const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
 public:
 typedef Number Value;
 typedef Edge Key;
-ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
+ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
 	     _res_graph) : res_graph(&_res_graph) { }
 Number operator[](const Edge& e) const {
 	if (res_graph->forward(e))
 	  return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
 	else
 	  return (*(res_graph->flow))[e];
 }
 };
-//    KEEP_MAPS(Parent, ResGraphWrapper);
+//    KEEP_MAPS(Parent, ResGraphAdaptor);
 };
 template <typename _Graph, typename FirstOutEdgesMap>
-class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
+class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
 public:
 typedef _Graph Graph;
-typedef GraphWrapperBase<_Graph> Parent;
+typedef GraphAdaptorBase<_Graph> Parent;
 protected:
 FirstOutEdgesMap* first_out_edges;
-ErasingFirstGraphWrapperBase() : Parent(),
+ErasingFirstGraphAdaptorBase() : Parent(),
 				     first_out_edges(0) { }
 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
 first_out_edges=&_first_out_edges;
 }
 };
 /// For blocking flows.
-///\warning Graph wrappers are in even more experimental state than the other
+///\warning Graph adaptors are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
-/// This graph wrapper is used for on-the-fly
+/// This graph adaptor is used for on-the-fly
 /// Dinits blocking flow computations.
 /// For each node, an out-edge is stored which is used when the
 /// \code
 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
 /// \endcode
 /// is called.
 ///
 /// \author Marton Makai
 template <typename _Graph, typename FirstOutEdgesMap>
-class ErasingFirstGraphWrapper :
+class ErasingFirstGraphAdaptor :
 public IterableGraphExtender<
-ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
+ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
 public:
 typedef _Graph Graph;
 typedef IterableGraphExtender<
-ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
+ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
-ErasingFirstGraphWrapper(Graph& _graph,
+ErasingFirstGraphAdaptor(Graph& _graph,
 			     FirstOutEdgesMap& _first_out_edges) {
 setGraph(_graph);
 setFirstOutEdgesMap(_first_out_edges);
 }
 ///@}
 } //namespace lemon
-#endif //LEMON_GRAPH_WRAPPER_H
+#endif //LEMON_GRAPH_ADAPTOR_H

changeset 1410	dcfad73b3965
parent 1383	79b68a337f9f
child 1425	f3717c08e2be