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 <typename Digraph>
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 <typename Digraph>
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<ListDigraph> 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<GR>" 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. <tt>GR = const %ListDigraph</tt>), as in the following example.
kpeter@39: 
kpeter@29: \code
kpeter@29: int algorithm1(const ListDigraph& g) {
kpeter@29:   ReverseDigraph<const ListDigraph> 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 <typename Digraph>
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<Digraph> 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<const Digraph> RDigraph;
kpeter@39:     RDigraph rg(g);
kpeter@39:     Bfs<RDigraph> 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 '<tt>const Digraph</tt>' 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<ListDigraph> 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<int> length(g);
kpeter@39:   ListDigraph::NodeMap<int> dist(g);
kpeter@39: 
kpeter@39:   dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(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<bool> node_filter(ug);
kpeter@39:   ListGraph::EdgeMap<bool> edge_filter(ug);
kpeter@39:   
kpeter@39:   SubGraph<ListGraph> 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<bool> filter(g, true);
kpeter@39:   FilterNodes<ListDigraph> 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<bool> 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<StaticDigraph::Node> 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<bool> dir_map(graph, true);
kpeter@39:   Orienter<ListGraph> 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 u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original
kpeter@39: graph will correspond to an arc (u<sub>out</sub>,v<sub>in</sub>).
kpeter@39: The adaptor also adds an additional bind arc (u<sub>in</sub>,u<sub>out</sub>)
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<ListDigraph> SplitGraph;
kpeter@29:   SplitGraph sg(g);
kpeter@29:   SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
kpeter@29:     combined_cost(node_cost, arc_cost);
kpeter@29:   SplitGraph::NodeMap<double> 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<int> flow(g);
kpeter@39:   ListDigraph::ArcMap<int> capacity(g);
kpeter@39: 
kpeter@39:   ResidualDigraph<ListDigraph> 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: }