Guide to LEDA 4.3


CONTENTS

1   WHAT IS LEDA?

LEDA (Library of Efficient Data Types and Algorithms) is an object-oriented C++ library of combinatorial, graph, and geometric data types and algorithms. The main features that LEDA offers are:


2   GETTING STARTED

The users of LEDA should be familiar with the C++ programming language, and the Unix and X-Windows environments. Version 4.3 of LEDA can be accessed from the machines in ELW B215 (or ELW B228) by connecting to machine mayne.

2.1   Logging on to mayne

From the machines in ELW 215, connect to mayne as follows (connections can also be made from the machines in ELW B228):

1. Use the right button to bring up the "Workspace Menu".

2. Click on "Hosts" and on "This Host" in the Hosts menu.

3. Connect to mayne via "ssh your-account-name@mayne", and using your regular password.

4. In the terminal window, execute the following command to set the environment variable:

setenv LEDAROOT /package/leda-4.3
setenv PATH /package/gcc-2.95.3/bin:$PATH

These commands may be added to your .cshrc file (in your home directory, ie. ~/.chsrc ). This will avoid having to execute the commands every time you log in to use LEDA.


3   LEDA TEST AND DEMO PROGRAMS

LEDA offers two directories, $LEDAROOT/demo and $LEDAROOT/test, containing pre-compiled example programs along with their source code files. The programs in the test directory mainly have an ASCII interface, whereas the programs in the demo directory have a graphical user interface.

3.1   Running the Test and Demo Programs

The test programs can be run directly from the terminal screen by going to the desired subdirectory within the $LEDAROOT/test directory and calling the program you wish to run.

There are two ways to run the demo programs. They can be run like the test programs from the terminal screen, or by using the xlman utility, which provides a graphical user interface for invoking the LEDA demos.

To start xlman, enter

xlman &

on the command line. The following xlman utility window will appear:

The text box shows the name of the LEDA manual page, which can be selected from the dropdown menu by clicking on the downward arrow beside the text box. The six buttons along the bottom of the utility window have the following functionality (from left to right):

  • Viewing the manual page that is currently selected.
  • Printing the currently selected manual page.
  • Access to the demo programs. Clicking on the button presents a list of the demo programs, from which you can select which program to execute.
  • Viewing the source code for the demo programs.
  • Access to the LEDA documents.
  • Configuration options for the xlman utility.

3.2   Examples of LEDA Demo Programs

Quicksort Animation:

The Quicksort Animation Demo provides a visual demonstration of how the quicksort algorithm works. As described in the previous section, there are two ways to invoke the quicksort demo.

Open the xlman utility and click on Run --> animation --> quicksort_anim

or

in the terminal window, enter $LEDAROOT/demo/animation/quicksort_anim. 

The following window will appear:

The Main Panel window has four buttons which have the following effect (from left to right):

  • Starts the execution of the animation.
  • Opens a window with configuration options (such as the number of elements to be sorted).
  • Opens a window with information about the algorithm.
  • Exits the quicksort demo.

Once the Run button is clicked, the animation begins, showing the movements of the elements during the sort. When the animation is complete, the sorted list of elements is shown at the bottom of the screen.

Voronoi Demo:

The Voronoi Demo allows the user to construct the Voronoi diagram, Delaunay diagram, convex hull, and minimum spanning tree for a given set of points. To invoke the Voronoi demo, do the following:

Open the xlman utility and click on Run --> geowin --> geowin_voro

or

in the terminal window, enter $LEDAROOT/demo/geowin/geowin_voro. 

The following window will appear:

The help window provides some instructions on how to use the demo. After reading the instructions, click on close. Below the menu bar, there are two sets of buttons. The three buttons in the center allow you to choose whether you want to generate single points, points on a line, or points on a circle (respectively). Only one of these three buttons can be selected at a given time. To generate points, simply click in the window with the left mouse button.  The six buttons on the left compute the Voronoi diagram, the farthest point Voronoi diagram, the minimum spanning tree, the Delaunay diagram, the farthest point Delaunay diagram, and the convex hull (respectively) of the given set of points. Any number of these six buttons can be selected at a given time and the diagram is updated each time a point is added to the window. The following is an example of the Voronoi diagram (blue), Delaunay diagram (orange), and the minimum spanning tree (black) for a set of 17 points:

To exit the Voronoi Demo, click on the Done button or click on File --> Exit.


4   THE ONLINE LEDA USER MANUAL

The online LEDA user manual can be accessed from any web browser at the following URL:

http://www.algorithmic-solutions.com/enledadoku.htm

The manual contains the specifications for all of the data types and algorithms available in LEDA 4.3, and gives examples of their use. It also contains installation information and compilation and linkage instructions.

The specification page of a LEDA data type mainly consists of the following sections:

Sometimes, there is a fifth section showing an example of how to use the data type.


5   WRITING PROGRAMS USING LEDA

5.1   The LEDA Header Files

All of the LEDA data types and algorithms are defined in the header files in the $LEDAROOT/incl/LEDA directory. To use a particular data type or algorithm, include the appropriate header file. The example programs in Section 5.4 show examples of header file inclusion.

5.2   Compiling and Linking LEDA Programs

To compile a file, say prog.cc, use the following command (note: the -I flag tells the compiler where to find the LEDA header files):

g++ -I$LEDAROOT/incl -c prog.cc

To link, use the following command (note: the -L flag tells the compiler where to find the LEDA libraries):

g++ -L$LEDAROOT/lib prog.o -o prog (libs)

To compile and link simultaneously, use the following command:

g++ -I$LEDAROOT/incl -L$LEDAROOT/lib prog.cc -o prog (libs)

This will create an executable program file called prog.

The (libs) can be used as needed by including the appropriate library flags while linking:

-lL -lm basic data types
-lG -lL -lm graph data types
-lP -lG -lL -lm planar geometry
-lD3 -lP -lG -lL -lm 3d geometry
-lW -lP -lG -lL -lX11 -lm windows
-lGeoW -lD3 -lW -lP -lG -lL -lX11 -lm GeoWin

5.3   Some Useful Functions

For many data types, such as dictionaries, lists, sets, arrays, and graph nodes and edges, LEDA provides the following iteration macros:

item-based data types:

    forall_items (it, D)    iterates over the items it of D.

    forall_rev_items (it, D)    iterates, in reverse order, over the items it of D.

lists, sets, arrays:

    forall (x, L)    iterates over the elements x of L.

    forall_rev (x, L)    iterates, in reverse order, over the items x of L.

graphs:

    forall_nodes (v, G)    iterates over the nodes v of graph G.

    forall_edges (e, G)    iterates over the edges e of graph G.

    forall_adj_edges (e, v)    iterates over the edges e that are adjacent to node v.


LEDA also provides the following functions, defined in the basic.h header file, that are useful for time and space analysis:

    float used_time ()    returns the currently used CPU time in seconds.

    float used_time (float& T)    returns the CPU time used since time T and assigns the current CPU time to T.

    void leda_wait (double s)    suspends program execution for s seconds.

    void print_statistics ()    prints a summary of the currently used memory.

5.4   Example Programs

Program 1: factorial.cc

#include <LEDA/basic.h>
#include <LEDA/integer.h>

//compute factorial of integer n
integer factorial (integer n) {
    integer product = 1;

    for ( integer i = 1 ; i <= n; i++ )
        product = product * i;
    
    return product;
}

main() {
    //get an integer from user input
    integer n = read_int( "compute factorial of: " );

    float startTime = used_time ();   //store starting time
    integer fact = factorial ( n );   //compute factorial
    float timeUsed = used_time () - startTime;    //calculate time used

    //print factorial of n
    cout << "factorial of " << n << " is: " << fact << endl;

    //print time taken to compute the factorial
    cout << string("time used = %f seconds" , timeUsed) << endl;
}

Description:

The program starts with the include statement for the basic.h header file, which allows us to use the used_time function of LEDA, and the integer.h header file, which allows us to use the LEDA data type integer.  As opposed to the C++ data type int, LEDA's integer operations never overflow, which makes it ideal for computations of large numbers.  In our program, we use this data type to implement a simple function to compute factorials.  In the first line of the main program, we read an integer from standard input and assign it to variable n.  Then we store the currently used CPU time in variable startTime.  We call our factorial function to compute the factorial of n, and then we calculate the time used to do the computation and store it in variable timeUsed.  We print the value of the factorial and the computation time to standard output.

To compile and link the factorial.cc file, enter the following command in the terminal window:

g++ -I$LEDAROOT/incl -L$LEDAROOT/lib factorial.cc -o factorial -lL -lm

To execute: ./factorial

Sample Output:

compute factorial of: 100
factorial of 100 is: 933262154439441526816992388562667004
907159682643816214685929638952175999932299156089414639761
565182862536979208272237582511852109168640000000000000000
00000000
time used = 0.010000 seconds

Program 2: arrsort.cc

#include <LEDA/array.h>

main () {
    //get the size of the array from user input
    int n = read_int ( "Please enter the size of the array: " );

    array< int > intArr( 1, n ); 
    random_source numGen( 1, 1000 );

    //store randomly generated integers in the array
    for ( int i = 1 ; i <= n ; i++)
        intArr[ i ] = numGen();

    //print unsorted array
    intArr.print( " Original Array " );
    cout << "\n" ;

    intArr.sort();   //sort array

    //print sorted array
    intArr.print( " Sorted Array " );
    cout << "\n" ;
}

Description:

The program starts with the include statement for the array.h header file, which allows us to use the LEDA data type array. In the first line of the main program, we read an integer from standard input and assign it to variable n.  In the second line, we define an integer array intArr, indexed from 1 to n.  Next, we define a random_source numGen with a range from 1 to 1000.  In the for loop, we use numGen to generate random integers within the specified range, and store the integers in intArr.  Then, the contents of the array are printed to standard output.  We sort the array, and then the contents of the sorted array are printed to standard output.

To compile and link the arrsort.cc file, enter the following command in the terminal window:

g++ -I$LEDAROOT/incl -L$LEDAROOT/lib arrsort.cc -o arrsort -lL -lm

To execute: ./arrsort

Sample Output:

Please enter the size of the array: 10
 Original Array 12 806 309 684 525 698 946 97 921 781
 Sorted Array 12 97 309 525 684 698 781 806 921 946

Program 3: drawgraph.cc

#include <LEDA/graphwin.h>

main() {
    GraphWin gw;

    //define locations for the nodes
    point p1(100,100);
    point p2(400,100);
    point p3(100,400);
    point p4(400,400);

    //create nodes
    node v1 = gw.new_node(p1);
    node v2 = gw.new_node(p2);
    node v3 = gw.new_node(p3);
    node v4 = gw.new_node(p4);

    //create edges
    gw.new_edge(v1,v2);
    gw.new_edge(v3,v2);
    gw.new_edge(v4,v3);
    gw.new_edge(v1,v4);
    gw.new_edge(v2,v4);

    gw.display(); //display the graph
    gw.edit(); //put into edit mode
}

Description:

The program starts with the include statement for the graphwin.h header file, which allows us to use the LEDA data type graphwin. In the first line of the main program, we define a new GraphWin.  Next, we define points in the graph window, and create nodes at these points.  Then we create edges between the nodes by specifying the source node and the target node (respectively) as arguments to the new_edge function. By default, these are directed edges.  Finally we display the graph and put it into edit mode (so the window can be closed by clicking on the Done button, or by clicking on File --> Exit).  If we do not put it into edit mode, the graph window will be closed automatically after being displayed very briefly.  

To compile and link the drawgraph.cc file, enter the following command in the terminal window:

g++ -I$LEDAROOT/incl -L$LEDAROOT/lib drawgraph.cc -o drawgraph -lW -lP -lG -lL -lX11 -lm

To execute: ./drawgraph

Output:

Program 4: The Line Segment Intersection Problem

  // This program generates 10 red and 10 black points at random in a window.
  // Then it uses Dijkstra's analysis to find a set of line segments such that
  // every red point is connected to a black point, with no segments intersecting.

  // To compile the program: g++ -I$LEDAROOT/incl -c prog.cc 
  // To link the program:    g++ -L$LEDAROOT/lib prog.o -o prog -lGeoW -lD3 -lW -lP -lG -lL -lX11 -lm
  // To execute the program: ./prog

  #include <LEDA/basic.h>
  #include <LEDA/array.h>
  #include <LEDA/array2.h>
  #include <LEDA/integer.h>
  #include <LEDA/window.h>
  #include <LEDA/float_kernel.h>

  main()
  {window W;
   W.init(-0.1, 1.1, -0.1);
   point p(0,0);
   integer found;

   const int n = 20;

   array <point> P(1, 20); 
   array <circle> C(1,20);
   array2 <segment> S(1,20,1,20);

   for ( int i = 1 ; i <= n; i++)
      random_point_in_unit_square(P[i], 100);

   for ( int i = 1 ; i <= n; i++)
      C[i] = circle(P[i], 0.01);

   W.display();

   for ( int i = 1 ; i <= n/2; i++)
      W.draw_disc(C[i],red);

   for ( int i = n/2+1 ; i <= n; i++)
      W.draw_disc(C[i],black);

   leda_wait(5.0);

   for ( int i = 1 ; i <= n; i++)
   {for ( int j = i+1 ; j <= n; j++)
        S(i,j) = segment(p, p);}

   for ( int i = 1 ; i <= n/2; i++)
      S(i,i+n/2) = segment (P[i], P[i+n/2]);

   for ( int i = 1 ; i <= n; i++)
   {for ( int j = i+1 ; j <= n; j++)
      W.draw_segment(S(i,j),blue);}
 
   found = 0;

   while (found == 0)
   {found = 1;

    for ( int i = 1 ; i <= n; i++)
    {for ( int j = i+1; j <= n; j++)
    {for ( int k = i+1 ; k <= n; k++)
    {for ( int l = k+1 ; l <= n; l++)
       if ((S(i,j).start() != p) && (S(k,l).start() != p))
         if (S(i,j).intersection(S(k,l))) 
           {S(i,l) = segment(S(i,j).start(), S(k,l).end()); 
            S(k,j) = segment(S(k,l).start(), S(i,j).end());
            S(i,j) = segment(p,p);  S(k,l) = segment(p,p);

            W.clear();

            for ( int a = 1 ; a <= n/2; a++)
            W.draw_disc(C[a],red);

            for ( int a = n/2+1 ; a <= n; a++)
            W.draw_disc(C[a],black);

            for ( int a = 1 ; a <= n; a++)
            {for ( int b = 1 ; b <= n; b++)
            W.draw_segment(S(a,b),blue);}
            leda_wait(2.0);
            found = 0;
           }
   }}}
   }
 


//   leda_wait(5.0);

   read_char( "Hit a key to terminate" );

   W.close();
  }