Next: Contents Up: Data Structures and Efficient Algorithms Contents Index

The LEDA User Manual

Version 4.2

Kurt Mehlhorn
Max-Planck-Institut für Informatik,
66123 Saarbrücken, Germany

Stefan Näher
Fachbereich Mathematik und Informatik
Martin-Luther Universität Halle-Wittenberg
06099 Halle, Germany

Michael Seel
Max-Planck-Institut für Informatik,
66123 Saarbrücken, Germany

Christian Uhrig
Algorithmic Solutions Software GmbH,
Postfach 151101
66041 Saarbrücken, Germany

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
- Installation
  - Source Code Package
    - Configuration
    - Compilation
  - 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 ( )
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 )
- Partially Persistent Dictionaries ( pp_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 )
- Weighted Matchings in General Graphs ( 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 )
- 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
- User Implementations
Bibliography
Index
About this document ...

LEDA research project
2000-10-12

The LEDA User Manual Version 4.2

The LEDA User Manual

Version 4.2