OS/2 Shareware BBS: 10 Tools

home *** CD-ROM | disk | FTP | other *** search

/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / CHANGES < prev next >

Wrap

Text File | 1996-09-03 | 67.1 KB | 2,141 lines

+==============================================================================+ | | | LEDA-R 3.4 | | | | RESEARCH VERSION | | | +==============================================================================+ ------------------------------------------------------------------------------- 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 <LEDA/param_types.h> 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<key,inf>) and its definition can be located in different source files (which was not possible in the previous version with many compilers). Example: #include <LEDA/list.h> 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<pair> 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 <LEDA>demo/geo - 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 <LEDA>/prog/demo and <LEDA>/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 | +==============================================================================+ - 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<I,E,ch_hash>) bugs in ch_hash fixed missing iteration statements added - set<T> 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 | +==============================================================================+ Bugfix Release (see Fixes) +==============================================================================+ | LEDA-R 3.2.1 | +==============================================================================+ 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 <LEDA/basic.h> has been split into a number of smaller files The most important is <LEDA/system.h>. 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 <LEDA/system.h> 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 (<LEDA/param_types.h>) 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<I,E>::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<point> L, GRAPH<point,edge>& G); void DELAUNAY_TRIANGULATION(const list<point>& L, GRAPH<point,edge>& T); void DELAUNAY_TRIANGULATION(const list<point>& L, graph& T, node_array<point>& pos, edge_array<edge>& rev); void DELAUNAY_TRIANGULATION(const list<point>& L, planar_map& T, node_array<point>& 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 <LEDA>/web/sweep). +==============================================================================+ | | | VERSION 3.1 | | | +==============================================================================+ 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<T> 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<T,int> 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 <LEDA/param_types.h>. Example: class pair { ... }; // declaration static int compare(const pair&, const pair&); // use dictionary<pair,int> 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<T>::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*) - array<T>::sort(cmp_func), ... for types T with sizeof(T) > sizeof(void*) - bug in vector::operator=(const vector&) fixed - bug in rs_tree (set<T>) 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<point>) 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<node> 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 -------------------------------------------------------------------------------- NEW FEATURES -------------------------------------------------------------------------------- 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<T*>$ 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 The distinction in directed and undirected graphs is not as strict as in previous versions. Data type $graph$ represents both directed and undirected graphs. Directed and undirected graphs only differ in the definition of adjacent edges or nodes. Now, two lists of edges are associated with every node $v$: the list $out_edges(v) = \{\ e \in E\ | source(e) = v\ \}$ of edges starting in $v$, and the list $in_edges(v) = \{\ e \in E\ | target(e) = v\ \}$ of edges ending in $v$. A graph is either {\em directed} or {\em undirected}. In a directed graph an edge is adjacent to its source and in an undirected graph it is adjacent to its source and target. In a directed graph a node $w$ is adjacent to a node $v$ if there is an edge $(v,w) \in E$; in an undirected graph $w$ is adjacent to $v$ if there is an edge $(v,w)$ or $(w,v)$ in the graph. There are iteration macros allowing to iterate over the list of starting, ending or adjacent edges (cf. \ref{Graphs} for details). New Data Types The old priority queue type $priority_queue<K,I>$ caused a lot of confusion because of the non-standard semantics of the type parameters $K$ and $I$ (the meaning of {\em key} and {\em information} was exchanged compared to most text book presentations of priority queues). To eliminate this confusion we introduced a new priority queue type $p_queue<P,I>$. Now $P$ is called the priority type of the queue. The basic library has been extended by several new numerical data types including an arbitrary length integer type ($integer$), a type of rational numbers ($rational$), and two filter types $ffloat$ and $real$ especially useful for floating point computations in geometric applications. Note that the temporarily (LEDA-3.1c) introduced data types $node_data$, $node_stack$, $node_queue$ are no longer available. Please use $node_map$, $edge_map$, $stack<node>$ and $queue<node>$ instead. A list of the new data types: priority queues p_queue<P,I> singly linked lists slist<T> big integers integer rational numbers rational floating point filter ffloat real numbers real rational point rat_point rational segments rat_segment maps map<I,E> node and edge maps node/edge_map<T> node lists node_list bounded node p_queues b_node_pq<n> Graph Generators and Algorithms LEDA now offers more generators for different types of graphs (see \ref{Graph Generators} for a complete list). The planarity test $PLANAR$ has been re-implemented and now has a boolean flag parameter $embed$. An embedding of the graph is computed only if $embed = true$. A second variant of $PLANAR$ computes a Kuratowsky-subgraph in the case of non-planarity. A new graph algorithm is $MIN_COST_MAX_FLOW$ computing a maximal flow with minimal cost. Windows and Panels The window and panel data types now are base on a plain X11 implementation. New features include -- opening more than one window or panel -- positioning, displaying, and closing of panels and windows -- changing the label of windows and panels -- 16 predefined colors -- accessing colors from the X11 data base by name -- drawing arcs, arc edges, and arc arrows -- changing the default fonts, -- reading and handling X11 events -- a simple graph editor (cf. <LEDA/graph_edit.h>) +==============================================================================+ | | | VERSION 3.0 | | | +==============================================================================+ LEDA-3.0 (template version) LEDA-N-3.0 (non-template version) ------------------------------------------------------------------------------ TEMPLATES & PARAMETERIZED DATA TYPES (cf. manual, section 1.1) ------------------------------------------------------------------------------ Starting with version 3.0 LEDA is using C++ templates for parameterized data types (e.g. dictionary<string,int>). This makes declare macros (e.g. declare2(dictionary,string,int)) and the "LEDA_TYPE_PARAMETER" macro obsolete. Any built-in, pointer, item, or user-defined class type can be used as actual type parameter for a parameterized data type. Class types however have to provide the following operations: a constructor taking no arguments T::T() a copy constructor T::T(const T&) a Read function void Read(T&, istream&) a Print function void Print(const T&, ostream&) A compare function "int compare(const T&, const T&)" (cf. section 1.4 of the user manual) has to be defined if required by the data type. Currently, the template version can be used with cfront 3.0.1 and g++-2.3.1. Note however that there are still many bugs in g++-2.3 (most of them should be fixed in the next version). In particular, there are problems with function templates that still make the use of the "LEDA_TYPE_PARAMETER" macro necessary for non-pointer type parameters. For compilers not supporting templates there is a non-template variant "LEDA-N" available whose parameterized data types are based on declare-macros as in the previous LEDA versions. See "prog/basic/param.c" for an example. ------------------------------------------------------------------------------ IMPLEMENTATION PARAMETERS (cf. user manual, section 1.2) ------------------------------------------------------------------------------ For many of the parameterized data types (dictionary,priority queue,d_array, sortseq) there are variants taking an additional data structure parameter for choosing a particular implementation, e.g. _dictionary<string,int,skiplist> D creates a dictionary D with key type string and information type int implemented by the skiplist data structure. Any such type _XYZ<T1,...,Tk,impl> is derived from the corresponding "normal" parameterized type XYZ<T1,...,Tk>, i.e., an instance of type _XYZ<T1,...,Tk,impl> can be passed as argument to functions with a formal parameter of type XYZ<T1,...,Tk>&. This provides a mechanism for choosing implementations of data types in pre-compiled algorithms. See "prog/graph/dijkstra.c" for an example. Language Limitations: -------------------- Templates cannot be overloaded (why ?), so we have to use different names. The names of data types with implementation parameters start with an underscore: _dictionary<K,I,impl> _priority_queue<K,I,impl> _d_array<I,E,impl> _sortseq<K,I,impl> Compiler Limitations: -------------------- Cfront 3.0.1 does not allow template arguments to be used as base classes. Therefore, we still have to use the macros from <generic.h> here: declare3(_dictionary,K,I,impl) ----> _dictionary(K,I,impl) declare3(_priority_queue,K,I,impl) ----> _priority_queue(K,I,impl) declare3(_sortseq,K,I,impl) ----> _sortseq(K,I,impl) declare3(_d_array,I,E,impl) ----> _d_array(K,I,impl) Example Programs: ----------------- _dictionary<K,I,impl> prog/dict/dic_test.c _priority_queue<K,I,impl> prog/graph/dijkstra.c _sortseq<K,I,impl> prog/plane/seg_int.c _d_array<K,I,impl> prog/dict/d_array_test.c A data structure "impl" for a data type has to provide a certain set of operations and to use certain virtual functions for type dependent operations (cf. manual, section 9). Sample header files for implementations of dictionaries, priority_queues, and sorted sequences can be found in <LEDA/impl/dic_impl.h>, <LEDA/impl/prio_impl.h>, <LEDA/impl/seq_impl.h>. ------------------------------------------------------------------------------ LINEAR ODERS ------------------------------------------------------------------------------ There is a new mechanism for deriving differently ordered type variants from a data type. The macro call DEFINE_LINEAR_ORDER(T,cmp,T1) introduces a new type T1 equivalent to type T with the linear order defined by the compare function "cmp". Examples: prog/basic/order.c prog/plane/order.c ------------------------------------------------------------------------------ GENERAL ------------------------------------------------------------------------------ "forall_xyz_items" no longer supported, use "forall_items" ------------------------------------------------------------------------------ Efficiency ------------------------------------------------------------------------------ The efficiency of many data types and algorithms has been improved. In particular: sorting (array::sort, list::sort) dictionaries, sets, d_arrays, sorted sequences (now implemented by randomized search trees) network algorithms: matching, minimum spanning tree (performance improved by a start heuristic) Macro LEDA_CHECKING_OFF: turns off range checking for arrays and node/edge_arrays (has to be defined before including LEDA header files) ------------------------------------------------------------------------------ Graphs ------------------------------------------------------------------------------ new operations: node G.first_node() node G.last_node() node G.succ_node(node) node G.pred_node(node) edge G.first_edge() edge G.last_edge() edge G.succ_edge(edge) edge G.pred_edge(edge) void G.make_undirected() inserts all edges (v,w) into the adjacency list of w i.e. both outgoing and incoming edges are traversed by forall_adj_edges void G.make_directed() removes all incoming edges from the adjacency lists void graph_edit(window& W, GRAPH<point,int>& G) cmdline_graph(graph& G, int argc, char** argv) builds a graph according to the command line arguments command line: <prog> ---> test_graph() <prog> n ---> complete graph with n nodes <prog> n m ---> random graph with n nodes and m edges <prog> file ---> read graph from "file" -------------------------------------------------------------------------------- planar_map (PLANAR_MAP) -------------------------------------------------------------------------------- edge P.split_edge(edge e) edge P.split_edge(edge e, vtype x) splits edge e and its reversal by introducing a new node u node p.new_node(face f) node p.new_node(face f, vtype x) splits face f into triangles by introducing a new node u and connecting it to all nodes of f node p.new_node(list<edge> el) node p.new_node(list<edge> el, vtype x) splits face bounded by the edges in el by introducing a new node u and connecting it to all source nodes of edges in el ------------------------------------------------------------------------------ node_pq<I> ------------------------------------------------------------------------------ I PQ.inf(node v) returns information of node v bool PQ.member(node v) true if v in PQ false otherwise ------------------------------------------------------------------------------ STRING ------------------------------------------------------------------------------ additional constructor string::string(char c) creates the one-character string "c" ------------------------------------------------------------------------------ MEMORY ------------------------------------------------------------------------------ LEDA_MEMORY_WITH_CHECK A debug version of the LEDA_MEMORY macro (cf. manual, section 7.3), gives an error message if the same pointer is deleted twice (slow!). ------------------------------------------------------------------------------ Directory Structure ------------------------------------------------------------------------------ a) All implementation header files have been moved to a new header subdirectory <LEDA/impl>. b) There is a new directory "util" containing some utility programs. Currently it contains a ksh variant of the Lman shell script, a program for shortening all file names to 15 characters (required by SCO UNIX/XENIX) and some DOS installation batch files. +==============================================================================+ | | | VERSION 2.2.2 | | | +==============================================================================+ minor changes for use with g++-2.2 and some bugs fixed +==============================================================================+ | | | VERSION 2.2.1 | | | +==============================================================================+ Some changes made for use with g++-2.1 and libg++-2.0 Some bugs fixed : string::operator+ matrix::operator= matrix::triang GRAPH::assign ... +==============================================================================+ | | | VERSION 2.2.0 | | | +==============================================================================+ -------------------------------------------------------------------------------- Parameterized data types -------------------------------------------------------------------------------- Now, arbitrary data types (not only pointer and simple types) can be used as type parameters. This makes data type "real" obsolete (use "double" or "float" instead), "real" is no longer included in the header file <LEDA/basic.h> but is still available in <LEDA/real.h>. Rules for type parameters: -------------------------- 1. Build-in types (char,int,long,float,double), pointer types, and LEDA simple types can be used as type parameters. 2. A class type T can be used as type parameter under the following conditions: a) The following operations and functions must be defined for T a constructor without arguments: T::T() an input operator: istream& operator>>(istream&,T&) an output operator: ostream& operator<<(ostream&,const T&) a compare function: int compare(const T&, const T&) b) The macro call LEDA_TYPE_PARAMETER(T) must appear before the first use of T as actual type parameter. c) If defined, destructor and copy constructor are used for copying and destroying objects. See "<LEDA>/prog/basic/param.c" for an example and for more informations and implementaion details: "S. N\"aher: Parameterized data types in LEDA", in preparation. -------------------------------------------------------------------------------- simple data types -------------------------------------------------------------------------------- Data type "real" is no longer supported (it is still available in <LEDA/real.h>) All parameters of type real have been replaced by double parameters. When reading the user manual take "real" as a synonym for "double". -------------------------------------------------------------------------------- graph -------------------------------------------------------------------------------- read & write overloaded for streams int G.read(istream I) reads compressed representation of G from I returns ... (see manual) int G.read(string file) reads compressed representation of G from file returns ... (see manual) void G.write(ostream O) writes compressed representation of G to O void G.write(string file) writes compressed representation of G to file -------------------------------------------------------------------------------- graph algorithms -------------------------------------------------------------------------------- bool PLANAR(graph& G) Planarity test: returns true iff $G$ is planar. If G is planar, it is transformed into a planar map by rearranging the adjaceny lists precondition: G is biconnected int BICONNECTED_COMPONENTS(ugraph& G, edge_array(int)& compnum) computes the biconnected components of the undirected graph G returns the number of biconnected components and in edge_array(int) compnum for each edge an integer with compnum[x]=compnum[y] iff edge x and y belong to the same biconnected component and 0 <= compnum[e]<=m-1 for all edges e -------------------------------------------------------------------------------- window -------------------------------------------------------------------------------- int W.get_button() non-blocking mouse read operation returns number of button (see read_mouse) if a button has been pressed and 0 otherwise void W.set_frame_label(string label) makes string "label" the window frame label -------------------------------------------------------------------------------- Memory Management: -------------------------------------------------------------------------------- Macro for making LEDA's memory managment available for user-defined data types LEDA_MEMORY(type) defines new & delete operators for "type" allocating and deallocating memory by LEDA's internal memory manager Example: class 3d_point { double x,y,z; public: ... LEDA_MEMORY(3d_point) }; Two functions for returning memory allocated by the LEDA memory manager to the system. void memory_clear() frees all currently not used memory blocks void memory_kill() frees all memory blocks regardless if they are still in use or not -------------------------------------------------------------------------------- New header files: -------------------------------------------------------------------------------- The basic two-dimensional data types point, segment, line, circle, polygon, and the 2d algorithms can be used separately by including the corresponding header files. The stream data types (file_istream, file_ostream, ...) are no longer included in <LEDA/basic.h> but are still available in <LEDA/stream.h> -------------------------------------------------------------------------------- Libraries: -------------------------------------------------------------------------------- The window library libWx.a (-lWx) or libWs.a (-lWs) now must appear after the plane library libP.a (-lP) on the compiler/linker command line. For example: CC prog.c -lP -lG -lL -lWx -lxview -lolgx -lX11 -lm or CC prog.c -lP -lG -lL -lWs -lsuntools -lsunwindow -lpixrect -lm +==============================================================================+ | | | VERSION 2.1.1 | | | +==============================================================================+ -------------------------------------------------------------------------------- vector/matrix -------------------------------------------------------------------------------- 1. Assignment (=) and comparison (==/!=) operators now can be applied to vectors/matrices with different dimensions. 2. The default initialization for arrays of vectors/matrices is the vector/matrix of dimension 0. 3. Problems with vector/matrix type parameters fixed. -------------------------------------------------------------------------------- graphics -------------------------------------------------------------------------------- graph_edit(window W, GRAPH(point,int) G, bool directed = true); Graph editor, edges are represented by arrows if directed = true and by segments if directed = false (declaration in <LEDA/graph_edit.h>) see example program "prog/graphics/matching.c" for details. -------------------------------------------------------------------------------- string -------------------------------------------------------------------------------- string(const char*, ...) new printf/form - like constructor e.g. s = string("x = %5.2f",x); -------------------------------------------------------------------------------- graph algorithms -------------------------------------------------------------------------------- list(edge) MAX_CARD_MATCHING(graph G) Maximum cardinality matching for general graphs, implemented by Edmond's Algorithm, returns list of matched edges. (source in "src/graph_alg/_mc_matching.c") (worst-case running time O(n*m) ) +==============================================================================+ | | | VERSION 2.1.0 | | | +==============================================================================+ -------------------------------------------------------------------------------- !!!!!!!!!!!! CHANGES IN HEADER FILES !!!!!!!!!!!!!!!!!! -------------------------------------------------------------------------------- I. <LEDA/graph.h> Header file <LEDA/graph.h> has been split into <LEDA/graph.h> : graph, GRAPH, node_array, edge_array <LEDA/ugraph.h> : ugraph, UGRAPH <LEDA/planar_map.h> : planar_map, PLANAR_MAP <LEDA/graph_alg.h> : graph algorithms + predefined node/edge array types node_array(int) edge_array(int) node_array(edge) edge_array(edge) node_array(bool) edge_array(bool); node_array(real) edge_array(real) node_matrix(bool) node_matrix(int) node_matrix(real) <LEDA/node_set.h> : node_set <LEDA/edge_set.h> : edge_set <LEDA/node_partition.h> : node_partition <LEDA/node_pq.h> : node_pq -------------------------------------------------------------------------------- II. <LEDA/plane.h> Header file <LEDA/plane.h> has been split into <LEDA/plane.h> : basic geometric objects (point,segment, ...) and predefined types list(point), list(segment), ... <LEDA/plane_alg.h> : plane algorithms, predefined type GRAPH(point,point) -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- data type "string" -------------------------------------------------------------------------------- int s.pos (string s_1, int i ) returns the first position of s_1 in s right of position i (-1 if no such position exists) string s.insert (string s_1, int i ) returns s(0,i-1) + s_1 + s(i+1,s.length()) Precondition:0 <= i <= s.length()-1 string s.replace (string s_1, string s_2, int i=1 ) returns the string created from s by replacing the i-th occurence of s_1 in s by s_2 string s.replace_all (string s_1, string s_2 ) returns the string created from s by replacing all occurences of s_1 in s by s_2 string s.replace (int i, int j, string s_1 ) returns the string created from s by replacing s(i,j) by s_1 string s.replace (int i, string s_1 ) returns the string created from s by replacing s[i] by s_1 string s.del (string s_1, int i=1 ) returns s.replace(s_1,"",i) string s.del_all (string s_1 ) returns s.replace_all(s_1,"") string s.del (int i, int j ) returns s.replace(i,j,"") string s.del (int i ) returns s.replace(i,"") void s.read (istream I, char delim = ' ' ) reads characters from input stream I into s until the first occurence of character delim void s.read (char delim = ' ' ) read(cin,delim) void s.readline (istream I ) read(I,'\n') void s.readline () readline(cin) -------------------------------------------------------------------------------- matrix -------------------------------------------------------------------------------- Operations matrix matrix::inv() O(n^3) vector matrix::solve(vector) O(n^2) double matrix::det() O(n^2) are now implemented by Gaussian eliminiation. matrix M.solve(matrix A) solves M*x_i = b_i simultaneously for all columns b_i of A, returns matrix (x_0,...,x_n-1) Preconditions: a) M is quadratic b) A.dim2() = M.dim1() -------------------------------------------------------------------------------- list -------------------------------------------------------------------------------- list_item L[int i] returns i-th item (nil if i<0 or i>L.length()-1) cost: O(i) -------------------------------------------------------------------------------- sortseq -------------------------------------------------------------------------------- void S.split (seq_item it, sortseq& S_1, sortseq& S_2 ) splits S at item it into sequences S_1 and S_2 and makes S empty. More precisely, if S = x_1,...,x_k-1,it,x_k+1,...,x_n then S1 = x_1,...,x_k-1,it and S2 = x_k+1,...,x_n Precondition: it is an item in S. sortseq& S.conc (sortseq& S_1 ) appends S_1 to S, makes S_1 empty, and returns S. Precondition: S.key(S.max()) <= S_1.key(S_1.min()). -------------------------------------------------------------------------------- graph G -------------------------------------------------------------------------------- void G.sort_nodes (node_array(T) A ) the nodes of G are sorted according to the entries of node_array A (cf. section 5.7) Precondition: T must be linearly ordered void G.sort_edges (edge_array(T) A ) the edges of G are sorted according to the entries of edge_array A (cf. section 5.7) Precondition: T must be linearly ordered pretty printing: void G.print(string s, ostream O) void G.print(string s) void G.print(ostream O) void G.print() void G.print_node(node v, ostream O = cout) void G.print_edge(edge e, ostream O = cout) -------------------------------------------------------------------------------- GRAPH(vtype,etype) G -------------------------------------------------------------------------------- void G.sort_nodes () the nodes of G are sorted according to their informations. Precondition: vtype is linearly ordered. void G.sort_edges () the edges of G are sorted according to their informations. Precondition: etype is linearly ordered. -------------------------------------------------------------------------------- node/edge_array -------------------------------------------------------------------------------- Creation of a node array (edge array):: a) ... b) ... c) ... d) node/edge_array(E) A(graph G, int n, E x) array for n nodes/edges of G Precondition: n >= |V| (|E|) +==============================================================================+ | | | VERSION 2.0.1 | | | +==============================================================================+ -------------------------------------------------------------------------------- GENERAL -------------------------------------------------------------------------------- forall_items(x,...) can be used for all kinds of items Read and Write functions for user defined I/O (cf. User Manual, section 1.5) must have an additional stream argument: Read(T&, istream&) defines an input function for reading objects of type T from an input stream. Write(T&,ostream&) defines an output function for printing objects of type T to an output stream. -------------------------------------------------------------------------------- string (section 2.3) -------------------------------------------------------------------------------- string s.tail(int i) returns the last i characters of s string s.head(int i) returns the first i characters of s -------------------------------------------------------------------------------- array (section 3.1) -------------------------------------------------------------------------------- void A.sort (int (*cmp)(E&, E&), int l, int h ) applies the sorting operation to the sub-array [l..h]. void A.read (istream I ) reads b-a+1 objects of type E from the input stream I into the array A using the overloaded Read function (section 1.5) void A.read () Calls A.read(cin) to read A from the standard input stream cin. void A.read (string s ) As above, but uses string s as a prompt. void A.print (ostream O, char space = ' ' ) Prints the contents of array A to the output stream O using the overload Print function (section 1.5) to print each element. The elements are separated by the space character space. void A.print (char space = ' ' ) Calls A.print(cout, space) to print A on the standard output stream cout. void A.print (string s, char space = ' ' ) As above, but uses string s as a header. -------------------------------------------------------------------------------- list (section 3.7) -------------------------------------------------------------------------------- void L.read (istream I, char delim = '\n' ) reads a sequence of objects of type E terminated by the delimiter delim from the input stream I using the overloaded Read function (section 1.5) L is made a list of appropriate length and the sequence is stored in L. void L.read (char delim = '\n' ) Calls L.read(cin, delim) to read L from the standard input stream cin. void L.read (string s, char delim = '\n' ) As above, but uses string s as a prompt. void L.print (ostream O, char space = ' ' ) Prints the contents of list L to the output stream O using the overload Print function (section 1.5) to print each element. The elements are separated by the space character space. void L.print (char space = ' ' ) Calls L.print(cout, space) to print L on the standard output stream cout. void L.print (string s, char space = ' ' ) As above, but uses string s as a header. void L.write (string fname ) writes G to the file with name fname. The overloaded functions Print(vtype,ostream) and Print(etype,ostream) (cf. section 1.6) are used to write the node and edge entries of G respectively. void L.read (string fname ) reads G from the file with name fname. The overloaded functions Read(vtype,istream) and Read(etype,istream) (cf. section 1.6) are used to read the node and edge entries of G respectively. -------------------------------------------------------------------------------- priority_queue (section 4.1) -------------------------------------------------------------------------------- Operation del_min has been overloaded K del_min() void del_min(K& k, I& i) removes an item x with minimal information assigns key(x) to k and inf(x) to i. -------------------------------------------------------------------------------- sortseq (section 4.6) -------------------------------------------------------------------------------- Operations "succ" and "pred" have been overloaded: seq_item S.succ(seq_item x) seq_item S.succ(K k) seq_item S.pred(seq_item x) seq_item S.pred(K k) NEW DATA TYPE: -------------------------------------------------------------------------------- 4.7 Persistent Dictionaries (p_dictionary) -------------------------------------------------------------------------------- 1. DEFINITION The difference between dictionaries (cf. section~4.3) and persistent dictionaries lies in the fact that update operations performed on a persistent dictionary D do not change D but create and return a new dictionary D'. For example, D.del(k) returns the dictionary D' containing all items it of D with key(it) != k. An instance D of the data type p_dictionary is a set of items (type p_dic_item). Every item in D contains a key from a linearly ordered data type K, called the key type of D, and an information from a data type I, called the information type of D. The number of items in D is called the size of D. A dictionary of size zero is called empty. We use <k,i> to denote an item with key k and information i (i is said to be the information associated with key k). For each k in K there is at most one item <k,i> in D. 2. DECLARATION declare2(p_dictionary,K,I) introduces a new data type with name p_dictionary(K,I) consisting of all persistent dictionaries with key type K and information type I. precond K is linearly ordered. 3. CREATION p_dictionary(K,I) D ; creates an instance D of type p_dictionary(K,I) and initializes D to an empty persistent dictionary. 4. OPERATIONS K D.key (dic_item it ) returns the key of item it. Precondition: it in D. I D.inf (dic_item it ) returns the information of item it. Precondition: it in D. dic_item D.lookup (K k ) returns the item with key k (nil if no such item exists in D). I D.access (K k ) returns the information associated with key k Precondition: there is an item with key k in D. p_dictionary(K,I) D.del (K k ) returns { x in D | key(x) != k }. p_dictionary(K,I) D.del_item (dic_item it ) returns { x in D | x != it }. p_dictionary(K,I) D.insert (K k, I i ) returns D.del(k) cup {<k,i>}. p_dictionary(K,I) D.change_inf (dic_item it, I i ) Let k = key(it), returns D.del_item(it) cup {<k,i>}. Precondition: it in D. p_dictionary(K,I) D.clear () returns an empty persistent dictionary. bool D.empty () returns true if D is empty, false otherwise. int D.size () returns the size of D. 5. ITERATION forall_items(i,D) { ``the items of D are successively assigned to i '' } 6. IMPLEMENTATION Persistent Dictionaries are implemented by leaf oriented persistent red black trees (cf. [DSST89]). Operations insert, lookup, del_item, del take time O(log n), key, inf, empty, size, change_inf and clear take time O(1). The space requirement is O(n). Here n is the number of all created persistent dictionaries (= number of all performed update operations). -------------------------------------------------------------------------------- GRAPH (section 5.4) -------------------------------------------------------------------------------- void G.write (string fname ) writes G to the file with name fname. The overloaded functions Print(vtype,ostream) and Print(etype,ostream) (cf. section 1.6) are used to write the node and edge entries of G respectively. int G.read (string fname ) reads G from the file with name fname. The overloaded functions Read(vtype,istream) and Read(etype,istream) (cf. section 1.6) are used to read the node and edge entries of G respectively. Returns error code 1 if file fname does not exist 2 if graph is not of type GRAPH(vtype,etype) 3 if file fname does not contain a graph 0 otherwise. -------------------------------------------------------------------------------- PLANE (section 6.1.6) -------------------------------------------------------------------------------- Function VORONOI (cf. section 6.1.6) has a new interface: void VORONOI(list(point), double R, GRAPH(point,point) ) VORONOI takes as input a list of points sites and a real number R. It computes a directed graph G representing the planar subdivision defined by the Voronoi-diagram of sites where all ``infinite" edges have length R. For each node v G.inf(v) is the corresponding Voronoi vertex (point) and for each edge e G.inf(e) is the site (point) whose Voronoi region is bounded by e. -------------------------------------------------------------------------------- point_set (section 6.3) -------------------------------------------------------------------------------- list(ps_item) S.convex_hull () returns the list of items containing all points of the convex hull of in clockwise order. -------------------------------------------------------------------------------- graphic windows (section 6.7) -------------------------------------------------------------------------------- Data type gwindow no longer exists, it is replaced by data type window The data type window provides an interface for the input and output of basic two-dimensinal geometric objects (cf. section 5.1) using the X11 (xview) or SunView window system. There are two object code libraries (libWs.a, libWx.a) containing implementations for different environments. Application programs using data type window have to be linked with one of these libraries (cf. section~1.6): a) For the SunView window system: CC prog.c -lWs -lP -lG -lL -lm -lsuntool -lsunwindow -lpixrect b) For the X11 (open windows) window system: CC prog.c -lWx -lP -lG -lL -lm -lxview -lolgx -lX11 -------------------------------------------------------------------------------- Creation of a graphic window -------------------------------------------------------------------------------- a) window W(int xpix, int ypix, int xpos, int ypos); b) window W(int xpix, int ypix); c) window W(); Variant a) creates a window W of physical size xpix times ypix pixels with its upper left corner at position (xpos,ypos) on the screen, variant b) places W into the upper right corner of the screen, and variant c) creates a 850 times 850 pixel window positioned into the upper right corner. All three variants initialize the coordinates of W to x0 = 0, x1 = 100 and y0 = 0. The init operation (see below) can later be used to change the window coordinates and scaling. -------------------------------------------------------------------------------- Additional operations -------------------------------------------------------------------------------- int W.read_panel (string h, int n, string* S ) displays a panel with header h and an array S[n] of n string buttons, returns the index of the selected button. int W.read_vpanel (string h, int n, string* S ) read_panel with vertical button layout int W.read_int (string p ) displays a panel with prompt p for integer input, returns the input real W.read_real (string p ) displays a panel with prompt p for real input returns the input string W.read_string (string p ) displays a panel with prompt p for string input, returns the input string W.read_string (string p, list(string) menu) as above, adds an additional menu button which can be used to select a string from menu. string W.read_string (string p, string label, list(string) menu) as above, the menu button is labelled with label. -------------------------------------------------------------------------------- PANELS -------------------------------------------------------------------------------- Creation: -------- panel P(string header); panel P; Operations: ---------- void P.text_item(string s) void P.bool_item(string label, bool& x) void P.real_item(string label, real& x) void P.color_item(string label, color& x) void P.int_item(string label, int& x) void P.int_item(string label, int& x, int min, int max) // slider void P.int_item(string label, int& x, int low, int high, int step) // choice void P.string_item(string label, string& x) void P.string_item(string label,string& x,list(string) L) // menu void P.choice_item(string label, int& x, list(string) L) void P.choice_item(string label, int& x, int l, string* L) void P.choice_item(string label, int& x, string, ... ) void P.button(string label) void P.new_button_line() void P.new_button_line(list(string) buttons) int P.open() int P.open(list(string)& buttons) -------------------------------------------------------------------------------- 7. Miscellaneous -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- Command input streams (cmd_istream) -------------------------------------------------------------------------------- An instance I of the data type cmd_istream is an C++ istream connected to the output of a shell command cmd, i.e., all input operations or operators applied to I read from the standard output of command cmd. 1. Creation of a command input stream cmd_istream in(string cmd); creates an instance in of type cmd_istream connected to the output of command cmd. 2. Operations All operations and operators (>>) defined for C++ istreams can be applied to command input streams as well. -------------------------------------------------------------------------------- Command output streams (cmd_ostream) -------------------------------------------------------------------------------- An instance O of the data type cmd_ostream is an C++ ostream connected to the input of a shell command cmd, i.e., all output operations or operators applied to O write into the standard input of command cmd. 1. Creation of a command output stream} cmd_ostream out(string cmd); creates an instance out of type cmd_ostream connected to the input of command cmd. 2. Operations All operations and operators (<<) defined for C++ ostreams can be applied to command output streams as well.