COIN-OR::LEMON - Graph Library

Changeset 39:31a1a79019bb in lemon-tutorial


Ignore:
Timestamp:
02/21/10 15:07:59 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Fully rework and extend the adaptors section

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • adaptors.dox

    r32 r39  
    2121[PAGE]sec_graph_adaptors[PAGE] Graph Adaptors 
    2222 
    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>. 
     23In typical algorithms and applications related to graphs and networks, 
     24we usually encounter situations in which a specific alteration of a graph 
     25has to be considered. 
     26If some nodes or arcs have to be hidden (maybe temporarily) or the reverse 
     27oriented graph has to be used, then this is the case. 
     28However, actually modifing physical storage of the graph or 
     29making a copy of the graph structure along with the required maps 
     30could be rather expensive (in time or in memory usage) compared to the 
     31operations that should be performed on the altered graph. 
     32In such cases, the LEMON \e graph \e adaptor \e classes could be used. 
     33 
     34 
     35[SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph 
     36 
     37Let us suppose that we have an instance \c g of a directed graph type, say 
     38\ref ListDigraph and an algorithm 
     39\code 
     40  template <typename Digraph> 
     41  int algorithm(const Digraph&); 
     42\endcode 
     43is needed to run on the reverse oriented digraph. 
     44In this situation, a certain adaptor class 
     45\code 
     46  template <typename Digraph> 
     47  class ReverseDigraph; 
     48\endcode 
     49can be used. 
     50 
     51The graph adaptors are special classes that serve for considering other graph 
     52structures in different ways. They can be used exactly the same as "real" 
     53graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all 
     54generic algorithms can be performed on them. However, the adaptor classes 
     55cannot be used alone but only in conjunction with actual graph representations. 
     56They do not alter the physical graph storage, they just give another view of it. 
     57When the methods of the adaptors are called, they use the underlying 
     58graph structures and their operations, thus these classes have only negligible 
     59memory usage and do not perform sophisticated algorithmic actions. 
     60 
     61This technique yields convenient tools that help writing compact and elegant 
     62code, and makes it possible to easily implement complex algorithms based on 
     63well tested standard components. 
     64 
     65For solving the problem introduced above, we could use the follwing code. 
     66 
     67\code 
     68  ListDigraph g; 
     69  ReverseDigraph<ListDigraph> rg(g); 
     70  int result = algorithm(rg); 
     71\endcode 
     72 
     73Note that the original digraph \c g remains untouched during the whole 
     74procedure. 
     75 
     76LEMON also provides simple "creator functions" for the adaptor 
     77classes to make their usage even simpler. 
     78For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph, 
     79thus the above code can be written like this. 
     80 
     81\code 
     82  ListDigraph g; 
     83  int result = algorithm(reverseDigraph(g)); 
     84\endcode 
     85 
     86Another essential feature of the adaptors is that their \c Node and \c Arc 
     87types convert to the original item types. 
     88Therefore, the maps of the original graph can be used in connection with 
     89the adaptor. 
     90 
     91In the following code, Dijksta's algorithm is run on the reverse oriented 
     92graph but using the original node and arc maps. 
     93 
     94\code 
     95  ListDigraph g; 
     96  ListDigraph::ArcMap length(g); 
     97  ListDigraph::NodeMap dist(g); 
     98 
     99  ListDigraph::Node s = g.addNode(); 
     100  // add more nodes and arcs 
     101 
     102  dijkstra(reverseDigraph(g), length).distMap(dist).run(s); 
     103\endcode 
     104 
     105In the above examples, we used \ref ReverseDigraph in such a way that the 
     106underlying digraph was not changed. However, the adaptor class can even be 
     107used for modifying the original graph structure. 
     108It allows adding and deleting arcs or nodes, and these operations are carried 
     109out by calling suitable functions of the underlying digraph (if it supports 
     110them). 
     111 
     112For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the 
     113following form. 
     114\code 
     115  ReverseDigraph(GR& gr); 
     116\endcode 
     117 
     118This means that in a situation, when the modification of the original graph 
     119has to be avoided (e.g. it is given as a const reference), then the adaptor 
     120class has to be instantiated with \c GR set to be \c const type 
     121(e.g. <tt>GR = const %ListDigraph</tt>), as in the following example. 
     122 
    98123\code 
    99124int algorithm1(const ListDigraph& g) { 
     
    103128\endcode 
    104129 
    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 
    121 item types. 
    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 
    134 network for flow and matching problems. 
    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. 
     130\note Modification capabilities are not supported for all adaptors. 
     131E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"), 
     132this makes no sense. 
     133 
     134As a more complex example, let us see how \ref ReverseDigraph can be used 
     135together with a graph search algorithm to decide whether a directed graph is 
     136strongly connected or not. 
     137We exploit the fact the a digraph is strongly connected if and only if 
     138for an arbitrarily selected node \c u, each other node is reachable from 
     139\c u (along a directed path) and \c u is reachable from each node. 
     140The latter condition is the same that each node is reachable from \c u 
     141in the reversed digraph. 
     142 
     143\code 
     144  template <typename Digraph> 
     145  bool stronglyConnected(const Digraph& g) { 
     146    typedef typename Digraph::NodeIt NodeIt; 
     147    NodeIt u(g); 
     148    if (u == INVALID) return true; 
     149 
     150    // Run BFS on the original digraph 
     151    Bfs<Digraph> bfs(g); 
     152    bfs.run(u); 
     153    for (NodeIt n(g); n != INVALID; ++n) { 
     154      if (!bfs.reached(n)) return false; 
     155    } 
     156 
     157    // Run BFS on the reverse oriented digraph 
     158    typedef ReverseDigraph<const Digraph> RDigraph; 
     159    RDigraph rg(g); 
     160    Bfs<RDigraph> rbfs(rg); 
     161    rbfs.run(u); 
     162    for (NodeIt n(g); n != INVALID; ++n) { 
     163      if (!rbfs.reached(n)) return false; 
     164    } 
     165 
     166    return true; 
     167  } 
     168\endcode 
     169 
     170Note that we have to use the adaptor with '<tt>const Digraph</tt>' type, since 
     171\c g is a \c const reference to the original graph structure. 
     172The \ref stronglyConnected() function provided in LEMON has a quite 
     173similar implementation. 
     174 
     175 
     176[SEC]sec_subgraphs[SEC] Subgraph Adaptorts 
     177 
     178Another typical requirement is the use of certain subgraphs of a graph, 
     179or in other words, hiding nodes and/or arcs from a graph. 
     180LEMON provides several convenient adaptors for these purposes. 
     181 
     182\ref FilterArcs can be used when some arcs have to be hidden from a digraph. 
     183A \e filter \e map has to be given to the constructor, which assign \c bool 
     184values to the arcs specifying whether they have to be shown or not in the 
     185subgraph structure. 
     186Suppose we have a \ref ListDigraph structure \c g. 
     187Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.) 
     188are hidden as follows. 
     189 
     190\code 
     191  ListDigraph::ArcMap filter(g, true); 
     192  filter[a1] = false; 
     193  filter[a2] = false; 
     194  // ... 
     195  FilterArcs<ListDigraph> subgraph(g, filter); 
     196\endcode 
     197 
     198The following more complex code runs Dijkstra's algorithm on a digraph 
     199that is obtained from another digraph by hiding all arcs having negative 
     200lengths. 
     201 
     202\code 
     203  ListDigraph::ArcMap<int> length(g); 
     204  ListDigraph::NodeMap<int> dist(g); 
     205 
     206  dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(0)) ), 
     207           length).distMap(dist).run(s); 
     208\endcode 
     209 
     210Note the extensive use of map adaptors and creator functions, which makes 
     211the code really compact and elegant. 
     212 
     213\note Implicit maps and graphs (e.g. created using functions) can only be 
     214used with the function-type interfaces of the algorithms, since they store 
     215only references for the used structures. 
     216 
     217\ref FilterEdges can be used for hiding edges from an undirected graph (like 
     218\ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering 
     219nodes along with the incident arcs or edges in a directed or undirected graph. 
     220If both arcs/edges and nodes have to be hidden, then you could use 
     221\ref SubDigraph or \ref SubGraph adaptors. 
     222 
     223\code 
     224  ListGraph ug; 
     225  ListGraph::NodeMap<bool> node_filter(ug); 
     226  ListGraph::EdgeMap<bool> edge_filter(ug); 
     227   
     228  SubGraph<ListGraph> sg(ug, node_filter, edge_filter); 
     229\endcode 
     230 
     231As you see, we needed two filter maps in this case: one for the nodes and 
     232another for the edges. If a node is hidden, then all of its incident edges 
     233are also considered to be hidden independently of their own filter values. 
     234 
     235The subgraph adaptors also make it possible to modify the filter values 
     236even after the construction of the adaptor class, thus the corresponding 
     237graph items can be hidden or shown on the fly. 
     238The adaptors store references to the filter maps, thus the map values can be 
     239set directly and even by using the \c enable(), \c disable() and \c status() 
     240functions. 
     241 
     242\code 
     243  ListDigraph g; 
     244  ListDigraph::Node x = g.addNode(); 
     245  ListDigraph::Node y = g.addNode(); 
     246  ListDigraph::Node z = g.addNode(); 
     247   
     248  ListDigraph::NodeMap<bool> filter(g, true); 
     249  FilterNodes<ListDigraph> subgraph(g, filter); 
     250  std::cout << countNodes(subgraph) << ", "; 
     251 
     252  filter[x] = false; 
     253  std::cout << countNodes(subgraph) << ", "; 
     254 
     255  subgraph.enable(x); 
     256  subgraph.disable(y); 
     257  subgraph.status(z, !subgraph.status(z)); 
     258  std::cout << countNodes(subgraph) << std::endl; 
     259\endcode 
     260 
     261The above example prints out this line. 
     262\code 
     263  3, 2, 1 
     264\endcode 
     265 
     266Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the 
     267modification of the underlying graph structures unless the graph template 
     268parameter is set to be \c const type. 
     269Moreover the item types of the original graphs and the subgraphs are 
     270convertible to each other. 
     271 
     272The iterators of the subgraph adaptors use the iterators of the original 
     273graph structures in such a way that each item with \c false filter value 
     274is skipped. If both the node and arc sets are filtered, then the arc iterators 
     275check for each arc the status of its end nodes in addition to its own assigned 
     276filter value. If the arc or one of its end nodes is hidden, then the arc 
     277is left out and the next arc is considered. 
     278(It is the same for edges in undirected graphs.) 
     279Therefore, the iterators of these adaptors are significantly slower than the 
     280original iterators. 
     281 
     282Using adaptors, these efficiency aspects should be kept in mind. 
     283For example, if rather complex algorithms have to be performed on a 
     284subgraph (e.g. the nodes and arcs need to be traversed several times), 
     285then it could worth copying the altered graph into an efficient 
     286structure (e.g. \ref StaticDigraph) and run the algorithm on it. 
    140287Note that the adaptor classes can also be used for doing this easily, 
    141288without having to copy the graph manually, as shown in the following 
     
    148295 
    149296  { 
    150     SmartDigraph temp_graph; 
    151     ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g); 
    152     digraphCopy(filterNodes(g, filter_map), temp_graph) 
     297    StaticDigraph tmp_graph; 
     298    ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g); 
     299    digraphCopy(filterNodes(g, filter_map), tmp_graph) 
    153300      .nodeRef(node_ref).run(); 
    154301 
    155     // use temp_graph 
     302    // use tmp_graph 
    156303  } 
    157304\endcode 
    158305 
    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. 
     306\note Using \ref ReverseDigraph could be as efficient as working with the 
     307original graph, but most of the adaptors cannot be so fast, of course.  
     308 
     309 
     310[SEC]sec_other_adaptors[SEC] Other Graph Adaptors 
     311 
     312Two other practical adaptors are \ref Undirector and \ref Orienter. 
     313\ref Undirector makes an undirected graph from a digraph disregarding the 
     314orientations of the arcs. More precisely, an arc of the original digraph 
     315is considered as an edge (and two arcs, as well) in the adaptor. 
     316\ref Orienter can be used for the reverse alteration, it assigns a certain 
     317orientation to each edge of an undirected graph to form a directed graph. 
     318A \c bool edge map of the underlying graph must be given to the constructor 
     319of the class, which define the direction of the arcs in the created adaptor 
     320(with respect to the inherent orientation of the original edges). 
     321 
     322\code 
     323  ListGraph graph; 
     324  ListGraph::EdgeMap<bool> dir_map(graph, true); 
     325  Orienter<ListGraph> directed_graph(graph, dir_map); 
     326\endcode 
     327 
     328LEMON also provides some more complex adaptors, for 
     329instance, \ref SplitNodes, which can be used for splitting each node of a 
     330directed graph into an in-node and an out-node. 
     331Formally, the adaptor replaces each node u in the graph with two nodes, 
     332namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original 
     333graph will correspond to an arc (u<sub>out</sub>,v<sub>in</sub>). 
     334The adaptor also adds an additional bind arc (u<sub>in</sub>,u<sub>out</sub>) 
     335for each node u of the original digraph. 
     336 
     337The aim of this class is to assign costs or capacities to the nodes when using 
     338algorithms which would otherwise consider arc costs or capacities only. 
     339For example, let us suppose that we have a digraph \c g with costs assigned to 
     340both the nodes and the arcs. Then Dijkstra's algorithm can be used in 
     341connection with \ref SplitNodes as follows. 
    176342 
    177343\code 
     
    184350\endcode 
    185351 
    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. 
     352\note This problem can also be solved using map adaptors to create 
     353an implicit arc map that assigns for each arc the sum of its cost 
     354and the cost of its target node. This map can be used with the original 
     355graph more efficiently than using the above solution. 
     356 
     357Another nice application is the problem of finding disjoint paths in 
     358a digraph. 
     359The maximum number of \e edge \e disjoint paths from a source node to 
     360a sink node in a digraph can be easily computed using a maximum flow 
     361algorithm with all arc capacities set to 1. 
     362On the other hand, \e node \e disjoint paths cannot be found directly 
     363using a standard algorithm. 
     364However, \ref SplitNodes adaptor makes it really simple. 
     365If a maximum flow computation is performed on this adaptor, then the 
     366bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs, 
     367thus the found flow will correspond to the union of some node disjoint 
     368paths in terms of the original digraph. 
     369 
     370In flow, circulation and matching problems, the residual network is of 
     371particular importance, which is implemented in \ref ResidualDigraph. 
     372Combining this adaptor with various algorithms, a range of weighted and 
     373cardinality optimization methods can be implemented easily. 
     374 
     375To construct a residual network, a digraph structure, a flow map and a 
     376capacity map have to be given to the constructor of the adaptor as shown 
     377in the following code. 
     378 
     379\code 
     380  ListDigraph g; 
     381  ListDigraph::ArcMap<int> flow(g); 
     382  ListDigraph::ArcMap<int> capacity(g); 
     383 
     384  ResidualDigraph<ListDigraph> res_graph(g, capacity, flow);  
     385\endcode 
     386 
     387\note In fact, this class is implemented using two other adaptors: 
     388\ref Undirector and \ref FilterArcs. 
    196389 
    197390[TRAILER] 
  • toc.txt

    r37 r39  
    2323**_algs_with_maps 
    2424* sec_graph_adaptors 
     25** sec_reverse_digraph 
     26** sec_subgraphs 
     27** sec_other_adaptors 
    2528* sec_lp 
    2629* sec_lgf 
Note: See TracChangeset for help on using the changeset viewer.