Changeset 1242:e48c4fe47aaf in lemon-0.x
- Timestamp:
- 03/22/05 17:00:00 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1669
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/graph_wrapper.h
r1198 r1242 42 42 /*! 43 43 Base type for the Graph Wrappers 44 44 45 45 \warning Graph wrappers are in even more experimental state than the other 46 46 parts of the lib. Use them at you own risk. 47 47 48 48 This is the base type for most of LEMON graph wrappers. 49 49 This class implements a trivial graph wrapper i.e. it only wraps the … … 315 315 316 316 /*! \brief A graph wrapper for hiding nodes and edges from a graph. 317 317 318 318 \warning Graph wrappers are in even more experimental state than the other 319 319 parts of the lib. Use them at you own risk. 320 320 321 This wrapper shows agraph with filtered node-set and321 SubGraphWrapper shows the graph with filtered node-set and 322 322 edge-set. 323 Given a bool-valued map on the node-set and one on 324 the edge-set of the graph, the iterators show only the objects 325 having true value. We have to note that this does not mean that an 323 Let \f$G=(V, A)\f$ be a directed graph 324 and suppose that the graph instance \c g of type ListGraph implements 325 \f$G\f$. 326 Let moreover \f$b_V\f$ and 327 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set. 328 SubGraphWrapper<...>::NodeIt iterates 329 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and 330 SubGraphWrapper<...>::EdgeIt iterates 331 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly, 332 SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates 333 only on edges leaving and entering a specific node which have true value. 334 335 We have to note that this does not mean that an 326 336 induced subgraph is obtained, the node-iterator cares only the filter 327 337 on the node-set, and the edge-iterators care only the filter on the 328 edge-set. 338 edge-set. 329 339 \code 330 typedef SmartGraph Graph;340 typedef ListGraph Graph; 331 341 Graph g; 332 342 typedef Graph::Node Node; … … 1020 1030 1021 1031 1022 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1023 1024 ///\warning Graph wrappers are in even more experimental state than the other 1025 ///parts of the lib. Use them at you own risk. 1026 /// 1027 /// A wrapper for composing the residual graph for directed flow and circulation problems. 1032 /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems. 1033 1034 A wrapper for composing the residual graph for directed flow and circulation problems. 1035 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a 1036 number type. Let moreover 1037 \f$f,c:A\to F\f$, be functions on the edge-set. 1038 In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow 1039 and \f$c\f$ for a capacity function. 1040 Suppose that a graph instange \c g of type 1041 \c ListGraph implements \f$G\f$. 1042 \code 1043 ListGraph g; 1044 \endcode 1045 Then RevGraphWrapper implements the graph structure with node-set 1046 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where 1047 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and 1048 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$, 1049 i.e. the so called residual graph. 1050 When we take the union \f$A_{forward}\cup A_{backward}\f$, 1051 multilicities are counted, i.e. if an edge is in both 1052 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it 1053 appears twice. 1054 The following code shows how 1055 such an instance can be constructed. 1056 \code 1057 typedef ListGraph Graph; 1058 Graph::EdgeMap<int> f(g); 1059 Graph::EdgeMap<int> c(g); 1060 ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g); 1061 \endcode 1062 \author Marton Makai 1063 */ 1028 1064 template<typename Graph, typename Number, 1029 1065 typename CapacityMap, typename FlowMap>
Note: See TracChangeset
for help on using the changeset viewer.