summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | bz2 | zip | gz |
help

author | Peter Kovacs <kpeter@inf.elte.hu> |

Sat, 15 Mar 2008 23:42:33 +0100 | |

changeset 83 | 3654324ec035 |

parent 82 | bce6c8f93d10 |

child 84 | 8161012eaa61 |

Improvements in groups.dox

- Apply the graph renamings.

- Apply the current map renamings.

- Apply the graph renamings.

- Apply the current map renamings.

doc/groups.dox | file | annotate | diff | comparison | revisions |

1.1 --- a/doc/groups.dox Sat Mar 15 23:39:41 2008 +0100 1.2 +++ b/doc/groups.dox Sat Mar 15 23:42:33 2008 +0100 1.3 @@ -38,13 +38,13 @@ 1.4 accessed. LEMON provides several physical graph structures to meet 1.5 the diverging requirements of the possible users. In order to save on 1.6 running time or on memory usage, some structures may fail to provide 1.7 -some graph features like edge or node deletion. 1.8 +some graph features like arc/edge or node deletion. 1.9 1.10 Alteration of standard containers need a very limited number of 1.11 operations, these together satisfy the everyday requirements. 1.12 In the case of graph structures, different operations are needed which do 1.13 not alter the physical graph, but gives another view. If some nodes or 1.14 -edges have to be hidden or the reverse oriented graph have to be used, then 1.15 +arcs have to be hidden or the reverse oriented graph have to be used, then 1.16 this is the case. It also may happen that in a flow implementation 1.17 the residual graph can be accessed by another algorithm, or a node-set 1.18 is to be shrunk for another algorithm. 1.19 @@ -81,10 +81,10 @@ 1.20 /** 1.21 @defgroup graph_maps Graph Maps 1.22 @ingroup maps 1.23 -\brief Special Graph-Related Maps. 1.24 +\brief Special graph-related maps. 1.25 1.26 This group describes maps that are specifically designed to assign 1.27 -values to the nodes and edges of graphs. 1.28 +values to the nodes and arcs of graphs. 1.29 */ 1.30 1.31 1.32 @@ -96,15 +96,15 @@ 1.33 This group describes map adaptors that are used to create "implicit" 1.34 maps from other maps. 1.35 1.36 -Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can 1.37 -make arithmetic operations between one or two maps (negation, scaling, 1.38 -addition, multiplication etc.) or e.g. convert a map to another one 1.39 -of different Value type. 1.40 +Most of them are \ref lemon::concepts::ReadMap "read-only maps". 1.41 +They can make arithmetic and logical operations between one or two maps 1.42 +(negation, shifting, addition, multiplication, logical 'and', 'or', 1.43 +'not' etc.) or e.g. convert a map to another one of different Value type. 1.44 1.45 The typical usage of this classes is passing implicit maps to 1.46 algorithms. If a function type algorithm is called then the function 1.47 type map adaptors can be used comfortable. For example let's see the 1.48 -usage of map adaptors with the \c graphToEps() function: 1.49 +usage of map adaptors with the \c digraphToEps() function. 1.50 \code 1.51 Color nodeColor(int deg) { 1.52 if (deg >= 2) { 1.53 @@ -116,39 +116,37 @@ 1.54 } 1.55 } 1.56 1.57 - Graph::NodeMap<int> degree_map(graph); 1.58 + Digraph::NodeMap<int> degree_map(graph); 1.59 1.60 - graphToEps(graph, "graph.eps") 1.61 + digraphToEps(graph, "graph.eps") 1.62 .coords(coords).scaleToA4().undirected() 1.63 - .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 1.64 + .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) 1.65 .run(); 1.66 \endcode 1.67 -The \c functorMap() function makes an \c int to \c Color map from the 1.68 +The \c functorToMap() function makes an \c int to \c Color map from the 1.69 \e nodeColor() function. The \c composeMap() compose the \e degree_map 1.70 -and the previous created map. The composed map is proper function to 1.71 -get color of each node. 1.72 +and the previously created map. The composed map is a proper function to 1.73 +get the color of each node. 1.74 1.75 The usage with class type algorithms is little bit harder. In this 1.76 case the function type map adaptors can not be used, because the 1.77 function map adaptors give back temporary objects. 1.78 \code 1.79 - Graph graph; 1.80 - 1.81 - typedef Graph::EdgeMap<double> DoubleEdgeMap; 1.82 - DoubleEdgeMap length(graph); 1.83 - DoubleEdgeMap speed(graph); 1.84 - 1.85 - typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap; 1.86 - 1.87 + Digraph graph; 1.88 + 1.89 + typedef Digraph::ArcMap<double> DoubleArcMap; 1.90 + DoubleArcMap length(graph); 1.91 + DoubleArcMap speed(graph); 1.92 + 1.93 + typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; 1.94 TimeMap time(length, speed); 1.95 1.96 - Dijkstra<Graph, TimeMap> dijkstra(graph, time); 1.97 + Dijkstra<Digraph, TimeMap> dijkstra(graph, time); 1.98 dijkstra.run(source, target); 1.99 \endcode 1.100 - 1.101 -We have a length map and a maximum speed map on a graph. The minimum 1.102 -time to pass the edge can be calculated as the division of the two 1.103 -maps which can be done implicitly with the \c DivMap template 1.104 +We have a length map and a maximum speed map on the arcs of a digraph. 1.105 +The minimum time to pass the arc can be calculated as the division of 1.106 +the two maps which can be done implicitly with the \c DivMap template 1.107 class. We use the implicit minimum time map as the length map of the 1.108 \c Dijkstra algorithm. 1.109 */ 1.110 @@ -315,7 +313,7 @@ 1.111 1.112 This group contains algorithm objects and functions to calculate 1.113 matchings in graphs and bipartite graphs. The general matching problem is 1.114 -finding a subset of the edges which does not shares common endpoints. 1.115 +finding a subset of the arcs which does not shares common endpoints. 1.116 1.117 There are several different algorithms for calculate matchings in 1.118 graphs. The matching problems in bipartite graphs are generally