Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

Introduction

Version 1.0

The Vienna Graph Template Library (VGTL) is a generic graph library with generic programming structure. It uses STL containers like map and vector to organize the internal structure of the graphs.

A collection of walking algorithms for analyzing and working with the graphs has been implemented as generic algorithms. Similar to STL iterators, which are used to handle data in containers independently of the container implementation, for graphs the walker concept (see Section Walker) is introduced.

Walker

A walker is, like an STL iterator, a generalization of a pointer. It dereferences to the data a graph node stores.

There are two different kinds of walkers: recursive walker and iterative walker.

Recursive Walker

A recursive walker is a pointer to graph nodes, which can be moved around on the graph by changing the node it points to. Walkers can move along the edges of the graph to new nodes. The operators reserved for that are << for moving along in-edges and >> for moving along out-edges. A recursive walker does not have an internal status, so the walking has to be done recursively.

Iterative Walker

An iterative walker (automatic walker) can walk through a graph without guidance. Simply using the operators ++ and --, the walker itself searches for the next node in the walk.

Trees and Forests

The first few of the collection of graph containers are the $n$-ary trees and forests. These trees come in various flavors: standard trees, labelled trees, with and without data hooks. Trees provide iterative walkers and recursive walkers.

Directed Graphs and DAGs

The next more complicated graphs are directed graphs. There are two classes implemented. Standard directed graphs and directed acyclic graphs (DAGs). Directed graphs provide recursive walkers only.

Generic Graphs

Generic graphs don't have directed edges. They are the most general class of graphs, and special walking algorithms are provided for them. Generic graphs only have recursive walkers.


Generated on Tue Nov 4 01:41:23 2003 for Vienna Graph Template Library by doxygen1.2.18