# Changeset 335:999eb3cd7b49 in lemon-0.x for src/work/marci/graph_wrapper.h

Ignore:
Timestamp:
04/16/04 10:26:00 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@454
Message:

jflsjfljskf

File:
1 edited

Unmodified
Removed
• ## src/work/marci/graph_wrapper.h

 r330 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 { 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 Node& v) const { It e; this->first(e, v); 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; } Node head(const Edge& e) const { }; //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 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 Node& v) const { It e; this->first(e, v); 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 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 { //    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 Node& v) const { It e; this->first(e, v); 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; } //    Node head(const Edge& e) const { return gw.head(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() const { //       It e; //       first(e); //       return e; //     } //     template< typename It > //     It first(Node v) const { //       It e; //       first(e, v); //       return e; //     } Node tail(Edge e) const { //     } 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 { //       It e; this->first(e); 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 {
Note: See TracChangeset for help on using the changeset viewer.