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@39: In typical algorithms and applications related to graphs and networks, kpeter@39: we usually encounter situations in which a specific alteration of a graph kpeter@39: has to be considered. kpeter@39: If some nodes or arcs have to be hidden (maybe temporarily) or the reverse kpeter@39: oriented graph has to be used, then this is the case. kpeter@39: However, actually modifing physical storage of the graph or kpeter@39: making a copy of the graph structure along with the required maps kpeter@39: could be rather expensive (in time or in memory usage) compared to the kpeter@39: operations that should be performed on the altered graph. kpeter@39: In such cases, the LEMON \e graph \e adaptor \e classes could be used. kpeter@29: kpeter@39: [SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph kpeter@29: kpeter@39: Let us suppose that we have an instance \c g of a directed graph type, say kpeter@39: \ref ListDigraph and an algorithm kpeter@29: \code kpeter@39: template kpeter@39: int algorithm(const Digraph&); kpeter@29: \endcode kpeter@39: is needed to run on the reverse oriented digraph. kpeter@39: In this situation, a certain adaptor class kpeter@29: \code kpeter@39: template kpeter@39: class ReverseDigraph; kpeter@29: \endcode kpeter@39: can be used. kpeter@39: kpeter@39: The graph adaptors are special classes that serve for considering other graph kpeter@39: structures in different ways. They can be used exactly the same as "real" kpeter@39: graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all kpeter@39: generic algorithms can be performed on them. However, the adaptor classes kpeter@39: cannot be used alone but only in conjunction with actual graph representations. kpeter@39: They do not alter the physical graph storage, they just give another view of it. kpeter@39: When the methods of the adaptors are called, they use the underlying kpeter@39: graph structures and their operations, thus these classes have only negligible kpeter@39: memory usage and do not perform sophisticated algorithmic actions. kpeter@39: kpeter@39: This technique yields convenient tools that help writing compact and elegant kpeter@39: code, and makes it possible to easily implement complex algorithms based on kpeter@39: well tested standard components. kpeter@39: kpeter@39: For solving the problem introduced above, we could use the follwing code. kpeter@39: kpeter@29: \code kpeter@39: ListDigraph g; kpeter@39: ReverseDigraph rg(g); kpeter@39: int result = algorithm(rg); kpeter@29: \endcode kpeter@29: kpeter@39: Note that the original digraph \c g remains untouched during the whole kpeter@39: procedure. kpeter@29: kpeter@39: LEMON also provides simple "creator functions" for the adaptor kpeter@39: classes to make their usage even simpler. kpeter@39: For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph, kpeter@39: thus the above code can be written like this. kpeter@29: kpeter@29: \code kpeter@39: ListDigraph g; kpeter@39: int result = algorithm(reverseDigraph(g)); kpeter@29: \endcode kpeter@39: kpeter@39: Another essential feature of the adaptors is that their \c Node and \c Arc kpeter@39: types convert to the original item types. kpeter@39: Therefore, the maps of the original graph can be used in connection with kpeter@39: the adaptor. kpeter@39: kpeter@39: In the following code, Dijksta's algorithm is run on the reverse oriented kpeter@39: graph but using the original node and arc maps. kpeter@39: kpeter@39: \code kpeter@39: ListDigraph g; kpeter@39: ListDigraph::ArcMap length(g); kpeter@39: ListDigraph::NodeMap dist(g); kpeter@39: kpeter@39: ListDigraph::Node s = g.addNode(); kpeter@39: // add more nodes and arcs kpeter@39: kpeter@39: dijkstra(reverseDigraph(g), length).distMap(dist).run(s); kpeter@39: \endcode kpeter@39: kpeter@39: In the above examples, we used \ref ReverseDigraph in such a way that the kpeter@39: underlying digraph was not changed. However, the adaptor class can even be kpeter@39: used for modifying the original graph structure. kpeter@39: It allows adding and deleting arcs or nodes, and these operations are carried kpeter@39: out by calling suitable functions of the underlying digraph (if it supports kpeter@39: them). kpeter@39: kpeter@39: For this, \ref ReverseDigraph "ReverseDigraph" has a constructor of the kpeter@39: following form. kpeter@39: \code kpeter@39: ReverseDigraph(GR& gr); kpeter@39: \endcode kpeter@39: kpeter@39: This means that in a situation, when the modification of the original graph kpeter@39: has to be avoided (e.g. it is given as a const reference), then the adaptor kpeter@39: class has to be instantiated with \c GR set to be \c const type kpeter@39: (e.g. GR = const %ListDigraph), as in the following example. kpeter@39: 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@39: \note Modification capabilities are not supported for all adaptors. kpeter@39: E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"), kpeter@39: this makes no sense. kpeter@29: kpeter@39: As a more complex example, let us see how \ref ReverseDigraph can be used kpeter@39: together with a graph search algorithm to decide whether a directed graph is kpeter@39: strongly connected or not. kpeter@39: We exploit the fact the a digraph is strongly connected if and only if kpeter@39: for an arbitrarily selected node \c u, each other node is reachable from kpeter@39: \c u (along a directed path) and \c u is reachable from each node. kpeter@39: The latter condition is the same that each node is reachable from \c u kpeter@39: in the reversed digraph. kpeter@29: kpeter@29: \code kpeter@39: template kpeter@39: bool stronglyConnected(const Digraph& g) { kpeter@39: typedef typename Digraph::NodeIt NodeIt; kpeter@39: NodeIt u(g); kpeter@39: if (u == INVALID) return true; kpeter@39: kpeter@39: // Run BFS on the original digraph kpeter@39: Bfs bfs(g); kpeter@39: bfs.run(u); kpeter@39: for (NodeIt n(g); n != INVALID; ++n) { kpeter@39: if (!bfs.reached(n)) return false; kpeter@39: } kpeter@39: kpeter@39: // Run BFS on the reverse oriented digraph kpeter@39: typedef ReverseDigraph RDigraph; kpeter@39: RDigraph rg(g); kpeter@39: Bfs rbfs(rg); kpeter@39: rbfs.run(u); kpeter@39: for (NodeIt n(g); n != INVALID; ++n) { kpeter@39: if (!rbfs.reached(n)) return false; kpeter@39: } kpeter@39: kpeter@39: return true; kpeter@39: } kpeter@29: \endcode kpeter@29: kpeter@39: Note that we have to use the adaptor with 'const Digraph' type, since kpeter@39: \c g is a \c const reference to the original graph structure. kpeter@39: The \ref stronglyConnected() function provided in LEMON has a quite kpeter@39: similar implementation. kpeter@29: kpeter@39: kpeter@39: [SEC]sec_subgraphs[SEC] Subgraph Adaptorts kpeter@39: kpeter@39: Another typical requirement is the use of certain subgraphs of a graph, kpeter@39: or in other words, hiding nodes and/or arcs from a graph. kpeter@39: LEMON provides several convenient adaptors for these purposes. kpeter@45: In the following image, a \ref SubDigraph adaptor is applied to an kpeter@41: underlying digraph structure to obtain a suitable subgraph. kpeter@41: kpeter@41: \image html adaptors1.png kpeter@41: \image latex adaptors1.eps "SubDigraph adaptor" width=\textwidth kpeter@39: kpeter@39: \ref FilterArcs can be used when some arcs have to be hidden from a digraph. kpeter@39: A \e filter \e map has to be given to the constructor, which assign \c bool kpeter@39: values to the arcs specifying whether they have to be shown or not in the kpeter@39: subgraph structure. kpeter@39: Suppose we have a \ref ListDigraph structure \c g. kpeter@39: Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.) kpeter@39: are hidden as follows. kpeter@39: kpeter@39: \code kpeter@39: ListDigraph::ArcMap filter(g, true); kpeter@39: filter[a1] = false; kpeter@39: filter[a2] = false; kpeter@39: // ... kpeter@39: FilterArcs subgraph(g, filter); kpeter@39: \endcode kpeter@39: kpeter@39: The following more complex code runs Dijkstra's algorithm on a digraph kpeter@39: that is obtained from another digraph by hiding all arcs having negative kpeter@39: lengths. kpeter@39: kpeter@39: \code kpeter@39: ListDigraph::ArcMap length(g); kpeter@39: ListDigraph::NodeMap dist(g); kpeter@39: kpeter@39: dijkstra(filterArcs( g, lessMap(length, constMap(0)) ), kpeter@39: length).distMap(dist).run(s); kpeter@39: \endcode kpeter@39: kpeter@39: Note the extensive use of map adaptors and creator functions, which makes kpeter@39: the code really compact and elegant. kpeter@39: kpeter@39: \note Implicit maps and graphs (e.g. created using functions) can only be kpeter@39: used with the function-type interfaces of the algorithms, since they store kpeter@39: only references for the used structures. kpeter@39: kpeter@39: \ref FilterEdges can be used for hiding edges from an undirected graph (like kpeter@39: \ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering kpeter@39: nodes along with the incident arcs or edges in a directed or undirected graph. kpeter@39: If both arcs/edges and nodes have to be hidden, then you could use kpeter@39: \ref SubDigraph or \ref SubGraph adaptors. kpeter@39: kpeter@39: \code kpeter@39: ListGraph ug; kpeter@39: ListGraph::NodeMap node_filter(ug); kpeter@39: ListGraph::EdgeMap edge_filter(ug); kpeter@39: kpeter@39: SubGraph sg(ug, node_filter, edge_filter); kpeter@39: \endcode kpeter@39: kpeter@39: As you see, we needed two filter maps in this case: one for the nodes and kpeter@39: another for the edges. If a node is hidden, then all of its incident edges kpeter@39: are also considered to be hidden independently of their own filter values. kpeter@39: kpeter@39: The subgraph adaptors also make it possible to modify the filter values kpeter@39: even after the construction of the adaptor class, thus the corresponding kpeter@39: graph items can be hidden or shown on the fly. kpeter@39: The adaptors store references to the filter maps, thus the map values can be kpeter@39: set directly and even by using the \c enable(), \c disable() and \c status() kpeter@39: functions. kpeter@39: kpeter@39: \code kpeter@39: ListDigraph g; kpeter@39: ListDigraph::Node x = g.addNode(); kpeter@39: ListDigraph::Node y = g.addNode(); kpeter@39: ListDigraph::Node z = g.addNode(); kpeter@39: kpeter@39: ListDigraph::NodeMap filter(g, true); kpeter@39: FilterNodes subgraph(g, filter); kpeter@39: std::cout << countNodes(subgraph) << ", "; kpeter@39: kpeter@39: filter[x] = false; kpeter@39: std::cout << countNodes(subgraph) << ", "; kpeter@39: kpeter@39: subgraph.enable(x); kpeter@39: subgraph.disable(y); kpeter@39: subgraph.status(z, !subgraph.status(z)); kpeter@39: std::cout << countNodes(subgraph) << std::endl; kpeter@39: \endcode kpeter@39: kpeter@39: The above example prints out this line. kpeter@39: \code kpeter@39: 3, 2, 1 kpeter@39: \endcode kpeter@39: kpeter@39: Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the kpeter@39: modification of the underlying graph structures unless the graph template kpeter@39: parameter is set to be \c const type. kpeter@39: Moreover the item types of the original graphs and the subgraphs are kpeter@39: convertible to each other. kpeter@39: kpeter@39: The iterators of the subgraph adaptors use the iterators of the original kpeter@39: graph structures in such a way that each item with \c false filter value kpeter@39: is skipped. If both the node and arc sets are filtered, then the arc iterators kpeter@39: check for each arc the status of its end nodes in addition to its own assigned kpeter@39: filter value. If the arc or one of its end nodes is hidden, then the arc kpeter@39: is left out and the next arc is considered. kpeter@39: (It is the same for edges in undirected graphs.) kpeter@39: Therefore, the iterators of these adaptors are significantly slower than the kpeter@39: original iterators. kpeter@39: kpeter@39: Using adaptors, these efficiency aspects should be kept in mind. kpeter@39: For example, if rather complex algorithms have to be performed on a kpeter@39: subgraph (e.g. the nodes and arcs need to be traversed several times), kpeter@39: then it could worth copying the altered graph into an efficient kpeter@39: structure (e.g. \ref StaticDigraph) 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@39: StaticDigraph tmp_graph; kpeter@39: ListDigraph::NodeMap node_ref(g); kpeter@39: digraphCopy(filterNodes(g, filter_map), tmp_graph) kpeter@29: .nodeRef(node_ref).run(); kpeter@29: kpeter@39: // use tmp_graph kpeter@29: } kpeter@29: \endcode kpeter@29: kpeter@39: \note Using \ref ReverseDigraph could be as efficient as working with the kpeter@39: original graph, but most of the adaptors cannot be so fast, of course. kpeter@29: kpeter@29: kpeter@39: [SEC]sec_other_adaptors[SEC] Other Graph Adaptors kpeter@39: kpeter@39: Two other practical adaptors are \ref Undirector and \ref Orienter. kpeter@39: \ref Undirector makes an undirected graph from a digraph disregarding the kpeter@39: orientations of the arcs. More precisely, an arc of the original digraph kpeter@39: is considered as an edge (and two arcs, as well) in the adaptor. kpeter@39: \ref Orienter can be used for the reverse alteration, it assigns a certain kpeter@39: orientation to each edge of an undirected graph to form a directed graph. kpeter@39: A \c bool edge map of the underlying graph must be given to the constructor kpeter@39: of the class, which define the direction of the arcs in the created adaptor kpeter@39: (with respect to the inherent orientation of the original edges). kpeter@39: kpeter@39: \code kpeter@39: ListGraph graph; kpeter@39: ListGraph::EdgeMap dir_map(graph, true); kpeter@39: Orienter directed_graph(graph, dir_map); kpeter@39: \endcode kpeter@39: kpeter@41: Sine the adaptor classes conform to the \ref graph_concepts "graph concepts", kpeter@41: we can even apply an adaptor to another one. kpeter@41: The following image illustrates a situation when a \ref SubDigraph and an kpeter@45: \ref Undirector adaptor is applied to a digraph. kpeter@41: kpeter@41: \image html adaptors2.png kpeter@41: \image latex adaptors2.eps "Arc disjoint paths" width=\textwidth kpeter@41: kpeter@39: LEMON also provides some more complex adaptors, for kpeter@39: instance, \ref SplitNodes, which can be used for splitting each node of a kpeter@39: directed graph into an in-node and an out-node. kpeter@39: Formally, the adaptor replaces each node u in the graph with two nodes, kpeter@39: namely uin and uout. Each arc (u,v) of the original kpeter@39: graph will correspond to an arc (uout,vin). kpeter@39: The adaptor also adds an additional bind arc (uin,uout) kpeter@39: for each node u of the original digraph. kpeter@39: kpeter@39: The aim of this class is to assign costs or capacities to the nodes when using kpeter@39: algorithms which would otherwise consider arc costs or capacities only. kpeter@39: For example, let us suppose that we have a digraph \c g with costs assigned to kpeter@39: both the nodes and the arcs. Then Dijkstra's algorithm can be used in kpeter@39: connection with \ref SplitNodes 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@39: \note This problem can also be solved using map adaptors to create kpeter@39: an implicit arc map that assigns for each arc the sum of its cost kpeter@39: and the cost of its target node. This map can be used with the original kpeter@39: graph more efficiently than using the above solution. kpeter@29: kpeter@39: Another nice application is the problem of finding disjoint paths in kpeter@39: a digraph. kpeter@39: The maximum number of \e edge \e disjoint paths from a source node to kpeter@39: a sink node in a digraph can be easily computed using a maximum flow kpeter@39: algorithm with all arc capacities set to 1. kpeter@40: For example, in the following digraph, four arc disjoint paths can be found kpeter@40: from the node on the left to the node on the right. kpeter@40: kpeter@40: \image html splitnodes1.png kpeter@40: \image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth kpeter@40: kpeter@39: On the other hand, \e node \e disjoint paths cannot be found directly kpeter@39: using a standard algorithm. kpeter@39: However, \ref SplitNodes adaptor makes it really simple. kpeter@39: If a maximum flow computation is performed on this adaptor, then the kpeter@39: bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs, kpeter@39: thus the found flow will correspond to the union of some node disjoint kpeter@39: paths in terms of the original digraph. kpeter@40: For example, in the above digraph, there are only three node disjoint paths. kpeter@40: kpeter@40: \image html splitnodes2.png kpeter@40: \image latex splitnodes2.eps "Node disjoint paths" width=\textwidth kpeter@39: kpeter@39: In flow, circulation and matching problems, the residual network is of kpeter@39: particular importance, which is implemented in \ref ResidualDigraph. kpeter@39: Combining this adaptor with various algorithms, a range of weighted and kpeter@39: cardinality optimization methods can be implemented easily. kpeter@39: kpeter@39: To construct a residual network, a digraph structure, a flow map and a kpeter@39: capacity map have to be given to the constructor of the adaptor as shown kpeter@39: in the following code. kpeter@39: kpeter@39: \code kpeter@39: ListDigraph g; kpeter@39: ListDigraph::ArcMap flow(g); kpeter@39: ListDigraph::ArcMap capacity(g); kpeter@39: kpeter@39: ResidualDigraph res_graph(g, capacity, flow); kpeter@39: \endcode kpeter@39: kpeter@39: \note In fact, this class is implemented using two other adaptors: kpeter@39: \ref Undirector and \ref FilterArcs. kpeter@29: kpeter@29: [TRAILER] kpeter@29: */ kpeter@32: }