From ef4a319984d22b88a9024ff523700d657621124d Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Tue, 10 Jul 2012 13:44:21 +1000 Subject: Add the LEMON graph library source to the repo I'll likely be using it, so this just makes it easier to get to from elsewhere. If I end up not using it then I can just delete it. --- lemon/doc/migration.dox | 145 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 145 insertions(+) create mode 100644 lemon/doc/migration.dox (limited to 'lemon/doc/migration.dox') diff --git a/lemon/doc/migration.dox b/lemon/doc/migration.dox new file mode 100644 index 0000000..3117aa3 --- /dev/null +++ b/lemon/doc/migration.dox @@ -0,0 +1,145 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * 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 +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 lemon-0.x-to-1.x.sh script replaces the words \c graph, +\c ugraph, \c edge and \c uedge in your own identifiers and in +strings, comments etc. as well as in all LEMON specific identifiers. +So use the script carefully and make a backup copy of your source files +before applying the script to them. + +\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 + +*/ +} -- cgit v1.2.3