- -The LEMON graph adaptor classes serve for considering graphs in -different ways. The adaptors can be used exactly the same as "real" -graphs (i.e., they conform to the graph concepts), thus all generic -algorithms can be performed on them. However, the adaptor classes use -the underlying graph structures and operations when their methods are -called, thus they have only negligible memory usage and do not perform -sophisticated algorithmic actions. This technique yields convenient and -elegant tools for the cases when a graph has to be used in a specific -alteration, but copying it would be too expensive (in time or in memory -usage) compared to the algorithm that should be executed on it. The -following example shows how the \ref ReverseDigraph adaptor can be used -to run Dijksta's algorithm on the reverse oriented graph. Note that the -maps of the original graph can be used in connection with the adaptor, -since the node and arc types of the adaptors convert to the original -item types. - -\code -dijkstra(reverseDigraph(g), length).distMap(dist).run(s); -\endcode - -Using \ref ReverseDigraph could be as efficient as working with the -original graph, but not all adaptors can be so fast, of course. For -example, the subgraph adaptors have to access filter maps for the nodes -and/or the arcs, thus their iterators are significantly slower than the -original iterators. LEMON also provides some more complex adaptors, for -instance, \ref SplitNodes, which can be used for splitting each node in -a directed graph and \ref ResidualDigraph for modeling the residual -network for flow and matching problems. - -Therefore, in cases when rather complex algorithms have to be used -on a subgraph (e.g. when the nodes and arcs have to be traversed several -times), it could worth copying the altered graph into an efficient structure -and run the algorithm on it. +\note Modification capabilities are not supported for all adaptors. +E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"), +this makes no sense. + +As a more complex example, let us see how \ref ReverseDigraph can be used +together with a graph search algorithm to decide whether a directed graph is +strongly connected or not. +We exploit the fact the a digraph is strongly connected if and only if +for an arbitrarily selected node \c u, each other node is reachable from +\c u (along a directed path) and \c u is reachable from each node. +The latter condition is the same that each node is reachable from \c u +in the reversed digraph. + +\code + template

- -Another interesting adaptor in LEMON is \ref SplitNodes. -It can be used for splitting each node into an in-node and an out-node -in a directed graph. Formally, the adaptor replaces each node -u in the graph with two nodes, namely node u