Next: Contents Up: LEDA home page Contents Index

$\includegraphics[angle=-90,width=8cm]{logo}$

Version 5.2

The LEDA User Manual

Algorithmic Solutions

Contents
License Terms and Availability
Preface
Basics
- Getting Started
- The LEDA Manual Page (the type specification)
- User Defined Parameter Types
- 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 )
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
- User Implementations
Technical Information
- LEDA Libraries and Packages
- Contents of a LEDA Source Code Package
- Source Code on UNIX Platforms
  - Source Code Configuration on UNIX
  - LEDA Compilation on UNIX
- Source Code on Windows with MS Visual C++
  - Source Code Configuration for MS Visual C++
  - LEDA Compilation with MS Visual C++
- Source Code on Windows with Borland C++
  - Source Code Configuration for Borland C++
  - LEDA Compilation 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
About this document ...

root 2007-03-08

Version 5.2 The LEDA User Manual

$\includegraphics[angle=-90,width=8cm]{logo}$

Version 5.2

The LEDA User Manual