1.1 --- a/src/lemon/graph_wrapper.h Wed Sep 29 16:31:24 2004 +0000
1.2 +++ b/src/lemon/graph_wrapper.h Wed Sep 29 19:02:26 2004 +0000
1.3 @@ -35,7 +35,7 @@
1.4 // Graph wrappers
1.5
1.6 /// \addtogroup gwrappers
1.7 - /// A main parts of LEMON are the different graph structures,
1.8 + /// The main parts of LEMON are the different graph structures,
1.9 /// generic graph algorithms, graph concepts which couple these, and
1.10 /// graph wrappers. While the previous ones are more or less clear, the
1.11 /// latter notion needs further explanation.
1.12 @@ -99,8 +99,13 @@
1.13 ///\warning Graph wrappers are in even more experimental state than the other
1.14 ///parts of the lib. Use them at you own risk.
1.15 ///
1.16 - ///This is the base type for the Graph Wrappers.
1.17 - ///\todo Some more docs...
1.18 + /// This is the base type for most of LEMON graph wrappers.
1.19 + /// This class implements a trivial graph wrapper i.e. it only wraps the
1.20 + /// functions and types of the graph. The purpose of this class is to
1.21 + /// make easier implementing graph wrappers. E.g. if a wrapper is
1.22 + /// considered which differs from the wrapped graph only in some of its
1.23 + /// functions or types, then it can be derived from GraphWrapper, and only the
1.24 + /// differences should be implemented.
1.25 ///
1.26 ///\author Marton Makai
1.27 template<typename Graph>
1.28 @@ -236,9 +241,23 @@
1.29 ///\warning Graph wrappers are in even more experimental state than the other
1.30 ///parts of the lib. Use them at you own risk.
1.31 ///
1.32 - /// A graph wrapper which reverses the orientation of the edges.
1.33 - /// Thus \c Graph have to be a directed graph type.
1.34 - ///
1.35 + /// Let \f$G=(V, A)\f$ be a directed graph and
1.36 + /// suppose that a graph instange \c g of type
1.37 + /// \c ListGraph implements \f$G\f$.
1.38 + /// \code
1.39 + /// ListGraph g;
1.40 + /// \endcode
1.41 + /// For each directed edge
1.42 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1.43 + /// reversing its orientation.
1.44 + /// Then RevGraphWrapper implements the graph structure with node-set
1.45 + /// \f$V\f$ and edge-set
1.46 + /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
1.47 + /// reversing the orientation of its edges. The following code shows how
1.48 + /// such an instance can be constructed.
1.49 + /// \code
1.50 + /// RevGraphWrapper<ListGraph> gw(g);
1.51 + /// \endcode
1.52 ///\author Marton Makai
1.53 template<typename Graph>
1.54 class RevGraphWrapper : public GraphWrapper<Graph> {
1.55 @@ -314,12 +333,40 @@
1.56 ///parts of the lib. Use them at you own risk.
1.57 ///
1.58 /// This wrapper shows a graph with filtered node-set and
1.59 - /// edge-set. Given a bool-valued map on the node-set and one on
1.60 - /// the edge-set of the graphs, the iterators show only the objects
1.61 - /// having true value.
1.62 - /// The quick brown fox iterators jump over
1.63 - /// the lazy dog nodes or edges if their values for are false in the
1.64 - /// corresponding bool maps.
1.65 + /// edge-set.
1.66 + /// Given a bool-valued map on the node-set and one on
1.67 + /// the edge-set of the graph, the iterators show only the objects
1.68 + /// having true value. We have to note that this does not mean that an
1.69 + /// induced subgraph is obtained, the node-iterator cares only the filter
1.70 + /// on the node-set, and the edge-iterators care only the filter on the
1.71 + /// edge-set.
1.72 + /// \code
1.73 + /// typedef SmartGraph Graph;
1.74 + /// Graph g;
1.75 + /// typedef Graph::Node Node;
1.76 + /// typedef Graph::Edge Edge;
1.77 + /// Node u=g.addNode(); //node of id 0
1.78 + /// Node v=g.addNode(); //node of id 1
1.79 + /// Node e=g.addEdge(u, v); //edge of id 0
1.80 + /// Node f=g.addEdge(v, u); //edge of id 1
1.81 + /// Graph::NodeMap<bool> nm(g, true);
1.82 + /// nm.set(u, false);
1.83 + /// Graph::EdgeMap<bool> em(g, true);
1.84 + /// em.set(e, false);
1.85 + /// typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
1.86 + /// SubGW gw(g, nm, em);
1.87 + /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
1.88 + /// std::cout << ":-)" << std::endl;
1.89 + /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
1.90 + /// \endcode
1.91 + /// The output of the above code is the following.
1.92 + /// \code
1.93 + /// 1
1.94 + /// :-)
1.95 + /// 1
1.96 + /// \endcode
1.97 + /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
1.98 + /// \c Graph::Node that is why \c g.id(n) can be applied.
1.99 ///
1.100 ///\author Marton Makai
1.101 template<typename Graph, typename NodeFilterMap,
1.102 @@ -611,16 +658,22 @@
1.103 ///\warning Graph wrappers are in even more experimental state than the other
1.104 ///parts of the lib. Use them at you own risk.
1.105 ///
1.106 - /// Suppose that for a directed graph $G=(V, A)$,
1.107 - /// two bool valued maps on the edge-set,
1.108 - /// $forward_filter$, and $backward_filter$
1.109 - /// is given, and we are dealing with the directed graph
1.110 - /// 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}\})$.
1.111 + /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
1.112 + /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
1.113 + /// reversing its orientation. We are given moreover two bool valued
1.114 + /// maps on the edge-set,
1.115 + /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
1.116 + /// SubBidirGraphWrapper implements the graph structure with node-set
1.117 + /// \f$V\f$ and edge-set
1.118 + /// \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$.
1.119 /// The purpose of writing + instead of union is because parallel
1.120 - /// edges can arose.
1.121 + /// edges can arise. (Similarly, antiparallel edges also can arise).
1.122 /// In other words, a subgraph of the bidirected graph obtained, which
1.123 /// is given by orienting the edges of the original graph in both directions.
1.124 - /// An example for such a construction is the \c RevGraphWrapper where the
1.125 + /// As the oppositely directed edges are logically different,
1.126 + /// the maps are able to attach different values for them.
1.127 + ///
1.128 + /// An example for such a construction is \c RevGraphWrapper where the
1.129 /// forward_filter is everywhere false and the backward_filter is
1.130 /// everywhere true. We note that for sake of efficiency,
1.131 /// \c RevGraphWrapper is implemented in a different way.
1.132 @@ -632,9 +685,7 @@
1.133 /// flow and circulation problems.
1.134 /// As wrappers usually, the SubBidirGraphWrapper implements the
1.135 /// above mentioned graph structure without its physical storage,
1.136 - /// that is the whole stuff eats constant memory.
1.137 - /// As the oppositely directed edges are logically different,
1.138 - /// the maps are able to attach different values for them.
1.139 + /// that is the whole stuff is stored in constant memory.
1.140 template<typename Graph,
1.141 typename ForwardFilterMap, typename BackwardFilterMap>
1.142 class SubBidirGraphWrapper : public GraphWrapper<Graph> {