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> {