COIN-OR::LEMON - Graph Library

Changeset 39:31a1a79019bb in lemon-tutorial


Ignore:
Timestamp:
02/21/10 15:07:59 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
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.