kpeter@29: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@29: * kpeter@29: * This file is a part of LEMON, a generic C++ optimization library. kpeter@29: * kpeter@32: * Copyright (C) 2003-2010 kpeter@29: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@29: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@29: * kpeter@29: * Permission to use, modify and distribute this software is granted kpeter@29: * provided that this copyright notice appears in all copies. For kpeter@29: * precise terms see the accompanying LICENSE file. kpeter@29: * kpeter@29: * This software is provided "AS IS" with no warranty of any kind, kpeter@29: * express or implied, and with no claim as to its suitability for any kpeter@29: * purpose. kpeter@29: * kpeter@29: */ kpeter@29: kpeter@29: namespace lemon { kpeter@29: /** kpeter@29: [PAGE]sec_graph_adaptors[PAGE] Graph Adaptors kpeter@29: kpeter@29: \todo Clarify this section. kpeter@29: kpeter@29: Alteration of standard containers need a very limited number of kpeter@29: operations, these together satisfy the everyday requirements. kpeter@29: In the case of graph structures, different operations are needed which do kpeter@29: not alter the physical graph, but gives another view. If some nodes or kpeter@29: arcs have to be hidden or the reverse oriented graph have to be used, then kpeter@29: this is the case. It also may happen that in a flow implementation kpeter@29: the residual graph can be accessed by another algorithm, or a node-set kpeter@29: is to be shrunk for another algorithm. kpeter@29: LEMON also provides a variety of graphs for these requirements called kpeter@29: \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only kpeter@29: in conjunction with other graph representations. kpeter@29: kpeter@29: The main parts of LEMON are the different graph structures, generic kpeter@29: graph algorithms, graph concepts, which couple them, and graph kpeter@29: adaptors. While the previous notions are more or less clear, the kpeter@29: latter one needs further explanation. Graph adaptors are graph classes kpeter@29: which serve for considering graph structures in different ways. kpeter@29: kpeter@29: A short example makes this much clearer. Suppose that we have an kpeter@29: instance \c g of a directed graph type, say ListDigraph and an algorithm kpeter@29: \code kpeter@29: template kpeter@29: int algorithm(const Digraph&); kpeter@29: \endcode kpeter@29: is needed to run on the reverse oriented graph. It may be expensive kpeter@29: (in time or in memory usage) to copy \c g with the reversed kpeter@29: arcs. In this case, an adaptor class is used, which (according kpeter@29: to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. kpeter@29: The adaptor uses the original digraph structure and digraph operations when kpeter@29: methods of the reversed oriented graph are called. This means that the adaptor kpeter@29: have minor memory usage, and do not perform sophisticated algorithmic kpeter@29: actions. The purpose of it is to give a tool for the cases when a kpeter@29: graph have to be used in a specific alteration. If this alteration is kpeter@29: obtained by a usual construction like filtering the node or the arc set or kpeter@29: considering a new orientation, then an adaptor is worthwhile to use. kpeter@29: To come back to the reverse oriented graph, in this situation kpeter@29: \code kpeter@29: template class ReverseDigraph; kpeter@29: \endcode kpeter@29: template class can be used. The code looks as follows kpeter@29: \code kpeter@29: ListDigraph g; kpeter@29: ReverseDigraph rg(g); kpeter@29: int result = algorithm(rg); kpeter@29: \endcode kpeter@29: During running the algorithm, the original digraph \c g is untouched. kpeter@29: This techniques give rise to an elegant code, and based on stable kpeter@29: graph adaptors, complex algorithms can be implemented easily. kpeter@29: kpeter@29: In flow, circulation and matching problems, the residual kpeter@29: graph is of particular importance. Combining an adaptor implementing kpeter@29: this with shortest path algorithms or minimum mean cycle algorithms, kpeter@29: a range of weighted and cardinality optimization algorithms can be kpeter@29: obtained. For other examples, the interested user is referred to the kpeter@29: detailed documentation of particular adaptors. kpeter@29: kpeter@29: The behavior of graph adaptors can be very different. Some of them keep kpeter@29: capabilities of the original graph while in other cases this would be kpeter@29: meaningless. This means that the concepts that they meet depend kpeter@29: on the graph adaptor, and the wrapped graph. kpeter@29: For example, if an arc of a reversed digraph is deleted, this is carried kpeter@29: out by deleting the corresponding arc of the original digraph, thus the kpeter@29: adaptor modifies the original digraph. kpeter@29: However in case of a residual digraph, this operation has no sense. kpeter@29: kpeter@29: Let us stand one more example here to simplify your work. kpeter@29: ReverseDigraph has constructor kpeter@29: \code kpeter@29: ReverseDigraph(Digraph& digraph); kpeter@29: \endcode kpeter@29: This means that in a situation, when a const %ListDigraph& kpeter@29: reference to a graph is given, then it have to be instantiated with kpeter@29: Digraph=const %ListDigraph. kpeter@29: \code kpeter@29: int algorithm1(const ListDigraph& g) { kpeter@29: ReverseDigraph rg(g); kpeter@29: return algorithm2(rg); kpeter@29: } kpeter@29: \endcode kpeter@29: kpeter@29:
kpeter@29: kpeter@29: The LEMON graph adaptor classes serve for considering graphs in kpeter@29: different ways. The adaptors can be used exactly the same as "real" kpeter@29: graphs (i.e., they conform to the graph concepts), thus all generic kpeter@29: algorithms can be performed on them. However, the adaptor classes use kpeter@29: the underlying graph structures and operations when their methods are kpeter@29: called, thus they have only negligible memory usage and do not perform kpeter@29: sophisticated algorithmic actions. This technique yields convenient and kpeter@29: elegant tools for the cases when a graph has to be used in a specific kpeter@29: alteration, but copying it would be too expensive (in time or in memory kpeter@29: usage) compared to the algorithm that should be executed on it. The kpeter@29: following example shows how the \ref ReverseDigraph adaptor can be used kpeter@29: to run Dijksta's algorithm on the reverse oriented graph. Note that the kpeter@29: maps of the original graph can be used in connection with the adaptor, kpeter@29: since the node and arc types of the adaptors convert to the original kpeter@32: item types. kpeter@29: kpeter@29: \code kpeter@29: dijkstra(reverseDigraph(g), length).distMap(dist).run(s); kpeter@29: \endcode kpeter@29: kpeter@29: Using \ref ReverseDigraph could be as efficient as working with the kpeter@29: original graph, but not all adaptors can be so fast, of course. For kpeter@29: example, the subgraph adaptors have to access filter maps for the nodes kpeter@29: and/or the arcs, thus their iterators are significantly slower than the kpeter@29: original iterators. LEMON also provides some more complex adaptors, for kpeter@29: instance, \ref SplitNodes, which can be used for splitting each node in kpeter@29: a directed graph and \ref ResidualDigraph for modeling the residual kpeter@32: network for flow and matching problems. kpeter@29: kpeter@29: Therefore, in cases when rather complex algorithms have to be used kpeter@29: on a subgraph (e.g. when the nodes and arcs have to be traversed several kpeter@29: times), it could worth copying the altered graph into an efficient structure kpeter@29: and run the algorithm on it. kpeter@29: Note that the adaptor classes can also be used for doing this easily, kpeter@29: without having to copy the graph manually, as shown in the following kpeter@29: example. kpeter@29: kpeter@29: \code kpeter@29: ListDigraph g; kpeter@29: ListDigraph::NodeMap filter_map(g); kpeter@29: // construct the graph and fill the filter map kpeter@29: kpeter@29: { kpeter@29: SmartDigraph temp_graph; kpeter@29: ListDigraph::NodeMap node_ref(g); kpeter@29: digraphCopy(filterNodes(g, filter_map), temp_graph) kpeter@29: .nodeRef(node_ref).run(); kpeter@29: kpeter@29: // use temp_graph kpeter@29: } kpeter@29: \endcode kpeter@29: kpeter@29:
kpeter@29: kpeter@29: Another interesting adaptor in LEMON is \ref SplitNodes. kpeter@29: It can be used for splitting each node into an in-node and an out-node kpeter@29: in a directed graph. Formally, the adaptor replaces each node kpeter@29: u in the graph with two nodes, namely node uin and node kpeter@29: uout. Each arc (u,c) in the original graph will correspond to an kpeter@29: arc (uout,vin). The adaptor also adds an kpeter@29: additional bind arc (uin,uout) for each node u kpeter@29: of the original digraph. kpeter@29: kpeter@29: The aim of this class is to assign costs to the nodes when using kpeter@29: algorithms which would otherwise consider arc costs only. kpeter@29: For example, let us suppose that we have a directed graph with costs kpeter@29: given for both the nodes and the arcs. kpeter@29: Then Dijkstra's algorithm can be used in connection with \ref SplitNodes kpeter@29: as follows. kpeter@29: kpeter@29: \code kpeter@29: typedef SplitNodes SplitGraph; kpeter@29: SplitGraph sg(g); kpeter@29: SplitGraph::CombinedArcMap kpeter@29: combined_cost(node_cost, arc_cost); kpeter@29: SplitGraph::NodeMap dist(sg); kpeter@29: dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u)); kpeter@29: \endcode kpeter@29: kpeter@29: Note that this problem can be solved more efficiently with kpeter@29: map adaptors. kpeter@29: kpeter@29: These techniques help writing compact and elegant code, and makes it possible kpeter@29: to easily implement complex algorithms based on well tested standard components. kpeter@29: For instance, in flow and matching problems the residual graph is of kpeter@29: particular importance. kpeter@29: Combining \ref ResidualDigraph adaptor with various algorithms, a kpeter@29: range of weighted and cardinality optimization methods can be obtained kpeter@29: directly. kpeter@29: kpeter@29: [TRAILER] kpeter@29: */ kpeter@32: }