LEDA 6.1
LEDA 6.0
LEDA 5.2
LEDA 5.1.1
LEDA 5.1
LEDA 5.0.1
LEDA 5.0
LEDA 4.5
LEDA 4.4.1
LEDA 4.4
LEDA 4.3
LEDA 4.2 - LEDA 2.01

LEDA 6.1

Support of .NET 2008
Several bug fixes.

LEDA 6.0

LEDA 5.2

new:
- new module: alignment algorithms

global:
- added support for g++-4.1

core:
- array data type re-designed:
now array is a pure class template and does no longer use the LEDA mechanism for parameterized data types (GenPtr/void* slots).
This improves the efficiency of many operations and makes the code much simpler

- queue<T> and b_queue<T>
+ now both suport iteration: forall(x,Q)
+ new operation:
Q.push(x) insert x at the front end of Q
(so Q can be used like a "double ended queue")

LEDA 5.1.1

globally:
- added support Visual Studio 2005 on MSWindows x64
- improved workaround for g++ -O2 optimization problems (g++ 3.x and higher)

bug fixes:
- see buglist.htm

LEDA 5.1

globally:
- added support for g++-4.0.x and Visual Studio 2005 (x86)
- added workaround for g++ -O2 optimization problems (g++ 3.x and higher)


graph:
- added graph and subgraph isomorphism algorithms
see the Manual pages and demo/graph_iso/gw_isomorphism.cpp for a demo program
- improved implementation of static graphs
- improved time efficiency of flow algorithms


geo:
r_circle_gen_poylgon:
- improved time efficiency of circular arc computations (up to a speedup of 10)
- added approximated computation (= input and output data contain curved segments, only the computation uses straight line approximations) of boolean operations as fast as in the case of straight line segments.

(rat_)gen_polygon:
- added parallel unite operation
- added (experimental) operation to compute a buffer (see manual pages)
- added (experimental) operation regional_decomposition for computing the "connected components" of a generalized polygon
- added reader/writer for WKB (well known binary) format (experimental)
- improved make_weakly_simple (see manual for new options)
- added contour operation

Nesting_Tree: new algorithm that computes the nesting relation of polygons in a boundary representation of a generalized polygon and represents this relation as a tree (see float_geo_alg.h)


graphics:
graphwin:
- export ps/latex : the .tex file now can be used by pdflatex if the graphics and color packages are included. The .ps file has to be converted to pdf before (using ps2pdf).
- added function to disable/enable blue label box for node/edge labels


numbers:
integer: new global function double_quotient(const integer& a, const integer& b) returns the best possible floating_point approximation of a/b
real: improved error bounds

platforms:
support of MacOS Darwin with gcc 3.3.x
support for upcoming Microsoft Visual Studio 2005 compiler

LEDA 5.0.1

Core

Globally:
leda::after has been replaced by leda::behind. (The old expression still works, but it is deprecated.)
d_int_set: added iteration forall_elements
list: added operation extract

Geo:
(rat_)polygon: added operation split_into_weakly_simple_parts
(rat_)gen_polygon: added operation make_weakly_simple
r_circle_gen_polygon: added operation unite that unites a list of polygons
segment_set: added operation intersection_sorted and rotation by multiples of 90 degrees
rat_segment_set: new class (with same functionality as segment_set)

Numbers:
bigfloat: added operation power (x^n)
improved conversion to double (computes error-bound and exactness)
real: uses improved bigfloat rounding

System:
file: added append_directory_delimiter and remove_trailing_delimiter

Bug Fixes:

static_graph
added missing destructor
cuckoo_hash
fixed some bugs
segment_set
fixed memory leak and bug in intersection query
real_point
added work-around for compiler bug in Borland 5.6
real_point, rat_point, point
fix for MSVC6 (related to mod arithmetics)
MW_MATCHING
fixed some bugs
EULER_TOUR
fixed bug
min cost flow
removed bug in capacity scaling
graphwin
added missing assignment operator for edge_info gw_move_edge_slider made safer
memory_manager:
LEDA_MEMORY macro
operator delete is now safe for NULL-pointers added work-around for compiler bug in Borland 5.6
Rijndael
fixed bug in destructor
r_circle_segment sweep
fixed bug related to isolated nodes
bigfloat
fixed bug in sqrt_bf
interval
fixed several bugs
fpu
fixed false initial fpu rounding mode for Solaris
manual
several typos corrected

LEDA 5.0

LEDA modules introduced(include structure has changed):
LEDA now consists of several modules. As a result, the include
structure has changed (see also manual section "Modules").
Old include structure is available under incl_old/

New Compilers: g++-3.4.x

New Supported Platforms: x86_64 (amd64) on Linux

Numbers:
real
better separation which often yield considerable speed-up
diamond-operator to compute the i-th real root of a polynomial with
real coefficients
integer
speed of all basic arithmetic operations improved by using new assembler
code for sparc and x86 platforms. In particular, sse2 instructions
are now used for pentium processors if available.

System:
socket_streambuf:
facilitates the handling of internet connections based on leda_socket
(see also secure_socket_streambuf below)

Graphs:
MAX_FLOW now supports lower capacity bounds, too
MAX_FLOW can compute a minimum s-t cut
BICONNECTED_COMPONENTS simplified and improved code
MIN_COST_FLOW
cost scaling
New much faster implementation of cost scaling (by using
a number of new heuristics) for static graphs.
The corresponding version for LEDA graphs is also much faster now
by working internally on a static graph copy.
capacity scaling
improved code now can deal with negative edge costs
DIJKSTRA
improvement of speed by using a new (lazy) heap data structure

Geometry:
some operations of r_circle_segment are much faster, in particular the
sweepline algorithm for computing intersections
new classes r_circle_polygon and r_circle_gen_polygon

Compression:
all coders support encoding/decoding of memory chunks in a direct and
user-friendly way
encoding_ofstream/decoding_ifstream
support seeks now (for encoding_ofstream only forward)
A0Coder
new Order0 model implementation which yields speed-up
(output remains the same -> backward compatibility)
AdaptiveHuffmanCoder
new
BlockCoder<Coder>
provides blockwise encoding/decoding which speeds up seeks
BWTCoder
replaced implementation by the code by Ferragina & Manzini
-> encoding: twice as fast and uses 40% less space
checksummers
allow O(1) time seek operations in decode mode
DeflateCoder
considerable speed-up for both encoding and decoding
supports now all compressing options provided by zlib
PPMIICoder
new coder with high compression at moderate speeds (reported to
outperform bzip2 in both compression ratio & speed)
MTF2Coder
sometimes yields better compression than MTFCoder
RLE0Coder
can be used as preprocessor after MTF(2) and often improves
compression

Cryptography:
CipherKey
provides key generation from passphrase (and optionally salt)
CBCoder, CBCCoder, CFBCoder, OFBCoder
coders for symmetric key encryption/decryption
(block cipher modes as stream ciphers)
Blowfish, Twofish, Rijndael
block ciphers to plug into the four coders above
OMACCoder
symmetric key authentication (based on a block cipher)
CryptAutoDecoder
like AutoDecoder, but allows the user to specify keys
SHACoder
checksummer which implements the SHA-1 hash algorithm
secure_socket_streambuf:
supports easy and secure internet connections based on leda_socket

Graphics
GraphWin
some minor improvements (fonts, animation speed, etc.)

Compression:
added a new module compression that offers several compression methods,
checksums and a compressable and decompressable stream type that can be
used in all LEDA methods that require a stream object (cf. Chapter
Compression in the LEDA Manual).

Real Geometry:
added a real kernel that allows to compute with objects having real
coordinates (data type real).
There is also a sweep on circular arc segments available.
This package is in experimental state!

Static Graphs:
manual pages explaining the concept and the available
operations of the data type static_graph have been added
(static graphs are not available when using MSVC++ 6.0,
Borland 5.5.1/5.6, or SGI).

Graph Algorithms:
new algorithm for stable matchings added.
new and more efficient implementations of several algorithms have
been added such as min cost flow using capacity scaling, min cost
flow using cost scaling, a variant of maximum weighted matching

timer:
new class for facilitating time measurements

list:
list<E>::search, list<E>::rank, list<E>::remove, list<E>::unique
do no longer require that a compare function for type E is defined.
They now use the equality operator (operator==) of type E.

dictionary:
added operation undefine()

graph:
sort_nodes(node_array<T>), sort_edges(edge_array<T>), type T can now
also be double, leda::integer, leda::rational or leda::real

h_array:
added operation set_default_value()

b_priority_queue:
changed interface

string:
type string is now a hashed type
new operation "contains"

window/panels:
several changes to make string output work properly with the X11
(openwin) version of Solaris 9 (vendor release 6610).
new operation "read_mouse_arc"

LEDA 4.4.1

New compiler supported:

.NET 2003 resp. MSVC++ 7.1, efficiency improved

xlman:
improved search function

number types:
integer,bigfloat,real
added a mutex mechanism to make these (reference counted) types thread safe
improved integer::operator++/--

graph_alg:
improved MIN_COST_FLOW (MCF_CAPACITY_SCALING) implementation

graphwin:
added support for polygon clusters

many bugs fixed; see the file Fixes in the package

LEDA 4.4

#define __LEDA__ 440

IMPORTANT CHANGE: namespace leda

constants: leda::before (former LEDA::before)
leda::after (LEDA::after)

functions: leda::min(const T&, const T&) (leda_min)
leda::max(const T&, const T&) (leda_max)
leda::swap(T&, T&) (leda_swap)

static graphs:
<LEDA/st_graph.h>
this version contains a first and (still experimentell) implementation
of a static graph data type as described in the paper
S. N\"aher, O. Zlotowski:
``Design and Implementation of Efficient Data Types for Static
Graphs'', LNCS 2461, Proceedings of the 10th Annual European
Symposium on Algorithms, Rome, 748-759, 2002
Test and example programs for flow algorithms can be found in
LEDAROOT/test/flow

tuples:
local types: first_type, second_type, etc.

list/array:
local types: size_type, diffence_type, value_type, pointer, reference

sockets:
new methods
void sock.send_int(int x)
bool sock.receive_int(int& x)

geometry:
handle types now are using less space
(25 % improvement for points)

new MINKOWSKI functions (taking two call-back function arguments
used in the partitioning and union steps, respectively).

compare_by_angle(POINT a, POINT b, POINT c, POINT d)

LEDA 4.3

#define __LEDA__ 430

SunPro C++ 5.2 (Forte 6.1)
g++-3.0
Metrowerks C++ (win32)
aCC (hpux)

implementation parameters:
dictionary, p_queue, sortseq, set, d_array
now have an additional optional implementation template
parameter this makes _dictionary<K,I,impl>, _p_queue<P,I,impl>, etc.
obsolete (see LEDAROOT/test/dict/dic_test.c for an example program).

error handling by c++ exceptions:
after calling
set_error_handler(exception_error_handler)
errors will be handled by throwing exceptions

number package:
improved number types: integer, rational, bigfloat, real
new number types: interval (interval arithmetic)
residual (modular arithmetic)

improved integer sorting:
see LEDAROOT/demo_cout/stl/stl_vs_leda_sort.c and stl_vs_leda_sort_int.c
for a comparison with STL.

dictionaries
new hashing data structure:
cuckoo hashing (see <LEDA/impl/cuckoo_hashing.h>
and LEDAROOT/test/dict/dic_test.c)

graphs
new (experimental) semi-dynamic graph representation. It can be used by adding -DGRAPH_REP=2 to the compiler command line and linking with libG2.a (libG2.so). This representation needs only about half of the space of the fully-dynamic standard graph data structure and can significantly reduce the running time of graph algorithms as shown for the maxflow example on http://www.informatik.uni-trier.de/~naeher/maxflow.html. (see also the examples in LEDAROOT/test/flow).

static graphs
new (experimental) static graph data type <LEDA/s_graph.h>.
This is work in progress. First implementations and test programs using this very efficient graph data type can be found in LEDAROOT/test/flow/mfs.c and LEDA/templates/max_flow_s.t.


graph algorithms
new algorithms for transitive closure and reduction (see <LEDA/basic_graph_alg.h>)
graph TRANSITIVE_CLOSURE(const graph&)
graph TRANSITIVE_REDUCTION(const graph&)
void MAKE_TRANSITIVELY_CLOSED(graph&)
void MAKE_TRANSITIVELY_REDUCED(graph&)

new algorithms for Euler tours (see <LEDA/euler_tour.h>)

new functions for reading and writing DIMACS graph problems (see <LEDA/dimacs.h> for details)

Read_Dimacs_SP : (single-source) shortest paths
Write_Dimacs_SP

Read_Dimacs_MF : max flow
Write_Dimacs_MF

Read_Dimacs_MCF : min cost flow
Write_Dimacs_MCF

Read_Dimacs_MAT : matching
Write_Dimacs_MAT

geometryall rotate90 methods now have an additional optional parameter i:
x.rotate90(point q, int i=1)
returns |x| rotated about $q$ by an angle of $i\times 90$
degrees. If $i > 0$ the rotation is counter-clockwise otherwise
it is clockwise.

new faster (rat_)polygon::area() method

new static member variable POLYGON::input_check_type for all polygon types whose value (NO_CHECK, WEAKLY_SIMPLE, SIMPLE, etc.) determines what kind of check should be performed when reading polygons from a stream (in operator>>).

window
show_orientation (new global flag)
if show_orientation = true all geometric objects are drawn
with arrows indicating their orientation or direction

GraphWin

directed edges:
direction attributes (directed_edge, redirected_edge, ...) now can be combined using the or (|) operator
e.g. gw.set_direction(e,directed_edge|mid_directed_edge);

edge borders:
new global edge attribute: edge_border
bool gw.set_edge_border(bool)
bool gw.get_edge_border()
If set to true edges are drawn with a border line.
Can be set intereactively in the Options->Global-Options panel.

new output formats:
exporting SVG (scalable vector graphics) format
gw.save_svg(string fname)

and windows metafont files
gw.save_wmf(string fname)