The LEDA Tutorial

Joachim Ziegler

Version 0.5.3.pre7

01/09/2009 12:21:27



The need for speed and newness, which can only be satisfied by consumerism, reflects restlessness, the inner flight from oneself; [...] looking for the next thing to do or the newest gadget to use is only a means of protecting oneself from being close to oneself or to another person.

 -- Erich Fromm, To Have Or To Be?

This tutorium is dedicated to Erich Fromm (1900-1980), from whose books I have learned a lot, for example not permanently to be looking for the next thing to do and for the newest gadget to use to protect myself from being close to myself or to another person. Only sometimes.

Table of Contents

1. What is LEDA?
2. Whom does this tutorial address?
3. How is this tutorial built up?
4. In case of questions, remarks, and errors
5. About the author
6. Acknowledgement
1. On your marks - get set - LEDA!
1.1. Preparations
1.2. Hello LEDA world! - The very first program
1.3. Compiling, linking, and starting LEDA programs
1.3.1. The Unix world
1.3.2. The MS-Windows world
2. Simple data types and simple container types
2.1. Strings (class string)
2.1.1. Further operations on strings
2.1.2. The LEDA set of rules, handle types, and the categorization of the LEDA types
2.2. Arrays
2.2.1. One-dimensional arrays (class array)
2.2.2. Two-dimensional arrays (class array2)
2.2.3. Time complexity, space complexity, and the O-notation
2.3. Linear lists (class list)
2.3.1. Basic operations on lists
2.3.2. Lists and the item-container-concept
2.3.3. Changing lists and searching in lists
2.3.4. Sorting lists
2.3.5. User-defined type parameters
2.3.6. Copying and comparing item-based types and item types
2.3.7. Further information and tips
2.3.8. Singly linked lists (class slist)
2.4. Stacks
2.4.1. Stacks with an unbounded number of elements (class stack)
2.4.2. Stacks with a bounded number of elements (class b_stack)
2.5. Random numbers (class random_source)
2.5.1. The integer mode
2.5.2. The bit mode
2.6. Random variables
2.6.1. Static random variables (class random_variate)
2.6.2. Dynamic random variables (class dynamic_random_variate)
2.7. Queues
2.7.1. Queues with an unbounded number of elements (class queue)
2.7.2. Queues with a bounded number of elements (class b_queue)
2.8. Sets (class set)
2.8.1. Inserting elements and membership test
2.8.2. Union, intersection, and difference of sets
2.8.3. Linearly ordered types
2.9. Sets of integer numbers
2.9.1. If one knows minimum and maximum in advance (class int_set)
2.9.2. If minimum or maximum are unknown (class d_int_set)
2.10. array, list, stack, queue, set and d_int_set compared
2.11. Useful little somethings
2.11.1. Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)
2.11.2. Dealing with directories and files
2.11.3. Dates (class date)
2.11.4. Efficient memory management for self-defined types
2.11.5. Some useful functions
2.12. What we did not cover
3. Associative container types
3.1. Dictionaries (class dictionary)
3.2. Dictionary arrays (class d_array)
3.3. Hashing types
3.3.1. Hashing and hashed types
3.3.2. Hashing arrays (class h_array)
3.3.3. Maps (class map)
3.4. Sorted sequences (class sortseq)
3.4.1. Basic functionality
3.4.2. Finger search and fast insertion
3.4.3. Splitting, concatenating, and merging
3.5. dictionary, d_array, h_array, map, and sortseq compared
3.6. Implementation parameters
3.7. What we did not cover
4. Priority queues
4.1. Priority queues with unbounded priorities (class p_queue)
4.2. Priority queues with bounded integral priorities (class b_priority_queue)
5. Graphs and graph algorithms
5.1. Basics
5.2. Graphs and associated information
5.2.1. How to start
5.2.2. Associating information to graphs
5.2.3. Directed and undirected graphs
5.2.4. Iterating over nodes and edges and navigating in graphs
5.2.5. Creating and storing graphs and the editor GraphWin
5.2.6. Planarly embedded graphs, maps, and faces
5.2.7. Special auxiliary data structures for graph algorithms
5.3. Built-in graph algorithms
5.3.1. Algorithms for basic properties
5.3.2. Basic graph algorithms
5.3.3. Algorithms for shortest paths
5.3.4. Network flow algorithms
5.3.5. Matching algorithms
5.3.6. Minimum spanning trees
5.3.7. Algorithms for planar graphs
5.3.8. Algorithms for graph drawing
5.4. A self-written graph algorithm
5.5. Markov chains (classes markov_chain and dynamic_markov_chain)
5.6. What we did not cover
6. Number types
6.1. Integers of arbitrary length (class integer)
6.2. Rational numbers (class rational)
6.3. Floating point numbers of arbitrary size and precision (class bigfloat)
6.4. Algebraic real numbers (class real)
6.5. Vector and matrix types
6.5.1. Double-valued vector and matrices (classes vector and matrix)
6.5.2. Vectors and matrices with integer entries (clasess integer_vector and integer_matrix)
6.5.3. Real-valued vectors and matrices (classes real_vector and real_matrix)
6.5.4. Rational vectors (class rat_vector)
6.6. What we did not cover
A. Categorization of the LEDA data types
B. The golden LEDA rules

List of Figures

2.1. An array of characters
2.2. A LEDA array with negative indices
2.3. The method resize() of arrays
2.4. Pascal's triangle
2.5. A two-dimensional array
2.6. The rules of Conway's game of the life
2.7. Tic-Tac-Toe
2.8. Running time analysis of sorting by minimum search
2.9. The asymptotical bounds O and Θ
2.10. A deque
2.11. Inserting and deleting of elements at the beginning and end of a list
2.12. A list with 5 integer numbers
2.13. Iteration in a list with the help of items
2.14. The Josephus problem
2.15. Creating pairings
2.16. A singly linked list
2.17. A stack
2.18. A stack for the evaluation of arithmetic expressions
2.19. A Galton board
2.20. A random walk
2.21. A queue
2.22. Old system at the Saarbrücken Central Station
2.23. New system at the Saarbrücken Central Station
2.24. A set
2.25. The set operations intersection, union, and symmetric difference
2.26. A search tree
2.27. A fractal set
2.28. A set of integer numbers, realized as a bit vector
3.1. An English-German dictionary
3.2. A graph
3.3. Breadth first search
3.4. Hashing
3.5. Hashing with chaining
3.6. A sorted sequence
3.7. Items and containers in an sorted sequence
3.8. Finger search
4.1. Huffman coding as a complete binary tree
4.2. Construction of the Huffman code
5.1. A directed graph
5.2. An undirected graph
5.3. Graph or tree?
5.4. A dependency graph
5.5. The graph K3,3
5.6. Internal representation of a directed graph
5.7. Internal representation of an undirected graph
5.8. Editing graphs with GraphWin
5.9. Visualizing graphs with GraphWin
5.10. A DFS forest, calculated with DFS_NUM() and visualized by GraphWin
5.11. The non-planar Kuratowski graphs K5 and K3,3
5.12. The Saarland as a graph
5.13. The Saarland as a bidirected graph.
5.14. A map
5.15. Maps and face cycles
5.16. The Saarland as a planar map
5.17. A plane map of the Saarland that complies with a planar embedding
5.18. A connected graph that is not biconnected
5.19. Strongly connected components
5.20. A distance graph and shortest paths therein
5.21. A network
5.22. A maximum flow
5.23. A minimum cut
5.24. A network with edges incident to the source and leaving the sink.
5.25. The marriage problem
5.26. A maximum general, weighted matching
5.27. A minimum spanning tree
5.28. A planar graph and its dual graph
5.29. A five-coloring of a graph
5.30. Spring embedding a graph
5.31. Straight line embedding of a graph
5.32. A Tutte embedding of a graph
5.33. A genetic graph
5.34. A non-genetic graph
5.35. A Markov chain
6.1. The IEEE 754 double format
6.2. The Bisection method
A.1. Categorization of the LEDA data types

List of Tables

1.1. The LEDA libraries
2.1. array, list, stack, queue, set and d_int_set compared
3.1. dictionary, d_array, h_array, and map compared
4.1. The Huffman code
5.1. 5 possibilities to associate information to a graph