LEDA - A platform for Combinatorial and Geometric Computing

Preface......Page 12
1.1 Some Programs......Page 18
1.2 The LEDA System......Page 25
1.3 The LEDA Web-Site......Page 27
1.5 Design Goals and Approach......Page 28
1.6 History......Page 30
2.1 Data Types......Page 33
2.2 Item Types......Page 43
2.3 Copy, Assignment, and Value Parameters......Page 49
2.4 More on Argument Passing and Function Value Return......Page 53
2.5 Iteration......Page 56
2.7 Data Types and C++......Page 58
2.8 Type Parameters......Page 62
2.10 Linearly Ordered Types, Equality and Hashed Types......Page 64
2.11 Implementation Parameters......Page 68
2.12 Helpful Small Functions......Page 69
2.14 Program Checking......Page 71
2.15 Header Files, Implementation Files, and Libraries......Page 73
2.16 Compilation Flags......Page 74
3.1 Stacks and Queues......Page 75
3.2 Lists......Page 78
3.3 Arrays......Page 90
3.4 Compressed Boolean Arrays (Type int_set)......Page 94
3.5 Random Sources......Page 96
3.6 Pairs, Triples, and such......Page 111
3.7 Strings......Page 112
3.8 Making Simple Demos and Tables......Page 113
4.1 Integers......Page 116
4.2 Rational Numbers......Page 120
4.3 Floating Point Numbers......Page 121
4.4 Algebraic Numbers......Page 125
4.5 Vectors and Matrices......Page 134
5.1 Sparse Arrays: Dictionary Arrays, Hashing Arrays, and Maps......Page 138
5.2 The Implementation of the Data Type Map......Page 150
5.3 Dictionaries and Sets......Page 163
5.4 Priority Queues......Page 164
5.5 Partition......Page 175
5.6 Sorted Sequences......Page 197
5.7 The Implementation of Sorted Sequences by Skiplists......Page 213
5.8 An Application of Sorted Sequences: Jordan Sorting......Page 245
6.1 Getting Started......Page 257
6.2 A First Example of a Graph Algorithm: Topological Ordering......Page 261
6.3 Node and Edge Arrays and Matrices......Page 262
6.4 Node and Edge Maps......Page 266
6.5 Node Lists......Page 268
6.6 Node Priority Queues and Shortest Paths......Page 270
6.7 Undirected Graphs......Page 274
6.8 Node Partitions and Minimum Spanning Trees......Page 276
6.9 Graph Generators......Page 280
6.10 Input and Output......Page 286
6.11 Iteration Statements......Page 288
6.12 Basic Graph Properties and their Algorithms......Page 291
6.13 Parameterized Graphs......Page 297
6.14 Space and Time Complexity......Page 298
7.1 Templates for Network Algorithms......Page 300
7.2 Algorithms on Weighted Graphs and Arithmetic Demand......Page 303
7.3 Depth-First Search and Breadth-First Search......Page 310
7.4 Reachability and Components......Page 313
7.5 Shortest Paths......Page 333
7.6 Bipartite Cardinality Matching......Page 377
7.7 Maximum Cardinality Matchings in General Graphs......Page 410
7.8 Maximum Weight Bipartite Matching and the Assignment Problem......Page 430
7.10 Maximum Flow......Page 460
7.11 Minimum Cost Flows......Page 506
7.12 Minimum Cuts in Undirected Graphs......Page 508
8 Embedded Graphs......Page 515
8.1 Drawings......Page 516
8.2 Bidirected Graphs and Maps......Page 518
8.3 Embeddings......Page 523
8.4 Order-Preserving Embeddings of Maps and Plane Maps......Page 528
8.5 The Face Cycles and the Genus of a Map......Page 529
8.6 Faces, Face Cycles, and the Genus of Plane Maps......Page 532
8.7 Planarity Testing, Planar Embeddings, and Kuratowski Subgraphs......Page 536
8.8 Manipulating Maps and Constructing Triangulated Maps......Page 581
8.9 Generating Plane Maps and Graphs......Page 586
8.10 Faces as Objects......Page 588
8.11 Embedded Graphs as Undirected Graphs......Page 591
8.12 Order from Geometry......Page 592
8.13 Miscellaneous Functions on Planar Graphs......Page 594
9 The Geometry Kernels......Page 598
9.1 Basics......Page 600
9.2 Geometric Primitives......Page 610
9.3 Affine Transformations......Page 618
9.4 Generators for Geometric Objects......Page 621
9.5 Writing Kernel Independent Code......Page 623
9.6 The Dangers of Floating Point Arithmetic......Page 626
9.7 Floating Point Filters......Page 630
9.8 Safe Use of the Floating Point Kernel......Page 649
9.10 History......Page 651
9.11 LEDA and CGAL......Page 652
10.1 Convex Hulls......Page 654
10.2 Triangulations......Page 673
10.3 Verification of Geometric Structures, Basics......Page 681
10.4 Delaunay Triangulations and Diagrams......Page 689
10.5 Voronoi Diagrams......Page 703
10.6 Point Sets and Dynamic Delaunay Triangulations......Page 725
10.7 Line Segment Intersection......Page 748
10.8 Polygons......Page 775
10.9 A Glimpse at Higher-Dimensional Geometric Algorithms......Page 807
10.10 A Complete Program: The Voronoi Demo......Page 812
11 Windows and Panels......Page 830
11.1 Pixel and User Coordinates......Page 831
11.2 Creation, Opening, and Closing of a Window......Page 832
11.3 Colors......Page 834
11.4 Window Parameters......Page 835
11.6 The Input and Output Operators << and >>......Page 838
11.7 Drawing Operations......Page 839
11.8 Pixrects and Bitmaps......Page 840
11.9 Clip Regions......Page 845
11.10 Buffering......Page 846
11.11 Mouse Input......Page 848
11.12 Events......Page 851
11.13 Timers......Page 859
11.14 The Panel Section of a Window......Page 861
11.15 Displaying Three-Dimensional Objects: d3_window......Page 872
12 GraphWin......Page 874
12.1 Overview......Page 875
12.2 Attributes and Parameters......Page 878
12.3 The Programming Interface......Page 883
12.4 Edit and Run: A Simple Recipe for Interactive Demos......Page 892
12.5 Customizing the Interactive Interface......Page 896
12.6 Visualizing Geometric Structures......Page 907
12.7 A Recipe for On-line Demos of Network Algorithms......Page 909
12.8 A Binary Tree Animation......Page 914
13.2 A Simple List Data Type......Page 921
13.3 The Template Approach......Page 923
13.4 The LEDA Solution......Page 926
13.5 Optimizations......Page 946
13.6 Implementation Parameters......Page 951
13.7 Independent Item Types (Handle Types)......Page 954
13.8 Memory Management......Page 958
13.9 Iteration......Page 960
13.10 Priority Queues by Fibonacci Heaps (A Complete Example)......Page 963
14.1 Lman and Fman......Page 980
14.2 Manual Pages......Page 983
14.3 Making a Manual: The Mkman Command......Page 1001
14.4 The Manual Directory in the LEDA System......Page 1002
14.5 Literate Programming and Documentation......Page 1003
Bibliography......Page 1009
Index......Page 1019
Errata......Page 1036