39 @{ |
39 @{ |
40 */ |
40 */ |
41 |
41 |
42 /*! |
42 /*! |
43 Base type for the Graph Wrappers |
43 Base type for the Graph Wrappers |
44 |
44 |
45 \warning Graph wrappers are in even more experimental state than the other |
45 \warning Graph wrappers are in even more experimental state than the other |
46 parts of the lib. Use them at you own risk. |
46 parts of the lib. Use them at you own risk. |
47 |
47 |
48 This is the base type for most of LEMON graph wrappers. |
48 This is the base type for most of LEMON graph wrappers. |
49 This class implements a trivial graph wrapper i.e. it only wraps the |
49 This class implements a trivial graph wrapper i.e. it only wraps the |
50 functions and types of the graph. The purpose of this class is to |
50 functions and types of the graph. The purpose of this class is to |
51 make easier implementing graph wrappers. E.g. if a wrapper is |
51 make easier implementing graph wrappers. E.g. if a wrapper is |
52 considered which differs from the wrapped graph only in some of its |
52 considered which differs from the wrapped graph only in some of its |
312 |
312 |
313 |
313 |
314 }; |
314 }; |
315 |
315 |
316 /*! \brief A graph wrapper for hiding nodes and edges from a graph. |
316 /*! \brief A graph wrapper for hiding nodes and edges from a graph. |
317 |
317 |
318 \warning Graph wrappers are in even more experimental state than the other |
318 \warning Graph wrappers are in even more experimental state than the other |
319 parts of the lib. Use them at you own risk. |
319 parts of the lib. Use them at you own risk. |
320 |
320 |
321 This wrapper shows a graph with filtered node-set and |
321 SubGraphWrapper shows the graph with filtered node-set and |
322 edge-set. |
322 edge-set. |
323 Given a bool-valued map on the node-set and one on |
323 Let \f$G=(V, A)\f$ be a directed graph |
324 the edge-set of the graph, the iterators show only the objects |
324 and suppose that the graph instance \c g of type ListGraph implements |
325 having true value. We have to note that this does not mean that an |
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 induced subgraph is obtained, the node-iterator cares only the filter |
336 induced subgraph is obtained, the node-iterator cares only the filter |
327 on the node-set, and the edge-iterators care only the filter on the |
337 on the node-set, and the edge-iterators care only the filter on the |
328 edge-set. |
338 edge-set. |
329 \code |
339 \code |
330 typedef SmartGraph Graph; |
340 typedef ListGraph Graph; |
331 Graph g; |
341 Graph g; |
332 typedef Graph::Node Node; |
342 typedef Graph::Node Node; |
333 typedef Graph::Edge Edge; |
343 typedef Graph::Edge Edge; |
334 Node u=g.addNode(); //node of id 0 |
344 Node u=g.addNode(); //node of id 0 |
335 Node v=g.addNode(); //node of id 1 |
345 Node v=g.addNode(); //node of id 1 |
1017 return (Number(0) < Number((*flow)[e])); |
1027 return (Number(0) < Number((*flow)[e])); |
1018 } |
1028 } |
1019 }; |
1029 }; |
1020 |
1030 |
1021 |
1031 |
1022 /// 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. |
1023 |
1033 |
1024 ///\warning Graph wrappers are in even more experimental state than the other |
1034 A wrapper for composing the residual graph for directed flow and circulation problems. |
1025 ///parts of the lib. Use them at you own risk. |
1035 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a |
1026 /// |
1036 number type. Let moreover |
1027 /// A wrapper for composing the residual graph for directed flow and circulation problems. |
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 template<typename Graph, typename Number, |
1064 template<typename Graph, typename Number, |
1029 typename CapacityMap, typename FlowMap> |
1065 typename CapacityMap, typename FlowMap> |
1030 class ResGraphWrapper : |
1066 class ResGraphWrapper : |
1031 public SubBidirGraphWrapper< |
1067 public SubBidirGraphWrapper< |
1032 Graph, |
1068 Graph, |