more docs
authormarci
Wed, 29 Sep 2004 19:02:26 +0000
changeset 923acbef5dd0e65
parent 922 e816fac59f6d
child 924 ccb657556d84
more docs
src/lemon/graph_wrapper.h
     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> {