29 making a copy of the graph structure along with the required maps |
29 making a copy of the graph structure along with the required maps |
30 could be rather expensive (in time or in memory usage) compared to the |
30 could be rather expensive (in time or in memory usage) compared to the |
31 operations that should be performed on the altered graph. |
31 operations that should be performed on the altered graph. |
32 In such cases, the LEMON \e graph \e adaptor \e classes could be used. |
32 In such cases, the LEMON \e graph \e adaptor \e classes could be used. |
33 |
33 |
34 |
|
35 [SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph |
34 [SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph |
36 |
35 |
37 Let us suppose that we have an instance \c g of a directed graph type, say |
36 Let us suppose that we have an instance \c g of a directed graph type, say |
38 \ref ListDigraph and an algorithm |
37 \ref ListDigraph and an algorithm |
39 \code |
38 \code |
176 [SEC]sec_subgraphs[SEC] Subgraph Adaptorts |
175 [SEC]sec_subgraphs[SEC] Subgraph Adaptorts |
177 |
176 |
178 Another typical requirement is the use of certain subgraphs of a graph, |
177 Another typical requirement is the use of certain subgraphs of a graph, |
179 or in other words, hiding nodes and/or arcs from a graph. |
178 or in other words, hiding nodes and/or arcs from a graph. |
180 LEMON provides several convenient adaptors for these purposes. |
179 LEMON provides several convenient adaptors for these purposes. |
|
180 In the following picture, a \ref SubDigraph adaptor is applied to an |
|
181 underlying digraph structure to obtain a suitable subgraph. |
|
182 |
|
183 \image html adaptors1.png |
|
184 \image latex adaptors1.eps "SubDigraph adaptor" width=\textwidth |
181 |
185 |
182 \ref FilterArcs can be used when some arcs have to be hidden from a digraph. |
186 \ref FilterArcs can be used when some arcs have to be hidden from a digraph. |
183 A \e filter \e map has to be given to the constructor, which assign \c bool |
187 A \e filter \e map has to be given to the constructor, which assign \c bool |
184 values to the arcs specifying whether they have to be shown or not in the |
188 values to the arcs specifying whether they have to be shown or not in the |
185 subgraph structure. |
189 subgraph structure. |
323 ListGraph graph; |
327 ListGraph graph; |
324 ListGraph::EdgeMap<bool> dir_map(graph, true); |
328 ListGraph::EdgeMap<bool> dir_map(graph, true); |
325 Orienter<ListGraph> directed_graph(graph, dir_map); |
329 Orienter<ListGraph> directed_graph(graph, dir_map); |
326 \endcode |
330 \endcode |
327 |
331 |
|
332 Sine the adaptor classes conform to the \ref graph_concepts "graph concepts", |
|
333 we can even apply an adaptor to another one. |
|
334 The following image illustrates a situation when a \ref SubDigraph and an |
|
335 \ref Undirector adaptor is applied on a digraph. |
|
336 |
|
337 \image html adaptors2.png |
|
338 \image latex adaptors2.eps "Arc disjoint paths" width=\textwidth |
|
339 |
328 LEMON also provides some more complex adaptors, for |
340 LEMON also provides some more complex adaptors, for |
329 instance, \ref SplitNodes, which can be used for splitting each node of a |
341 instance, \ref SplitNodes, which can be used for splitting each node of a |
330 directed graph into an in-node and an out-node. |
342 directed graph into an in-node and an out-node. |
331 Formally, the adaptor replaces each node u in the graph with two nodes, |
343 Formally, the adaptor replaces each node u in the graph with two nodes, |
332 namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original |
344 namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original |