doc/migration.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 343 956a29f30887
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@305
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@305
     2
 *
alpar@305
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@305
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@305
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@305
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@305
     8
 *
alpar@305
     9
 * Permission to use, modify and distribute this software is granted
alpar@305
    10
 * provided that this copyright notice appears in all copies. For
alpar@305
    11
 * precise terms see the accompanying LICENSE file.
alpar@305
    12
 *
alpar@305
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@305
    14
 * express or implied, and with no claim as to its suitability for any
alpar@305
    15
 * purpose.
alpar@305
    16
 *
alpar@305
    17
 */
alpar@305
    18
kpeter@306
    19
namespace lemon {
alpar@305
    20
/*!
alpar@305
    21
alpar@305
    22
\page migration Migration from the 0.x Series
alpar@305
    23
alpar@305
    24
This guide gives an in depth description on what has changed compared
kpeter@306
    25
to the 0.x release series.
alpar@305
    26
alpar@305
    27
Many of these changes adjusted automatically by the
kpeter@343
    28
<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
alpar@305
    29
update are typeset <b>boldface</b>.
alpar@305
    30
alpar@305
    31
\section migration-graph Graph Related Name Changes
alpar@305
    32
kpeter@306
    33
- \ref concepts::Digraph "Directed graphs" are called \c Digraph and
kpeter@306
    34
  they have <tt>Arc</tt>s (instead of <tt>Edge</tt>s), while
kpeter@306
    35
  \ref concepts::Graph "undirected graphs" are called \c Graph
kpeter@306
    36
  (instead of \c UGraph) and they have <tt>Edge</tt>s (instead of
kpeter@306
    37
  <tt>UEdge</tt>s). These changes reflected thoroughly everywhere in
alpar@305
    38
  the library. Namely,
alpar@305
    39
  - \c Graph -> \c Digraph
kpeter@306
    40
    - \c %ListGraph -> \c ListDigraph, \c %SmartGraph -> \c SmartDigraph etc.
alpar@305
    41
  - \c UGraph -> \c Graph
alpar@305
    42
    - \c ListUGraph -> \c ListGraph, \c SmartUGraph -> \c SmartGraph etc.
kpeter@306
    43
  - \c Edge -> \c Arc, \c UEdge -> \c Edge
kpeter@306
    44
  - \c EdgeMap -> \c ArcMap, \c UEdgeMap -> \c EdgeMap
kpeter@306
    45
  - \c EdgeIt -> \c ArcIt, \c UEdgeIt -> \c EdgeIt
kpeter@306
    46
  - Class names and function names containing the words \c graph,
kpeter@306
    47
    \c ugraph, \e edge or \e arc should also be updated.
alpar@305
    48
- <b>The two endpoints of an (\e undirected) \c Edge can be obtained by the
kpeter@306
    49
  <tt>u()</tt> and <tt>v()</tt> member function of the graph
alpar@305
    50
  (instead of <tt>source()</tt> and <tt>target()</tt>). This change
alpar@305
    51
  must be done by hand.</b>
alpar@305
    52
  \n Of course, you can still use <tt>source()</tt> and <tt>target()</tt>
alpar@305
    53
  for <tt>Arc</tt>s (directed edges).
alpar@305
    54
kpeter@306
    55
\warning
kpeter@343
    56
<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
kpeter@343
    57
\c ugraph, \c edge and \c uedge in your own identifiers and in
kpeter@343
    58
strings, comments etc. as well as in all LEMON specific identifiers.
kpeter@343
    59
So use the script carefully and make a backup copy of your source files
kpeter@343
    60
before applying the script to them.</b>
kpeter@306
    61
kpeter@314
    62
\section migration-lgf LGF tools
deba@308
    63
 - The \ref lgf-format "LGF file format" has changed,
deba@308
    64
   <tt>\@nodeset</tt> has changed to <tt>\@nodes</tt>,
deba@308
    65
   <tt>\@edgeset</tt> and <tt>\@uedgeset</tt> to <tt>\@arcs</tt> or
deba@308
    66
   <tt>\@edges</tt>, which become completely equivalents. The
deba@308
    67
   <tt>\@nodes</tt>, <tt>\@edges</tt> and <tt>\@uedges</tt> sections are
deba@308
    68
   removed from the format, the content of them should be
deba@308
    69
   the part of <tt>\@attributes</tt> section. The data fields in
deba@308
    70
   the sections must follow a strict format, they must be either character
deba@308
    71
   sequences without whitespaces or quoted strings.
deba@308
    72
 - The <tt>LemonReader</tt> and <tt>LemonWriter</tt> core interfaces
deba@308
    73
   are no longer available.
deba@308
    74
 - The implementation of the general section readers and writers has changed
deba@308
    75
   they are simple functors now. Beside the old
deba@308
    76
   stream based section handling, currently line oriented section
deba@308
    77
   reading and writing are also supported. In the
deba@308
    78
   section readers the lines must be counted manually. The sections
deba@308
    79
   should be read and written with the SectionWriter and SectionReader
deba@308
    80
   classes.
deba@308
    81
 - Instead of the item readers and writers, item converters should be
deba@308
    82
   used. The converters are functors, which map the type to
deba@308
    83
   std::string or std::string to the type. The converters for standard
deba@308
    84
   containers hasn't yet been implemented in the new LEMON. The converters
deba@308
    85
   can return strings in any format, because if it is necessary, the LGF
deba@308
    86
   writer and reader will quote and unquote the given value.
deba@308
    87
 - The DigraphReader and DigraphWriter can used similarly to the
deba@308
    88
   0.x series, however the <tt>read</tt> or <tt>write</tt> prefix of
deba@308
    89
   the member functions are removed.
deba@308
    90
 - The new LEMON supports the function like interface, the \c
deba@308
    91
   digraphReader and \c digraphWriter functions are more convenient than
deba@308
    92
   using the classes directly.
alpar@305
    93
alpar@305
    94
\section migration-search BFS, DFS and Dijkstra
kpeter@306
    95
- <b>Using the function interface of BFS, DFS and %Dijkstra both source and
kpeter@306
    96
  target nodes can be given as parameters of the <tt>run()</tt> function
kpeter@306
    97
  (instead of \c bfs(), \c dfs() or \c dijkstra() itself).</b>
kpeter@306
    98
- \ref named-templ-param "Named class template parameters" of \c Bfs,
kpeter@306
    99
  \c Dfs, \c Dijkstra, \c BfsVisit, \c DfsVisit are renamed to start
kpeter@306
   100
  with "Set" instead of "Def". Namely,
kpeter@306
   101
  - \c DefPredMap -> \c SetPredMap
kpeter@306
   102
  - \c DefDistMap -> \c SetDistMap
kpeter@306
   103
  - \c DefReachedMap -> \c SetReachedMap
kpeter@306
   104
  - \c DefProcessedMap -> \c SetProcessedMap
kpeter@306
   105
  - \c DefHeap -> \c SetHeap
kpeter@306
   106
  - \c DefStandardHeap -> \c SetStandardHeap
kpeter@306
   107
  - \c DefOperationTraits -> \c SetOperationTraits
kpeter@306
   108
  - \c DefProcessedMapToBeDefaultMap -> \c SetStandardProcessedMap
alpar@305
   109
alpar@305
   110
\section migration-error Exceptions and Debug tools
alpar@305
   111
alpar@307
   112
<b>The class hierarchy of exceptions has largely been simplified. Now,
alpar@307
   113
only the i/o related tools may throw exceptions. All other exceptions
alpar@307
   114
have been replaced with either the \c LEMON_ASSERT or the \c LEMON_DEBUG
alpar@307
   115
macros.</b>
alpar@307
   116
alpar@307
   117
<b>On the other hand, the parameter order of constructors of the
alpar@307
   118
exceptions has been changed. See \ref IoError and \ref FormatError for
alpar@307
   119
more details.</b>
alpar@307
   120
alpar@305
   121
\section migration-other Others
kpeter@306
   122
- <b>The contents of <tt>graph_utils.h</tt> are moved to <tt>core.h</tt>
kpeter@306
   123
  and <tt>maps.h</tt>. <tt>core.h</tt> is included by all graph types,
kpeter@306
   124
  therefore it usually do not have to be included directly.</b>
kpeter@306
   125
- <b><tt>path_utils.h</tt> is merged to \c path.h.</b>
alpar@307
   126
- <b>The semantic of the assignment operations and copy constructors of maps
alpar@307
   127
  are still under discussion. So, you must copy them by hand (i.e. copy
alpar@307
   128
  each entry one-by-one)</b>
kpeter@306
   129
- <b>The parameters of the graph copying tools (i.e. \c GraphCopy,
kpeter@306
   130
  \c DigraphCopy) have to be given in the from-to order.</b>
kpeter@306
   131
- \c copyDigraph() and \c copyGraph() are renamed to \c digraphCopy()
kpeter@306
   132
  and \c graphCopy(), respectively.
alpar@307
   133
- <b>The interface of \ref DynArcLookUp has changed. It is now the same as
alpar@307
   134
  of \ref ArcLookUp and \ref AllArcLookUp</b>
kpeter@306
   135
- Some map types should also been renamed. Namely,
kpeter@306
   136
  - \c IntegerMap -> \c RangeMap
kpeter@306
   137
  - \c StdMap -> \c SparseMap
kpeter@306
   138
  - \c FunctorMap -> \c FunctorToMap
kpeter@306
   139
  - \c MapFunctor -> \c MapToFunctor
kpeter@306
   140
  - \c ForkWriteMap -> \c ForkMap
kpeter@306
   141
  - \c StoreBoolMap -> \c LoggerBoolMap
kpeter@306
   142
- \c dim2::BoundingBox -> \c dim2::Box
kpeter@306
   143
alpar@305
   144
*/
kpeter@306
   145
}