# Changeset 923:acbef5dd0e65 in lemon-0.x for src/lemon/graph_wrapper.h

Ignore:
Timestamp:
09/29/04 21:02:26 (19 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1234
Message:

more docs

File:
1 edited

### Legend:

Unmodified
 r921 /// \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 ///parts of the lib. Use them at you own risk. /// ///This is the base type for the Graph Wrappers. ///\todo Some more docs... /// This is the base type for most of LEMON graph wrappers. /// 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 ///parts of the lib. Use them at you own risk. /// /// A graph wrapper which reverses the orientation of the edges. /// Thus \c Graph have to be a directed graph type. /// /// 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$. /// \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 gw(g); /// \endcode ///\author Marton Makai template /// /// This wrapper shows a graph with filtered node-set and /// edge-set. Given a bool-valued map on the node-set and one on /// the edge-set of the graphs, the iterators show only the objects /// having true value. /// The quick brown fox iterators jump over /// the lazy dog nodes or edges if their values for are false in the /// corresponding bool maps. /// edge-set. /// Given a bool-valued map on the node-set and one on /// the edge-set of the graph, the iterators show only the objects /// having 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 /// 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 nm(g, true); /// nm.set(u, false); /// Graph::EdgeMap em(g, true); /// em.set(e, false); /// typedef SubGraphWrapper, Graph::EdgeMap > 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 ///parts of the lib. Use them at you own risk. /// /// Suppose that for a directed graph $G=(V, A)$, /// two bool valued maps on the edge-set, /// $forward_filter$, and $backward_filter$ /// is given, and we are dealing with the directed graph /// 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}\})$. /// 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 /// \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, /// As wrappers usually, the SubBidirGraphWrapper implements the /// above mentioned graph structure without its physical storage, /// that is the whole stuff eats constant memory. /// As the oppositely directed edges are logically different, /// the maps are able to attach different values for them. /// that is the whole stuff is stored in constant memory. template