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
  
  
• Modules
• 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 )
  • 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 )
  • Sockets ( leda_socket )
  • Socket Streambuffer ( socket_streambuf )
  • Some Useful Functions ( misc )
  • Timer ( timer )
  • Counter ( counter )
  • Two Tuples ( two_tuple )
  • Three Tuples ( three_tuple )
  • Four Tuples ( four_tuple )
  • A date interface ( date )
  
  
• Alignment Data Types
  • Alphabet ( alphabet )
  • String Matching Algorithms ( string_matching )
  • Score Matrix ( score_matrix )
  • String Distance Function ( distance )
  • Alignment Functions ( alignment )
  
  
• Number Types and Linear Algebra
  • Integers of Arbitrary Length ( integer )
  • Rational Numbers ( rational )
  • The data type bigfloat ( bigfloat )
  • The data type real ( real )
  • Interval Arithmetic in LEDA ( interval )
  • Modular Arithmetic in LEDA ( residual )
  • The mod kernel of type residual ( residual )
  • The smod kernel of type residual ( residual )
  • A Floating Point Filter ( floatf )
  • Double-Valued Vectors ( vector )
  • Double-Valued Matrices ( matrix )
  • Vectors with Integer Entries ( integer_vector )
  • Matrices with Integer Entries ( integer_matrix )
  • Rational Vectors ( rat_vector )
  • Real-Valued Vectors ( real_vector )
  • Real-Valued Matrices ( real_matrix )
  • Numerical Analysis Functions ( numerical_analysis )
    • Minima and Maxima
    • Integration
    • Useful Numerical Functions
    • Root Finding
  
  
• Basic Data Types
  • 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 )
  
  
• Dictionary Types
  • Dictionaries ( dictionary )
  • Dictionary Arrays ( d_array )
  • Hashing Arrays ( h_array )
  • Maps ( map )
  • Two-Dimensional Maps ( map2 )
  • Persistent Dictionaries ( p_dictionary )
  • Partially Persistent Dictionaries ( pp_dictionary )
  • Sorted Sequences ( sortseq )
  
  
• Priority Queues
  • Priority Queues ( p_queue )
  • Bounded Priority Queues ( b_priority_queue )
  
  
• Lossless Compression
  • Adaptive Arithmetic Coder ( A0Coder )
  • Static Arithmetic Coder ( A0sCoder )
  • Prediction by Partial Matching ( PPMIICoder )
  • Deflation/Inflation Coder ( DeflateCoder )
  • Dictionary Based Coder ( DictCoder )
  • Static Huffman Coder ( HuffmanCoder )
  • Adaptive Huffman Coder ( AdaptiveHuffmanCoder )
  • Run-Length Coder ( RLECoder )
  • Burrows-Wheeler Transform ( BWTCoder )
  • Move-To-Front Coder ( MTFCoder )
  • Move-To-Front Coder II ( MTF2Coder )
  • RLE for Runs of Zero ( RLE0Coder )
  • Checksummers ( checksummer_base )
  • CRC32 Checksum ( CRC32Coder )
  • CRC-CCITT Checksum ( CCITTCoder )
  • Adler32 Checksum ( Adler32Coder )
  • MD5 Checksum ( MD5SumCoder )
  • SHA-1 Checksum ( SHACoder )
  • Encoding Output Stream ( encoding_ostream )
  • Decoding Input Stream ( decoding_istream )
  • Encoding File Stream ( encoding_ofstream )
  • Decoding File Stream ( decoding_ifstream )
  • Coder Pipes ( CoderPipe2 )
  • Automatic Decoder ( AutoDecoder )
  • Block Coder ( BlockCoder )
  • Memory Streambuffer ( memory_streambuf )
  
  
• Symmetric Key Cryptography
  • Secure Byte String ( CryptByteString )
  • Key for Cryptography ( CryptKey )
  • Encryption and Decryption with Ciphers
  • Example for a Stream-Cipher ( CBCCoder )
  • Authentication ( OMACCoder )
  • Automatic Decoder supporting Cryptography ( CryptAutoDecoder )
  • Secure Socket Streambuffer ( secure_socket_streambuf )
  
  
• Graphs and Related Data Types
  • Graphs ( graph )
  • Parameterized Graphs ( GRAPH )
  • Static Graphs ( static_graph )
  • Undirected Graphs ( ugraph )
  • Parameterized Ugraph ( 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 )
  • The LEDA graph input/output format
  
  
• 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 )
  • General Weighted Matchings ( mw_matching )
  • Stable Matching ( stable_matching )
  • Minimum Spanning Trees ( min_span )
  • Euler Tours ( euler_tour )
  • Algorithms for Planar Graphs ( plane_graph_alg )
  • Graph Drawing Algorithms ( graph_draw )
  • Graph Morphism Algorithms ( graph_morphism )
  • Graph Morphism Algorithm Functionality ( graph_morphism_algorithm )
  
  
• 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 )
  • Triangles ( triangle )
  • Iso-oriented Rectangles ( rectangle )
  • Rational Points ( rat_point )
  • Rational Segments ( rat_segment )
  • Rational Rays ( rat_ray )
  • Straight Rational Lines ( rat_line )
  • Rational Circles ( rat_circle )
  • Rational Triangles ( rat_triangle )
  • Iso-oriented Rational Rectangles ( rat_rectangle )
  • Real Points ( real_point )
  • Real Segments ( real_segment )
  • Real Rays ( real_ray )
  • Straight Real Lines ( real_line )
  • Real Circles ( real_circle )
  • Real Triangles ( real_triangle )
  • Iso-oriented Real Rectangles ( real_rectangle )
  • Geometry Algorithms ( geo_alg )
  • Transformation ( TRANSFORM )
  • Point Generators ( point generators )
  • Point on Rational Circle ( r_circle_point )
  • Segment of Rational Circle ( r_circle_segment )
  • Polygons with circular edges ( r_circle_polygon )
  • Generalized polygons with circular edges ( r_circle_gen_polygon )
  • Parser for well known binary format ( wkb_io )
  
  
• 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 )
  • Sets of Parallel Rational Segments ( rat_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 )
  • 3D Triangulation and Voronoi Diagram Algorithms ( d3_delaunay )
  
  
• Graphics
  • Colors ( color )
  • Windows ( window )
  • Panels ( panel )
  • Menues ( menu )
  • Postscript Files ( ps_file )
  • Graph Windows ( GraphWin )
  • The GraphWin (GW) File Format
    • A complete example
  • Geometry Windows ( GeoWin )
  • Windows for 3d visualization ( d3_window )
  
  
• Implementations
  • List of data structures
    • Dictionaries
    • Priority Queues
    • Geometry
  • User Implementations
    • Dictionaries
    • Priority Queues
    • Sorted Sequences
  
  
• Technical Information
  • LEDA Libraries and Packages
  • Contents of a LEDA Source Code Package
  • Source Code on UNIX Platforms
  • Source Code on Windows with MS Visual C++
  • Source Code on Windows with Borland C++
  • Compiling LEDA for Multithreading
  • Usage of Header Files
  • Object Code on UNIX
  • Static Libraries for MS Visual Studio 6
  • DLL's for MS Visual Studio 6
  • Static Libraries for MS Visual C++ .NET
  • DLL's for MS Visual C++ .NET
  • Static Libraries for Borland C++
  • DLL's for Borland C++
  • Namespaces and Interaction with other Libraries
  • Platforms
  
  
• The golden LEDA rules
  • The LEDA rules in detail
  • Code examples for the LEDA rules
  
  
• The LEDA Tools for Manual Production and Documentation
• Bibliography
• Index