60 |
60 |
61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". |
61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts". |
62 */ |
62 */ |
63 |
63 |
64 /** |
64 /** |
65 @defgroup graph_adaptors Adaptor Classes for graphs |
65 @defgroup graph_adaptors Adaptor Classes for Graphs |
66 @ingroup graphs |
66 @ingroup graphs |
67 \brief This group contains several adaptor classes for digraphs and graphs |
67 \brief Adaptor classes for digraphs and graphs |
|
68 |
|
69 This group contains several useful adaptor classes for digraphs and graphs. |
68 |
70 |
69 The main parts of LEMON are the different graph structures, generic |
71 The main parts of LEMON are the different graph structures, generic |
70 graph algorithms, graph concepts which couple these, and graph |
72 graph algorithms, graph concepts, which couple them, and graph |
71 adaptors. While the previous notions are more or less clear, the |
73 adaptors. While the previous notions are more or less clear, the |
72 latter one needs further explanation. Graph adaptors are graph classes |
74 latter one needs further explanation. Graph adaptors are graph classes |
73 which serve for considering graph structures in different ways. |
75 which serve for considering graph structures in different ways. |
74 |
76 |
75 A short example makes this much clearer. Suppose that we have an |
77 A short example makes this much clearer. Suppose that we have an |
76 instance \c g of a directed graph type say ListDigraph and an algorithm |
78 instance \c g of a directed graph type, say ListDigraph and an algorithm |
77 \code |
79 \code |
78 template <typename Digraph> |
80 template <typename Digraph> |
79 int algorithm(const Digraph&); |
81 int algorithm(const Digraph&); |
80 \endcode |
82 \endcode |
81 is needed to run on the reverse oriented graph. It may be expensive |
83 is needed to run on the reverse oriented graph. It may be expensive |
82 (in time or in memory usage) to copy \c g with the reversed |
84 (in time or in memory usage) to copy \c g with the reversed |
83 arcs. In this case, an adaptor class is used, which (according |
85 arcs. In this case, an adaptor class is used, which (according |
84 to LEMON digraph concepts) works as a digraph. The adaptor uses the |
86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. |
85 original digraph structure and digraph operations when methods of the |
87 The adaptor uses the original digraph structure and digraph operations when |
86 reversed oriented graph are called. This means that the adaptor have |
88 methods of the reversed oriented graph are called. This means that the adaptor |
87 minor memory usage, and do not perform sophisticated algorithmic |
89 have minor memory usage, and do not perform sophisticated algorithmic |
88 actions. The purpose of it is to give a tool for the cases when a |
90 actions. The purpose of it is to give a tool for the cases when a |
89 graph have to be used in a specific alteration. If this alteration is |
91 graph have to be used in a specific alteration. If this alteration is |
90 obtained by a usual construction like filtering the arc-set or |
92 obtained by a usual construction like filtering the node or the arc set or |
91 considering a new orientation, then an adaptor is worthwhile to use. |
93 considering a new orientation, then an adaptor is worthwhile to use. |
92 To come back to the reverse oriented graph, in this situation |
94 To come back to the reverse oriented graph, in this situation |
93 \code |
95 \code |
94 template<typename Digraph> class ReverseDigraph; |
96 template<typename Digraph> class ReverseDigraph; |
95 \endcode |
97 \endcode |
96 template class can be used. The code looks as follows |
98 template class can be used. The code looks as follows |
97 \code |
99 \code |
98 ListDigraph g; |
100 ListDigraph g; |
99 ReverseDigraph<ListGraph> rg(g); |
101 ReverseDigraph<ListDigraph> rg(g); |
100 int result = algorithm(rg); |
102 int result = algorithm(rg); |
101 \endcode |
103 \endcode |
102 After running the algorithm, the original graph \c g is untouched. |
104 During running the algorithm, the original digraph \c g is untouched. |
103 This techniques gives rise to an elegant code, and based on stable |
105 This techniques give rise to an elegant code, and based on stable |
104 graph adaptors, complex algorithms can be implemented easily. |
106 graph adaptors, complex algorithms can be implemented easily. |
105 |
107 |
106 In flow, circulation and bipartite matching problems, the residual |
108 In flow, circulation and matching problems, the residual |
107 graph is of particular importance. Combining an adaptor implementing |
109 graph is of particular importance. Combining an adaptor implementing |
108 this, shortest path algorithms and minimum mean cycle algorithms, |
110 this with shortest path algorithms or minimum mean cycle algorithms, |
109 a range of weighted and cardinality optimization algorithms can be |
111 a range of weighted and cardinality optimization algorithms can be |
110 obtained. For other examples, the interested user is referred to the |
112 obtained. For other examples, the interested user is referred to the |
111 detailed documentation of particular adaptors. |
113 detailed documentation of particular adaptors. |
112 |
114 |
113 The behavior of graph adaptors can be very different. Some of them keep |
115 The behavior of graph adaptors can be very different. Some of them keep |
114 capabilities of the original graph while in other cases this would be |
116 capabilities of the original graph while in other cases this would be |
115 meaningless. This means that the concepts that they are models of depend |
117 meaningless. This means that the concepts that they meet depend |
116 on the graph adaptor, and the wrapped graph(s). |
118 on the graph adaptor, and the wrapped graph. |
117 If an arc of \c rg is deleted, this is carried out by deleting the |
119 For example, if an arc of a reversed digraph is deleted, this is carried |
118 corresponding arc of \c g, thus the adaptor modifies the original graph. |
120 out by deleting the corresponding arc of the original digraph, thus the |
119 |
121 adaptor modifies the original digraph. |
120 But for a residual graph, this operation has no sense. |
122 However in case of a residual digraph, this operation has no sense. |
|
123 |
121 Let us stand one more example here to simplify your work. |
124 Let us stand one more example here to simplify your work. |
122 RevGraphAdaptor has constructor |
125 ReverseDigraph has constructor |
123 \code |
126 \code |
124 ReverseDigraph(Digraph& digraph); |
127 ReverseDigraph(Digraph& digraph); |
125 \endcode |
128 \endcode |
126 This means that in a situation, when a <tt>const ListDigraph&</tt> |
129 This means that in a situation, when a <tt>const %ListDigraph&</tt> |
127 reference to a graph is given, then it have to be instantiated with |
130 reference to a graph is given, then it have to be instantiated with |
128 <tt>Digraph=const ListDigraph</tt>. |
131 <tt>Digraph=const %ListDigraph</tt>. |
129 \code |
132 \code |
130 int algorithm1(const ListDigraph& g) { |
133 int algorithm1(const ListDigraph& g) { |
131 RevGraphAdaptor<const ListDigraph> rg(g); |
134 ReverseDigraph<const ListDigraph> rg(g); |
132 return algorithm2(rg); |
135 return algorithm2(rg); |
133 } |
136 } |
134 \endcode |
137 \endcode |
135 */ |
138 */ |
136 |
139 |