1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
116 usage) compared to the algorithm that should be executed on it. The |
116 usage) compared to the algorithm that should be executed on it. The |
117 following example shows how the \ref ReverseDigraph adaptor can be used |
117 following example shows how the \ref ReverseDigraph adaptor can be used |
118 to run Dijksta's algorithm on the reverse oriented graph. Note that the |
118 to run Dijksta's algorithm on the reverse oriented graph. Note that the |
119 maps of the original graph can be used in connection with the adaptor, |
119 maps of the original graph can be used in connection with the adaptor, |
120 since the node and arc types of the adaptors convert to the original |
120 since the node and arc types of the adaptors convert to the original |
121 item types. |
121 item types. |
122 |
122 |
123 \code |
123 \code |
124 dijkstra(reverseDigraph(g), length).distMap(dist).run(s); |
124 dijkstra(reverseDigraph(g), length).distMap(dist).run(s); |
125 \endcode |
125 \endcode |
126 |
126 |
129 example, the subgraph adaptors have to access filter maps for the nodes |
129 example, the subgraph adaptors have to access filter maps for the nodes |
130 and/or the arcs, thus their iterators are significantly slower than the |
130 and/or the arcs, thus their iterators are significantly slower than the |
131 original iterators. LEMON also provides some more complex adaptors, for |
131 original iterators. LEMON also provides some more complex adaptors, for |
132 instance, \ref SplitNodes, which can be used for splitting each node in |
132 instance, \ref SplitNodes, which can be used for splitting each node in |
133 a directed graph and \ref ResidualDigraph for modeling the residual |
133 a directed graph and \ref ResidualDigraph for modeling the residual |
134 network for flow and matching problems. |
134 network for flow and matching problems. |
135 |
135 |
136 Therefore, in cases when rather complex algorithms have to be used |
136 Therefore, in cases when rather complex algorithms have to be used |
137 on a subgraph (e.g. when the nodes and arcs have to be traversed several |
137 on a subgraph (e.g. when the nodes and arcs have to be traversed several |
138 times), it could worth copying the altered graph into an efficient structure |
138 times), it could worth copying the altered graph into an efficient structure |
139 and run the algorithm on it. |
139 and run the algorithm on it. |