LEDA 4.2.1
#define __LEDA__ 421
new compilers supported:
Sun C++ 6.0
g++-2.96
REDEFINE_NAMES:
prefixing for implementation classes added
Bipartite Weighted Matching:
a new heuristic was added to the bipartite matching code.
It reduces the running time to 2/3 to 1/10 of its old values.
The heurisic is described and analysed in wbm-heur.ps.gz
(postscript format).
window:
W.screenshot(string fname)
writes a screenshot of window W to file fname.ps in postscript format
(on unix systems) or fname.wmf in metafile format (on windows systems).
leda_socket:
a new data type for establishing socket connections
(see and the sample programs in test/socket)
GeoWin:
a data type for the visulization and animation of geometric
algorithms and data structures (see and
the demo programs in demo/geowin)
point
missing functions inside/on/outside_circle added
node_pq
bug in print_node method
random_source
added private copy_constructor
events
problem with macros solved by using no-macro version
polygon
bug in bounding_box method fixed
bug in simplicity test fixed
LEDA 4.2
#define __LEDA__ 420
critical change:
"newline" macro removed (to reduce name space pollution)
please use "cout << endl;" instead
new compilers supported:
KAI C++ 3.4
Borland C++ 5.5
new data types:
pp_dictionary: partially persistent dictionaries
win32:
we now use the nasm assembler for all compilers
integer:
faster multiplication on i386 (improved assembler-code)
(try test/numbers/leda_vs_gmp for a comparison with GMP)
graph algorithms:
new algorithms for computing weighted matchings in general graphs
(see and )
minimum spanning tree taking a compare object:
list MIN_SPANNING_TREE(const graph&, const leda_cmp_base& cmp)
d2_geo:
CONVEX_COMPONENTS : partition a polygon into convex parts
MINKOWSKI_SUM : computes the Minkowski Sum of two polygons
MINKOWSKI_DIFF : computes the Minkowski Difference of two polygons
TRIANGULATE_GEN_POLYGON : Triangulation of generalized polygons
window:
new read_mouse variants: read_mouse_line and read_mouse_ray
GraphWin 1.7
the "load gw-graph" dialog now allows joining to an existing graph
support of dimacs (maxflow) file format
new AGD client-server connection
modified graph generator and file menu
graph name operations
string gw.set_graphname(string name)
string gw.get_graphname()
replace former file name functions
(set/get_gw/gml/ps_filename)
new gw-format (version 1.4): colors represented by rgb-values
minor changes and fixes
LEDA 4.1
Borland C++ 5.4 (C++ Builder 4) now supported !
New Platforms
sunpro 5.0
mipspro 7.3
egcs 2.95
Note that for Visual C++ "advapi32.lib" must be added to the list of libraries.
sortseq:
static member function sortseq::my_sortseq(seq_item it)
returns a pointer to the sortseq of it
new: numerical analysis
graph:
graph_misc.h:
bool Is_Simple(const graph& G, list& el);
bool Is_Series_Parallel(const graph G&);
graph_gen.h:
random_sp_graph
node/edge/face array:
use_node/edge/face_data now returns a boolean value indicating
whether a free data slot was available or not.
graph drawing:
SP_EMBEDDING (series-parallel drawing)
D3_SP_EMBEDDING (3d-series-parallel drawing)
ORTHO_DRAW
orthogonal drawings of arbitrary (non-simple, high-degree, ...)
planar graphs.
d2_geo:
edge TRIANGULATE_GRAPH(GRAPH& G);
edge TRIANGULATE_GRAPH(GRAPH& G);
edge TRIANGULATE_SEGMENTS(list L, GRAPH& G);
edge TRIANGULATE_SEGMENTS(list L, ...);
edge TRIANGULATE_POLYGON(list L, GRAPH& G);
edge TRIANGULATE_POLYGON(list L, ...);
d3_geo:
new types: d3_(rat)_segment
d3_(rat)_ray
d3_(rat)_line
d3_(rat)_simplex
d3_(rat_)plane: intersection with d3_lines and d3_planes
window:
new parameter: precision
defines the precision (number of bits) used for input coordinates
new operations for zooming, scrolling, reading double clicks, ...
(see /demo/window/draw.c)
xpm-pixmaps now can have transparent pixels (color "None");
new parameters:
- point_style
possible values: pixel_point, cross_point(default), plus_point
circle_point, disc_point, rect_point, box_point
- fill_color
used by "W << x" to draw the interior of x
(use "invisible" to prevent filling)
new pre-defined panel items:
W.lstyle_item(string,line_style&, ... )
W.lwidth_item(string,int&, ... )
W.pstyle_item(string,point_style&,... )
graphwin:
support for series-parallel graphs (Graph-Menu)
generation, test, drawing
arbitrary fonts for node and edge labels:
gw.set_node_label_font(string font_name)
gw.set_edge_label_font(string font_name)
gw.finish_menu_bar()
should be called before any additional buttons are
added directly (by gw.get_window().button(...)) to
the panel section of the underlying window.
(see demo/animation/preflow_push_anim.c for an example)
LEDA 3.8
-->
--> global constants:
--> "before" (leda_before) and "after" (leda_after) no longer exist,
--> use LEDA::before and LEDA::after instead
-->
-->
--> min/max templates:
--> "min" and "max" no longer exist, use leda_min/leda_max instead.
-->
compare objects:
every parameterized data type based on a linearly ordered type, e.g., key
(dictionary) or priority (p_queue), now has a constructor taking
a "compare object" argument (see the user manual for details).
local types:
many data types define local types. Examples are
for all item-based data types: dtype<...>::item
for all dictionary types: dictionary::key_type (= K)
dictionary::inf_type (= I)
for lists list::value_type (= E)
...
see the user manual for more information.
integer:
new implementation by C.Burnikel and J.Ziegler
better performance on many platforms (linux/i386, solaris/sparc, irix/mips)
see test programs:
test/numbers/integer_test.c (LEDA integers vs. old LEDA integers)
test/numbers/leda_vs_cln.c (LEDA integers vs. CLN integers)
test/numbers/leda_vs_gmp.c (LEDA integers vs. GMP integers)
graph:
node/edge/face_maps are now derived from node/edge/face_array
and can be passed (by reference) to graph algorithms taking
node/edge/face_array arguments.
random_source:
unsigned long ran.get()
now returns a random long integer of maximal precision
(32 bit on 32-bit platforms and 64 bit on 64-bit platforms)
array:
resize operations A.resize(int l, int r)
A.resize(int n)
std header files:
setting the flag LEDA_STD_HEADERS will cause LEDA to use
the new std header files (without ".h"). This can be done
by using -DLEDA_STD_HEADERS on the compiler command line
or by uncommenting the corresponding definition at the end
of . Note that all libraries have to be
compiled with this flag enabled and that old and new header
files cannot be used simultaneously.
partition:
new operation: int P.number_of_blocks()
forall_items iteration
2D-Geometry
New Types:
(rat_)rectangle : iso-oriented rectangles
(rat_)gen_polygon : generalized polygons (with holes)
(rat_)point_set : former delaunay_triang
New Algorithms:
WIDTH(const list&, LINE&, LINE&)
CRUST(const list&, GRAPH&)
3D-Geometry:
New Types:
d3_(rat_)sphere
d3_rat_sphere/
d3_rat_point: floating point filter for side_of_sphere
(using the expression compiler of Stefan Funke)
d3_(rat)_plane:
int P.intersection(p1,p2,q)
computes intersection of line through p1 and p2 with P
window:
void W.set_bg_redraw(void (*f)(window*,double,double,double,double)
GraphWin* W.get_graphwin()
shortcut characters (for triggering buttons with ALT+...)
can be defined by inserting a '&' into the button label before
the corresponding character (example: the button created by
W.button("E&xit") can be triggered with ALT+x)
W.set_window_delete_handler(void (*F)(window*)
F is called when the window manager requests to close the window
(e.g. after clicking the X-button). The default handler terminates
the application program.
void* W.set_client_data(void*)
void* W.get_client_data()
// drawing
void W.draw_roundrect(...)
void W.draw_roundbox(...)
new menu/panel style
GraphWin
support for embedded graphs (Graph->Embed Menu)
undo/redo stack
Extending node/edge context menus:
edit action functions (see gw.set_action()) now can be added
to the context menus for nodes and edges:
gw.add_node_menu(string label, gw_action func)
gw.add_edge_menu(string label, gw_action func)
pixmaps in postscript output
export LaTeX/Postscript: size of picture can be adjusted
zoom_objects default: true
new node shapes: roundrect_node and ovalrect_node
default node shape: circle_node
GraphWin now can handle undirected graphs
New Export Formats:
windows meta files
windows clipboard (meta file / bitmap)
screenshot (Postscript)
newline's can be inserted using the RETURN key
during label editing (node/edge context menu)
a sequence of '-' inserts a horizontal line
when resizing a node by clicking and dragging on its
border line the SHIFT key must be pressed simultaneously
ps_file
draw_ray operations
LEDA 3.7.1
list/array
improved (template-based) sorting methods (not supported for some compilers)
d_array/h_array
clear() operation added
graph
hiding nodes: void G.hide_node(node v)
void G.hide_node(node v, list& h_edges)
bool G.is_hidden(node v)
void G.restore_node(node v)
void G.restore_all_nodes()
node_list/node_slists
declared operator= private
clear operation added
graph_misc
new variants of "CopyGraph" for constructing copies of subgraphs
graph_alg
maximum weight matching for general graphs (back again)
graphwin
gw.set_bg_redraw(void (*func)(window*,double,double,double,double)
(see LEDAROOT/test/graphwin/gw_redraw.c)
exporting Latex figures
improved grid mode
new node shape (rhombus)
date class
a type for representing and manipulating dates
see Lman date ( or )
param_handler & param_panel
types for reading command line arguments
stl-style iterators for list, array, dictionary, sortseq, p_queue, set
use -DLEDA_STL_ITERATORS compile flag
see the example programs in $LEDAROOT/demo/stl
linear order objects
leda_cmp_base
LEDA 3.7
graph
graph::graph(int n_slots, int e_slots) constructor specifies
the number of additional free data slots in nodes and edges
that can be used by node and edge arrays (see also the
description of the used_node_data() and used_edge_data()
operations of node and edge arrays).
graph_misc.h
CopyGraph(H,G,V,E) constructs copy H of subgraph (V,E) of G
graph_alg
new faster implementation of many graph and network algorithms
and corresponding checkers (see the user manual for details)
graph iterators and data accessors (M. Nissen and C. Weihe)
now fully integrated
(see the corresponding section in the user manual)
multi-threading
map and h_array are thread safe now
window
- new color "invisible", objects drawn in this color are invisible
GraphWin (new version: 1.3)
- new edge attribute "direction" (individual direction)
- printing postscript files directly from the "File Menu"
- circle and bezier edges in postscript output
- ...
LEDA 3.6.1
node/edge/face_array/map:
new method:
const graph& A.get_graph() returns reference to graph of A
list:
made constructor list(const E& x) "explicit"
map:
new operation: map::clear() makes map empty.
Platforms:
Shared libraries for HP-UX and Irix
Prexifing:
New leda-prefixed type names:
node,edge,face
colors and other enumerations used by the window class
Graphwin:
GML graph format
context menues
edge sliders
gw.set_zoom_objects(bool)
gw.set_layout(node_array pos, edge_array > bends);
Error Handling:
On some platforms (e.g. solaris/g++) the default error handler now
prints the contents of the function call stack. For window programs
this option can be selected by clicking the "where" button in
the default error panel.
System Errors (bus errors, segmentation faults, etc) are handled by
LEDA's error handler if the environmant variable LEDA_CATCH_SYSTEM_ERRORS
is defined. Together with the new stack trace option mentioned above this
might be useful for finding the location of crashes without using a debugger.
Environment Variables:
- LEDA_INIT
a colon separated list of commands (strings).
Currently, only two commands are recognized
show_memory_leaks: print a summary of memory still in use that
was allocated by LEDA's memory manager (i.e. by
the LEDA_MEMORY macro) after program termination.
show_memory_statistics: print a table of the total memory consumption
of the program after termination.
- LEDA_CATCH_SYSTEM_ERRORS (see above)
LEDA 3.6
Tuple Types: ()
two_tuple
three_tuple
four_tuple (replaces former quadruple)
Global Name Space Cleaning:
+ Global enums have been moved into class "LEDA" (),
now you have to use LEDA::after/LEDA::before instead of after/before
(e.g. used by list::insert, list::split, graph::new_edge, ...)
+ Global function "wait" renamed to "leda_wait"
+ Min/Max templates renamed to "leda_min" and "leda_max"
"leda_" prefix:
All object code libraries (libL, libG, libP, ...) use the prefixed class
type names by default now. The REDEFINE_NAMES.h and UNDEFINE_NAMES.h
header files don't have to be edited before installation any more.
Application programs can decide to use the "leda_" prefix
by defining the "LEDA_PREFIX" preprocessor macro , e.g. by using
a -DLEDA_PREFIX compiler switch.
LEDA_STL_ITERATORS
before using stl-style iterators the macro LEDA_STL_ITERATORS has
to be defined (g++/CC ... -DLEDA_STL_ITERATORS ... )
(see LEDAROOT/demo/stl)
partition/node_partition:
New operation: void P.split(list L)
turns all items in L to singleton blocks.
Precondition: L is a union of blocks.
Linear Orders:
comparison based data types (dictionary, p_queues, sort_seq, ...):
constructor taking a compare function that defines a linear
order on the key (prio) type. Example:
dictionary D(cmp_strings);
d_int_set:
unbounded version of int_set
Graphs:
list G.hidden_edges() returns the list of all hidden edges
bool Is_Biconnected(G,v) // computes cut vertex v1 if result is false
bool Is_Triconnected(G,v1,v2) // computes split pair (v1,v2) if false
Graph Iterators: (experimental, does not work with all compilers)
see Manual/contrib/graph_iterator.ps
File and Directory Functions:
see
string
new operation s.read_file(istream&)
array
new operations: A.binary_locate(E x)
A.binary_locate(cmp, E x)
Geometry
polygon/rat_polygon
new operations: P.diff(Q)
P.sym_diff(Q)
P.complement()
SWEEP_SEGMENTS
void SWEEP_SEGMENTS(list L, GRAPH& G, bool embed=false);
SEG in { segment, rat_segment }, POINT in { point, rat_point }
computes planar map if optional flag embed = true
MULMULEY_SEGMENTS
void MULMULEY_SEGMENTS(list L, GRAPH& G, bool embed=false);
SEG in { segment, rat_segment }, POINT in { point, rat_point }
computes planar map if optional flag embed = true
window/panel
New Operations:
P.string_item(const char* label, string& s, list menu, int sz)
string item with scroll box menu
W.text_box(x0,x1,y,text); formated ouput of text into a box
W.text_box(text); into window
// xpm pixmaps
W.create_pixrect(char** xpm_data);
W.create_pixrect(char* xpm_file_name);
// background pixrects (pixmaps)
W.set_bg_pixrect(char* pixrect);
GraphWin
+ Setting default attributes using
gw.set_node/edge_param(param_type x, bool apply=true)
now also changes the corresponding parameter for all existing nodes/edges
(if default parameter apply is not explicitely set to false)
+ Double clicks and dragging events are much better distinguished and handled.
+ Changing the set of default menues (now works)
gw.set_default_menu(menu_mask)
here menu_mask is the bitwise or of a subset of
{ M_FILE, M_EDIT, M_GRAPH, M_LAYOUT, M_WINDOW, M_OPTIONS, M_HELP }
gw.del_menu(menu_mask)
have to be called before the first gw.display() !
Example Program: demo/graph/gw_menu.c
+ Pixmaps for nodes and background of window
// setting background pixmaps
gw.set_bg_pixmap(char* pixrect)
gw.set_bg_xpm(char** xpm_data)
// setting pixmaps of nodes
gw.set_pixmap(node v, char* pixrect)
gw.set_pixmap(list L, char* pixrect)
gw.get_pixmap(node v)
gw.set_node_pixmap(char* pixrect)
gw.get_node_pixmap(char* pixrect)
+ Saving and Restoring Attributes
gw.save_node_attributes();
gw.save_edge_attributes();
gw.restore_node_attributes();
gw.restore_edge_attributes();
Windows
+ Buffering
W.start_buffering()
W.flush_buffer()
W.flush_buffer(x0,y0,x1,y1)
W.stop_buffering()
+ Pixmaps for buttons
Example Programs: demo/win/pm_buttons, demo/geo/poly_demo.c
Collection of pixmaps:
W.button(char* pr1, char* pr2, string s, int n);
W.button(char* pr1, char* pr2, string s, int n, void (*F)(int));
W.button(char* pr1, char* pr2, string s, int n, window& M);
adds a button with number n, name s (function F, menu M).
Pixrect pr1 is used for unpressed and pr2 for pressed button.
+ Status Window (Line)
W.open_status_window();
W.set_status_string(string);
W.close_status_window();
+ File Panels (experimental)
see demo/win/file_panel.c for an example.
LEDA 3.5.2
General
Changed the return types of all read-only access operations to "const T&"
Windows
New drawing operations for curves:
W.draw_bezier(const list& L, int m, color c)
W.draw_spline(const list& L, int m, color c)
W.draw_bezier_arrow(const list& L, int m, color c)
W.draw_spline_arrow(const list& L, int m, color c)
Interface for drawing circle arcs has changed !
W.draw_arc(point a, point b, point c, ...)
W.draw_arc_arrrow(point a, point b, point c, ...)
draws arc starting in a passing through b ending in c.
GraphWin
- edge_shapes: poly_edge, circle_edge, bezier_edge, spline_edge
- moving of edge bends is much faster now
LEDA 3.5.1
- IMPORTANT CHANGE (FORALL-ITERATIONS)
Now the CURRENT ITEM may be deleted in iteration loops as in
// delete all items with contents x from a list
forall_items(it,L) {
if (L[it] == x) L.del_item(it)
}
// delete selfloops
forall_edges(e,G) {
if (source(e) == target(e) G.del_edge(e)
}
...
HOWEVER, NO OTHER ITEM MAY BE DELETED.
Previous LEDA versions did not allow to change the set of
items at all during iterations. However, deleting items different
from the current item (e.g. the successor item) worked, as in
// delete all items except for the first
forall_items(it,D)
{ list_item next = D.succ(it);
if (next) D.del_item(next);
}
This kind of code will not work and crash with LEDA-3.5.1 !!!
--------------------------------------------------------------------------------
- Version Macro __LEDA__ (defined to 351 in the current version)
- Lists
list::reverse() and list::reverse(list_item it1, list_item it2)
now have a semantics different than list::reverse_items() and
list::reverse_items(it1,it2):
They only reverse the sequence of ENTRIES (values) of the
corresponding sublist of items, but leave the sequence of items
(or iterators) unchanged.
- Iterations
Now, the "current" item or object may be deleted from the data type
Examples: forall_items(it,D)
D.del_item(it);
forall_adj_edges(e,v)
if (target(e) == u) G.del_edge(e);
forall_adj_nodes(u,v)
if (G.outdeg(u) < 4) G.del_node(u);
- Graphs
- Faster Planarity Test
- Extension of the graph file format by reversal edges
- Geometry
SEGMENT_INTERSECTION(const list& L,
void (*report)(const segment& const segment&));
point/rat_point
new geometric primitve: cmp_signed_dist(a,b,c,d)
- GraphWin
- Edge Anchors
gw.set_souce_anchor(edge e, point p)
gw.set_target_anchor(edge e, point p)
- Setting Parameters (flush,node_width, node_height, ...)
before displaying the window (gw.display)
LEDA 3.5
- Version Macro __LEDA__ (defined to 350 in the current version)
- new data types
map2 : two-dimensional maps (sparce matrices)
node_map2 : two-dimensional node maps (sparse node matrices)
ps_file : data type for producing Postsript graphics with the same
interface as window (see /Manual/contrib for details)
- memory management
now can handle blocks of arbitrary size
- leda_type_id() function (special treatement of built_in types)
- numbers
new implementation of bigfloats and reals
(much more efficient)
- list
- L.pop() now checks precondition (non-empty list)
- L.reverse(it1,it2) reverses sub-list
- L.bucket_sort(int (*f)(const T&))
same as L.bucket_sort(i,j,f) where i and j are the
minimal and maximal value of f(e) as e ranges over
all elements of L.
renamed:
- list_item L.item(int i) ---> list_item L.get_item(int i)
- void L.move_to_rear(list_item) ---> void L.move_to_back(list_item)
- STL iterators (list::[const_]iterator or list::[const_]item)
- STL operations
splice reverse merge swap remove front back push_front push_back
pop_front pop_back erase erase begin end
- array
- STL iterators (array::[const_]iterator or array::[const_]item)
- Graphs
20% Space Reduction
G.choose_node/edge/face() now returns a random node/edge face of G
New Member Functions:
boid G.make_bidirected(list& R)
bool G.is_bidirected()
bool G.is_map()
void G.make_map(list& R)
void G.join(graph& G1)
node G.merge_nodes(node v1, node v2)
void G.del_nodes(const list& V)
void G.del_edges(const list& E)
void G.restore_all_edges();
void G.bucket_sort_nodes(int l, int h, int (*ord)(const node&));
void G.bucket_sort_nodes(int (*ord)(const node&));
void G.bucket_sort_nodes(const node_array& ord);
void G.bucket_sort_edges(int l, int h, int (*ord)(const edge&));
void G.bucket_sort_edges(int (*ord)(const edge&));
void G.bucket_sort_edges(const edge_array& ord);
Animation and Callback-Functions
bool pre_new_node_handler();
void post_new_node_handler(node);
bool pre_del_node_handler(node);
void post_del_node_handler();
bool pre_new_edge_handler();
void post_new_edge_handler(edge);
bool pre_del_edge_handler(edge);
void post_del_edge_handler();
New File Format (delimiters for node and edge data)
- 2D Geometry
- for all float basic objects (point,segment,ray,line,circle,polygon)
a) x.translate(double phi, double d) renamed to x.translate_by_angle(phi,d)
b) x.translate(double dx, double dy) translation by vector (dx,dy)
Algorithms for POINT in { point, rat_point }
CIRCLE in { circle, rat_circle }
- faster algorithms for Delaunay triangulation and Voronoi diagrams
DELAUNAY_TRIANG(const list& L, GRAPH& DT)
VORONOI(const list& L, GRAPH& DT)
- furthest point Delaunay triangulation
void F_DELAUNAY_TRIANG(const list& L, GRAPH& DT)
- furthest point Voronoi diagram
void F_VORONOI(const list& L, GRAPH& DT)
- Euclidean Minimum Spanning Tree Algorithm
void MIN_SPANNING_TREE(list&, GRAPH& T)
- Largest Empty Circle
CIRCLE LARGEST_EMPTY_CIRCLE(const list&)
- Smallest Enclosing Circle
CIRCLE SMALLEST_ENCLOSING_CIRCLE(const list&)
- Minimum Width Annulus
void MIN_WIDTH_ANNULUS(const list&, POINT& c, POINT& i, POINT& o)
- Minimum Area Annulus
void MIN_AREA_ANNULUS(const list&, POINT& c, POINT& i, POINT& o)
- 3D Geometry
3D Points
- d3_point
- d3_rat_point
3D Planes
- d3_plane
- d3_rat_plane
3D Convex Hull (for POINT in { d3_point, d3_rat_point }
- CONVEX_HULL(const list& L, GRAPH& polyeder)
- CONVEX_HULL(const list& L, GRAPH& polyeder)
- Windows/Panels
bitmaps in choice items and buttons
multiple choice items
improved pull-down menues
Timer: W.start_timer(int msec, void (*action)(window*))
W.stop_timer();
Redrawing: drawing mode is set to "src_mode" before calling any
user-defined redraw (and timer) function. If a different
drawing mode is to be used it has to be set in the
corresponding redraw function explicitely.
- GraphWin
see src/graphwin/CHANGES
LEDA 3.4.1
- graph:
new planar map operations ("planar_map" data type obsolete)
GML - Format (new I/O operations)
G.write_gml(file_name)
G.read_gml(file_name)
- windows and panels:
string_items can be edited using mouse and cursor keys
- GraphWin: (still experimental)
many changes (see graphwin/CHANGES)
- new dynamic trees implementation "dynamic_trees"
Many problems fixed (see FIXES).
LEDA 3.4
------------------------------------------------------------------------------
GENERAL
-------------------------------------------------------------------------------
IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT IMPORTANT
Name of window library has changed
OLD name: libWx (-lWx)
NEW name: libW (-lW)
AND it now has to appear in front of all other libraries
... -lW -lP -lG -lL -lX11 ....
-------------------------------------------------------------------------------
Print and Read
-------------------------------------------------------------------------------
Functions "Print" and "Read" are no longer used to implement
user defined I/O routines. Now, the usual output and input stream
operators (operator<< and opertor>>) are used. For backward
compatibility Print and Read functions will still work but
should be avoided. Missing I/O operators will be reported at
compile time.
-------------------------------------------------------------------------------
Linear Orders (compare)
-------------------------------------------------------------------------------
There is no default implementation of "int compare(const T&, const T&)
giving an error message at run time. Now
only contains a template {\bf declaration} for compare. The effect is
that missing compare functions will be reported by the linker. Now
the use of a compare functions (e.g. in a parameterized data type as
in dictionary) and its definition can be located in different
source files (which was not possible in the previous version
with many compilers).
Example:
#include
class pair {
double x;
double y;
public:
pair(double a=0, double b=0) : x(a), y(b) {}
pair(const pair& p) x(p.x), y(p.y) {}
friend istream& operator>>(istream& is, pair& p)
{ return is >> p.x >> p.y; }
friend ostream& operator<<(ostream& os, const pair& p)
{ return os << p.x << " " << p.y; }
friend int compare(const pair& p, const pair& q);
};
main()
{ list L;
L.read("list of pairs: ");
L.sort();
L.print("sorted:\n",'\n');
return 0;
}
int compare(const pair& p, const pair& q)
{ if (p.x < q.x) return -1;
if (p.x > q.x) return 1;
if (p.y < q.y) return -1;
if (p.y > q.y) return 1;
return 0;
}
-------------------------------------------------------------------------------
New Compilers/Platforms (lconfig)
-------------------------------------------------------------------------------
Win32 (NT, Win95)
- Borland C++
- Microsoft Viusal C++
- Watcom C++
(please contact LEDA GmbH for DLL's)
LINUX: shared Libraries
-------------------------------------------------------------------------------
Documentation and manual tools
-------------------------------------------------------------------------------
please see section 1.12 of the LEDA manual
-------------------------------------------------------------------------------
Memory Management
-------------------------------------------------------------------------------
encapsulated into class memory_manager
- multiple managers
- table size parameter
-------------------------------------------------------------------------------
multi-threads
-------------------------------------------------------------------------------
Multithread safety is available for posix, cps package and solaris package.
To use the right package, please edit the file incl/LEDA/thread.h
-------------------------------------------------------------------------------
Graphs & Planar Maps
-------------------------------------------------------------------------------
G.move_edge(edge e, node v, node w)
G.move_edge(edge e, edge e1, edge e2)
G.move_edge(edge e, edge e1, node w)
Reversals and Faces
G.make_map()
G.reversal(e);
G.face_cycle_succ();
G.face_cycle_pred();
G.compute_faces();
...
face_array, face_map
See the section on graphs and related data types in the user manual
for more details.
-------------------------------------------------------------------------------
Graph Algorithms
-------------------------------------------------------------------------------
MIN_COST_FLOW(G,lcap,ucap, cost,supply,flow)
MIN_COST_FLOW(G,cap, cost,supply,flow)
MIN_COST_MAX_FLOW(G,s,t,cap,cost,flow)
-------------------------------------------------------------------------------
GEOMETRY
-------------------------------------------------------------------------------
all objects now both with floating point and exact rational arithmetic
- new types
ray
rat_ray
rat_circle
rat_line
- name changes
x.vertical() --> x.is_vertical()
x.horizontal() --> x.is_horizontal()
converting rational to floating point objects:
x.topoint() --> x.to_point()
x.tosegment() --> x.to_segment()
x.toline() --> x.to_line()
x.tocircle() --> x.to_circle()
- new transformations
x.reflect(p,q)
x.reflect(p)
- delaunay_tree removed
replaced by "delaunay_triang", an efficient and robust data structure
base on LEDA graphs and exact arithmetic (see section on advanced
data types for geometry and the delaunay_demo program on demo/geo
- float_delaunay_triang (floating point version)
- new algorithms (plane_alg.h)
all algorithms for both float and rational objects
Balaban
Mulmuley
DELAUNAY_FLIPPING
VORONOI
-------------------------------------------------------------------------------
windows and graphics
-------------------------------------------------------------------------------
many bugs fixed
improved panels and menues
choice_items and buttons with bitmaps
graphwin (experimental)
-------------------------------------------------------------------------------
New Demos
-------------------------------------------------------------------------------
in /prog/demo and /demo/...
segint_demo: segment intersection
delaunay_demo: delaunay and voronoi diagrams
graphwin: graphwin demo
LEDA-R 3.3.1 (Research Version)
- bug fix release
see file FIXES
- lconfig.bat now works with Windows NT and Windows 95 with compilers Watcom
10.5 (lconfig wcnt) and MSVC++ 4.0 (lconfig msvc).
The graphics part is also running under Windows!
see INSTALL.W32
- new tools (based on perl) for extracting and viewing the manual.
see directory Manual
the old methods are still available (directory man)
LEDA-R 3.3 (Research Version)
- new installation & configuration procedures for UNIX, dos, windows
(see INSTALL and INSTALL.dos ).
- new mechanism for avoiding name conflicts with other packages (STL),
(experimental, see the INSTALL file ).
- shared libraries for Solaris with SunPro C++ and g++
(see the INSTALL file ).
- const-ref parameters
All parameterized data types now use const reference parameters
for argument passing. This avoids unnecessary copy operations
which is particularly important when using non-simple type parameters.
- strings
string length explicityly stored in string_rep (efficiency)
bug in string::operator[](int) fixed
- hashing (h_array, _d_array)
bugs in ch_hash fixed
missing iteration statements added
- set
new operations for intersection, union, and difference of sets
- graphs
The implementation of graphs has been rewritten. Now undirected graphs
again have ordered adjacency lists (as in previous versions of LEDA)
and you can specify where a new edge is to be inserted into the adjacency
lists of both the source and target node of the edge.
Please read the new manual pages for graphs !
- planarity test
PLANAR: now works for multi-graphs
PLANAR1: new and faster test based on PQ-Trees
- planar_map
int M.number_of_faces() new
int M.size(face f) new
-Geometry
bug in circle::intersection(line/segment) fixed
bug in line::perpendicular(point) fixed
bugs in DELAUNAY_TRIANG fixed
use member initializationa in segment_rep(point,point)
new data type "rat_polygon"
point/rat_point
side_of_circle(a,b,c,d)
incircle(a,b,c,d)
outcircle(a,b,c,d)
cocircular(a,b,c,d)
- windows, panels, and colors
The window and panel types have been extended and (hopefully) improved.
Now panels and windows are essentially the same and you can include
panel items into your windows. A short description of the new features
can be found in "Changes.win" in this directory.
Two of the changes that probably will cause problems with old code are
+ W.read_mouse(...) now returns the constants MOUSE_BUTTON(i) (i=1,2,3)
instead of 1,2,3 for the left/middle/right button
+ windows have to be opened explicitely by W.open(...)
Please read the new manual pages for windows !
- Changes of global function and macro names
internally used functions:
Copy --> leda_copy
Convert --> leda_cast
Access --> leda_access
Clear --> leda_clear
Create --> leda_create
Int_Type --> leda_itype
Type_Name --> leda_tname
reverse iteration:
Forall(x,S) --> forall_rev(x,S)
Forall_nodes(v,G) --> forall_rev_nodes(v,G)
Forall_edges(e,G) --> forall_rev_edges(e,G)
LEDA-R 3.2.2 (Research Version)
Bugfix Release (see Fixes)
LEDA-R 3.2.1 (Research Version)
Bugfix Release (see Fixes)
LEDA-R 3.2 (Research Version)
The new release is mainly a bug-fix release, however it also contains some new
algorithms for graphs and computational geometry.
See the "Fixes" file for the list of fixed bugs.
------------------------------------------------------------------------------
1. GENERAL CHANGES
------------------------------------------------------------------------------
SYSTEM DEPENDENT FLAGS
has been split into a number of smaller files
The most important is . Here several flags are
defined indicating particular features or limitations of
compilers. Examples are
__BUILTIN_BOOL__
__NEW_SCOPE_RULES__
__TEMPLATE_FUNCTIONS__
__EXPLICIT_DESTRUCTION__
The current settings in have been tested with
g++-2.5.8, g++-2.6.3, g++-2.7.0, AT&T cfront 2.0.3, sunpro c++ 4.0.1,
lucid c++ 3.1 , watcom 10.0, zortech 3.1, borland 4.5
IF YOU ARE USING A DIFFERENT COMPILER OR VERSION YOU MAY HAVE TO EDIT THIS FILE.
MACROS
Macros "forever" and "loop" are no longer defined
ITERATION
The "forall(x,S)" macro can now be used to iterate over the elements
of arrays and d_arrays.
PARAMETERIZED DATA TYPES
The implementation of parameterized data types () has
been rewritten to make it more readable and stable. It now should work with
all c++ compilers supporting function templates. In particular the problems
on 64 bit architectures and the one-word bug have been fixed.
There is no special treatement of handle types anymore.
------------------------------------------------------------------------------
2. Data Types
------------------------------------------------------------------------------
string
the printf-like string(const char*,...) constructor has been
rewritten (should work now with all varargs - implementations)
vector/matrix
Read & Print with dimensions
integer
speed of addition/subtraction improved on SPARC
list
the split operation now has an additional parameter "dir"
indicating whether the splitting should happen before or after
the provided item
priority queues
new data structure: r_heap (redistributive heap)
d_array
delete operation: d_array::undefine(I i)
planar_map
new iteration macro:
forall_adj_faces(f,v)
{ "v is successively assigned all faces adjacent to node v" }
random_planar_graph
generates connected graphs now
New Graph Algorithms
MAX_WEIGHT_MATCHING
MIN_CUT
------------------------------------------------------------------------------
3. GEOMETRY
------------------------------------------------------------------------------
New Operations on (rat_)points and (rat_)segments
point::rot90
segment::rot90
rat_point::rot90
rat_segment::rot90
geometric primitives (evaluated exactly for rat_ ...):
orientation(point,point,point)
left_turn(point,point,point)
right_turn(point,point,point)
collinear(point,point,point)
incircle(point,point,point,point)
cmp_slopes(segment,segment)
Algorithms
void TRIANGULATE_POINTS(list L, GRAPH& G);
void DELAUNAY_TRIANGULATION(const list& L, GRAPH& T);
void DELAUNAY_TRIANGULATION(const list& L, graph& T,
node_array& pos,
edge_array& rev);
void DELAUNAY_TRIANGULATION(const list& L, planar_map& T,
node_array& pos);
SWEEP_SEGMENTS
The SWEEP_SEGMENTS function has been completely rewritten. It is
based on the new geometric primitives mentioned above which makes
the code more readable, robust and efficient. This also fixes bugs
in the SEGMENT_INTERSECTION function and the polygon::intersection
method (see also /web/sweep).
LEDA-R 3.1.1 (Research Version)
Many changes were made to make LEDA work with new compilers (g++-2.6.3,
Lucid \CC, Watcom \CC Sunpro \CC, ...) and on more platforms (Silicon
Graphics, IBM, HP, Solaris-2.3, Linux, ...). All reported bugs of version
3.0 we were able to find and understand have been fixed (see LEDA/Fixes
for a list). Several new data types and algorithms (especially in the graph
and window section) have been included.
------------------------------------------------------------------------------
Changes that might cause unexpected behavior or problems
------------------------------------------------------------------------------
The following list is not complete, please report all problems to
leda@mpi-sb.mpg.de
1. compare, Print, Read, and Hash
+ there are no predefined versions for pointer types anymore
so you will receive a run time error "compare undefined"
when, for example, sorting a list of pointers without having
defined a compare function for the pointer type.
+ in general, if you use one of these functions before declaring it
you will receive an error message. Uses can be hidden in instantiations
of parameterized types. Example:
list D; // here the default error template compare is instantiated.
// since list has an operation (sort) that uses compare
int compare(const T&, const T&); // error : compare multiply defined
dictionary D;
+ a possible bug in g++ :
if you declare a compare function static and define it later
in the file, g++ will not use it but will use the default
template version from .
Example:
class pair {
...
};
// declaration
static int compare(const pair&, const pair&);
// use
dictionary D;
// definition
int compare(const pair& p, const pair& q) { ... }
Using inline compare functions seems to be a work-around for this problem
(maybe extern works also ?).
2. ugraph
Some of the functionality of ugraphs available in previous versions, e.g.,
a linear ordering of all adjacent edges, is not supported in the
current version.
3. PLANAR(graph&, bool embed=false)
PLANAR has a different behavior: an embedding is constructed only
if the optional boolean flag embed is set to true.
4. random
There is no LEDA random function any more ( they caused a lot of problems
with existing random functions on many systems). Now LEDA contains
a new data type "random source" for the generation of different
types of random numbers.
5. The newly introduced numerical types bigfloat and real might cause problems
on several systems. If so, please report ... You can ignore all compiler
error messages if you do not intend to use these types.
------------------------------------------------------------------------------
Fixed Bugs (see also LEDA/Fixes)
------------------------------------------------------------------------------
- array::operator= fixed
- graph::read and graph::write
- node_set edge_set rewritten
- int_set: hard coded word size replaced by sizeof-call
- list::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*)
- array::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*)
- bug in vector::operator=(const vector&) fixed
- bug in rs_tree (set) copy constructor fixed
- LEDA_MEMORY: operator new & delete now use the size argument
- array copy constructor fixed
- memory leak in list::assign() fixed
- polygon CONVEX_HULL(list) new algorithm (Graham's Scan)
- bugs in segment::intersection() and line::intersection() fixed
- bug in binary heaps (negative integer keys) fixed
- UGRAPH::assign(node/edge,...) fixed
- bug in list graph::adj_nodes() (undirected graphs) fixed
- Iteration (forall_defined) for h_arrays
- some problems in _leda_panel.c fixed (slider items, buttons, ...)
- multi-definition problem with read_mouse(window, ...) and g++ fixed
- skiplist copy constructor
- memory leaks in leda panels
- nested forall-loops
- string::read now can read strings of arbitrary length
- made dlist::bucket_sort stable
- memory bug in dp_hash (dynamic perfect hashing) fixed
- k_heap::del_item fixed
- made rs_tree::change_inf (dictionary) clear old and copy new information
- dlist::search (replaced != by call of virtual cmp function)
- fixed bug in queue::append (replaced Convert by Copy)
- bugs in MAX_WEIGHT_BIPARTITE_MATCHING fixed (by M. Paul)
- prio.h: added missing ostream argument cout to Print calls
- stack::push(x) replaced Convert(x) by Copy(x)
- segment::angle() now returns zero for segments of length zero
- memory leak in draw_(filled_)polygon fixed
- bug in ab_tree::clear() fixed (forgot to set counter to zero)
- made dlist update operations protected
- missing operation ugraph::read(istream&) inserted
LEDA-R 3.1 (Research Version)
Manual Pages
All manual pages have been incorporated into the corresponding
header files. There are tools (see LEDA/man/README) to extract and
typeset the new user manual from these files. A postscript and
LaTeX version of the manual is available on the ftp server.
Parameterized Data Types
The LEDA_TYPE_PARAMERER macro that had to be called for type
arguments in parameterized data types when using the \gg compiler
is not needed anymore for \gg versions $>=$ 2.6.3.
Linear Orders, I/O, and Hashing
$compare$, $Hash$, $Read$ and $Print$ functions only have to be
defined for type parameters of a parameterized data type if they are
actually used by operations of the data type. If one of these function
is called and has not been defined explicitely, a default version giving
an error message is instantiated from a function template.
Except for the built-in types and some basic LEDA types ($string$ and
$point$) there are no predefined versions of these functions any more.
In particular, they are not predefined for arbitrary pointer types.
You will notice the effect of this change, for instance, when calling
the sort operation on a list of pointers $list$ for
without a definition of a compare function for $T*$. Previous LEDA
releases sorted the list by increasing addresses of the pointers in
this case. In version~3.1 the program will exit with the exception
``no compare function defined for $T*$". Operations based on functions
$Hash$, $Read$, or $Print$ show a similar behavior.
compare, ord, and hash function arguments
used e.g. in list::sort, array::sort, list::bucket_sort, ...
have to use const reference parameters, i.e., have to be of type
int cmp(const T&, const T&)
int ord(const T&)
Nested Forall Loops
The limitation of previous versions that {\bf forall}-loops (e.g.
on lists) could not be nested is no longer valid.
Graphs
