6 |
6 |
7 namespace hugo { |
7 namespace hugo { |
8 |
8 |
9 /// Graph wrappers |
9 /// Graph wrappers |
10 |
10 |
11 /// The main parts of HUGOlib are the different graph structures, |
11 /// A main parts of HUGOlib are the different graph structures, |
12 /// generic graph algorithms, graph concepts which couple these, and |
12 /// generic graph algorithms, graph concepts which couple these, and |
13 /// graph wrappers. While the previous ones are more or less clear, the |
13 /// graph wrappers. While the previous ones are more or less clear, the |
14 /// latter notion needs further explanation. |
14 /// latter notion needs further explanation. |
15 /// Graph wrappers are graph classes which serve for considering graph |
15 /// Graph wrappers are graph classes which serve for considering graph |
16 /// structures in different ways. A short example makes the notion much more |
16 /// structures in different ways. A short example makes the notion much |
17 /// clear. |
17 /// clearer. |
18 /// Suppose that we have an instance \code g \endcode of a directed graph |
18 /// Suppose that we have an instance \c g of a directed graph |
19 /// type say \code ListGraph \endcode and an algorithm |
19 /// type say \c ListGraph and an algorithm |
20 /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
20 /// \code template<typename Graph> int algorithm(const Graph&); \endcode |
21 /// is needed to run on the reversed oriented graph. |
21 /// is needed to run on the reversely oriented graph. |
22 /// It can be expensive (in time or in memory usage) to copy |
22 /// It may be expensive (in time or in memory usage) to copy |
23 /// \code g \endcode with the reversed orientation. |
23 /// \c g with the reverse orientation. |
24 /// Thus, a wrapper class |
24 /// Thus, a wrapper class |
25 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
25 /// \code template<typename Graph> class RevGraphWrapper; \endcode is used. |
26 /// The code looks as follows |
26 /// The code looks as follows |
27 /// \code |
27 /// \code |
28 /// ListGraph g; |
28 /// ListGraph g; |
29 /// RevGraphWrapper<ListGraph> rgw(g); |
29 /// RevGraphWrapper<ListGraph> rgw(g); |
30 /// int result=algorithm(rgw); |
30 /// int result=algorithm(rgw); |
31 /// \endcode |
31 /// \endcode |
32 /// After running the algorithm, the original graph \code g \endcode |
32 /// After running the algorithm, the original graph \c g |
33 /// is untouched. Thus the above used graph wrapper is to consider the |
33 /// remains untouched. Thus the graph wrapper used above is to consider the |
34 /// original graph with reversed orientation. |
34 /// original graph with reverse orientation. |
35 /// This techniques gives rise to an elegant code, and |
35 /// This techniques gives rise to an elegant code, and |
36 /// based on stable graph wrappers, complex algorithms can be |
36 /// based on stable graph wrappers, complex algorithms can be |
37 /// implemented easily. |
37 /// implemented easily. |
38 /// In flow, circulation and bipartite matching problems, the residual |
38 /// In flow, circulation and bipartite matching problems, the residual |
39 /// graph is of particualar significance. Combining a wrapper impleneting |
39 /// graph is of particular importance. Combining a wrapper implementing |
40 /// this, shortest path algorithms and mimimum mean cycle algorithms, |
40 /// this, shortest path algorithms and minimum mean cycle algorithms, |
41 /// a range of weighted and cardinality optimization algorithms can be |
41 /// a range of weighted and cardinality optimization algorithms can be |
42 /// obtained. For lack of space, for other examples, |
42 /// obtained. For lack of space, for other examples, |
43 /// the interested user is referred to the detailed domumentation of graph |
43 /// the interested user is referred to the detailed documentation of graph |
44 /// wrappers. |
44 /// wrappers. |
45 /// The behavior of graph wrappers are very different. Some of them keep |
45 /// The behavior of graph wrappers can be very different. Some of them keep |
46 /// capabilities of the original graph while in other cases this would be |
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 |
47 /// meaningless. This means that the concepts that they are a model of depend |
48 /// on the graph wrapper, and the wrapped graph(s). |
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 |
49 /// If an edge of \c rgw is deleted, this is carried out by |
50 /// deleting the corresponding edge of \code g \endcode. But for a residual |
50 /// deleting the corresponding edge of \c g. But for a residual |
51 /// graph, this operation has no sense. |
51 /// graph, this operation has no sense. |
52 /// Let we stand one more example here to simplify your work. |
52 /// Let we stand one more example here to simplify your work. |
53 /// wrapper class |
53 /// wrapper class |
54 /// \code template<typename Graph> class RevGraphWrapper; \endcode |
54 /// \code template<typename Graph> class RevGraphWrapper; \endcode |
55 /// has constructor |
55 /// has constructor |
56 /// \code RevGraphWrapper(Graph& _g); \endcode. |
56 /// <tt> RevGraphWrapper(Graph& _g)</tt>. |
57 /// This means that in a situation, |
57 /// This means that in a situation, |
58 /// when a \code const ListGraph& \endcode reference to a graph is given, |
58 /// when a <tt> const ListGraph& </tt> reference to a graph is given, |
59 /// then it have to be instatiated with Graph=const ListGraph. |
59 /// then it have to be instantiated with <tt>Graph=const ListGraph</tt>. |
60 /// \code |
60 /// \code |
61 /// int algorithm1(const ListGraph& g) { |
61 /// int algorithm1(const ListGraph& g) { |
62 /// RevGraphWrapper<const ListGraph> rgw(g); |
62 /// RevGraphWrapper<const ListGraph> rgw(g); |
63 /// return algorithm2(rgw); |
63 /// return algorithm2(rgw); |
64 /// } |
64 /// } |