LEDA: a platform for combinatorial and geometric computing

Contents Preface page xi 1 Introduction 1 1.1 Some Programs 1 1.2 The LEDA System 8 1.3 The LEDA Web-Site 10 1.4 Systems that Go Well with LEDA 11 1.5 Design Goals and Approach 11 1.6 History 13 2 Foundations 16 2.1 Data Types 16 2.2 Item Types 26 2.3 Copy, Assignment, and Value Parameters 32 2.4 More on Argument Passing and Function Value Return 36 2.5 Iteration 39 2.6 STL Style Iterators 41 2.7 Data Types and C++ 41 2.8 Type Parameters 45 2.9 Memory Management 47 2.10 Linearly Ordered Types, Equality and Hashed Types 47 2.11 Implementation Parameters 51 2.12 Helpful Small Functions 52 2.13 Error Handling 54 2.14 Program Checking 54 v vi Contents 2.15 Header Files, Implementation Files, and Libraries 56 2.16 Compilation Flags 57 3 Basic Data Types 58 3.1 Stacks and Queues 58 3.2 Lists 61 3.3 Arrays 73 3.4 Compressed Boolean Arrays (Type int set) 77 3.5 Random Sources 79 3.6 Pairs, Triples, and such 94 3.7 St LEDA is a library of efficient data types and algorithms in combinatorial and geometric computing. The main features of the library are its wide collection of data types and algorithms, the precise and readable specification of these types, its efficiency, its extendibility, and its ease of use. 1. Introduction Combinatorial and geometric computing is a core area of computer science. In fact, most CS curricula contain a course in data structures and algorithms. The area deals with objects such as graphs, sequences, dictionaries, trees, shortest paths, flows, matchings, points, segments, lines, convex hulls, and Voronoi diagrams and forms the basis for application areas such as discrete optimization, scheduling, traffic control, CAD, and graphics. There is no standard library of the data structures and algorithms of combinatorial and geometric computing. This is in sharp contrast to many other areas of computing. There are, e.g., packages in statistics (SPSS), numerical analysis (LINPAC..