Next: Contents Up: LEDA home page

Version 4.4

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
- The LEDA Tools for Manual Production and Documentation
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
- Compiling LEDA for Usage with STD Headers with the Standard C++ Library
- 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
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 )
- 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 )
- 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 )
- Numerical Analysis Functions ( numerical_analysis )
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 )
- Sorted Sequences ( sortseq )
- Dictionary Arrays ( d_array )
- Hashing Arrays ( h_array )
- Maps ( map )
- Two-Dimensional Maps ( map2 )
- Persistent Dictionaries ( p_dictionary )
- Partially Persistent Dictionaries ( pp_dictionary )
Priority Queues
- Priority Queues ( 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 )
- General Weighted Matchings ( mw_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 )
- 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 )
- 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 )
- Windows for 3d visualization ( d3_window )
Implementations
- List of data structures
- User Implementations
Bibliography
Index
About this document ...