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
  • Error Handling ( error )
  • Files and Directories ( file )
  • Some Useful Functions ( misc )
  • Two Tuples ( two_tuple )
  • Three Tuples ( three_tuple )
  • Four Tuples ( four_tuple )
• 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 )
• 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 )
  • Old-Style Priority Queues ( priority_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 )
• Graphs 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
  • Helper Types for Flexibly Adaptable Graph Algorithms
    • Iterators
    • STL iterators
    • Data Accessors
    • Graphiterator Algorithms
  • Node Iterators ( NodeIt )
  • Edge Iterators ( EdgeIt )
  • Adjacency Iterators for leaving edges ( OutAdjIt )
  • Adjacency Iterators for incoming edges ( InAdjIt )
  • Adjacency Iterators ( AdjIt )
  • 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 )
  • Planes ( d3_plane )
  • Rational Points in 3D-Space ( d3_rat_point )
  • Rational Planes ( d3_rat_plane )
  • 3D Convex Hull Algorithms ( d3_hull )
• Graphics
  • Colors ( color )
  • Windows ( window )
  • Panels ( panel )
  • Menues ( menu )
  • Postscript Files ( ps_file )
  • Graph Windows ( GraphWin )
• 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.