Changeset 335:999eb3cd7b49 in lemon0.x for src/work/marci/graph_wrapper.h
 Timestamp:
 04/16/04 10:26:00 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@454
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/graph_wrapper.h
r330 r335 7 7 namespace hugo { 8 8 9 /// Graph wrappers 10 11 /// The main parts of HUGOlib are the different graph structures, 12 /// generic graph algorithms, graph concepts which couple these, and 13 /// graph wrappers. While the previous ones are more or less clear, the 14 /// latter notion needs further explanation. 15 /// Graph wrappers are graph classes which serve for considering graph 16 /// structures in different ways. A short example makes the notion much more 17 /// clear. 18 /// Suppose that we have an instance \code g \endcode of a directed graph 19 /// type say \code ListGraph \endcode and an algorithm 20 /// \code template<typename Graph> int algorithm(const Graph&); \endcode 21 /// is needed to run on the reversed oriented graph. 22 /// It can be expensive (in time or in memory usage) to copy 23 /// \code g \endcode with the reversed orientation. 24 /// Thus, a wrapper class 25 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. 26 /// The code looks as follows 27 /// \code 28 /// ListGraph g; 29 /// RevGraphWrapper<ListGraph> rgw(g); 30 /// int result=algorithm(rgw); 31 /// \endcode 32 /// After running the algorithm, the original graph \code g \endcode 33 /// is untouched. Thus the above used graph wrapper is to consider the 34 /// original graph with reversed orientation. 35 /// This techniques gives rise to an elegant code, and 36 /// based on stable graph wrappers, complex algorithms can be 37 /// implemented easily. 38 /// In flow, circulation and bipartite matching problems, the residual 39 /// graph is of particualar significance. Combining a wrapper impleneting 40 /// this, shortest path algorithms and mimimum mean cycle algorithms, 41 /// a range of weighted and cardinality optimization algorithms can be 42 /// obtained. For lack of space, for other examples, 43 /// the interested user is referred to the detailed domumentation of graph 44 /// wrappers. 45 /// The behavior of graph wrappers are very different. Some of them keep 46 /// capabilities of the original graph while in other cases this would be 47 /// meaningless. This means that the concepts that they are model of depend 48 /// on the graph wrapper, and the wrapped graph(s). 49 /// If an edge of \code rgw \endcode is deleted, this is carried out by 50 /// deleting the corresponding edge of \code g \endcode. But for a residual 51 /// graph, this operation has no sense. 52 /// Let we stand one more example here to simplify your work. 53 /// wrapper class 54 /// \code template<typename Graph> class RevGraphWrapper; \endcode 55 /// has constructor 56 /// \code RevGraphWrapper(Graph& _g); \endcode. 57 /// This means that in a situation, 58 /// when a \code const ListGraph& \endcode reference to a graph is given, 59 /// then it have to be instatiated with Graph=const ListGraph. 60 /// \code 61 /// int algorithm1(const ListGraph& g) { 62 /// RevGraphWrapper<const ListGraph> rgw(g); 63 /// return algorithm2(rgw); 64 /// } 65 /// \endcode 9 66 template<typename Graph> 10 67 class GraphWrapper { … … 110 167 EdgeIt& next(EdgeIt& i) const { graph>next(i.e); return i; } 111 168 // template<typename I> I& next(I &i) const { graph>next(i); return i; } 112 template< typename It > It first() const {113 It e; this>first(e); return e; }114 115 template< typename It > It first(const Node& v) const {116 It e; this>first(e, v); return e; }169 // template< typename It > It first() const { 170 // It e; this>first(e); return e; } 171 172 // template< typename It > It first(const Node& v) const { 173 // It e; this>first(e, v); return e; } 117 174 118 175 Node head(const Edge& e) const { … … 275 332 }; 276 333 277 //Subgraph on the same nodeset and partial edgeset 334 /// Wrapper for hiding nodes and edges from a graph. 335 336 /// This wrapper shows a graph with filtered nodeset and 337 /// edgeset. The quick brown fox iterators jumps over 338 /// the lazy dog nodes or edges if the values for them are false 339 /// in the bool maps. 278 340 template<typename Graph, typename NodeFilterMap, 279 341 typename EdgeFilterMap> … … 484 546 bool hidden(const Edge& e) const { return (*edge_filter_map)[e]; } 485 547 486 template< typename It > It first() const {487 It e; this>first(e); return e; }488 489 template< typename It > It first(const Node& v) const {490 It e; this>first(e, v); return e; }548 // template< typename It > It first() const { 549 // It e; this>first(e); return e; } 550 551 // template< typename It > It first(const Node& v) const { 552 // It e; this>first(e, v); return e; } 491 553 }; 492 554 … … 743 805 } 744 806 745 template<typename I> I& first(I& i) const { graph>first(i); return i; }746 template<typename I, typename P> I& first(I& i, const P& p) const {747 graph>first(i, p); return i; }807 // template<typename I> I& first(I& i) const { graph>first(i); return i; } 808 // template<typename I, typename P> I& first(I& i, const P& p) const { 809 // graph>first(i, p); return i; } 748 810 749 811 NodeIt& next(NodeIt& n) const { … … 769 831 770 832 // template<typename I> I& next(I &i) const { graph>next(i); return i; } 771 template< typename It > It first() const {772 It e; this>first(e); return e; }773 774 template< typename It > It first(const Node& v) const {775 It e; this>first(e, v); return e; }833 // template< typename It > It first() const { 834 // It e; this>first(e); return e; } 835 836 // template< typename It > It first(const Node& v) const { 837 // It e; this>first(e, v); return e; } 776 838 777 839 // Node head(const Edge& e) const { return gw.head(e); } … … 1252 1314 1253 1315 1254 template< typename It >1255 It first() const {1256 It e;1257 first(e);1258 return e;1259 }1260 1261 template< typename It >1262 It first(Node v) const {1263 It e;1264 first(e, v);1265 return e;1266 }1316 // template< typename It > 1317 // It first() const { 1318 // It e; 1319 // first(e); 1320 // return e; 1321 // } 1322 1323 // template< typename It > 1324 // It first(Node v) const { 1325 // It e; 1326 // first(e, v); 1327 // return e; 1328 // } 1267 1329 1268 1330 Node tail(Edge e) const { … … 1801 1863 // } 1802 1864 1803 template< typename It > It first() const {1804 It e; this>first(e); return e; }1805 1806 template< typename It > It first(const Node& v) const {1807 It e; this>first(e, v); return e; }1865 // template< typename It > It first() const { 1866 // It e; this>first(e); return e; } 1867 1868 // template< typename It > It first(const Node& v) const { 1869 // It e; this>first(e, v); return e; } 1808 1870 1809 1871 void erase(const OutEdgeIt& e) const {
Note: See TracChangeset
for help on using the changeset viewer.