NodeSubGraphWrapper, test, and ducumentation modifications.
authormarci
Fri, 01 Oct 2004 11:31:03 +0000
changeset 9331b7c88fbb950
parent 932 ade3cdb9b45d
child 934 003736604835
NodeSubGraphWrapper, test, and ducumentation modifications.
src/lemon/graph_wrapper.h
src/test/graph_wrapper_test.cc
     1.1 --- a/src/lemon/graph_wrapper.h	Fri Oct 01 10:08:43 2004 +0000
     1.2 +++ b/src/lemon/graph_wrapper.h	Fri Oct 01 11:31:03 2004 +0000
     1.3 @@ -368,115 +368,9 @@
     1.4    Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
     1.5    \c Graph::Node that is why \c g.id(n) can be applied.
     1.6  
     1.7 -  Consider now a mathematically more invloved problem, where the application 
     1.8 -  of SubGraphWrapper is reasonable sure enough. If a shortest path is to be 
     1.9 -  searched between two nodes \c s and \c t, then this can be done easily by 
    1.10 -  applying the Dijkstra algorithm class. What happens, if a maximum number of 
    1.11 -  edge-disjoint shortest paths is to be computed. It can be proved that an 
    1.12 -  edge can be in a shortest path if and only if it is tight with respect to 
    1.13 -  the potential function computed by Dijkstra. Moreover, any path containing 
    1.14 -  only such edges is a shortest one. Thus we have to compute a maximum number 
    1.15 -  of edge-disjoint path between \c s and \c t in the graph which has edge-set 
    1.16 -  all the tight edges. The computation will be demonstrated on the following 
    1.17 -  graph, which is read from a dimacs file.
    1.18 -  
    1.19 -  \dot
    1.20 -  digraph lemon_dot_example {
    1.21 -  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    1.22 -  n0 [ label="0 (s)" ];
    1.23 -  n1 [ label="1" ];
    1.24 -  n2 [ label="2" ];
    1.25 -  n3 [ label="3" ];
    1.26 -  n4 [ label="4" ];
    1.27 -  n5 [ label="5" ];
    1.28 -  n6 [ label="6 (t)" ];
    1.29 -  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    1.30 -  n5 ->  n6 [ label="9, length:4" ];
    1.31 -  n4 ->  n6 [ label="8, length:2" ];
    1.32 -  n3 ->  n5 [ label="7, length:1" ];
    1.33 -  n2 ->  n5 [ label="6, length:3" ];
    1.34 -  n2 ->  n6 [ label="5, length:5" ];
    1.35 -  n2 ->  n4 [ label="4, length:2" ];
    1.36 -  n1 ->  n4 [ label="3, length:3" ];
    1.37 -  n0 ->  n3 [ label="2, length:1" ];
    1.38 -  n0 ->  n2 [ label="1, length:2" ];
    1.39 -  n0 ->  n1 [ label="0, length:3" ];
    1.40 -  }
    1.41 -  \enddot
    1.42 +  For other examples see also the documentation of NodeSubGraphWrapper and 
    1.43 +  EdgeSubGraphWrapper.
    1.44  
    1.45 -  \code
    1.46 -  Graph g;
    1.47 -  Node s, t;
    1.48 -  LengthMap length(g);
    1.49 -
    1.50 -  readDimacs(std::cin, g, length, s, t);
    1.51 -
    1.52 -  cout << "edges with lengths (of form id, tail--length->head): " << endl;
    1.53 -  for(EdgeIt e(g); e!=INVALID; ++e) 
    1.54 -    cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" 
    1.55 -         << length[e] << "->" << g.id(g.head(e)) << endl;
    1.56 -
    1.57 -  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
    1.58 -  \endcode
    1.59 -  Next, the potential function is computed with Dijkstra.
    1.60 -  \code
    1.61 -  typedef Dijkstra<Graph, LengthMap> Dijkstra;
    1.62 -  Dijkstra dijkstra(g, length);
    1.63 -  dijkstra.run(s);
    1.64 -  \endcode
    1.65 -  Next, we consrtruct a map which filters the edge-set to the tight edges.
    1.66 -  \code
    1.67 -  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
    1.68 -    TightEdgeFilter;
    1.69 -  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
    1.70 -  
    1.71 -  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
    1.72 -  SubGW gw(g, tight_edge_filter);
    1.73 -  \endcode
    1.74 -  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
    1.75 -  with a max flow algorithm Preflow.
    1.76 -  \code
    1.77 -  ConstMap<Edge, int> const_1_map(1);
    1.78 -  Graph::EdgeMap<int> flow(g, 0);
    1.79 -
    1.80 -  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
    1.81 -    preflow(gw, s, t, const_1_map, flow);
    1.82 -  preflow.run();
    1.83 -  \endcode
    1.84 -  Last, the output is:
    1.85 -  \code  
    1.86 -  cout << "maximum number of edge-disjoint shortest path: " 
    1.87 -       << preflow.flowValue() << endl;
    1.88 -  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
    1.89 -       << endl;
    1.90 -  for(EdgeIt e(g); e!=INVALID; ++e) 
    1.91 -    if (flow[e])
    1.92 -      cout << " " << g.id(g.tail(e)) << "--" 
    1.93 -	   << length[e] << "->" << g.id(g.head(e)) << endl;
    1.94 -  \endcode
    1.95 -  The program has the following (expected :-)) output:
    1.96 -  \code
    1.97 -  edges with lengths (of form id, tail--length->head):
    1.98 -   9, 5--4->6
    1.99 -   8, 4--2->6
   1.100 -   7, 3--1->5
   1.101 -   6, 2--3->5
   1.102 -   5, 2--5->6
   1.103 -   4, 2--2->4
   1.104 -   3, 1--3->4
   1.105 -   2, 0--1->3
   1.106 -   1, 0--2->2
   1.107 -   0, 0--3->1
   1.108 -  s: 0 t: 6
   1.109 -  maximum number of edge-disjoint shortest path: 2
   1.110 -  edges of the maximum number of edge-disjoint shortest s-t paths:
   1.111 -   9, 5--4->6
   1.112 -   8, 4--2->6
   1.113 -   7, 3--1->5
   1.114 -   4, 2--2->4
   1.115 -   2, 0--1->3
   1.116 -   1, 0--2->2
   1.117 -  \endcode
   1.118    \author Marton Makai
   1.119    */
   1.120    template<typename Graph, typename NodeFilterMap, 
   1.121 @@ -670,6 +564,36 @@
   1.122    };
   1.123  
   1.124  
   1.125 +  /*! \brief A wrapper for hiding nodes from a graph.
   1.126 +
   1.127 +  \warning Graph wrappers are in even more experimental state than the other
   1.128 +  parts of the lib. Use them at you own risk.
   1.129 +  
   1.130 +  A wrapper for hiding nodes from a graph.
   1.131 +  This wrapper specializes SubGraphWrapper in the way that only the node-set 
   1.132 +  can be filtered. Note that this does not mean of considering induced 
   1.133 +  subgraph, the edge-iterators consider the original edge-set.
   1.134 +  \author Marton Makai
   1.135 +  */
   1.136 +  template<typename Graph, typename NodeFilterMap>
   1.137 +  class NodeSubGraphWrapper : 
   1.138 +    public SubGraphWrapper<Graph, NodeFilterMap, 
   1.139 +			   ConstMap<typename Graph::Edge,bool> > {
   1.140 +  public:
   1.141 +    typedef SubGraphWrapper<Graph, NodeFilterMap, 
   1.142 +			    ConstMap<typename Graph::Edge,bool> > Parent;
   1.143 +  protected:
   1.144 +    ConstMap<typename Graph::Edge, bool> const_true_map;
   1.145 +  public:
   1.146 +    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) : 
   1.147 +      Parent(), const_true_map(true) { 
   1.148 +      Parent::setGraph(_graph);
   1.149 +      Parent::setNodeFilterMap(_node_filter_map);
   1.150 +      Parent::setEdgeFilterMap(const_true_map);
   1.151 +    }
   1.152 +  };
   1.153 +
   1.154 +
   1.155    /*! \brief A wrapper for hiding edges from a graph.
   1.156  
   1.157    \warning Graph wrappers are in even more experimental state than the other
   1.158 @@ -677,7 +601,123 @@
   1.159    
   1.160    A wrapper for hiding edges from a graph.
   1.161    This wrapper specializes SubGraphWrapper in the way that only the edge-set 
   1.162 -  can be filtered.
   1.163 +  can be filtered. The usefulness of this wrapper is demonstrated in the 
   1.164 +  problem of searching a maximum number of edge-disjoint shortest paths 
   1.165 +  between 
   1.166 +  two nodes \c s and \c t. Shortest here means being shortest w.r.t. 
   1.167 +  non-negative edge-lengths. Note that 
   1.168 +  the comprehension of the presented solution 
   1.169 +  need's some knowledge from elementary combinatorial optimization. 
   1.170 +
   1.171 +  If a single shortest path is to be 
   1.172 +  searched between two nodes \c s and \c t, then this can be done easily by 
   1.173 +  applying the Dijkstra algorithm class. What happens, if a maximum number of 
   1.174 +  edge-disjoint shortest paths is to be computed. It can be proved that an 
   1.175 +  edge can be in a shortest path if and only if it is tight with respect to 
   1.176 +  the potential function computed by Dijkstra. Moreover, any path containing 
   1.177 +  only such edges is a shortest one. Thus we have to compute a maximum number 
   1.178 +  of edge-disjoint paths between \c s and \c t in the graph which has edge-set 
   1.179 +  all the tight edges. The computation will be demonstrated on the following 
   1.180 +  graph, which is read from a dimacs file.
   1.181 +  
   1.182 +  \dot
   1.183 +  digraph lemon_dot_example {
   1.184 +  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   1.185 +  n0 [ label="0 (s)" ];
   1.186 +  n1 [ label="1" ];
   1.187 +  n2 [ label="2" ];
   1.188 +  n3 [ label="3" ];
   1.189 +  n4 [ label="4" ];
   1.190 +  n5 [ label="5" ];
   1.191 +  n6 [ label="6 (t)" ];
   1.192 +  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   1.193 +  n5 ->  n6 [ label="9, length:4" ];
   1.194 +  n4 ->  n6 [ label="8, length:2" ];
   1.195 +  n3 ->  n5 [ label="7, length:1" ];
   1.196 +  n2 ->  n5 [ label="6, length:3" ];
   1.197 +  n2 ->  n6 [ label="5, length:5" ];
   1.198 +  n2 ->  n4 [ label="4, length:2" ];
   1.199 +  n1 ->  n4 [ label="3, length:3" ];
   1.200 +  n0 ->  n3 [ label="2, length:1" ];
   1.201 +  n0 ->  n2 [ label="1, length:2" ];
   1.202 +  n0 ->  n1 [ label="0, length:3" ];
   1.203 +  }
   1.204 +  \enddot
   1.205 +
   1.206 +  \code
   1.207 +  Graph g;
   1.208 +  Node s, t;
   1.209 +  LengthMap length(g);
   1.210 +
   1.211 +  readDimacs(std::cin, g, length, s, t);
   1.212 +
   1.213 +  cout << "edges with lengths (of form id, tail--length->head): " << endl;
   1.214 +  for(EdgeIt e(g); e!=INVALID; ++e) 
   1.215 +    cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" 
   1.216 +         << length[e] << "->" << g.id(g.head(e)) << endl;
   1.217 +
   1.218 +  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
   1.219 +  \endcode
   1.220 +  Next, the potential function is computed with Dijkstra.
   1.221 +  \code
   1.222 +  typedef Dijkstra<Graph, LengthMap> Dijkstra;
   1.223 +  Dijkstra dijkstra(g, length);
   1.224 +  dijkstra.run(s);
   1.225 +  \endcode
   1.226 +  Next, we consrtruct a map which filters the edge-set to the tight edges.
   1.227 +  \code
   1.228 +  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
   1.229 +    TightEdgeFilter;
   1.230 +  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
   1.231 +  
   1.232 +  typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
   1.233 +  SubGW gw(g, tight_edge_filter);
   1.234 +  \endcode
   1.235 +  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
   1.236 +  with a max flow algorithm Preflow.
   1.237 +  \code
   1.238 +  ConstMap<Edge, int> const_1_map(1);
   1.239 +  Graph::EdgeMap<int> flow(g, 0);
   1.240 +
   1.241 +  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
   1.242 +    preflow(gw, s, t, const_1_map, flow);
   1.243 +  preflow.run();
   1.244 +  \endcode
   1.245 +  Last, the output is:
   1.246 +  \code  
   1.247 +  cout << "maximum number of edge-disjoint shortest path: " 
   1.248 +       << preflow.flowValue() << endl;
   1.249 +  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
   1.250 +       << endl;
   1.251 +  for(EdgeIt e(g); e!=INVALID; ++e) 
   1.252 +    if (flow[e])
   1.253 +      cout << " " << g.id(g.tail(e)) << "--" 
   1.254 +	   << length[e] << "->" << g.id(g.head(e)) << endl;
   1.255 +  \endcode
   1.256 +  The program has the following (expected :-)) output:
   1.257 +  \code
   1.258 +  edges with lengths (of form id, tail--length->head):
   1.259 +   9, 5--4->6
   1.260 +   8, 4--2->6
   1.261 +   7, 3--1->5
   1.262 +   6, 2--3->5
   1.263 +   5, 2--5->6
   1.264 +   4, 2--2->4
   1.265 +   3, 1--3->4
   1.266 +   2, 0--1->3
   1.267 +   1, 0--2->2
   1.268 +   0, 0--3->1
   1.269 +  s: 0 t: 6
   1.270 +  maximum number of edge-disjoint shortest path: 2
   1.271 +  edges of the maximum number of edge-disjoint shortest s-t paths:
   1.272 +   9, 5--4->6
   1.273 +   8, 4--2->6
   1.274 +   7, 3--1->5
   1.275 +   4, 2--2->4
   1.276 +   2, 0--1->3
   1.277 +   1, 0--2->2
   1.278 +  \endcode
   1.279 +
   1.280    \author Marton Makai
   1.281    */
   1.282    template<typename Graph, typename EdgeFilterMap>
     2.1 --- a/src/test/graph_wrapper_test.cc	Fri Oct 01 10:08:43 2004 +0000
     2.2 +++ b/src/test/graph_wrapper_test.cc	Fri Oct 01 11:31:03 2004 +0000
     2.3 @@ -49,6 +49,14 @@
     2.4  			Graph::EdgeMap<bool> > SubGW;
     2.5  template void checkCompileStaticGraph<SubGW>(SubGW &);
     2.6  
     2.7 +//Compile NodeSubGraphWrapper
     2.8 +typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW;
     2.9 +template void checkCompileStaticGraph<NodeSubGW>(NodeSubGW &);
    2.10 +
    2.11 +//Compile EdgeSubGraphWrapper
    2.12 +typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW;
    2.13 +template void checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &);
    2.14 +
    2.15  //Compile UndirGraphWrapper
    2.16  /// \bug UndirGraphWrapper cannot pass the StaticGraph test
    2.17  //typedef UndirGraphWrapper<Graph> UndirGW;