diff -r 63703ea7d02f -r 999eb3cd7b49 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Thu Apr 15 20:50:03 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Fri Apr 16 08:26:00 2004 +0000 @@ -6,6 +6,63 @@ namespace hugo { + /// Graph wrappers + + /// The main parts of HUGOlib are the different graph structures, + /// generic graph algorithms, graph concepts which couple these, and + /// graph wrappers. While the previous ones are more or less clear, the + /// latter notion needs further explanation. + /// Graph wrappers are graph classes which serve for considering graph + /// structures in different ways. A short example makes the notion much more + /// clear. + /// Suppose that we have an instance \code g \endcode of a directed graph + /// type say \code ListGraph \endcode and an algorithm + /// \code template int algorithm(const Graph&); \endcode + /// is needed to run on the reversed oriented graph. + /// It can be expensive (in time or in memory usage) to copy + /// \code g \endcode with the reversed orientation. + /// Thus, a wrapper class + /// \code template class RevGraphWrapper; \endcode is used. + /// The code looks as follows + /// \code + /// ListGraph g; + /// RevGraphWrapper rgw(g); + /// int result=algorithm(rgw); + /// \endcode + /// After running the algorithm, the original graph \code g \endcode + /// is untouched. Thus the above used graph wrapper is to consider the + /// original graph with reversed orientation. + /// This techniques gives rise to an elegant code, and + /// based on stable graph wrappers, complex algorithms can be + /// implemented easily. + /// In flow, circulation and bipartite matching problems, the residual + /// graph is of particualar significance. Combining a wrapper impleneting + /// this, shortest path algorithms and mimimum mean cycle algorithms, + /// a range of weighted and cardinality optimization algorithms can be + /// obtained. For lack of space, for other examples, + /// the interested user is referred to the detailed domumentation of graph + /// wrappers. + /// The behavior of graph wrappers are very different. Some of them keep + /// capabilities of the original graph while in other cases this would be + /// meaningless. This means that the concepts that they are model of depend + /// on the graph wrapper, and the wrapped graph(s). + /// If an edge of \code rgw \endcode is deleted, this is carried out by + /// deleting the corresponding edge of \code g \endcode. But for a residual + /// graph, this operation has no sense. + /// Let we stand one more example here to simplify your work. + /// wrapper class + /// \code template class RevGraphWrapper; \endcode + /// has constructor + /// \code RevGraphWrapper(Graph& _g); \endcode. + /// This means that in a situation, + /// when a \code const ListGraph& \endcode reference to a graph is given, + /// then it have to be instatiated with Graph=const ListGraph. + /// \code + /// int algorithm1(const ListGraph& g) { + /// RevGraphWrapper rgw(g); + /// return algorithm2(rgw); + /// } + /// \endcode template class GraphWrapper { protected: @@ -109,11 +166,11 @@ InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } // template I& next(I &i) const { graph->next(i); return i; } - template< typename It > It first() const { - It e; this->first(e); return e; } +// template< typename It > It first() const { +// It e; this->first(e); return e; } - template< typename It > It first(const Node& v) const { - It e; this->first(e, v); return e; } +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } Node head(const Edge& e) const { return Node(graph->head(static_cast(e))); } @@ -274,7 +331,12 @@ { return GraphWrapper::head(e); } }; - //Subgraph on the same node-set and partial edge-set + /// Wrapper for hiding nodes and edges from a graph. + + /// This wrapper shows a graph with filtered node-set and + /// edge-set. The quick brown fox iterators jumps over + /// the lazy dog nodes or edges if the values for them are false + /// in the bool maps. template class SubGraphWrapper : public GraphWrapper { @@ -483,11 +545,11 @@ bool hidden(const Node& n) const { return (*node_filter_map)[n]; } bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } - template< typename It > It first() const { - It e; this->first(e); return e; } +// template< typename It > It first() const { +// It e; this->first(e); return e; } - template< typename It > It first(const Node& v) const { - It e; this->first(e, v); return e; } +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } }; // //Subgraph on the same node-set and partial edge-set @@ -742,9 +804,9 @@ i=EdgeIt(*this); return i; } - template I& first(I& i) const { graph->first(i); return i; } - template I& first(I& i, const P& p) const { - graph->first(i, p); return i; } +// template I& first(I& i) const { graph->first(i); return i; } +// template I& first(I& i, const P& p) const { +// graph->first(i, p); return i; } NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); @@ -768,11 +830,11 @@ } // template I& next(I &i) const { graph->next(i); return i; } - template< typename It > It first() const { - It e; this->first(e); return e; } +// template< typename It > It first() const { +// It e; this->first(e); return e; } - template< typename It > It first(const Node& v) const { - It e; this->first(e, v); return e; } +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } // Node head(const Edge& e) const { return gw.head(e); } // Node tail(const Edge& e) const { return gw.tail(e); } @@ -1251,19 +1313,19 @@ // } - template< typename It > - It first() const { - It e; - first(e); - return e; - } +// template< typename It > +// It first() const { +// It e; +// first(e); +// return e; +// } - template< typename It > - It first(Node v) const { - It e; - first(e, v); - return e; - } +// template< typename It > +// It first(Node v) const { +// It e; +// first(e, v); +// return e; +// } Node tail(Edge e) const { return ((e.forward) ? graph->tail(e) : graph->head(e)); } @@ -1800,11 +1862,11 @@ // return i; // } - template< typename It > It first() const { - It e; this->first(e); return e; } +// template< typename It > It first() const { +// It e; this->first(e); return e; } - template< typename It > It first(const Node& v) const { - It e; this->first(e, v); return e; } +// template< typename It > It first(const Node& v) const { +// It e; this->first(e, v); return e; } void erase(const OutEdgeIt& e) const { OutEdgeIt f=e;