Contents

• Contents
• Preface
• Basics
  • Getting Started
  • The LEDA Manual Page (the type specification)
  • User Defined Parameter Types
    • Linear Orders
    • Hashed Types
    • Implementation Parameters
  • Arguments
  • Items
  • Iteration
  • The LEDA Tools for Manual Production and Documentation
• Technical Information
  • Installation
    • Source Code Package
    • Object Code Packages
  • Usage
    • Header Files
    • Libraries
  • Namespaces, Standard Compliance, and Interaction with other Libraries
  • Platforms
• Simple Data Types and Basic Support Operations
  • Strings ( string )
  • File Input Streams ( file_istream )
  • File Output Streams ( file_ostream )
  • String Input Streams ( string_istream )
  • String Output Streams ( string_ostream )
  • Command Input Streams ( cmd_istream )
  • Command Output Streams ( cmd_ostream )
  • Random Sources ( random_source )
  • Random Variates ( random_variate )
  • Dynamic Random Variates ( dynamic_random_variate )
  • Memory Management
  • Memory Allocator ( leda_allocator )
  • Error Handling ( error )
  • Files and Directories ( file )
  • Some Useful Functions ( misc )
  • Two Tuples ( two_tuple )
  • Three Tuples ( three_tuple )
  • Four Tuples ( four_tuple )
  • A date interface ( date )
• Number Types and Linear Algebra
  • Integers of Arbitrary Length ( integer )
  • Rational Numbers ( rational )
  • Big Floatingpoint Numbers ( bigfloat )
  • Algebraic Real Numbers ( real )
  • A Floating Point Filter ( floatf )
  • Real-Valued Vectors ( vector )
  • Real-Valued Matrices ( matrix )
  • Vectors with Integer Entries ( integer_vector )
  • Matrices with Integer Entries ( integer_matrix )
  • Rational Vectors ( rat_vector )
  • Functions of Numerical Analysis ( )
    • Minima and Maxima
    • Integration
    • Useful Numerical Functions
    • Root Finding
• Basic Data Types
  • One Dimensional Arrays ( array )
  • Two Dimensional Arrays ( array2 )
  • Stacks ( stack )
  • Queues ( queue )
  • Bounded Stacks ( b_stack )
  • Bounded Queues ( b_queue )
  • Linear Lists ( list )
  • Singly Linked Lists ( slist )
  • Sets ( set )
  • Integer Sets ( int_set )
  • Dynamic Integer Sets ( d_int_set )
  • Partitions ( partition )
  • Parameterized Partitions ( Partition )
  • Dynamic Trees ( dynamic_trees )
  • Dynamic Collections of Trees ( tree_collection )
• Dictionaries
  • Dictionaries ( dictionary )
  • Dictionaries with Implementation Parameter ( _dictionary )
  • Sorted Sequences ( sortseq )
  • Sorted Sequences with Implementation Parameter ( _sortseq )
  • Dictionary Arrays ( d_array )
  • Dictionary Arrays with Implementation Parameter ( _d_array )
  • Hashing Arrays ( h_array )
  • Maps ( map )
  • Two-Dimensional Maps ( map2 )
  • Persistent Dictionaries ( p_dictionary )
• Priority Queues
  • Priority Queues ( p_queue )
  • Priority Queues with Implementation Parameter ( _p_queue )
  • Bounded Priority Queues ( b_priority_queue )
• Graphs and Related Data Types
  • Graphs ( graph )
  • Parameterized Graphs ( GRAPH )
  • Undirected Graphs ( ugraph )
  • Parameterized Ugraphs ( UGRAPH )
  • Planar Maps ( planar_map )
  • Parameterized Planar Maps ( PLANAR_MAP )
  • Node Arrays ( node_array )
  • Edge Arrays ( edge_array )
  • Face Arrays ( face_array )
  • Node Maps ( node_map )
  • Edge Maps ( edge_map )
  • Face Maps ( face_map )
  • Two Dimensional Node Arrays ( node_matrix )
  • Two-Dimensional Node Maps ( node_map2 )
  • Sets of Nodes ( node_set )
  • Sets of Edges ( edge_set )
  • Lists of Nodes ( node_list )
  • Node Partitions ( node_partition )
  • Node Priority Queues ( node_pq )
  • Bounded Node Priority Queues ( b_node_pq )
  • Graph Generators ( graph_gen )
  • Miscellaneous Graph Functions ( graph_misc )
  • Markov Chains ( markov_chain )
  • Dynamic Markov Chains ( dynamic_markov_chain )
  • GML Parser for Graphs ( gml_graph )
• Graph Algorithms
  • Basic Graph Algorithms ( basic_graph_alg )
  • Shortest Path Algorithms ( shortest_path )
  • Maximum Flow ( max_flow )
  • Min Cost Flow Algorithms ( min_cost_flow )
  • Minimum Cut ( min_cut )
  • Maximum Cardinality Matchings in Bipartite Graphs ( mcb_matching )
  • Bipartite Weighted Matchings and Assignments ( mwb_matching )
  • Maximum Cardinality Matchings in General Graphs ( mc_matching )
  • Maximum Weight Matchings in General Graphs ( max_weight_matching )
  • Minimum Spanning Trees ( min_span )
  • Algorithms for Planar Graphs ( plane_graph_alg )
  • Graph Drawing Algorithms ( graph_draw )
• Graphs and Iterators
  • Introduction
    • Iterators
    • Handles and Iterators
    • STL Iterators
    • Circulators
    • Data Accessors
    • Graphiterator Algorithms
  • Node Iterators ( NodeIt )
  • Edge Iterators ( EdgeIt )
  • Face Iterators ( FaceIt )
  • Adjacency Iterators for leaving edges ( OutAdjIt )
  • Adjacency Iterators for incoming edges ( InAdjIt )
  • Adjacency Iterators ( AdjIt )
  • Face Circulators ( FaceCirc )
  • Filter Node Iterator ( FilterNodeIt )
  • Comparison Predicate ( CompPred )
  • Observer Node Iterator ( ObserverNodeIt )
  • STL Iterator Wrapper ( STLNodeIt )
  • Node Array Data Accessor ( node_array_da )
  • Constant Accessors ( constant_da )
  • Node Member Accessors ( node_member_da )
  • Node Attribute Accessors ( node_attribute_da )
  • Breadth First Search (flexible) ( GIT_BFS )
  • Depth First Search (flexible) ( GIT_DFS )
  • Topological Sort (flexible) ( GIT_TOPOSORT )
  • Strongly Connected Components (flexible) ( GIT_SCC )
  • Dijkstra(flexible) ( GIT_DIJKSTRA )
• Basic Data Types for Two-Dimensional Geometry
  • Points ( point )
  • Segments ( segment )
  • Straight Rays ( ray )
  • Straight Lines ( line )
  • Circles ( circle )
  • Polygons ( POLYGON )
  • Generalized Polygons ( GEN_POLYGON )
  • Rational Points ( rat_point )
  • Rational Segments ( rat_segment )
  • Rational Rays ( rat_ray )
  • Straight Rational Lines ( rat_line )
  • Rational Circles ( rat_circle )
  • Geometry Algorithms ( geo_alg )
  • Transformation ( TRANSFORM )
  • Point Generators ( point generators )
• Advanced Data Types for Two-Dimensional Geometry
  • Two-Dimensional Dictionaries ( d2_dictionary )
  • Point Sets and Delaunay Triangulations ( POINT_SET )
  • Sets of Intervals ( interval_set )
  • Sets of Parallel Segments ( segment_set )
  • Planar Subdivisions ( subdivision )
• Basic Data Types for Three-Dimensional Geometry
  • Points in 3D-Space ( d3_point )
  • Straight Rays in 3D-Space ( d3_ray )
  • Segments in 3D-Space ( d3_segment )
  • Straight Lines in 3D-Space ( d3_line )
  • Planes ( d3_plane )
  • Spheres in 3D-Space ( d3_sphere )
  • Simplices in 3d space ( d3_simplex )
  • Rational Points in 3D-Space ( d3_rat_point )
  • Straight Rational Rays in 3D-Space ( d3_rat_ray )
  • Rational Lines in 3D-Space ( d3_rat_line )
  • Rational Segments in 3D-Space ( d3_rat_segment )
  • Rational Planes ( d3_rat_plane )
  • Rational Spheres ( d3_rat_sphere )
  • Rational Simplices ( d3_rat_simplex )
  • 3D Convex Hull Algorithms ( d3_hull )
• Graphics
  • Colors ( color )
  • Windows ( window )
  • Panels ( panel )
  • Menues ( menu )
  • Postscript Files ( ps_file )
  • Graph Windows ( GraphWin )
  • Geometry Windows ( GeoWin )
• Implementations
  • List of data structures
    • Dictionaries
    • Priority Queues
    • Geometry
  • User Implementations
    • Dictionaries
    • Priority Queues
    • Sorted Sequences
• Bibliography
• Index

Acknowledgement
Many people contributed to this new version of LEDA. Their names are listed in the Acknowledgements file in the LEDA root directory. The authors want to thank all of them for their bug reports, helpful suggestions and valuable comments.