Index

Symbols

!=

integer, Integers of arbitrary length (class integer)

%

integer, Integers of arbitrary length (class integer)

%=

integer, Integers of arbitrary length (class integer)

&

int_set, If one knows minimum and maximum in advance (class int_set)

&&

integer, Integers of arbitrary length (class integer)

&&=

integer, Integers of arbitrary length (class integer)

()

random_source, The integer mode
string, Tips for the use of the class string

(a,b)-tree

niveau-connected, Finger search and fast insertion

*

integer, Integers of arbitrary length (class integer)

*=

integer, Integers of arbitrary length (class integer)

+

date, Dates (class date)
integer, Integers of arbitrary length (class integer)
string, Further operations on strings

++

date, Dates (class date)
integer, Integers of arbitrary length (class integer)

+=

integer, Integers of arbitrary length (class integer)
string, Strings (class string)

-

date, Dates (class date)
integer, Integers of arbitrary length (class integer)

--

date, Dates (class date)
integer, Integers of arbitrary length (class integer)

-=

integer, Integers of arbitrary length (class integer)

-MDd

compiler option, Compiling, linking, and starting

-Tp

compiler option, Compiling, linking, and starting

.gml (see gml format)

.gw (see standard format)

/

integer, Integers of arbitrary length (class integer)

/=

integer, Integers of arbitrary length (class integer)

<

integer, Integers of arbitrary length (class integer)
set, Union, intersection, and difference of sets

<<

integer, Integers of arbitrary length (class integer)

<=

integer, Integers of arbitrary length (class integer)

=, Simple-structured types and their copy concept

(see also type and copy concept)
list, Copying of objects of an item-based type
string, Further operations on strings
with simple-structured types, Simple-structured types and their copy concept

==, Comparisons of LEDA objects

(see also equality predicate)
and hashed types, Hashing in LEDA
integer, Integers of arbitrary length (class integer)
list, Comparisons of LEDA objects
string, Strings (class string)

>

integer, Integers of arbitrary length (class integer)

>=

integer, Integers of arbitrary length (class integer)

>>

random_source, The integer mode, The bit mode

[]

array, Defining arrays and access to elements
d_array, Dictionary arrays (class d_array)
dictionary, Dictionaries (class dictionary)
edge_map, Node maps and edge maps
GRAPH, The class GRAPH, Graph iterators
list, Lists and the item-container-concept
map, Maps (class map)
node_array, Node arrays and edge arrays
node_map, Node maps and edge maps
string, Strings (class string)

|

int_set, If one knows minimum and maximum in advance (class int_set)
integer, Integers of arbitrary length (class integer)

|=

integer, Integers of arbitrary length (class integer)

~

int_set, If one knows minimum and maximum in advance (class int_set)
integer, Integers of arbitrary length (class integer)

Θ(f(n)), The O-notation

A

adj_edges(v), Directed graphs in LEDA

adj_pred()

graph, Influencing the order in in_edges(v) and out_edges(v)

adj_succ()

graph, Influencing the order in in_edges(v) and out_edges(v)

adjacency list, Directed graphs in LEDA

cyclic predecessor, Face cycles
cyclic successor, Face cycles

adjacent, Basics, Undirected graphs in LEDA

AdjIt, Graph iterators

Algorithmic Solutions, Purchasing LEDA

ALL_PAIRS_SHORTEST_PATHS(), Running times and further information

amortized analysis, Amortized analysis

anagram, An example: Lists of string pairs in the computation of anagrams

ancestor

of a node, Exercises

animation

in GraphWin, Spring Embedding

animation_steps

GraphWin, Spring Embedding

anti-symmetry, Linear orders

append

to queue, Queues

append()

list, Appending and deleting of elements at the end of a list
queue, Queues with an unbounded number of elements (class queue)

apply()

list, Further list modifying operations

array, Arrays

and set, Sets (class set)

as opposed to lists, Linear lists (class list)

constructor, Defining arrays and access to elements

doubling strategy, Exercises

dynamical enlarging, Enlarging arrays dynamically

of arrays, Two-dimensional arrays (class array2)

rotating elements, Exercises

two-dimensional, Two-dimensional arrays (class array2)

(see also array2)

array2, Two-dimensional arrays (class array2)

constructor, Two-dimensional arrays (class array2)

articulation point, Connected and biconnected graphs

assign()

list, Lists and the item-container-concept

assignment operator

and LEDA objects, Copying of objects of an item-based type

(see also type and copy concept)

assignment problem, Matching algorithms

asymptotical, The O-notation

attribute

of an item, Lists and the item-container-concept

automaton

cellular, Two-dimensional arrays (class array2)

B

b_node_pq, Special auxiliary data structures for graph algorithms

b_pq_item, Priority queues with bounded integral priorities (class b_priority_queue)

b_priority_queue, Priority queues, Priority queues with bounded integral priorities (class b_priority_queue)

b_queue, Queues, Queues with a bounded number of elements (class b_queue)

constructor, Queues with a bounded number of elements (class b_queue)

b_stack, Stacks, Stacks with a bounded number of elements (class b_stack)

constructor, Stacks with a bounded number of elements (class b_stack)

back()

list, Changing lists and searching in lists

bag

implementation by associative container types, array, list, stack, queue, set and d_int_set compared

basic_graph_alg.h, A first program, Basic graph algorithms

beast of burden, Stacks

BFS(), The class GRAPH

BICONNECTED_COMPONENTS(), Running times and further information

big marriage bureau, Union, intersection, and difference of sets

binary search, Useful methods of the class array, Exercises

binary_locate()

array, Useful methods of the class array

binary_search()

array, Useful methods of the class array

binomial coefficient, Enlarging arrays dynamically

Binomial distribution, The bit mode

binomial distribution, Queues with an unbounded number of elements (class queue)

border_color

GraphWin, Attributes of GraphWin

border_width

GraphWin, Attributes of GraphWin

bound

asymptotically lower, The O-notation
asymptotically upper, The O-notation

boxing club

creating pairs, Exercises

breadth first search, A working example: Breadth first search in a graph, Algorithms for shortest paths

with BFS(), The class GRAPH

bucket_sort()

list, Sorting lists

bucket_sort_nodes()

graph, Iterating over all nodes and edges

C

capacity

of an edge in a network, Maximum flows

capacity constraint, Maximum flows

cardinality matching, Maximum bipartite, unweighted matchings, Maximum general, unweighted matchings.

chance, Random numbers (class random_source)

change_inf()

dictionary, Dictionaries (class dictionary)
p_queue, Priority queues with unbounded priorities (class p_queue)
sortseq, Basic functionality

chess tournament

creating pairings, Exercises

child

of a node, Exercises

choose()

set, Inserting elements and membership test

Christian Uhrig , What we did not cover

clear()

d_array, Dictionary arrays (class d_array)
int_set, If one knows minimum and maximum in advance (class int_set)
map, Maps (class map)
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

coding

prefix-free, A working example: Huffman coding

optimal, A working example: Huffman coding

with fixed length, A working example: Huffman coding

with variable length, A working example: Huffman coding

collision

during hashing, Hashing with chaining and table doubling

color

GraphWin, Attributes of GraphWin

coloring problem, Coloring problems and dual graphs

compare(), Sorting lists, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

and linear order, Linearly ordered types
and namespace leda, Making a type of our own linearly ordered
by means of polar coordinates, Exercises
defining several linear orders on a type, Several linear orders on a type

compare-equivalent, Linearly ordered types

complete_graph()

graph, Graph generators

completion number, An example: Visualizing DFS_NUM()

complexity

quadratic, Time complexity
space, Space complexity
time, Time complexity

component

strongly connected, of a graph, Strongly connected components

COMPONENTS(), Strongly connected components

compound type, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

compression method

Huffman coding, A working example: Huffman coding

compression rate, A working example: Huffman coding

compute_faces()

graph, Face cycles

conc()

list, Further list modifying operations
sortseq, Splitting, concatenating, and merging

connected component, Exercises

strongly connected, Strongly connected components

constant

time complexity, The O-notation

constructor

with specification of the linear order, Several linear orders on a type

container

and items, Lists and the item-container-concept

associative

requirements on key type, Order of the pairs in an associative container and requirements on the key type

container type, Defining arrays and access to elements, Filling and emptying lists

associative, Associative container types

comparison of the types of LEDA, dictionary, d_array, h_array, map, and sortseq compared
order of elements, Order of the pairs in an associative container and requirements on the key type

simple, Simple data types and simple container types

comparison of LEDA's types, array, list, stack, queue, set and d_int_set compared

contents()

list, Lists and the item-container-concept

Conway's game of life, Two-dimensional arrays (class array2)

copy

of a graph

isomorphic, Copying graphs

CopyGraph(), Copying graphs

core module, Structure of include directories as of LEDA 5.0

creating Latin random texts, A working example: Creating Latin random texts

cut

minimum, Minimum cuts
of a network, Minimum cuts
value, Minimum cuts

cut edge, Minimum cuts

cut vertex (see articulation point)

cycle, Basics

negative, in a distance graph, Algorithms for shortest paths

cyclic_adj_pred()

graph, Influencing the order in in_edges(v) and out_edges(v), Face cycles

cyclic_adj_succ()

graph, Influencing the order in in_edges(v) and out_edges(v), Face cycles

cyclic_pred()

list, Lists and the item-container-concept

cyclic_succ()

list, Lists and the item-container-concept

D

d_array, Dictionary arrays (class d_array)

constructor and default value, Dictionary arrays (class d_array)

d_int_set, Sets of integer numbers, If minimum or maximum are unknown (class d_int_set)

constructor, If minimum or maximum are unknown (class d_int_set)

data label, Reading from and writing to a file

data type

abstract, Implementation parameters
simple, Simple data types and simple container types

date, Dates (class date) (see date)

constructor, Dates (class date)

decrease_inf()

b_priority_queue, Priority queues with bounded integral priorities (class b_priority_queue)

decrease_p()

p_queue, Priority queues with unbounded priorities (class p_queue)

default initialization, Strings (class string)

default order, An example: Lists of string pairs in the computation of anagrams, Linearly ordered types

DEFINE_LINEAR_ORDER, Several linear orders on a type

defined()

d_array, Dictionary arrays (class d_array)
map, Maps (class map)

degree, Basics

degree()

graph, An example

del()

dictionary, Dictionaries (class dictionary)
int_set, If one knows minimum and maximum in advance (class int_set)
set, Inserting elements and membership test
string, Further operations on strings

del_edge()

graph, A first program

del_item()

list, Changing lists and searching in lists
p_queue, Priority queues with unbounded priorities (class p_queue)

del_message()

GraphWin, The programming interface of the class GraphWin

del_min()

p_queue, Priority queues with unbounded priorities (class p_queue)

del_node()

graph, A first program

delete, Efficient memory management for self-defined types

Delete_Loops(), Further functions

dependency graph, How to start

depth first search, Exercises

with DFS(), Algorithms for systematic searching
with DFS_NUM(), An example: Visualizing DFS_NUM()

descendant

of a node, Exercises

DFS number, An example: Visualizing DFS_NUM()

DFS(), Algorithms for systematic searching

DFS_NUM(), An example: Visualizing DFS_NUM()

dic_item, Dictionaries (class dictionary)

dice

fair, The integer mode
loaded, Static random variables (class random_variate)

dictionary, Dictionaries (class dictionary)

persistent, Persistent dictionaries

dictionary array, Dictionary arrays (class d_array)

(see also d_array)

dictionary type, Dictionaries (class dictionary)

diff()

set, Union, intersection, and difference of sets

difference

of sets, Union, intersection, and difference of sets
symmetric, Union, intersection, and difference of sets

direction

GraphWin, Attributes of GraphWin

directory

traversing, Dealing with directories and files

discrete event simulation, Priority queues

display()

GraphWin, The programming interface of the class GraphWin

distance

of two nodes, A working example: Breadth first search in a graph, Algorithms for shortest paths

doubling strategy

and arrays, Exercises

download area

of the tutorial, Additional materials

drawing

a graph vs. embedding, Spring Embedding

dynamic_markov_chain, The class dynamic_markov_chain

dynamic_random_variate, Random variables , Dynamic random variables (class dynamic_random_variate)

constructor, Dynamic random variables (class dynamic_random_variate)

dynamic_trees, What we did not cover

E

edge, A working example: Breadth first search in a graph, Basics

adjacent

in a directed graph, Directed graphs in LEDA
in an undirected graph, Undirected graphs in LEDA

adjacent vs. incident, Directed graphs in LEDA

directed, Basics

incident, Basics

leaving, Basics

reverse, Basics

edge array, Node arrays and edge arrays

edge iterator, Graph iterators

edge map (see edge_map)

edge, A first program

edge_array, A first program, Node arrays and edge arrays

constructor specifying the maximum number of edges, Node arrays and edge arrays

edge_map, Node maps and edge maps

instead of map<edge,V>, Use cases for map

edge_set, Special auxiliary data structures for graph algorithms

EdgeIt, Graph iterators

edit()

GraphWin, The programming interface of the class GraphWin

edit-and-run scheme, The programming interface of the class GraphWin

eight-queen-problem, Exercises

element

of a container type, Defining arrays and access to elements
of a list, Lists and the item-container-concept

embedding

order preserving, Order preserving embeddings
planar, Planar embeddings, Spring Embedding
straight line, Straight line embedding
Tutte, Exercises
vs. drawing, Spring Embedding

empty string, Strings (class string)

empty()

list, Filling and emptying lists
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

equal (see equality of objects)

equality of objects, Comparisons of LEDA objects, Hashing in LEDA

equality predicate

and LEDA objects, Comparisons of LEDA objects

equivalence

and linear orders, Linear orders

equivalent (see compare-equivalent)

error handler, Error handling

error handling, Error handling

Euler tour, Exercises, Exercises

exception, Error handling

expression

arithmetic

evaluation on stack, Stacks with an unbounded number of elements (class stack)
fully parenthesized, Exercises
partially parenthesized, Exercises

F

f(n)=O(g(n))), The O-notation

face, Maps and faces in daily life, Face cycles

outer, Maps and faces in daily life, Faces and face cycles
surrounding face cycle, Faces and face cycles

face cycle, Face cycles

face cycle predecessor, Face cycles

face cycle successor, Face cycles

face_array, The classes face_array and face_map

face_cycle_pred()

graph, Face cycles

face_cycle_succ()

graph, Face cycles

face_map, The classes face_array and face_map

Fibonacci heap

in the implementation of priority queues, Priority queues with unbounded priorities (class p_queue)

Fibonacci number, Integers of arbitrary length (class integer)

FIFO principle, Queues, Priority queues

(see also queue)

file

obtaining information about, Dealing with directories and files

file.h, Dealing with directories and files

file_istream, What we did not cover

file_ostream, What we did not cover

find_min()

p_queue, Priority queues with unbounded priorities (class p_queue)

finger, Finger search and fast insertion

finger search, Finger search and fast insertion

finger_locate()

sortseq, Finger search and fast insertion

finger_locate_from_front()

sortseq, Finger search and fast insertion

finger_locate_from_rear()

sortseq, Finger search and fast insertion

first()

list, Lists and the item-container-concept
two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

first-in-first-out (see FIFO principle)

Five Color Theorem, Coloring problems and dual graphs

five-coloring, Coloring problems and dual graphs

FIVE_COLOR(), Coloring problems and dual graphs

fixed-length coding, A working example: Huffman coding

flow, Maximum flows

flow conservation, Maximum flows

forall

over d_array, Iteration and iteration order
over list, Iterating with the forall macros
over set, Inserting elements and membership test
realization by macro expansion, A closer look at the forall macros

forall_adj_edges

on graph, Iterating over adjacent edges and nodes

forall_adj_nodes

on graph, Iterating over adjacent edges and nodes

forall_defined

over d_array, Iteration and iteration order

forall_edges

on graph, A first program, Iterating over all nodes and edges

forall_face_edges

on graph, Face cycles

forall_faces

on graph, Face cycles

forall_in_edges

on graph, Iterating over adjacent edges and nodes

forall_inout_edges

on graph, Iterating over adjacent edges and nodes

forall_items

over dictionary, Dictionaries (class dictionary)
over list, Lists and the item-container-concept
realization by macro expansion, A closer look at the forall macros

forall_nodes

on graph, A first program, Iterating over all nodes and edges

forall_out_edges

on graph, Iterating over adjacent edges and nodes

forall_rev

over list, Iterating with the forall macros

forall_rev_edges

on graph, Iterating over all nodes and edges

forall_rev_items

over list, Lists and the item-container-concept

forall_rev_nodes

on graph, Iterating over all nodes and edges

forest, Exercises, An example: Visualizing DFS_NUM()

minimum spanning, Minimum spanning trees

forward reference, How to start

Four Color Theorem, Coloring problems and dual graphs

four_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

fourth()

four_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

from LOVE to PAIN, A working example: Breadth first search in a graph

From LOVE to PAIN

with BFS(), The class GRAPH

front()

list, Changing lists and searching in lists

G

Galton board, The bit mode

generate()

random_variate, Static random variables (class random_variate)

get_day()

date, Dates (class date)

get_day_of_week()

date, Dates (class date)

get_directories(), Dealing with directories and files

get_files, Dealing with directories and files

get_msg()

leda_exception, Error handling

get_num()

leda_exception, Error handling

get_position()

GraphWin, Spring Embedding

get_selected_nodes()

GraphWin, Algorithms for shortest paths

get_xmax()

GraphWin, Spring Embedding

get_xmin()

GraphWin, Spring Embedding

get_ymax()

GraphWin, Spring Embedding

get_ymin()

GraphWin, Spring Embedding

gml format, The gml format

grammar

context free, Exercises

graph, A working example: Breadth first search in a graph, Basics, A first program

(see also graph)

(see also GRAPH)

acyclic, Further functions

algorithms for drawing, Algorithms for graph drawing

associating information, Graphs and associated information, Node arrays and edge arrays

comparison of the possibilities, A comparison of the possibilities

biconnected, Connected and biconnected graphs

bidirected, Undirected graphs in LEDA, Bidirected graphs

bipartite, Planar embeddings, Further functions

connected, Basics, Connected and biconnected graphs

constructor specifying the number of slots, Node arrays and edge arrays, Node maps and edge maps

cyclic, Basics

deleting self-loops, Further functions

dependency, How to start

directed, Basics, Directed graphs in LEDA

directed version of an undirected graph, Basics

directed vs. undirected, The real difference between directed and undirected graphs in LEDA

dual, Coloring problems and dual graphs

dynamic, The class GRAPH

embedded, Planar embeddings

finding a path that traverses every edge once in both directions, Exercises

generating with graph generator, Graph generators

genetic, A self-written graph algorithm

hiding edges temporarily, Hiding edges temporarily

influencing the order of the edges in the adjacency lists, Influencing the order in in_edges(v) and out_edges(v)

input via GraphWin, Interactive input with the editor GraphWin

iterating over nodes and edges, Iterating over nodes and edges and navigating in graphs

Kuratowski, Planar embeddings

making an isomorphic copy, Copying graphs

navigating in, Navigating

parameterized, The class GRAPH

planar, Exercises, Planar embeddings

algorithms for, Algorithms for planar graphs

planarly embedded, Order preserving embeddings

reading from and writing into a file, Reading from and writing to a file

regular of degree r, Exercises

simple, Further functions

static, Static graphs

storing in standard format (see standard format)

strongly connected, Basics, Strongly connected components

subdivision, Planar embeddings

undirected, Basics, Undirected graphs in LEDA

undirected version of a directed graph, Basics

vs. tree, Exercises

GRAPH, The class GRAPH

Graph

complete, Graph generators
directed vs. undirected in LEDA, Directed and undirected graphs

graph algorithm

built-in, Built-in graph algorithms
self written, A self-written graph algorithm

graph generator, Graph generators

graph iterator, Graph iterators

graph_draw.h, Algorithms for graph drawing

graph_gen.h, Graph generators

graph_iterator.h, Graph iterators

graph_misc.h, Exercises, Algorithms for basic properties

GraphWin, Interactive input with the editor GraphWin

animations, Spring Embedding
edit-and-run scheme, The programming interface of the class GraphWin
explicitly specifying the position of nodes and edges, Spring Embedding
node and edge attributes, Attributes of GraphWin
programming interface, The programming interface of the class GraphWin
using the user interface, Interactive input with the editor GraphWin

H

h_array, Hashing in LEDA, Hashing arrays (class h_array)

default value and constructor, Hashing arrays (class h_array)
specifying the initial table size, Hashing arrays (class h_array)

handle scheme, Handle types and handle-like types

handle technique, Queues with an unbounded number of elements (class queue)

handle type, Handle types and handle-like types

Handshaking Lemma, Exercises

hash, The basic idea of hashing

order of iteration, Order of iteration

hash function, The basic idea of hashing

good and bad, Good and bad hash functions

hash table (see hash)

hash value, Hashing types

Hash(), Hashing in LEDA

hashing, Hashing types

one-level and two-level methods, Hashing in LEDA
storing arbitrary information, Numbers and other keys
table doubling, Hashing in LEDA
with chaining, Hashing with chaining and table doubling
with node maps and edge maps, Node maps and edge maps

hashing array (see h_array)

head

of a queue, Queues

head()

list, Appending and deleting of elements at the end of a list
string, Further operations on strings

header files, The header files of LEDA

using old include structure with LEDA version >= 5.0, Structure of include directories as of LEDA 5.0

height

GraphWin, Attributes of GraphWin

Hello world!, Hello LEDA world! - The very first program

Hewlett-Packard (see pocket calculator with RPN)

hidden_edges()

graph, Hiding edges temporarily

hide_edge()

graph, Hiding edges temporarily

high()

array, Useful methods of the class array

high1()

array2, Two-dimensional arrays (class array2)

high2()

array2, Two-dimensional arrays (class array2)

Huffman coding, A working example: Huffman coding

I

identical (see identity of objects)

identical(), Comparisons of LEDA objects

identity of objects, Comparisons of LEDA objects

identity predicate (see identical())

implementation

concrete of an abstract data type, Implementation parameters

implementation parameter, Implementation parameters

in-degree, Basics

in_edges(v), Directed graphs in LEDA

InAdjIt, Graph iterators

indeg()

graph, An example

inf()

b_priority_queue, Priority queues with bounded integral priorities (class b_priority_queue)
dictionary, Dictionaries (class dictionary)
graph, The class GRAPH
p_queue, Priority queues with unbounded priorities (class p_queue)
sortseq, Basic functionality

infix notation, Stacks with an unbounded number of elements (class stack)

init()

AdjIt, Graph iterators
array, Useful methods of the class array
InAdjIt, Graph iterators
NodeIt, Graph iterators
OutAdjIt, Graph iterators
window, Spring Embedding

insert()

b_priority_queue, Priority queues with bounded integral priorities (class b_priority_queue)
dictionary, Dictionaries (class dictionary)
int_set, If one knows minimum and maximum in advance (class int_set)
list, Lists and the item-container-concept
p_dictionary, Persistent dictionaries
p_queue, Priority queues with unbounded priorities (class p_queue)
set, Inserting elements and membership test
sortseq, Basic functionality
string, Further operations on strings

insert_at()

sortseq, Fast insertion

int_set, Sets of integer numbers

constructor, If one knows minimum and maximum in advance (class int_set)

integer, Integers of arbitrary length (class integer)

intersect()

set, Union, intersection, and difference of sets

intersection

of sets, Union, intersection, and difference of sets

invariant, Defining arrays and access to elements

IP-address, Inserting elements and membership test

Is_Acyclic(), Further functions

Is_Biconnected(), Connected and biconnected graphs

is_bidirected()

graph, Bidirected graphs

Is_Bipartite(), Further functions

Is_Connected(), Connected and biconnected graphs

is_directed()

graph, The real difference between directed and undirected graphs in LEDA

is_hidden()

graph, Hiding edges temporarily

Is_Planar(), Exercises

Is_Plane_Map()

graph, Order preserving embeddings

Is_Simple(), Further functions

item, Lists and the item-container-concept

item type

dependent, Lists and the item-container-concept, Comparisons of LEDA objects
independent, Lists and the item-container-concept, Comparisons of LEDA objects

item-container-concept, Lists and the item-container-concept

iterator

edge, Graph iterators
node, Graph iterators
on graph, Graph iterators

J

join()

set, Union, intersection, and difference of sets

Josephus problem, Changing lists and searching in lists

generalized version, Exercises

Jumping Jack Flash, Filling and emptying lists

K

K3,3, Exercises, Planar embeddings

K5, Planar embeddings

key

of a key-value pair, Associative container types

key()

b_priority_queue, Priority queues with bounded integral priorities (class b_priority_queue)
dictionary, Dictionaries (class dictionary)
sortseq, Basic functionality

Kirchhoff's Law, Maximum flows

Kruskal' algorithm, What we did not cover

Kuratowski graph, Planar embeddings

Kuratowski Kazimierz , Planar embeddings

L

label_color

GraphWin, Attributes of GraphWin

label_pos

GraphWin, Attributes of GraphWin

label_type

GraphWin, Attributes of GraphWin

labyrinth

finding a way out, Exercises

Landau's symbol, The O-notation

last()

list, Lists and the item-container-concept

last-in-first-out (see LIFO principle)

layer, A working example: Breadth first search in a graph

LD_LIBRARY_PATH, Starting

leaf, Exercises

LEDA, What is LEDA?

categorization of data types, Categorization of the LEDA data types

compendium, Whom does this tutorial address?

compiling programs, Compiling, linking, and starting LEDA programs

discussion list, Where do we get help?

error handler, Error handling

getting help, Preparations

Guide, Whom does this tutorial address?

guide, Where do we get help?

header files, The header files of LEDA

include directories (see LEDA header files)

installing, Preparations

integrated development environment, The MS-Windows world

libraries, Linking

link in the librarieslibW and libP, A first program

link in the librarylibG, A first program

linking programs, Compiling, linking, and starting LEDA programs

memory manager, Efficient memory management for self-defined types

news list, Where do we get help?

online manual, Whom does this tutorial address?

Online-Manual, Where do we get help?

purchasing, Preparations

set of rules, The LEDA set of rules, The golden LEDA rules

(see also LEDA rule)
overview, The golden LEDA rules

starting programs, Compiling, linking, and starting LEDA programs

type and copy concept, Simple-structured types and their copy concept

under MS-Windows, The MS-Windows world

under Unix, The Unix world

leda

namespace, The namespace leda, Making a type of our own linearly ordered

LEDA rule

copy of a value, Simple-structured types and their copy concept, Copying of objects of an item-based type
definition with initialization by copying, The LEDA set of rules
equality and identity, Comparisons of LEDA objects
illegal access via an item, Changing lists and searching in lists
Modification of objects of an item-based container type while iterating over them, A closer look at the forall macros
Requirements for linearly ordered types, Linearly ordered types
requirements for type parameters, User-defined type parameters
requirements on hashed types, Hashing in LEDA
specification of the structure to be traversed in forall-macros, A closer look at the forall macros

leda::after, Lists and the item-container-concept, Further list modifying operations

leda::before, Lists and the item-container-concept, Further list modifying operations

LEDA_CHECKING_OFF, Automatic range checking

leda_exception, Error handling

leda_mdd.dll, The MS-Windows world

leda_mdd.lib, The MS-Windows world

LEDA_MEMORY(T), Efficient memory management for self-defined types

LEDAROOT, Compiling

lib3D, Linking

libG, Linking

libG2, Linking

libGeoWin, Linking

libL, Linking

libleda, Linking

libm, Linking

libP, Linking

libW, Linking

LIFO principle, Stacks

list, Linear lists (class list)

(see also list)
(see also slist)
accessing elements, Lists and the item-container-concept
and set, Sets (class set)
concatenating, Changing lists and searching in lists
delete from, Lists and the item-container-concept
deleting an element, Changing lists and searching in lists
doubly linked, Appending and deleting of elements at the end of a list, Lists and the item-container-concept
element, Lists and the item-container-concept
insert into, Lists and the item-container-concept
linear, Linear lists (class list)
permuting, Changing lists and searching in lists
reversing, Changing lists and searching in lists
searching in, Changing lists and searching in lists
singly linked, Singly linked lists (class slist)
sorting, Sorting lists
splitting, Changing lists and searching in lists
vs. array, Linear lists (class list)

load factor, Hashing with chaining and table doubling

locate()

sortseq, Basic functionality

locate_pred()

sortseq, Basic functionality

logarithmic

time complexity, The O-notation

lookup()

dictionary, Dictionaries (class dictionary)
sortseq, Basic functionality

lottery

creating variations, An application: creating variations

low()

array, Useful methods of the class array

low1()

array2, Two-dimensional arrays (class array2)

low2()

array2, Two-dimensional arrays (class array2)

M

macro expansion

of the forall macros, A closer look at the forall macros

Make_Biconnected(), Connected and biconnected graphs

make_bidirected()

graph, Undirected graphs in LEDA, Bidirected graphs

Make_Connected(), Connected and biconnected graphs

make_directed()

graph, The methods make_directed() and make_undirected()

make_map()

graph, Maps

make_undirected()

graph, Undirected graphs in LEDA, The methods make_directed() and make_undirected()

Makefile

generic, Linking

map, Hashing in LEDA, Maps (class map), Maps and faces in daily life, Maps

planar, Order preserving embeddings
two-dimensional (see map2)
use cases, Use cases for map

map2, Two-dimensional maps

Markov chain, Markov chains (classes markov_chain and dynamic_markov_chain)

(see also markov_chain)

markov_chain, Markov chains (classes markov_chain and dynamic_markov_chain)

marriage problem, Matching algorithms

matching, Matching algorithms

bipartite, unweighted, Maximum bipartite, unweighted matchings
bipartite, weighted, Maximum bipartite, weighted matchings
cardinality, bipartite, Maximum bipartite, unweighted matchings
cardinality, general, Maximum general, unweighted matchings.
general, unweighted, Maximum general, unweighted matchings.
general, weighted, Maximum general, weighted matchings
maximum, Matching algorithms
perfect, Matching algorithms

mathematicians' problem, Exercises

max()

int_set, If one knows minimum and maximum in advance (class int_set)
list, Further information about the class list

Max-Planck-Institut für Informatik, What is LEDA?

MAX_CARD_BIPARTITE_MATCHING(), Maximum bipartite, unweighted matchings

MAX_CARD_MATCHING(), Maximum general, unweighted matchings.

MAX_FLOW(), Maximum flows

max_flow.h, Maximum flows

max_item()

sortseq, Basic functionality

MAX_WEIGHT_BIPARTITE_MATCHING(), Maximum bipartite, weighted matchings

MAX_WEIGHT_MATCHING(), Maximum general, weighted matchings

maximum flow, Maximum flows

with minimum cost, Maximum flows with minimum cost

MAXNONREPMIRP number, Exercises

mc_matching.h, Maximum general, unweighted matchings.

mcb_matching.h, Maximum bipartite, unweighted matchings

member()

int_set, If one knows minimum and maximum in advance (class int_set)
set, Inserting elements and membership test

memory manager, Efficient memory management for self-defined types

merge()

list, Sorting lists
sortseq, Splitting, concatenating, and merging

merge_sort()

list, Sorting lists

Mergesort, Exercises

message()

GraphWin, The programming interface of the class GraphWin

min()

int_set, If one knows minimum and maximum in advance (class int_set)
list, Further information about the class list

MIN_COST_FLOW(), Further information

min_cost_flow.h, Maximum flows with minimum cost

MIN_COST_MAX_FLOW(), Maximum flows with minimum cost

MIN_CUT(), Minimum cuts

min_cut.h, Minimum cuts

min_item()

sortseq, Basic functionality

min_span.h, Minimum spanning trees

MIN_SPANNING_TREE(), Minimum spanning trees

minimum cut, Minimum cuts

minimum spanning forest, Minimum spanning trees

minimum spanning tree, Minimum spanning trees

misc.h, Defining arrays and access to elements, Some useful functions

module, Structure of include directories as of LEDA 5.0

core module, Structure of include directories as of LEDA 5.0

Monopoly, Exercises

MPII (see Max-Planck-Institut für Informatik)

multiedge

in a directed graph, Directed graphs in LEDA

multiset, Sets (class set)

mw_matching.h, Maximum general, weighted matchings

mwb_matching.h, Maximum bipartite, weighted matchings

N

namespace

leda, The namespace leda

neighbor node, Basics

network, Maximum flows

network flow (see flow)

network flow algorithm, Network flow algorithms

new, Efficient memory management for self-defined types

new_edge()

graph, A first program, Influencing the order in in_edges(v) and out_edges(v)
GRAPH, The class GRAPH

new_node()

graph, A first program
GRAPH, The class GRAPH

node

adjacent, Basics
reachable via a path, Basics

node array, Node arrays and edge arrays

node, A working example: Breadth first search in a graph, Basics

node iterator, Graph iterators

node map (see node_map)

node, A first program

node_array, A first program, Node arrays and edge arrays

constructor specifying the maximum number of nodes, Node arrays and edge arrays
valid on a graph, Node arrays and edge arrays

node_list, Special auxiliary data structures for graph algorithms, Algorithms for shortest paths

node_map, Node maps and edge maps

instead of map<node,V>, Use cases for map

node_map2, The classes node_matrix and node_map2

node_matrix, The classes node_matrix and node_map2

node_partition, Special auxiliary data structures for graph algorithms

node_pq, Special auxiliary data structures for graph algorithms

node_set, Special auxiliary data structures for graph algorithms

NodeIt, Graph iterators

number type

as a template parameter of graph algorithms, Functions templatized with number types

number_of_nodes()

graph, A first program

number_of_visits()

markov_chain, Markov chains (classes markov_chain and dynamic_markov_chain)

O

O(log(n)), The O-notation

O(n), The O-notation

O(n2), The O-notation

O-notation, The O-notation

Θ, The O-notation

opposite()

graph, The class GRAPH, Navigating

order

linear, Linear orders, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

realized by a compare-function, Linear orders
several on a type, Several linear orders on a type

user-defined, An example: Lists of string pairs in the computation of anagrams

order of magnitude

of a method, The O-notation

out-degree, Basics

out_edges(v), Directed graphs in LEDA

OutAdjIt, Graph iterators

outdeg()

graph, An example

P

p_dictionary, Persistent dictionaries

p_queue, Queues with an unbounded number of elements (class queue), Priority queues, Priority queues with unbounded priorities (class p_queue)

pair, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also two_tuple)

pairing, Exercises

palindrome, Strings (class string)

parent

of a node, Exercises

partition, What we did not cover

Pascal's triangle, Enlarging arrays dynamically

path, Basics

length, Basics, Algorithms for shortest paths
shortest (see shortest path)
simple, Basics

permute()

array, Useful methods of the class array
list, Further list modifying operations

persistence of variables, Persistence of variables

place_into_win()

GraphWin, Straight line embedding

PLANAR(), Order preserving embeddings, Algorithms for planar graphs, Exercises

planar_map, The classes planar_map and PLANAR_MAP

PLANAR_MAP, The classes planar_map and PLANAR_MAP

plane_graph_alg.h, Order preserving embeddings, Algorithms for planar graphs

pocket calculator

with RPN, Stacks with an unbounded number of elements (class stack)

pointer

as elements of a container type, Queues with an unbounded number of elements (class queue)

polar coordinates

and compare(), Exercises

pop()

list, Filling and emptying lists
queue, Queues with an unbounded number of elements (class queue)
stack, Stacks, Stacks with an unbounded number of elements (class stack)

pop_back()

list, Appending and deleting of elements at the end of a list

pos()

string, Further operations on strings

position

GraphWin, Attributes of GraphWin

postfix notation, Stacks with an unbounded number of elements (class stack)

pp_dictionary, Persistent dictionaries

pq_item, Priority queues with unbounded priorities (class p_queue)

precondition, Preconditions, Error handling

pred()

list, Lists and the item-container-concept
sortseq, Basic functionality

predecessor, A working example: Breadth first search in a graph

prefix-free coding, A working example: Huffman coding

print()

array, Useful methods of the class array
list, Sorting lists

print_statistics(), Efficient memory management for self-defined types

prio()

p_queue, Priority queues with unbounded priorities (class p_queue)

priority, Priority queues

priority queue, Priority queues

with bounded integral priorities (see b_priority_queue)
with unbounded priorities (see p_queue)

profiling, Useful little somethings

push

into queue, Queues

push down automaton, Stacks with an unbounded number of elements (class stack)

push()

list, Filling and emptying lists
stack, Stacks, Stacks with an unbounded number of elements (class stack)

Q

quadruple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also four_tuple)

queue, Queues

and deque, Exercises
simulation, Queues with an unbounded number of elements (class queue)
with unbounded number of elements (see b_queue)

Quicksort, The O-notation

R

rand_int, The seed

random number, Random numbers (class random_source)

random text, A working example: Creating Latin random texts

random variable, Random variables

non-uniformly distributed, Random variables
uniformly distributed, The integer mode, Random variables

random walk, Dynamic random variables (class dynamic_random_variate)

and Markov chain, Markov chains (classes markov_chain and dynamic_markov_chain)

random_graph()

graph, Graph generators

random_source, Random numbers (class random_source)

bit mode, The bit mode
constructor, The integer mode, The bit mode
creating double values, An example: Creating fractal sets
instead of random_variate, Queues with an unbounded number of elements (class queue)
integer mode, The integer mode
precision, The bit mode

random_variate, Random variables , Static random variables (class random_variate), Queues with an unbounded number of elements (class queue)

constructor, Static random variables (class random_variate)

range checking, Automatic range checking

automatic, The integer mode

read()

graph, Reading from and writing to a file
list, Further information about the class list
string, Filling and emptying lists

read_line()

string, Strings (class string), Built-in sorting methods

read_string(), Defining arrays and access to elements

redraw()

GraphWin, The programming interface of the class GraphWin

reference counting, Handle types and handle-like types

reflexivity, Linear orders

rehash, Hashing with chaining and table doubling

rel_freq_of_visit()

markov_chain, Markov chains (classes markov_chain and dynamic_markov_chain)

replace()

string, Further operations on strings

replace_all()

string, Further operations on strings

resize()

array, Arbitrary intervals as index sets, Useful methods of the class array, Enlarging arrays dynamically, Basic operations on lists
doubling strategy with array, Dynamic random variables (class dynamic_random_variate)

restore_all_edges()

graph, Hiding edges temporarily

restore_edge()

graph, Hiding edges temporarily

reversal edge, Bidirected graphs

reverse edge, Basics, Undirected graphs in LEDA

inserting by make_bidirected(), Strongly connected components

reverse Polish notation (see postfix notation)

reverse()

list, Further list modifying operations

reverse_items()

list, Further list modifying operations

reversing standard input (see tac)

root, Exercises

RPN (see postfix notation)

rule (see LEDA rule)

S

s-t-cut, Minimum cuts

Saarbrücken Central Station, Queues with an unbounded number of elements (class queue)

SCC (see strongly connected component)

search tree, Balanced search trees

search()

list, Further list modifying operations

second()

two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

seed, The seed

self-loop, Basics

sentinel, Two-dimensional arrays (class array2)

seq_item, Basic functionality

set, Sets (class set)

(see also set)
fractal, An example: Creating fractal sets
of integer numbers, Sets of integer numbers

set, Sets (class set)

set_animation_steps()

GraphWin, Spring Embedding

set_border_width()

GraphWin, The programming interface of the class GraphWin

set_default_value()

d_array, Dictionary arrays (class d_array)

set_directory(), Dealing with directories and files

set_edge_label_pos()

GraphWin, Face cycles

set_edge_label_type()

GraphWin, Face cycles

set_error_handler(), Error handling

set_flush()

GraphWin, The programming interface of the class GraphWin

set_node_border_width()

GraphWin, The programming interface of the class GraphWin

set_position()

GraphWin, Spring Embedding

set_precision()

random_source, The bit mode

set_range()

random_source, The integer mode

set_reversal()

graph, Maps

set_seed()

random_source, The seed

set_to_current_date()

date, Dates (class date)

set_weight()

dynamic_markov_chain, The class dynamic_markov_chain
dynamic_random_variate, Dynamic random variables (class dynamic_random_variate)

shape

GraphWin, Attributes of GraphWin

shortest path, A working example: Breadth first search in a graph, Algorithms for shortest paths

algorithms from shortest_path.h, Algorithms for shortest paths

shortest path problem, Algorithms for shortest paths

SHORTEST_PATH(), Algorithms for shortest paths

shortest_path.h, Algorithms for shortest paths

signature, An example: Lists of string pairs in the computation of anagrams

simulation

discrete event, Priority queues

single pass, How to start

sink

in a network, Maximum flows

size()

array, Useful methods of the class array
d_array, Dictionary arrays (class d_array)
dictionary, Dictionaries (class dictionary)
list, Appending and deleting of elements at the end of a list
p_queue, A working example: Huffman coding
queue, Queues with an unbounded number of elements (class queue)
set, Union, intersection, and difference of sets
stack, Stacks with an unbounded number of elements (class stack)

size_of_file(), Dealing with directories and files

skiplist, Finger search and fast insertion

as implementation parameter, Implementation parameters

slist, Singly linked lists (class slist)

slot, The basic idea of hashing

sort()

array, Built-in sorting methods, The O-notation
list, Sorting lists

sort_edges()

graph, A first program

sort_nodes()

graph, A first program, Iterating over all nodes and edges

sorted sequence (see sortseq)

sorting

by minimum search, Defining arrays and access to elements, Time complexity, space complexity, and the O-notation
of unequal integer numbers, If one knows minimum and maximum in advance (class int_set)
topological (see topological sorting)

sorting algorithm

stable, Sorting lists

sortseq, Queues with an unbounded number of elements (class queue), Sorted sequences (class sortseq)

source

in a network, Maximum flows
of a node, Basics

source()

graph, Navigating

space complexity, Space complexity

spanning forest, Minimum spanning trees

spanning tree, Minimum spanning trees

SPANNING_TREE(), Minimum spanning trees

split()

list, Further list modifying operations
sortseq, Splitting, concatenating, and merging

spring embedder, Spring Embedding

SPRING_EMBEDDING(), Spring Embedding

stack, Stacks, Stacks with an unbounded number of elements (class stack)

(see also stack)
top of, Stacks

standard format, The standard format

std

namespace, The namespace leda

step()

markov_chain, Markov chains (classes markov_chain and dynamic_markov_chain)

straight line embedding, Straight line embedding

STRAIGHT_LINE_EMBEDDING(), Straight line embedding

string, Strings (class string)

(see also string)
constructor, Handle types and handle-like types
empty string, Strings (class string)

string.h, The header files of LEDA

string_istream, What we did not cover

string_ostream, What we did not cover

STRONG_COMPONENTS(), Strongly connected components

strongly connected component, Strongly connected components

style

GraphWin, Attributes of GraphWin

subdivision

of a graph, Planar embeddings

subgraph, Exercises

subscript operator (see [])

subtree, Exercises

succ()

list, Lists and the item-container-concept

symdiff()

set, Union, intersection, and difference of sets

T

tac, Basic operations on lists

tail()

list, Appending and deleting of elements at the end of a list
string, Further operations on strings

target

of a node, Basics

target()

graph, Navigating

third()

three_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

three_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

tic-tac-toe, Exercises

time

amortized, Amortized analysis
constant, The O-notation
expected, The O-notation
linear, The O-notation
logarithmic, The O-notation

time complexity, Time complexity

time-space-tradeoff, Space complexity

top

of queue, Queues

top of stack, Stacks

top()

queue, Queues with an unbounded number of elements (class queue)
stack, Stacks with an unbounded number of elements (class stack)

topological sorting, How to start, An example: An implementation of TOPSORT()

recognizing a cycle, Exercises

TOPSORT(), A first program

implementation, An example: An implementation of TOPSORT()

TORWAT algorithm, An example: Creating fractal sets

tradeoff

time vs. space, Space complexity

transitivity, Linear orders

Traveller, Queues with an unbounded number of elements (class queue)

tree

minimum spanning, Minimum spanning trees
niveau-connected, Finger search and fast insertion
representation by means of graph, Exercises
vs. graph, Exercises

tree_collection, What we did not cover

triple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

(see also three_tuple)

try-catch, Error handling

Tutte embedder, Exercises

TUTTE_EMBEDDING(), Exercises

two_tuple, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)

type

compound type, Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)
dependent item type , Comparisons of LEDA objects
handle type, Handle types and handle-like types
handle-like, Handle types and handle-like types
hashed, Hashing in LEDA
hashing, Hashing types
independent item type, Comparisons of LEDA objects
item-based structured, Lists and the item-container-concept
linearly ordered, An example: Lists of string pairs in the computation of anagrams, Linear orders
non-item-based, Simple-structured types and their copy concept
non-primitive (see structured)
primitive, Simple-structured types and their copy concept
simple-structured, Simple-structured types and their copy concept
structured, Simple-structured types and their copy concept

type and copy concept, Copying of objects of an item-based type

type parameter, Defining arrays and access to elements, User-defined type parameters

U

ugraph, The class ugraph

undefine()

d_array, Dictionary arrays (class d_array)

unification problem, Sorting lists

and sets, Inserting elements and membership test

union

of sets, Union, intersection, and difference of sets

unique()

array, Useful methods of the class array
list, Sorting lists

universality of binary coding, Hashing types

update_graph()

GraphWin, The programming interface of the class GraphWin, Face cycles

use_node_data()

graph, Node arrays and edge arrays, Node maps and edge maps

used_time(), Some useful functions

user coordinate system

querying and setting the position of objects, Spring Embedding

user_label

GraphWin, Attributes of GraphWin

using declaration, The namespace leda

using directive, The namespace leda

V

value

of a cut, Minimum cuts
of a key-value pair, Associative container types
of a network flow, Maximum flows

variable

persistent, Persistence of variables

variable-length coding, A working example: Huffman coding

variation

creating by permuting a list, An application: creating variations

VCVARS32.BAT, Setting the environment variables for Visual C++

vector (see array)

vertex (see node)

Visual C++, Setting the environment variables for Visual C++

Visual Studio, The MS-Windows world

W

wait()

GraphWin, The programming interface of the class GraphWin

weight

of a random variable, Static random variables (class random_variate)

width

GraphWin, Attributes of GraphWin

window, Interactive input with the editor GraphWin

wrap-around

in integer operations, Integers of arbitrary length (class integer)

write()

graph, Reading from and writing to a file

X

xcoord()

point, Spring Embedding

xmax()

window, Spring Embedding

xmin()

window, Spring Embedding

Y

ycoord()

point, Spring Embedding

ymax()

window, Spring Embedding

ymin()

window, Spring Embedding


Bibliography