1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/adaptors.dox Mon Feb 15 01:18:18 2010 +0100
1.3 @@ -0,0 +1,199 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +namespace lemon {
1.23 +/**
1.24 +[PAGE]sec_graph_adaptors[PAGE] Graph Adaptors
1.25 +
1.26 +\todo Clarify this section.
1.27 +
1.28 +Alteration of standard containers need a very limited number of
1.29 +operations, these together satisfy the everyday requirements.
1.30 +In the case of graph structures, different operations are needed which do
1.31 +not alter the physical graph, but gives another view. If some nodes or
1.32 +arcs have to be hidden or the reverse oriented graph have to be used, then
1.33 +this is the case. It also may happen that in a flow implementation
1.34 +the residual graph can be accessed by another algorithm, or a node-set
1.35 +is to be shrunk for another algorithm.
1.36 +LEMON also provides a variety of graphs for these requirements called
1.37 +\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
1.38 +in conjunction with other graph representations.
1.39 +
1.40 +The main parts of LEMON are the different graph structures, generic
1.41 +graph algorithms, graph concepts, which couple them, and graph
1.42 +adaptors. While the previous notions are more or less clear, the
1.43 +latter one needs further explanation. Graph adaptors are graph classes
1.44 +which serve for considering graph structures in different ways.
1.45 +
1.46 +A short example makes this much clearer. Suppose that we have an
1.47 +instance \c g of a directed graph type, say ListDigraph and an algorithm
1.48 +\code
1.49 +template <typename Digraph>
1.50 +int algorithm(const Digraph&);
1.51 +\endcode
1.52 +is needed to run on the reverse oriented graph. It may be expensive
1.53 +(in time or in memory usage) to copy \c g with the reversed
1.54 +arcs. In this case, an adaptor class is used, which (according
1.55 +to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
1.56 +The adaptor uses the original digraph structure and digraph operations when
1.57 +methods of the reversed oriented graph are called. This means that the adaptor
1.58 +have minor memory usage, and do not perform sophisticated algorithmic
1.59 +actions. The purpose of it is to give a tool for the cases when a
1.60 +graph have to be used in a specific alteration. If this alteration is
1.61 +obtained by a usual construction like filtering the node or the arc set or
1.62 +considering a new orientation, then an adaptor is worthwhile to use.
1.63 +To come back to the reverse oriented graph, in this situation
1.64 +\code
1.65 +template<typename Digraph> class ReverseDigraph;
1.66 +\endcode
1.67 +template class can be used. The code looks as follows
1.68 +\code
1.69 +ListDigraph g;
1.70 +ReverseDigraph<ListDigraph> rg(g);
1.71 +int result = algorithm(rg);
1.72 +\endcode
1.73 +During running the algorithm, the original digraph \c g is untouched.
1.74 +This techniques give rise to an elegant code, and based on stable
1.75 +graph adaptors, complex algorithms can be implemented easily.
1.76 +
1.77 +In flow, circulation and matching problems, the residual
1.78 +graph is of particular importance. Combining an adaptor implementing
1.79 +this with shortest path algorithms or minimum mean cycle algorithms,
1.80 +a range of weighted and cardinality optimization algorithms can be
1.81 +obtained. For other examples, the interested user is referred to the
1.82 +detailed documentation of particular adaptors.
1.83 +
1.84 +The behavior of graph adaptors can be very different. Some of them keep
1.85 +capabilities of the original graph while in other cases this would be
1.86 +meaningless. This means that the concepts that they meet depend
1.87 +on the graph adaptor, and the wrapped graph.
1.88 +For example, if an arc of a reversed digraph is deleted, this is carried
1.89 +out by deleting the corresponding arc of the original digraph, thus the
1.90 +adaptor modifies the original digraph.
1.91 +However in case of a residual digraph, this operation has no sense.
1.92 +
1.93 +Let us stand one more example here to simplify your work.
1.94 +ReverseDigraph has constructor
1.95 +\code
1.96 +ReverseDigraph(Digraph& digraph);
1.97 +\endcode
1.98 +This means that in a situation, when a <tt>const %ListDigraph&</tt>
1.99 +reference to a graph is given, then it have to be instantiated with
1.100 +<tt>Digraph=const %ListDigraph</tt>.
1.101 +\code
1.102 +int algorithm1(const ListDigraph& g) {
1.103 + ReverseDigraph<const ListDigraph> rg(g);
1.104 + return algorithm2(rg);
1.105 +}
1.106 +\endcode
1.107 +
1.108 +<hr>
1.109 +
1.110 +The LEMON graph adaptor classes serve for considering graphs in
1.111 +different ways. The adaptors can be used exactly the same as "real"
1.112 +graphs (i.e., they conform to the graph concepts), thus all generic
1.113 +algorithms can be performed on them. However, the adaptor classes use
1.114 +the underlying graph structures and operations when their methods are
1.115 +called, thus they have only negligible memory usage and do not perform
1.116 +sophisticated algorithmic actions. This technique yields convenient and
1.117 +elegant tools for the cases when a graph has to be used in a specific
1.118 +alteration, but copying it would be too expensive (in time or in memory
1.119 +usage) compared to the algorithm that should be executed on it. The
1.120 +following example shows how the \ref ReverseDigraph adaptor can be used
1.121 +to run Dijksta's algorithm on the reverse oriented graph. Note that the
1.122 +maps of the original graph can be used in connection with the adaptor,
1.123 +since the node and arc types of the adaptors convert to the original
1.124 +item types.
1.125 +
1.126 +\code
1.127 +dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
1.128 +\endcode
1.129 +
1.130 +Using \ref ReverseDigraph could be as efficient as working with the
1.131 +original graph, but not all adaptors can be so fast, of course. For
1.132 +example, the subgraph adaptors have to access filter maps for the nodes
1.133 +and/or the arcs, thus their iterators are significantly slower than the
1.134 +original iterators. LEMON also provides some more complex adaptors, for
1.135 +instance, \ref SplitNodes, which can be used for splitting each node in
1.136 +a directed graph and \ref ResidualDigraph for modeling the residual
1.137 +network for flow and matching problems.
1.138 +
1.139 +Therefore, in cases when rather complex algorithms have to be used
1.140 +on a subgraph (e.g. when the nodes and arcs have to be traversed several
1.141 +times), it could worth copying the altered graph into an efficient structure
1.142 +and run the algorithm on it.
1.143 +Note that the adaptor classes can also be used for doing this easily,
1.144 +without having to copy the graph manually, as shown in the following
1.145 +example.
1.146 +
1.147 +\code
1.148 + ListDigraph g;
1.149 + ListDigraph::NodeMap<bool> filter_map(g);
1.150 + // construct the graph and fill the filter map
1.151 +
1.152 + {
1.153 + SmartDigraph temp_graph;
1.154 + ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g);
1.155 + digraphCopy(filterNodes(g, filter_map), temp_graph)
1.156 + .nodeRef(node_ref).run();
1.157 +
1.158 + // use temp_graph
1.159 + }
1.160 +\endcode
1.161 +
1.162 +<hr>
1.163 +
1.164 +Another interesting adaptor in LEMON is \ref SplitNodes.
1.165 +It can be used for splitting each node into an in-node and an out-node
1.166 +in a directed graph. Formally, the adaptor replaces each node
1.167 +u in the graph with two nodes, namely node u<sub>in</sub> and node
1.168 +u<sub>out</sub>. Each arc (u,c) in the original graph will correspond to an
1.169 +arc (u<sub>out</sub>,v<sub>in</sub>). The adaptor also adds an
1.170 +additional bind arc (u<sub>in</sub>,u<sub>out</sub>) for each node u
1.171 +of the original digraph.
1.172 +
1.173 +The aim of this class is to assign costs to the nodes when using
1.174 +algorithms which would otherwise consider arc costs only.
1.175 +For example, let us suppose that we have a directed graph with costs
1.176 +given for both the nodes and the arcs.
1.177 +Then Dijkstra's algorithm can be used in connection with \ref SplitNodes
1.178 +as follows.
1.179 +
1.180 +\code
1.181 + typedef SplitNodes<ListDigraph> SplitGraph;
1.182 + SplitGraph sg(g);
1.183 + SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
1.184 + combined_cost(node_cost, arc_cost);
1.185 + SplitGraph::NodeMap<double> dist(sg);
1.186 + dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
1.187 +\endcode
1.188 +
1.189 +Note that this problem can be solved more efficiently with
1.190 +map adaptors.
1.191 +
1.192 +These techniques help writing compact and elegant code, and makes it possible
1.193 +to easily implement complex algorithms based on well tested standard components.
1.194 +For instance, in flow and matching problems the residual graph is of
1.195 +particular importance.
1.196 +Combining \ref ResidualDigraph adaptor with various algorithms, a
1.197 +range of weighted and cardinality optimization methods can be obtained
1.198 +directly.
1.199 +
1.200 +[TRAILER]
1.201 +*/
1.202 +}
1.203 \ No newline at end of file
2.1 --- a/toc.txt Mon Feb 15 00:36:27 2010 +0100
2.2 +++ b/toc.txt Mon Feb 15 01:18:18 2010 +0100
2.3 @@ -16,7 +16,7 @@
2.4 ** sec_digraph_types
2.5 ** sec_undir_graphs
2.6 ** sec_special_graphs
2.7 -*_sec_graph_adaptors
2.8 +* sec_graph_adaptors
2.9 *_sec_tools
2.10 **_sec_lgf
2.11 **_sec_time_count