home *** CD-ROM | disk | FTP | other *** search
- +==============================================================================+
- | |
- | 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 typ 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.
-
-
-