Changeset - r83:3654324ec035
« 82:bce6c8
84:816101 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Improvements in groups.dox - Apply the graph renamings. - Apply the current map renamings.
0 1 0
default
1 file changed with 27 insertions and 29 deletions:
doc/groups.dox
27
29
↑ Collapse diff ↑
doc/groups.dox
Ignore white space 12 line context
... ... 
@@ -35,19 +35,19 @@
35 35 
usage of different physical graph implementations. These differences
36 36 
appear in the size of graph we require to handle, memory or time usage
37 37 
limitations or in the set of operations through which the graph can be
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
	
	
		
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
	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. 


			




	51
	51
	
		
LEMON also provides a variety of graphs for these requirements called 


			




	52
	52
	
		
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 


			




	53
	53
	
		
in conjunction with other graph representations. 


			




	...
	...
	
		
@@ -78,80 +78,78 @@


			




	78
	78
	
		
new maps from existing ones.


			




	79
	79
	
		
*/


			




	80
	80
	
		

			




	81
	81
	
		
/**


			




	82
	82
	
		
@defgroup graph_maps Graph Maps 


			




	83
	83
	
		
@ingroup maps


			




	84
	
	
		
\brief Special Graph-Related Maps.


			




	
	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 edges of graphs.


			




	
	87
	
		
values to the nodes and arcs of graphs.


			




	88
	88
	
		
*/


			




	89
	89
	
		

			




	90
	90
	
		

			




	91
	91
	
		
/**


			




	92
	92
	
		
\defgroup map_adaptors Map Adaptors


			




	93
	93
	
		
\ingroup maps


			




	94
	94
	
		
\brief Tools to create new maps from existing ones


			




	95
	95
	
		

			




	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 graphToEps() function:


			




	
	107
	
		
usage of map adaptors with the \c digraphToEps() function.


			




	108
	108
	
		
\code


			




	109
	109
	
		
  Color nodeColor(int deg) {


			




	110
	110
	
		
    if (deg >= 2) {


			




	111
	111
	
		
      return Color(0.5, 0.0, 0.5);


			




	112
	112
	
		
    } else if (deg == 1) {


			




	113
	113
	
		
      return Color(1.0, 0.5, 1.0);


			




	114
	114
	
		
    } else {


			




	115
	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
	122
	
		
    .coords(coords).scaleToA4().undirected()


			




	123
	
	
		
    .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 


			




	
	123
	
		
    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))


			




	124
	124
	
		
    .run();


			




	125
	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
	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<Graph, TimeMap> dijkstra(graph, time);


			




	
	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
	
		
*/


			




	155
	153
	
		

			




	156
	154
	
		
/**


			




	157
	155
	
		
@defgroup matrices Matrices 


			




	...
	...
	
		
@@ -312,13 +310,13 @@


			




	312
	310
	
		
@defgroup matching Matching algorithms 


			




	313
	311
	
		
@ingroup algs


			




	314
	312
	
		
\brief Algorithms for finding matchings in graphs and bipartite graphs.


			




	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 edges which does not shares common endpoints.


			




	
	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


			




	322
	320
	
		
easier than in general graphs. The goal of the matching optimization


			




	323
	321
	
		
can be the finding maximum cardinality, maximum weight or minimum cost


			




	324
	322
	
		
matching. The search can be constrained to find perfect or


			




        

    






    
    



    


    

     
    
0 comments (0 inline)