36 appear in the size of graph we require to handle, memory or time usage |
36 appear in the size of graph we require to handle, memory or time usage |
37 limitations or in the set of operations through which the graph can be |
37 limitations or in the set of operations through which the graph can be |
38 accessed. LEMON provides several physical graph structures to meet |
38 accessed. LEMON provides several physical graph structures to meet |
39 the diverging requirements of the possible users. In order to save on |
39 the diverging requirements of the possible users. In order to save on |
40 running time or on memory usage, some structures may fail to provide |
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 Alteration of standard containers need a very limited number of |
43 Alteration of standard containers need a very limited number of |
44 operations, these together satisfy the everyday requirements. |
44 operations, these together satisfy the everyday requirements. |
45 In the case of graph structures, different operations are needed which do |
45 In the case of graph structures, different operations are needed which do |
46 not alter the physical graph, but gives another view. If some nodes or |
46 not alter the physical graph, but gives another view. If some nodes or |
47 edges have to be hidden or the reverse oriented graph have to be used, then |
47 arcs have to be hidden or the reverse oriented graph have to be used, then |
48 this is the case. It also may happen that in a flow implementation |
48 this is the case. It also may happen that in a flow implementation |
49 the residual graph can be accessed by another algorithm, or a node-set |
49 the residual graph can be accessed by another algorithm, or a node-set |
50 is to be shrunk for another algorithm. |
50 is to be shrunk for another algorithm. |
51 LEMON also provides a variety of graphs for these requirements called |
51 LEMON also provides a variety of graphs for these requirements called |
52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only |
52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only |
94 \brief Tools to create new maps from existing ones |
94 \brief Tools to create new maps from existing ones |
95 |
95 |
96 This group describes map adaptors that are used to create "implicit" |
96 This group describes map adaptors that are used to create "implicit" |
97 maps from other maps. |
97 maps from other maps. |
98 |
98 |
99 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can |
99 Most of them are \ref lemon::concepts::ReadMap "read-only maps". |
100 make arithmetic operations between one or two maps (negation, scaling, |
100 They can make arithmetic and logical operations between one or two maps |
101 addition, multiplication etc.) or e.g. convert a map to another one |
101 (negation, shifting, addition, multiplication, logical 'and', 'or', |
102 of different Value type. |
102 'not' etc.) or e.g. convert a map to another one of different Value type. |
103 |
103 |
104 The typical usage of this classes is passing implicit maps to |
104 The typical usage of this classes is passing implicit maps to |
105 algorithms. If a function type algorithm is called then the function |
105 algorithms. If a function type algorithm is called then the function |
106 type map adaptors can be used comfortable. For example let's see the |
106 type map adaptors can be used comfortable. For example let's see the |
107 usage of map adaptors with the \c graphToEps() function: |
107 usage of map adaptors with the \c digraphToEps() function. |
108 \code |
108 \code |
109 Color nodeColor(int deg) { |
109 Color nodeColor(int deg) { |
110 if (deg >= 2) { |
110 if (deg >= 2) { |
111 return Color(0.5, 0.0, 0.5); |
111 return Color(0.5, 0.0, 0.5); |
112 } else if (deg == 1) { |
112 } else if (deg == 1) { |
114 } else { |
114 } else { |
115 return Color(0.0, 0.0, 0.0); |
115 return Color(0.0, 0.0, 0.0); |
116 } |
116 } |
117 } |
117 } |
118 |
118 |
119 Graph::NodeMap<int> degree_map(graph); |
119 Digraph::NodeMap<int> degree_map(graph); |
120 |
120 |
121 graphToEps(graph, "graph.eps") |
121 digraphToEps(graph, "graph.eps") |
122 .coords(coords).scaleToA4().undirected() |
122 .coords(coords).scaleToA4().undirected() |
123 .nodeColors(composeMap(functorMap(nodeColor), degree_map)) |
123 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) |
124 .run(); |
124 .run(); |
125 \endcode |
125 \endcode |
126 The \c functorMap() function makes an \c int to \c Color map from the |
126 The \c functorToMap() function makes an \c int to \c Color map from the |
127 \e nodeColor() function. The \c composeMap() compose the \e degree_map |
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 |
128 and the previously created map. The composed map is a proper function to |
129 get color of each node. |
129 get the color of each node. |
130 |
130 |
131 The usage with class type algorithms is little bit harder. In this |
131 The usage with class type algorithms is little bit harder. In this |
132 case the function type map adaptors can not be used, because the |
132 case the function type map adaptors can not be used, because the |
133 function map adaptors give back temporary objects. |
133 function map adaptors give back temporary objects. |
134 \code |
134 \code |
135 Graph graph; |
135 Digraph graph; |
136 |
136 |
137 typedef Graph::EdgeMap<double> DoubleEdgeMap; |
137 typedef Digraph::ArcMap<double> DoubleArcMap; |
138 DoubleEdgeMap length(graph); |
138 DoubleArcMap length(graph); |
139 DoubleEdgeMap speed(graph); |
139 DoubleArcMap speed(graph); |
140 |
140 |
141 typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap; |
141 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; |
142 |
|
143 TimeMap time(length, speed); |
142 TimeMap time(length, speed); |
144 |
143 |
145 Dijkstra<Graph, TimeMap> dijkstra(graph, time); |
144 Dijkstra<Digraph, TimeMap> dijkstra(graph, time); |
146 dijkstra.run(source, target); |
145 dijkstra.run(source, target); |
147 \endcode |
146 \endcode |
148 |
147 We have a length map and a maximum speed map on the arcs of a digraph. |
149 We have a length map and a maximum speed map on a graph. The minimum |
148 The minimum time to pass the arc can be calculated as the division of |
150 time to pass the edge can be calculated as the division of the two |
149 the two maps which can be done implicitly with the \c DivMap template |
151 maps which can be done implicitly with the \c DivMap template |
|
152 class. We use the implicit minimum time map as the length map of the |
150 class. We use the implicit minimum time map as the length map of the |
153 \c Dijkstra algorithm. |
151 \c Dijkstra algorithm. |
154 */ |
152 */ |
155 |
153 |
156 /** |
154 /** |
313 @ingroup algs |
311 @ingroup algs |
314 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
312 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
315 |
313 |
316 This group contains algorithm objects and functions to calculate |
314 This group contains algorithm objects and functions to calculate |
317 matchings in graphs and bipartite graphs. The general matching problem is |
315 matchings in graphs and bipartite graphs. The general matching problem is |
318 finding a subset of the edges which does not shares common endpoints. |
316 finding a subset of the arcs which does not shares common endpoints. |
319 |
317 |
320 There are several different algorithms for calculate matchings in |
318 There are several different algorithms for calculate matchings in |
321 graphs. The matching problems in bipartite graphs are generally |
319 graphs. The matching problems in bipartite graphs are generally |
322 easier than in general graphs. The goal of the matching optimization |
320 easier than in general graphs. The goal of the matching optimization |
323 can be the finding maximum cardinality, maximum weight or minimum cost |
321 can be the finding maximum cardinality, maximum weight or minimum cost |