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

equal deleted inserted replaced

-:455e234b7e4d
+:1688aff13989
 namespace lemon {
 // Graph wrappers
 /// \addtogroup gwrappers
-/// A main parts of LEMON are the different graph structures,
+/// The main parts of LEMON are the different graph structures,
 /// generic graph algorithms, graph concepts which couple these, and
 /// graph wrappers. While the previous ones are more or less clear, the
 /// latter notion needs further explanation.
 /// Graph wrappers are graph classes which serve for considering graph
 /// structures in different ways. A short example makes the notion much
 ///Base type for the Graph Wrappers
 ///\warning Graph wrappers 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 the Graph Wrappers.
+/// This is the base type for most of LEMON graph wrappers.
-///\todo Some more docs...
+/// This class implements a trivial graph wrapper 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
+/// 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
+/// differences should be implemented.
 ///
 ///\author Marton Makai
 template<typename Graph>
 class GraphWrapper {
 protected:
 /// A graph wrapper which reverses the orientation of the edges.
 ///\warning Graph wrappers are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
-/// A graph wrapper which reverses the orientation of the edges.
+/// Let \f$G=(V, A)\f$ be a directed graph and
-/// Thus \c Graph have to be a directed graph type.
+/// suppose that a graph instange \c g of type
-///
+/// \c ListGraph implements \f$G\f$.
+/// \code
+/// 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
+/// \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);
+/// \endcode
 ///\author Marton Makai
 template<typename Graph>
 class RevGraphWrapper : public GraphWrapper<Graph> {
 public:
 typedef GraphWrapper<Graph> Parent;
 ///\warning Graph wrappers are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
 /// This wrapper shows a graph with filtered node-set and
-/// edge-set. Given a bool-valued map on the node-set and one on
+/// edge-set.
-/// the edge-set of the graphs, the iterators show only the objects
+/// Given a bool-valued map on the node-set and one on
-/// having true value.
+/// the edge-set of the graph, the iterators show only the objects
-/// The quick brown fox iterators jump over
+/// having true value. We have to note that this does not mean that an
-/// the lazy dog nodes or edges if their values for are false in the
+/// induced subgraph is obtained, the node-iterator cares only the filter
-/// corresponding bool maps.
+/// on the node-set, and the edge-iterators care only the filter on the
+/// edge-set.
+/// \code
+/// typedef SmartGraph Graph;
+/// Graph g;
+/// typedef Graph::Node Node;
+/// typedef Graph::Edge Edge;
+/// Node u=g.addNode(); //node of id 0
+/// Node v=g.addNode(); //node of id 1
+/// Node e=g.addEdge(u, v); //edge of id 0
+/// 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;
+/// 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
+/// The output of the above code is the following.
+/// \code
+/// 1
+/// :-)
+/// 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.
 ///
 ///\author Marton Makai
 template<typename Graph, typename NodeFilterMap,
 	   typename EdgeFilterMap>
 class SubGraphWrapper : public GraphWrapper<Graph> {
 /// bidirected graph made from a directed one.
 ///
 ///\warning Graph wrappers are in even more experimental state than the other
 ///parts of the lib. Use them at you own risk.
 ///
-/// Suppose that for a directed graph $G=(V, A)$,
+/// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
-/// two bool valued maps on the edge-set,
+/// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
-/// $forward_filter$, and $backward_filter$
+/// reversing its orientation. We are given moreover two bool valued
-/// is given, and we are dealing with the directed graph
+/// maps on the edge-set,
-/// a $G'=(V, \{uv : uv\in A \mbox{ and } forward_filter(uv) \mbox{ is true}\}+\{vu : uv\in A \mbox{ and } backward_filter(uv) \mbox{ is true}\})$.
+/// \f$forward\_filter\f$, and \f$backward\_filter\f$.
+/// SubBidirGraphWrapper 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 arose.
+/// 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.
-/// An example for such a construction is the \c RevGraphWrapper where the
+/// 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
 /// 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.
 /// But BidirGraphWrapper is obtained from
 /// SubBidirGraphWrapper by considering everywhere true
 /// Finally, one of the most important applications of SubBidirGraphWrapper
 /// is ResGraphWrapper, which stands for the residual graph in directed
 /// flow and circulation problems.
 /// As wrappers usually, the SubBidirGraphWrapper implements the
 /// above mentioned graph structure without its physical storage,
-/// that is the whole stuff eats constant memory.
+/// that is the whole stuff is stored in constant memory.
-/// As the oppositely directed edges are logically different,
-/// the maps are able to attach different values for them.
 template<typename Graph,
 	   typename ForwardFilterMap, typename BackwardFilterMap>
 class SubBidirGraphWrapper : public GraphWrapper<Graph> {
 public:
 typedef GraphWrapper<Graph> Parent;

changeset 924	ccb657556d84
parent 921	818510fa3d99
child 930	e89f3bd26fd4