1.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 15 20:50:03 2004 +0000
1.2 +++ b/src/work/marci/graph_wrapper.h Fri Apr 16 08:26:00 2004 +0000
1.3 @@ -6,6 +6,63 @@
1.4
1.5 namespace hugo {
1.6
1.7 + /// Graph wrappers
1.8 +
1.9 + /// The main parts of HUGOlib are the different graph structures,
1.10 + /// generic graph algorithms, graph concepts which couple these, and
1.11 + /// graph wrappers. While the previous ones are more or less clear, the
1.12 + /// latter notion needs further explanation.
1.13 + /// Graph wrappers are graph classes which serve for considering graph
1.14 + /// structures in different ways. A short example makes the notion much more
1.15 + /// clear.
1.16 + /// Suppose that we have an instance \code g \endcode of a directed graph
1.17 + /// type say \code ListGraph \endcode and an algorithm
1.18 + /// \code template<typename Graph> int algorithm(const Graph&); \endcode
1.19 + /// is needed to run on the reversed oriented graph.
1.20 + /// It can be expensive (in time or in memory usage) to copy
1.21 + /// \code g \endcode with the reversed orientation.
1.22 + /// Thus, a wrapper class
1.23 + /// \code template<typename Graph> class RevGraphWrapper; \endcode is used.
1.24 + /// The code looks as follows
1.25 + /// \code
1.26 + /// ListGraph g;
1.27 + /// RevGraphWrapper<ListGraph> rgw(g);
1.28 + /// int result=algorithm(rgw);
1.29 + /// \endcode
1.30 + /// After running the algorithm, the original graph \code g \endcode
1.31 + /// is untouched. Thus the above used graph wrapper is to consider the
1.32 + /// original graph with reversed orientation.
1.33 + /// This techniques gives rise to an elegant code, and
1.34 + /// based on stable graph wrappers, complex algorithms can be
1.35 + /// implemented easily.
1.36 + /// In flow, circulation and bipartite matching problems, the residual
1.37 + /// graph is of particualar significance. Combining a wrapper impleneting
1.38 + /// this, shortest path algorithms and mimimum mean cycle algorithms,
1.39 + /// a range of weighted and cardinality optimization algorithms can be
1.40 + /// obtained. For lack of space, for other examples,
1.41 + /// the interested user is referred to the detailed domumentation of graph
1.42 + /// wrappers.
1.43 + /// The behavior of graph wrappers are very different. Some of them keep
1.44 + /// capabilities of the original graph while in other cases this would be
1.45 + /// meaningless. This means that the concepts that they are model of depend
1.46 + /// on the graph wrapper, and the wrapped graph(s).
1.47 + /// If an edge of \code rgw \endcode is deleted, this is carried out by
1.48 + /// deleting the corresponding edge of \code g \endcode. But for a residual
1.49 + /// graph, this operation has no sense.
1.50 + /// Let we stand one more example here to simplify your work.
1.51 + /// wrapper class
1.52 + /// \code template<typename Graph> class RevGraphWrapper; \endcode
1.53 + /// has constructor
1.54 + /// \code RevGraphWrapper(Graph& _g); \endcode.
1.55 + /// This means that in a situation,
1.56 + /// when a \code const ListGraph& \endcode reference to a graph is given,
1.57 + /// then it have to be instatiated with Graph=const ListGraph.
1.58 + /// \code
1.59 + /// int algorithm1(const ListGraph& g) {
1.60 + /// RevGraphWrapper<const ListGraph> rgw(g);
1.61 + /// return algorithm2(rgw);
1.62 + /// }
1.63 + /// \endcode
1.64 template<typename Graph>
1.65 class GraphWrapper {
1.66 protected:
1.67 @@ -109,11 +166,11 @@
1.68 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
1.69 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
1.70 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.71 - template< typename It > It first() const {
1.72 - It e; this->first(e); return e; }
1.73 +// template< typename It > It first() const {
1.74 +// It e; this->first(e); return e; }
1.75
1.76 - template< typename It > It first(const Node& v) const {
1.77 - It e; this->first(e, v); return e; }
1.78 +// template< typename It > It first(const Node& v) const {
1.79 +// It e; this->first(e, v); return e; }
1.80
1.81 Node head(const Edge& e) const {
1.82 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
1.83 @@ -274,7 +331,12 @@
1.84 { return GraphWrapper<Graph>::head(e); }
1.85 };
1.86
1.87 - //Subgraph on the same node-set and partial edge-set
1.88 + /// Wrapper for hiding nodes and edges from a graph.
1.89 +
1.90 + /// This wrapper shows a graph with filtered node-set and
1.91 + /// edge-set. The quick brown fox iterators jumps over
1.92 + /// the lazy dog nodes or edges if the values for them are false
1.93 + /// in the bool maps.
1.94 template<typename Graph, typename NodeFilterMap,
1.95 typename EdgeFilterMap>
1.96 class SubGraphWrapper : public GraphWrapper<Graph> {
1.97 @@ -483,11 +545,11 @@
1.98 bool hidden(const Node& n) const { return (*node_filter_map)[n]; }
1.99 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; }
1.100
1.101 - template< typename It > It first() const {
1.102 - It e; this->first(e); return e; }
1.103 +// template< typename It > It first() const {
1.104 +// It e; this->first(e); return e; }
1.105
1.106 - template< typename It > It first(const Node& v) const {
1.107 - It e; this->first(e, v); return e; }
1.108 +// template< typename It > It first(const Node& v) const {
1.109 +// It e; this->first(e, v); return e; }
1.110 };
1.111
1.112 // //Subgraph on the same node-set and partial edge-set
1.113 @@ -742,9 +804,9 @@
1.114 i=EdgeIt(*this); return i;
1.115 }
1.116
1.117 - template<typename I> I& first(I& i) const { graph->first(i); return i; }
1.118 - template<typename I, typename P> I& first(I& i, const P& p) const {
1.119 - graph->first(i, p); return i; }
1.120 +// template<typename I> I& first(I& i) const { graph->first(i); return i; }
1.121 +// template<typename I, typename P> I& first(I& i, const P& p) const {
1.122 +// graph->first(i, p); return i; }
1.123
1.124 NodeIt& next(NodeIt& n) const {
1.125 GraphWrapper<Graph>::next(n);
1.126 @@ -768,11 +830,11 @@
1.127 }
1.128
1.129 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
1.130 - template< typename It > It first() const {
1.131 - It e; this->first(e); return e; }
1.132 +// template< typename It > It first() const {
1.133 +// It e; this->first(e); return e; }
1.134
1.135 - template< typename It > It first(const Node& v) const {
1.136 - It e; this->first(e, v); return e; }
1.137 +// template< typename It > It first(const Node& v) const {
1.138 +// It e; this->first(e, v); return e; }
1.139
1.140 // Node head(const Edge& e) const { return gw.head(e); }
1.141 // Node tail(const Edge& e) const { return gw.tail(e); }
1.142 @@ -1251,19 +1313,19 @@
1.143 // }
1.144
1.145
1.146 - template< typename It >
1.147 - It first() const {
1.148 - It e;
1.149 - first(e);
1.150 - return e;
1.151 - }
1.152 +// template< typename It >
1.153 +// It first() const {
1.154 +// It e;
1.155 +// first(e);
1.156 +// return e;
1.157 +// }
1.158
1.159 - template< typename It >
1.160 - It first(Node v) const {
1.161 - It e;
1.162 - first(e, v);
1.163 - return e;
1.164 - }
1.165 +// template< typename It >
1.166 +// It first(Node v) const {
1.167 +// It e;
1.168 +// first(e, v);
1.169 +// return e;
1.170 +// }
1.171
1.172 Node tail(Edge e) const {
1.173 return ((e.forward) ? graph->tail(e) : graph->head(e)); }
1.174 @@ -1800,11 +1862,11 @@
1.175 // return i;
1.176 // }
1.177
1.178 - template< typename It > It first() const {
1.179 - It e; this->first(e); return e; }
1.180 +// template< typename It > It first() const {
1.181 +// It e; this->first(e); return e; }
1.182
1.183 - template< typename It > It first(const Node& v) const {
1.184 - It e; this->first(e, v); return e; }
1.185 +// template< typename It > It first(const Node& v) const {
1.186 +// It e; this->first(e, v); return e; }
1.187
1.188 void erase(const OutEdgeIt& e) const {
1.189 OutEdgeIt f=e;