doc/groups.dox
changeset 127 1c9a9e2f7d4d
parent 71 9df0fe5e5109
child 156 e561aa7675de
equal deleted inserted replaced
3:352f3a9637d7 4:38442f527c8c
    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 
    79 */
    79 */
    80 
    80 
    81 /**
    81 /**
    82 @defgroup graph_maps Graph Maps 
    82 @defgroup graph_maps Graph Maps 
    83 @ingroup maps
    83 @ingroup maps
    84 \brief Special Graph-Related Maps.
    84 \brief Special graph-related maps.
    85 
    85 
    86 This group describes maps that are specifically designed to assign
    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 \defgroup map_adaptors Map Adaptors
    92 \defgroup map_adaptors Map Adaptors
    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