[29] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[32] | 5 | * Copyright (C) 2003-2010 |
---|
[29] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | namespace lemon { |
---|
| 20 | /** |
---|
| 21 | [PAGE]sec_graph_adaptors[PAGE] Graph Adaptors |
---|
| 22 | |
---|
| 23 | \todo Clarify this section. |
---|
| 24 | |
---|
| 25 | Alteration of standard containers need a very limited number of |
---|
| 26 | operations, these together satisfy the everyday requirements. |
---|
| 27 | In the case of graph structures, different operations are needed which do |
---|
| 28 | not alter the physical graph, but gives another view. If some nodes or |
---|
| 29 | arcs have to be hidden or the reverse oriented graph have to be used, then |
---|
| 30 | this is the case. It also may happen that in a flow implementation |
---|
| 31 | the residual graph can be accessed by another algorithm, or a node-set |
---|
| 32 | is to be shrunk for another algorithm. |
---|
| 33 | LEMON also provides a variety of graphs for these requirements called |
---|
| 34 | \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only |
---|
| 35 | in conjunction with other graph representations. |
---|
| 36 | |
---|
| 37 | The main parts of LEMON are the different graph structures, generic |
---|
| 38 | graph algorithms, graph concepts, which couple them, and graph |
---|
| 39 | adaptors. While the previous notions are more or less clear, the |
---|
| 40 | latter one needs further explanation. Graph adaptors are graph classes |
---|
| 41 | which serve for considering graph structures in different ways. |
---|
| 42 | |
---|
| 43 | A short example makes this much clearer. Suppose that we have an |
---|
| 44 | instance \c g of a directed graph type, say ListDigraph and an algorithm |
---|
| 45 | \code |
---|
| 46 | template <typename Digraph> |
---|
| 47 | int algorithm(const Digraph&); |
---|
| 48 | \endcode |
---|
| 49 | is needed to run on the reverse oriented graph. It may be expensive |
---|
| 50 | (in time or in memory usage) to copy \c g with the reversed |
---|
| 51 | arcs. In this case, an adaptor class is used, which (according |
---|
| 52 | to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph. |
---|
| 53 | The adaptor uses the original digraph structure and digraph operations when |
---|
| 54 | methods of the reversed oriented graph are called. This means that the adaptor |
---|
| 55 | have minor memory usage, and do not perform sophisticated algorithmic |
---|
| 56 | actions. The purpose of it is to give a tool for the cases when a |
---|
| 57 | graph have to be used in a specific alteration. If this alteration is |
---|
| 58 | obtained by a usual construction like filtering the node or the arc set or |
---|
| 59 | considering a new orientation, then an adaptor is worthwhile to use. |
---|
| 60 | To come back to the reverse oriented graph, in this situation |
---|
| 61 | \code |
---|
| 62 | template<typename Digraph> class ReverseDigraph; |
---|
| 63 | \endcode |
---|
| 64 | template class can be used. The code looks as follows |
---|
| 65 | \code |
---|
| 66 | ListDigraph g; |
---|
| 67 | ReverseDigraph<ListDigraph> rg(g); |
---|
| 68 | int result = algorithm(rg); |
---|
| 69 | \endcode |
---|
| 70 | During running the algorithm, the original digraph \c g is untouched. |
---|
| 71 | This techniques give rise to an elegant code, and based on stable |
---|
| 72 | graph adaptors, complex algorithms can be implemented easily. |
---|
| 73 | |
---|
| 74 | In flow, circulation and matching problems, the residual |
---|
| 75 | graph is of particular importance. Combining an adaptor implementing |
---|
| 76 | this with shortest path algorithms or minimum mean cycle algorithms, |
---|
| 77 | a range of weighted and cardinality optimization algorithms can be |
---|
| 78 | obtained. For other examples, the interested user is referred to the |
---|
| 79 | detailed documentation of particular adaptors. |
---|
| 80 | |
---|
| 81 | The behavior of graph adaptors can be very different. Some of them keep |
---|
| 82 | capabilities of the original graph while in other cases this would be |
---|
| 83 | meaningless. This means that the concepts that they meet depend |
---|
| 84 | on the graph adaptor, and the wrapped graph. |
---|
| 85 | For example, if an arc of a reversed digraph is deleted, this is carried |
---|
| 86 | out by deleting the corresponding arc of the original digraph, thus the |
---|
| 87 | adaptor modifies the original digraph. |
---|
| 88 | However in case of a residual digraph, this operation has no sense. |
---|
| 89 | |
---|
| 90 | Let us stand one more example here to simplify your work. |
---|
| 91 | ReverseDigraph has constructor |
---|
| 92 | \code |
---|
| 93 | ReverseDigraph(Digraph& digraph); |
---|
| 94 | \endcode |
---|
| 95 | This means that in a situation, when a <tt>const %ListDigraph&</tt> |
---|
| 96 | reference to a graph is given, then it have to be instantiated with |
---|
| 97 | <tt>Digraph=const %ListDigraph</tt>. |
---|
| 98 | \code |
---|
| 99 | int algorithm1(const ListDigraph& g) { |
---|
| 100 | ReverseDigraph<const ListDigraph> rg(g); |
---|
| 101 | return algorithm2(rg); |
---|
| 102 | } |
---|
| 103 | \endcode |
---|
| 104 | |
---|
| 105 | <hr> |
---|
| 106 | |
---|
| 107 | The LEMON graph adaptor classes serve for considering graphs in |
---|
| 108 | different ways. The adaptors can be used exactly the same as "real" |
---|
| 109 | graphs (i.e., they conform to the graph concepts), thus all generic |
---|
| 110 | algorithms can be performed on them. However, the adaptor classes use |
---|
| 111 | the underlying graph structures and operations when their methods are |
---|
| 112 | called, thus they have only negligible memory usage and do not perform |
---|
| 113 | sophisticated algorithmic actions. This technique yields convenient and |
---|
| 114 | elegant tools for the cases when a graph has to be used in a specific |
---|
| 115 | alteration, but copying it would be too expensive (in time or in memory |
---|
| 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 |
---|
| 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, |
---|
| 120 | since the node and arc types of the adaptors convert to the original |
---|
[32] | 121 | item types. |
---|
[29] | 122 | |
---|
| 123 | \code |
---|
| 124 | dijkstra(reverseDigraph(g), length).distMap(dist).run(s); |
---|
| 125 | \endcode |
---|
| 126 | |
---|
| 127 | Using \ref ReverseDigraph could be as efficient as working with the |
---|
| 128 | original graph, but not all adaptors can be so fast, of course. For |
---|
| 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 |
---|
| 131 | original iterators. LEMON also provides some more complex adaptors, for |
---|
| 132 | instance, \ref SplitNodes, which can be used for splitting each node in |
---|
| 133 | a directed graph and \ref ResidualDigraph for modeling the residual |
---|
[32] | 134 | network for flow and matching problems. |
---|
[29] | 135 | |
---|
| 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 |
---|
| 138 | times), it could worth copying the altered graph into an efficient structure |
---|
| 139 | and run the algorithm on it. |
---|
| 140 | Note that the adaptor classes can also be used for doing this easily, |
---|
| 141 | without having to copy the graph manually, as shown in the following |
---|
| 142 | example. |
---|
| 143 | |
---|
| 144 | \code |
---|
| 145 | ListDigraph g; |
---|
| 146 | ListDigraph::NodeMap<bool> filter_map(g); |
---|
| 147 | // construct the graph and fill the filter map |
---|
| 148 | |
---|
| 149 | { |
---|
| 150 | SmartDigraph temp_graph; |
---|
| 151 | ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g); |
---|
| 152 | digraphCopy(filterNodes(g, filter_map), temp_graph) |
---|
| 153 | .nodeRef(node_ref).run(); |
---|
| 154 | |
---|
| 155 | // use temp_graph |
---|
| 156 | } |
---|
| 157 | \endcode |
---|
| 158 | |
---|
| 159 | <hr> |
---|
| 160 | |
---|
| 161 | Another interesting adaptor in LEMON is \ref SplitNodes. |
---|
| 162 | It can be used for splitting each node into an in-node and an out-node |
---|
| 163 | in a directed graph. Formally, the adaptor replaces each node |
---|
| 164 | u in the graph with two nodes, namely node u<sub>in</sub> and node |
---|
| 165 | u<sub>out</sub>. Each arc (u,c) in the original graph will correspond to an |
---|
| 166 | arc (u<sub>out</sub>,v<sub>in</sub>). The adaptor also adds an |
---|
| 167 | additional bind arc (u<sub>in</sub>,u<sub>out</sub>) for each node u |
---|
| 168 | of the original digraph. |
---|
| 169 | |
---|
| 170 | The aim of this class is to assign costs to the nodes when using |
---|
| 171 | algorithms which would otherwise consider arc costs only. |
---|
| 172 | For example, let us suppose that we have a directed graph with costs |
---|
| 173 | given for both the nodes and the arcs. |
---|
| 174 | Then Dijkstra's algorithm can be used in connection with \ref SplitNodes |
---|
| 175 | as follows. |
---|
| 176 | |
---|
| 177 | \code |
---|
| 178 | typedef SplitNodes<ListDigraph> SplitGraph; |
---|
| 179 | SplitGraph sg(g); |
---|
| 180 | SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap> |
---|
| 181 | combined_cost(node_cost, arc_cost); |
---|
| 182 | SplitGraph::NodeMap<double> dist(sg); |
---|
| 183 | dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u)); |
---|
| 184 | \endcode |
---|
| 185 | |
---|
| 186 | Note that this problem can be solved more efficiently with |
---|
| 187 | map adaptors. |
---|
| 188 | |
---|
| 189 | These techniques help writing compact and elegant code, and makes it possible |
---|
| 190 | to easily implement complex algorithms based on well tested standard components. |
---|
| 191 | For instance, in flow and matching problems the residual graph is of |
---|
| 192 | particular importance. |
---|
| 193 | Combining \ref ResidualDigraph adaptor with various algorithms, a |
---|
| 194 | range of weighted and cardinality optimization methods can be obtained |
---|
| 195 | directly. |
---|
| 196 | |
---|
| 197 | [TRAILER] |
---|
| 198 | */ |
---|
[32] | 199 | } |
---|