Next

Chapter 1. Boost.MPL.Graph (proposed)

Gordon Woodhull

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Table of Contents

Introduction
Data Structures
incidence_list
adjacency_list
Concepts
IncidenceGraph
BidirectionalGraph
AdjacencyGraph
VertexListGraph
EdgeListGraph
Acknowledgements

MPL.Graph is a proposed Boost library for creating and traversing metadata graphs at compile time.

Graph data structures and algorithms are applicable at compile time for a variety of purposes. Not only does this allow for "perfectly" efficient implementations which do not waste runtime cycles on abstractions, but it can make it possible to implement patterns which would be too complex and error-prone in an ad-hoc manner.

Some examples of familiar compile-time graphs:

  • Class hierarchies form a DAG
  • State machines, e.g. from MSM
  • Expression trees e.g. from Proto expression templates
  • Grammars. Note that Spirit grammar is usually known at compile-time, but Spirit uses runtime variables to merge trees by common rule references.

Some constructs have graph structure that is partly compile-time and partly run-time:

  • Call graphs - the set of all possible calls between functions is (usually) a static graph, but a particular run is a tree.
  • Ownership of objects - the relationships type-owns-type form a static graph which describes the actual ownership of objects by objects in a runtime graph or tree.
  • Pointers between objects - the relationships type-holds-pointer-to-type form a static graph which describes the pattern of the runtime graph of objects pointing to each other.

Metaprogramming these constructs allows analysis with graph algorithms, and production from computed graphs. Specification and analysis using compile-time graphs avoids wasting runtime cycles on abstractions, and improves conceptual clarity and abstraction (once the "meta" barrier is hurdled).

So far, MPL.Graph provides compile-time versions of BGL's incidence_list and adjacency_list, and the algorithms breadth_first_search and depth_first_search.

It is used in MSM (where it is currently a sub-library) for identifying regions (connected components) and unreachable states.

Last revised: January 18, 2011 at 00:13:38 GMT


Next