r83:3654324ec035
Sat, 15 Mar 2008 23:42:33
[Not Reviewed]
0 comments (0 inline)
0
1
0
27
29
| ... | ... |
@@ -38,13 +38,13 @@ |
| 38 | 38 |
accessed. LEMON provides several physical graph structures to meet |
| 39 | 39 |
the diverging requirements of the possible users. In order to save on |
| 40 | 40 |
running time or on memory usage, some structures may fail to provide |
| 41 |
some graph features like edge or node deletion. |
|
| 41 |
some graph features like arc/edge or node deletion. |
|
| 42 | 42 |
|
| 43 | 43 |
Alteration of standard containers need a very limited number of |
| 44 | 44 |
operations, these together satisfy the everyday requirements. |
| 45 | 45 |
In the case of graph structures, different operations are needed which do |
| 46 | 46 |
not alter the physical graph, but gives another view. If some nodes or |
| 47 |
|
|
| 47 |
arcs have to be hidden or the reverse oriented graph have to be used, then |
|
| 48 | 48 |
this is the case. It also may happen that in a flow implementation |
| 49 | 49 |
the residual graph can be accessed by another algorithm, or a node-set |
| 50 | 50 |
is to be shrunk for another algorithm. |
| ... | ... |
@@ -81,10 +81,10 @@ |
| 81 | 81 |
/** |
| 82 | 82 |
@defgroup graph_maps Graph Maps |
| 83 | 83 |
@ingroup maps |
| 84 |
\brief Special |
|
| 84 |
\brief Special graph-related maps. |
|
| 85 | 85 |
|
| 86 | 86 |
This group describes maps that are specifically designed to assign |
| 87 |
values to the nodes and |
|
| 87 |
values to the nodes and arcs of graphs. |
|
| 88 | 88 |
*/ |
| 89 | 89 |
|
| 90 | 90 |
|
| ... | ... |
@@ -96,15 +96,15 @@ |
| 96 | 96 |
This group describes map adaptors that are used to create "implicit" |
| 97 | 97 |
maps from other maps. |
| 98 | 98 |
|
| 99 |
Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can |
|
| 100 |
make arithmetic operations between one or two maps (negation, scaling, |
|
| 101 |
addition, multiplication etc.) or e.g. convert a map to another one |
|
| 102 |
of different Value type. |
|
| 99 |
Most of them are \ref lemon::concepts::ReadMap "read-only maps". |
|
| 100 |
They can make arithmetic and logical operations between one or two maps |
|
| 101 |
(negation, shifting, addition, multiplication, logical 'and', 'or', |
|
| 102 |
'not' etc.) or e.g. convert a map to another one of different Value type. |
|
| 103 | 103 |
|
| 104 | 104 |
The typical usage of this classes is passing implicit maps to |
| 105 | 105 |
algorithms. If a function type algorithm is called then the function |
| 106 | 106 |
type map adaptors can be used comfortable. For example let's see the |
| 107 |
usage of map adaptors with the \c |
|
| 107 |
usage of map adaptors with the \c digraphToEps() function. |
|
| 108 | 108 |
\code |
| 109 | 109 |
Color nodeColor(int deg) {
|
| 110 | 110 |
if (deg >= 2) {
|
| ... | ... |
@@ -116,39 +116,37 @@ |
| 116 | 116 |
} |
| 117 | 117 |
} |
| 118 | 118 |
|
| 119 |
|
|
| 119 |
Digraph::NodeMap<int> degree_map(graph); |
|
| 120 | 120 |
|
| 121 |
|
|
| 121 |
digraphToEps(graph, "graph.eps") |
|
| 122 | 122 |
.coords(coords).scaleToA4().undirected() |
| 123 |
.nodeColors(composeMap( |
|
| 123 |
.nodeColors(composeMap(functorToMap(nodeColor), degree_map)) |
|
| 124 | 124 |
.run(); |
| 125 | 125 |
\endcode |
| 126 |
The \c |
|
| 126 |
The \c functorToMap() function makes an \c int to \c Color map from the |
|
| 127 | 127 |
\e nodeColor() function. The \c composeMap() compose the \e degree_map |
| 128 |
and the previous created map. The composed map is proper function to |
|
| 129 |
get color of each node. |
|
| 128 |
and the previously created map. The composed map is a proper function to |
|
| 129 |
get the color of each node. |
|
| 130 | 130 |
|
| 131 | 131 |
The usage with class type algorithms is little bit harder. In this |
| 132 | 132 |
case the function type map adaptors can not be used, because the |
| 133 | 133 |
function map adaptors give back temporary objects. |
| 134 | 134 |
\code |
| 135 |
Graph graph; |
|
| 136 |
|
|
| 137 |
typedef Graph::EdgeMap<double> DoubleEdgeMap; |
|
| 138 |
DoubleEdgeMap length(graph); |
|
| 139 |
DoubleEdgeMap speed(graph); |
|
| 140 |
|
|
| 141 |
typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap; |
|
| 142 |
|
|
| 135 |
Digraph graph; |
|
| 136 |
|
|
| 137 |
typedef Digraph::ArcMap<double> DoubleArcMap; |
|
| 138 |
DoubleArcMap length(graph); |
|
| 139 |
DoubleArcMap speed(graph); |
|
| 140 |
|
|
| 141 |
typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; |
|
| 143 | 142 |
TimeMap time(length, speed); |
| 144 | 143 |
|
| 145 |
Dijkstra< |
|
| 144 |
Dijkstra<Digraph, TimeMap> dijkstra(graph, time); |
|
| 146 | 145 |
dijkstra.run(source, target); |
| 147 | 146 |
\endcode |
| 148 |
|
|
| 149 |
We have a length map and a maximum speed map on a graph. The minimum |
|
| 150 |
time to pass the edge can be calculated as the division of the two |
|
| 151 |
maps which can be done implicitly with the \c DivMap template |
|
| 147 |
We have a length map and a maximum speed map on the arcs of a digraph. |
|
| 148 |
The minimum time to pass the arc can be calculated as the division of |
|
| 149 |
the two maps which can be done implicitly with the \c DivMap template |
|
| 152 | 150 |
class. We use the implicit minimum time map as the length map of the |
| 153 | 151 |
\c Dijkstra algorithm. |
| 154 | 152 |
*/ |
| ... | ... |
@@ -315,7 +313,7 @@ |
| 315 | 313 |
|
| 316 | 314 |
This group contains algorithm objects and functions to calculate |
| 317 | 315 |
matchings in graphs and bipartite graphs. The general matching problem is |
| 318 |
finding a subset of the |
|
| 316 |
finding a subset of the arcs which does not shares common endpoints. |
|
| 319 | 317 |
|
| 320 | 318 |
There are several different algorithms for calculate matchings in |
| 321 | 319 |
graphs. The matching problems in bipartite graphs are generally |
0 comments (0 inline)