Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 316)
+++ doc/Makefile.am (revision 317)
@@ -8,4 +8,5 @@
doc/license.dox \
doc/mainpage.dox \
+ doc/migration.dox \
doc/named-param.dox \
doc/namespaces.dox \
Index: doc/groups.dox
===================================================================
--- doc/groups.dox (revision 236)
+++ doc/groups.dox (revision 314)
@@ -55,5 +55,7 @@
You are free to use the graph structure that fit your requirements
the best, most graph algorithms and auxiliary data structures can be used
-with any graph structures.
+with any graph structure.
+
+See also: \ref graph_concepts "Graph Structure Concepts".
*/
@@ -75,6 +77,8 @@
This group describes the map structures implemented in LEMON.
-LEMON provides several special purpose maps that e.g. combine
+LEMON provides several special purpose maps and map adaptors that e.g. combine
new maps from existing ones.
+
+See also: \ref map_concepts "Map Concepts".
*/
@@ -87,5 +91,4 @@
values to the nodes and arcs of graphs.
*/
-
/**
@@ -105,5 +108,5 @@
algorithms. If a function type algorithm is called then the function
type map adaptors can be used comfortable. For example let's see the
-usage of map adaptors with the \c digraphToEps() function.
+usage of map adaptors with the \c graphToEps() function.
\code
Color nodeColor(int deg) {
@@ -119,5 +122,5 @@
Digraph::NodeMap degree_map(graph);
- digraphToEps(graph, "graph.eps")
+ graphToEps(graph, "graph.eps")
.coords(coords).scaleToA4().undirected()
.nodeColors(composeMap(functorToMap(nodeColor), degree_map))
@@ -125,5 +128,5 @@
\endcode
The \c functorToMap() function makes an \c int to \c Color map from the
-\e nodeColor() function. The \c composeMap() compose the \e degree_map
+\c nodeColor() function. The \c composeMap() compose the \c degree_map
and the previously created map. The composed map is a proper function to
get the color of each node.
@@ -174,5 +177,4 @@
\sa lemon::concepts::Path
-
*/
@@ -186,5 +188,4 @@
*/
-
/**
@defgroup algs Algorithms
@@ -202,9 +203,9 @@
This group describes the common graph search algorithms like
-Breadth-first search (Bfs) and Depth-first search (Dfs).
-*/
-
-/**
-@defgroup shortest_path Shortest Path algorithms
+Breadth-First Search (BFS) and Depth-First Search (DFS).
+*/
+
+/**
+@defgroup shortest_path Shortest Path Algorithms
@ingroup algs
\brief Algorithms for finding shortest paths.
@@ -214,5 +215,5 @@
/**
-@defgroup max_flow Maximum Flow algorithms
+@defgroup max_flow Maximum Flow Algorithms
@ingroup algs
\brief Algorithms for finding maximum flows.
@@ -242,9 +243,8 @@
provides functions to query the minimum cut, which is the dual linear
programming problem of the maximum flow.
-
-*/
-
-/**
-@defgroup min_cost_flow Minimum Cost Flow algorithms
+*/
+
+/**
+@defgroup min_cost_flow Minimum Cost Flow Algorithms
@ingroup algs
@@ -256,5 +256,5 @@
/**
-@defgroup min_cut Minimum Cut algorithms
+@defgroup min_cut Minimum Cut Algorithms
@ingroup algs
@@ -283,9 +283,8 @@
If you want to find minimum cut just between two distinict nodes,
please see the \ref max_flow "Maximum Flow page".
-
-*/
-
-/**
-@defgroup graph_prop Connectivity and other graph properties
+*/
+
+/**
+@defgroup graph_prop Connectivity and Other Graph Properties
@ingroup algs
\brief Algorithms for discovering the graph properties
@@ -299,5 +298,5 @@
/**
-@defgroup planar Planarity embedding and drawing
+@defgroup planar Planarity Embedding and Drawing
@ingroup algs
\brief Algorithms for planarity checking, embedding and drawing
@@ -311,5 +310,5 @@
/**
-@defgroup matching Matching algorithms
+@defgroup matching Matching Algorithms
@ingroup algs
\brief Algorithms for finding matchings in graphs and bipartite graphs.
@@ -349,9 +348,8 @@
\image html bipartite_matching.png
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
-
-*/
-
-/**
-@defgroup spantree Minimum Spanning Tree algorithms
+*/
+
+/**
+@defgroup spantree Minimum Spanning Tree Algorithms
@ingroup algs
\brief Algorithms for finding a minimum cost spanning tree in a graph.
@@ -361,7 +359,6 @@
*/
-
-/**
-@defgroup auxalg Auxiliary algorithms
+/**
+@defgroup auxalg Auxiliary Algorithms
@ingroup algs
\brief Auxiliary algorithms implemented in LEMON.
@@ -372,5 +369,6 @@
/**
-@defgroup approx Approximation algorithms
+@defgroup approx Approximation Algorithms
+@ingroup algs
\brief Approximation algorithms.
@@ -386,9 +384,8 @@
This group describes some general optimization frameworks
implemented in LEMON.
-
-*/
-
-/**
-@defgroup lp_group Lp and Mip solvers
+*/
+
+/**
+@defgroup lp_group Lp and Mip Solvers
@ingroup gen_opt_group
\brief Lp and Mip solver interfaces for LEMON.
@@ -397,9 +394,8 @@
various LP solvers could be used in the same manner with this
interface.
-
-*/
-
-/**
-@defgroup lp_utils Tools for Lp and Mip solvers
+*/
+
+/**
+@defgroup lp_utils Tools for Lp and Mip Solvers
@ingroup lp_group
\brief Helper tools to the Lp and Mip solvers.
@@ -442,5 +438,5 @@
/**
-@defgroup timecount Time measuring and Counting
+@defgroup timecount Time Measuring and Counting
@ingroup misc
\brief Simple tools for measuring the performance of algorithms.
@@ -448,13 +444,4 @@
This group describes simple tools for measuring the performance
of algorithms.
-*/
-
-/**
-@defgroup graphbits Tools for Graph Implementation
-@ingroup utils
-\brief Tools to make it easier to create graphs.
-
-This group describes the tools that makes it easier to create graphs and
-the maps that dynamically update with the graph changes.
*/
@@ -472,6 +459,7 @@
This group describes the tools for importing and exporting graphs
-and graph related data. Now it supports the LEMON format, the
-\c DIMACS format and the encapsulated postscript (EPS) format.
+and graph related data. Now it supports the \ref lgf-format
+"LEMON Graph Format", the \c DIMACS format and the encapsulated
+postscript (EPS) format.
*/
@@ -479,5 +467,5 @@
@defgroup lemon_io LEMON Input-Output
@ingroup io_group
-\brief Reading and writing \ref lgf-format "LEMON Graph Format".
+\brief Reading and writing LEMON Graph Format.
This group describes methods for reading and writing
@@ -486,5 +474,5 @@
/**
-@defgroup eps_io Postscript exporting
+@defgroup eps_io Postscript Exporting
@ingroup io_group
\brief General \c EPS drawer and graph exporter
@@ -493,5 +481,4 @@
graph exporting tools.
*/
-
/**
@@ -522,7 +509,5 @@
- Finally, They can serve as a skeleton of a new implementation of a concept.
-
-*/
-
+*/
/**
@@ -535,8 +520,10 @@
*/
-/* --- Unused group
-@defgroup experimental Experimental Structures and Algorithms
-This group describes some Experimental structures and algorithms.
-The stuff here is subject to change.
+/**
+@defgroup map_concepts Map Concepts
+@ingroup concept
+\brief Skeleton and concept checking classes for maps
+
+This group describes the skeletons and concept checking classes of maps.
*/
Index: doc/lgf.dox
===================================================================
--- doc/lgf.dox (revision 236)
+++ doc/lgf.dox (revision 313)
@@ -79,5 +79,5 @@
\endcode
-The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
+The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
also store the edge set of an undirected graph. In such case there is
a conventional method for store arc maps in the file, if two columns
Index: doc/mainpage.dox
===================================================================
--- doc/mainpage.dox (revision 209)
+++ doc/mainpage.dox (revision 314)
@@ -51,5 +51,5 @@
If you
want to see how LEMON works, see
-some \ref demoprograms "demo programs"!
+some \ref demoprograms "demo programs".
If you know what you are looking for then try to find it under the
@@ -57,4 +57,5 @@
section.
-
+If you are a user of the old (0.x) series of LEMON, please check out the
+\ref migration "Migration Guide" for the backward incompatibilities.
*/
Index: doc/migration.dox
===================================================================
--- doc/migration.dox (revision 314)
+++ doc/migration.dox (revision 314)
@@ -0,0 +1,143 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2008
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+namespace lemon {
+/*!
+
+\page migration Migration from the 0.x Series
+
+This guide gives an in depth description on what has changed compared
+to the 0.x release series.
+
+Many of these changes adjusted automatically by the
+script/lemon-0.x-to-1.x.sh tool. Those requiring manual
+update are typeset boldface.
+
+\section migration-graph Graph Related Name Changes
+
+- \ref concepts::Digraph "Directed graphs" are called \c Digraph and
+ they have Arcs (instead of Edges), while
+ \ref concepts::Graph "undirected graphs" are called \c Graph
+ (instead of \c UGraph) and they have Edges (instead of
+ UEdges). These changes reflected thoroughly everywhere in
+ the library. Namely,
+ - \c Graph -> \c Digraph
+ - \c %ListGraph -> \c ListDigraph, \c %SmartGraph -> \c SmartDigraph etc.
+ - \c UGraph -> \c Graph
+ - \c ListUGraph -> \c ListGraph, \c SmartUGraph -> \c SmartGraph etc.
+ - \c Edge -> \c Arc, \c UEdge -> \c Edge
+ - \c EdgeMap -> \c ArcMap, \c UEdgeMap -> \c EdgeMap
+ - \c EdgeIt -> \c ArcIt, \c UEdgeIt -> \c EdgeIt
+ - Class names and function names containing the words \c graph,
+ \c ugraph, \e edge or \e arc should also be updated.
+- The two endpoints of an (\e undirected) \c Edge can be obtained by the
+ u() and v() member function of the graph
+ (instead of source() and target()). This change
+ must be done by hand.
+ \n Of course, you can still use source() and target()
+ for Arcs (directed edges).
+
+\warning
+The script/lemon-0.x-to-1.x.sh tool replaces all instances of
+the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
+in strings, comments etc. as well as in all identifiers.
+
+\section migration-lgf LGF tools
+ - The \ref lgf-format "LGF file format" has changed,
+ \@nodeset has changed to \@nodes,
+ \@edgeset and \@uedgeset to \@arcs or
+ \@edges, which become completely equivalents. The
+ \@nodes, \@edges and \@uedges sections are
+ removed from the format, the content of them should be
+ the part of \@attributes section. The data fields in
+ the sections must follow a strict format, they must be either character
+ sequences without whitespaces or quoted strings.
+ - The LemonReader and LemonWriter core interfaces
+ are no longer available.
+ - The implementation of the general section readers and writers has changed
+ they are simple functors now. Beside the old
+ stream based section handling, currently line oriented section
+ reading and writing are also supported. In the
+ section readers the lines must be counted manually. The sections
+ should be read and written with the SectionWriter and SectionReader
+ classes.
+ - Instead of the item readers and writers, item converters should be
+ used. The converters are functors, which map the type to
+ std::string or std::string to the type. The converters for standard
+ containers hasn't yet been implemented in the new LEMON. The converters
+ can return strings in any format, because if it is necessary, the LGF
+ writer and reader will quote and unquote the given value.
+ - The DigraphReader and DigraphWriter can used similarly to the
+ 0.x series, however the read or write prefix of
+ the member functions are removed.
+ - The new LEMON supports the function like interface, the \c
+ digraphReader and \c digraphWriter functions are more convenient than
+ using the classes directly.
+
+\section migration-search BFS, DFS and Dijkstra
+- Using the function interface of BFS, DFS and %Dijkstra both source and
+ target nodes can be given as parameters of the run() function
+ (instead of \c bfs(), \c dfs() or \c dijkstra() itself).
+- \ref named-templ-param "Named class template parameters" of \c Bfs,
+ \c Dfs, \c Dijkstra, \c BfsVisit, \c DfsVisit are renamed to start
+ with "Set" instead of "Def". Namely,
+ - \c DefPredMap -> \c SetPredMap
+ - \c DefDistMap -> \c SetDistMap
+ - \c DefReachedMap -> \c SetReachedMap
+ - \c DefProcessedMap -> \c SetProcessedMap
+ - \c DefHeap -> \c SetHeap
+ - \c DefStandardHeap -> \c SetStandardHeap
+ - \c DefOperationTraits -> \c SetOperationTraits
+ - \c DefProcessedMapToBeDefaultMap -> \c SetStandardProcessedMap
+
+\section migration-error Exceptions and Debug tools
+
+The class hierarchy of exceptions has largely been simplified. Now,
+only the i/o related tools may throw exceptions. All other exceptions
+have been replaced with either the \c LEMON_ASSERT or the \c LEMON_DEBUG
+macros.
+
+On the other hand, the parameter order of constructors of the
+exceptions has been changed. See \ref IoError and \ref FormatError for
+more details.
+
+\section migration-other Others
+- The contents of graph_utils.h are moved to core.h
+ and maps.h. core.h is included by all graph types,
+ therefore it usually do not have to be included directly.
+- path_utils.h is merged to \c path.h.
+- The semantic of the assignment operations and copy constructors of maps
+ are still under discussion. So, you must copy them by hand (i.e. copy
+ each entry one-by-one)
+- The parameters of the graph copying tools (i.e. \c GraphCopy,
+ \c DigraphCopy) have to be given in the from-to order.
+- \c copyDigraph() and \c copyGraph() are renamed to \c digraphCopy()
+ and \c graphCopy(), respectively.
+- The interface of \ref DynArcLookUp has changed. It is now the same as
+ of \ref ArcLookUp and \ref AllArcLookUp
+- Some map types should also been renamed. Namely,
+ - \c IntegerMap -> \c RangeMap
+ - \c StdMap -> \c SparseMap
+ - \c FunctorMap -> \c FunctorToMap
+ - \c MapFunctor -> \c MapToFunctor
+ - \c ForkWriteMap -> \c ForkMap
+ - \c StoreBoolMap -> \c LoggerBoolMap
+- \c dim2::BoundingBox -> \c dim2::Box
+
+*/
+}