Chapter 5. Graphs and graph algorithms

Table of Contents

5.1. Basics
5.2. Graphs and associated information
5.2.1. How to start
5.2.2. Associating information to graphs
5.2.3. Directed and undirected graphs
5.2.4. Iterating over nodes and edges and navigating in graphs
5.2.5. Creating and storing graphs and the editor GraphWin
5.2.6. Planarly embedded graphs, maps, and faces
5.2.7. Special auxiliary data structures for graph algorithms
5.3. Built-in graph algorithms
5.3.1. Algorithms for basic properties
5.3.2. Basic graph algorithms
5.3.3. Algorithms for shortest paths
5.3.4. Network flow algorithms
5.3.5. Matching algorithms
5.3.6. Minimum spanning trees
5.3.7. Algorithms for planar graphs
5.3.8. Algorithms for graph drawing
5.4. A self-written graph algorithm
5.5. Markov chains (classes markov_chain and dynamic_markov_chain)
5.6. What we did not cover

One of the main reasons for LEDA's success is its support of graphs, by the extremely powerful class graph on the one hand , by a variety of built-in graph algorithms on the other hand.

This chapter first gives a short introduction to the basic concepts from the world of graphs. Then it describes the usage of the class graph and how to code, process, and visualize graphs with this class. A survey of the most important built-in graph algorithms follows, each beginning with the description of the underlying problem definition by means of a small example; this problem then is solved exemplarily with the respective algorithm. The chapter closes with an example of a self-written graph algorithm that unites some of the techniques and algorithmic constituents imparted before.