documentation os SubGraphWrapper with code example.
authormarci
Thu, 30 Sep 2004 17:30:20 +0000
changeset 930e89f3bd26fd4
parent 929 882790531532
child 931 9227ecd7b0bc
documentation os SubGraphWrapper with code example.
src/lemon/graph_wrapper.h
     1.1 --- a/src/lemon/graph_wrapper.h	Thu Sep 30 16:08:20 2004 +0000
     1.2 +++ b/src/lemon/graph_wrapper.h	Thu Sep 30 17:30:20 2004 +0000
     1.3 @@ -327,48 +327,159 @@
     1.4  
     1.5  
     1.6  
     1.7 -  /// A graph wrapper for hiding nodes and edges from a graph.
     1.8 +  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
     1.9    
    1.10 -  ///\warning Graph wrappers are in even more experimental state than the other
    1.11 -  ///parts of the lib. Use them at you own risk.
    1.12 -  ///
    1.13 -  /// This wrapper shows a graph with filtered node-set and 
    1.14 -  /// edge-set. 
    1.15 -  /// Given a bool-valued map on the node-set and one on 
    1.16 -  /// the edge-set of the graph, the iterators show only the objects 
    1.17 -  /// having true value. We have to note that this does not mean that an 
    1.18 -  /// induced subgraph is obtained, the node-iterator cares only the filter 
    1.19 -  /// on the node-set, and the edge-iterators care only the filter on the 
    1.20 -  /// edge-set.
    1.21 -  /// \code
    1.22 -  /// typedef SmartGraph Graph;
    1.23 -  /// Graph g;
    1.24 -  /// typedef Graph::Node Node;
    1.25 -  /// typedef Graph::Edge Edge;
    1.26 -  /// Node u=g.addNode(); //node of id 0
    1.27 -  /// Node v=g.addNode(); //node of id 1
    1.28 -  /// Node e=g.addEdge(u, v); //edge of id 0
    1.29 -  /// Node f=g.addEdge(v, u); //edge of id 1
    1.30 -  /// Graph::NodeMap<bool> nm(g, true);
    1.31 -  /// nm.set(u, false);
    1.32 -  /// Graph::EdgeMap<bool> em(g, true);
    1.33 -  /// em.set(e, false);
    1.34 -  /// typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    1.35 -  /// SubGW gw(g, nm, em);
    1.36 -  /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    1.37 -  /// std::cout << ":-)" << std::endl;
    1.38 -  /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
    1.39 -  /// \endcode
    1.40 -  /// The output of the above code is the following.
    1.41 -  /// \code
    1.42 -  /// 1
    1.43 -  /// :-)
    1.44 -  /// 1
    1.45 -  /// \endcode
    1.46 -  /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
    1.47 -  /// \c Graph::Node that is why \c g.id(n) can be applied.
    1.48 -  ///
    1.49 -  ///\author Marton Makai
    1.50 +  \warning Graph wrappers are in even more experimental state than the other
    1.51 +  parts of the lib. Use them at you own risk.
    1.52 +  
    1.53 +  This wrapper shows a graph with filtered node-set and 
    1.54 +  edge-set. 
    1.55 +  Given a bool-valued map on the node-set and one on 
    1.56 +  the edge-set of the graph, the iterators show only the objects 
    1.57 +  having true value. We have to note that this does not mean that an 
    1.58 +  induced subgraph is obtained, the node-iterator cares only the filter 
    1.59 +  on the node-set, and the edge-iterators care only the filter on the 
    1.60 +  edge-set.
    1.61 +  \code
    1.62 +  typedef SmartGraph Graph;
    1.63 +  Graph g;
    1.64 +  typedef Graph::Node Node;
    1.65 +  typedef Graph::Edge Edge;
    1.66 +  Node u=g.addNode(); //node of id 0
    1.67 +  Node v=g.addNode(); //node of id 1
    1.68 +  Node e=g.addEdge(u, v); //edge of id 0
    1.69 +  Node f=g.addEdge(v, u); //edge of id 1
    1.70 +  Graph::NodeMap<bool> nm(g, true);
    1.71 +  nm.set(u, false);
    1.72 +  Graph::EdgeMap<bool> em(g, true);
    1.73 +  em.set(e, false);
    1.74 +  typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    1.75 +  SubGW gw(g, nm, em);
    1.76 +  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    1.77 +  std::cout << ":-)" << std::endl;
    1.78 +  for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
    1.79 +  \endcode
    1.80 +  The output of the above code is the following.
    1.81 +  \code
    1.82 +  1
    1.83 +  :-)
    1.84 +  1
    1.85 +  \endcode
    1.86 +  Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
    1.87 +  \c Graph::Node that is why \c g.id(n) can be applied.
    1.88 +
    1.89 +  Consider now a mathematically more invloved problem, where the application 
    1.90 +  of SubGraphWrapper is reasonable sure enough. If a shortest path is to be 
    1.91 +  searched between two nodes \c s and \c t, then this can be done easily by 
    1.92 +  applying the Dijkstra algorithm class. What happens, if a maximum number of 
    1.93 +  edge-disjoint shortest paths is to be computed. It can be proved that an 
    1.94 +  edge can be in a shortest path if and only if it is tight with respect to 
    1.95 +  the potential function computed by Dijkstra. Moreover, any path containing 
    1.96 +  only such edges is a shortest one. Thus we have to compute a maximum number 
    1.97 +  of edge-disjoint path between \c s and \c t in the graph which has edge-set 
    1.98 +  all the tight edges. The computation will be demonstrated on the following 
    1.99 +  graph, which is read from a dimacs file.
   1.100 +  
   1.101 +  \dot
   1.102 +  digraph lemon_dot_example {
   1.103 +  node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   1.104 +  n0 [ label="0 (s)" ];
   1.105 +  n1 [ label="1" ];
   1.106 +  n2 [ label="2" ];
   1.107 +  n3 [ label="3" ];
   1.108 +  n4 [ label="4" ];
   1.109 +  n5 [ label="5" ];
   1.110 +  n6 [ label="6 (t)" ];
   1.111 +  edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
   1.112 +  n5 ->  n6 [ label="9, length:4" ];
   1.113 +  n4 ->  n6 [ label="8, length:2" ];
   1.114 +  n3 ->  n5 [ label="7, length:1" ];
   1.115 +  n2 ->  n5 [ label="6, length:3" ];
   1.116 +  n2 ->  n6 [ label="5, length:5" ];
   1.117 +  n2 ->  n4 [ label="4, length:2" ];
   1.118 +  n1 ->  n4 [ label="3, length:3" ];
   1.119 +  n0 ->  n3 [ label="2, length:1" ];
   1.120 +  n0 ->  n2 [ label="1, length:2" ];
   1.121 +  n0 ->  n1 [ label="0, length:3" ];
   1.122 +  }
   1.123 +  \enddot
   1.124 +
   1.125 +  \code
   1.126 +  Graph g;
   1.127 +  Node s, t;
   1.128 +  LengthMap length(g);
   1.129 +
   1.130 +  readDimacs(std::cin, g, length, s, t);
   1.131 +
   1.132 +  cout << "edges with lengths (of form id, tail--length->head): " << endl;
   1.133 +  for(EdgeIt e(g); e!=INVALID; ++e) 
   1.134 +    cout << g.id(e) << ", " << g.id(g.tail(e)) << "--" 
   1.135 +         << length[e] << "->" << g.id(g.head(e)) << endl;
   1.136 +
   1.137 +  cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
   1.138 +  \endcode
   1.139 +  Next, the potential function is computed with Dijkstra.
   1.140 +  \code
   1.141 +  typedef Dijkstra<Graph, LengthMap> Dijkstra;
   1.142 +  Dijkstra dijkstra(g, length);
   1.143 +  dijkstra.run(s);
   1.144 +  \endcode
   1.145 +  Next, we consrtruct a map which filters the edge-set to the tight edges.
   1.146 +  \code
   1.147 +  typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 
   1.148 +    TightEdgeFilter;
   1.149 +  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
   1.150 +  
   1.151 +  ConstMap<Node, bool> const_true_map(true);
   1.152 +  typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
   1.153 +  SubGW gw(g, const_true_map, tight_edge_filter);
   1.154 +  \endcode
   1.155 +  Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed 
   1.156 +  with a max flow algorithm Preflow.
   1.157 +  \code
   1.158 +  ConstMap<Edge, int> const_1_map(1);
   1.159 +  Graph::EdgeMap<int> flow(g, 0);
   1.160 +
   1.161 +  Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 
   1.162 +    preflow(gw, s, t, const_1_map, flow);
   1.163 +  preflow.run();
   1.164 +  \endcode
   1.165 +  Last, the output is:
   1.166 +  \code  
   1.167 +  cout << "maximum number of edge-disjoint shortest path: " 
   1.168 +       << preflow.flowValue() << endl;
   1.169 +  cout << "edges of the maximum number of edge-disjoint shortest s-t paths: " 
   1.170 +       << endl;
   1.171 +  for(EdgeIt e(g); e!=INVALID; ++e) 
   1.172 +    if (flow[e])
   1.173 +      cout << " " << g.id(g.tail(e)) << "--" 
   1.174 +	   << length[e] << "->" << g.id(g.head(e)) << endl;
   1.175 +  \endcode
   1.176 +  The program has the following (expected :-)) output:
   1.177 +  \code
   1.178 +  edges with lengths (of form id, tail--length->head):
   1.179 +   9, 5--4->6
   1.180 +   8, 4--2->6
   1.181 +   7, 3--1->5
   1.182 +   6, 2--3->5
   1.183 +   5, 2--5->6
   1.184 +   4, 2--2->4
   1.185 +   3, 1--3->4
   1.186 +   2, 0--1->3
   1.187 +   1, 0--2->2
   1.188 +   0, 0--3->1
   1.189 +  s: 0 t: 6
   1.190 +  maximum number of edge-disjoint shortest path: 2
   1.191 +  edges of the maximum number of edge-disjoint shortest s-t paths:
   1.192 +   9, 5--4->6
   1.193 +   8, 4--2->6
   1.194 +   7, 3--1->5
   1.195 +   4, 2--2->4
   1.196 +   2, 0--1->3
   1.197 +   1, 0--2->2
   1.198 +  \endcode
   1.199 +  \author Marton Makai
   1.200 +  */
   1.201    template<typename Graph, typename NodeFilterMap, 
   1.202  	   typename EdgeFilterMap>
   1.203    class SubGraphWrapper : public GraphWrapper<Graph> {