Skip to content

Lab note

C++ template papers and graph tools

Why the Blitz++, Turing-complete templates, and Veldhuizen thesis references sit next to a graph viewer. The connection is not historical accident - it is the same generic programming work.

A small shelf of papers next to a graph viewer panel

Why the papers are here

A casual visitor to this site might wonder why three C++ template papers sit next to a graph viewer’s demos and docs. The answer is that the same generic programming work that produced Blitz++ produced the kind of high-performance numerical code that scientific graph tooling needs.

The papers are not decoration. They are part of the technical background that makes a viewer like Ubigraph possible.

The Blitz++ arrays paper

The Blitz++ arrays companion page covers the paper itself. The short version is that Blitz++ used C++ templates to produce array operations that compile to tight numerical loops without the abstraction penalty that array libraries usually pay.

For a graph viewer the connection is one step removed but real. A force-directed layout is a numerical simulation. The inner loop computes forces between vertices. The performance of that inner loop determines how many vertices the viewer can handle. The techniques in Blitz++ apply directly.

If you have ever wondered why scientific C++ code looks the way it does, the Blitz++ paper is one of the answers.

C++ templates as a Turing-complete metalanguage

The C++ templates Turing-completeness companion page covers the proof. The short version is that the C++ template system, used in a certain way, can compute anything a Turing machine can compute. That is interesting in its own right and it is also the foundation for the kind of compile-time work that makes Blitz++ possible.

For a graph viewer the connection is slightly more abstract. The work that lets a numerical library specialise itself at compile time is the same work that lets a graph data structure specialise itself for the kind of graph you are using. Sparse versus dense graphs. Static versus dynamic graphs. Labelled versus unlabelled edges. A library that takes advantage of compile-time specialisation can handle all of those without paying for the abstraction at runtime.

This is the kind of background that makes the difference between a graph library that is a curiosity and one that is fast enough to be useful.

The Veldhuizen thesis

The Veldhuizen thesis companion page covers the thesis. The short version is that it is a longer-form treatment of the same ideas - active libraries, compile-time work, generic programming - applied to scientific computing.

For a graph viewer the thesis is the most directly relevant of the three papers. The thesis is about how to build libraries that are flexible at the design level and efficient at runtime. That is exactly the problem a graph library has. A force-directed layout, an attribute system, a streaming API - all of those have to be flexible enough to be used and fast enough to be useful.

Reading the thesis with a graph library in mind is a useful exercise. The techniques carry over almost directly.

Where the connection breaks down

The papers are not graph theory papers. They do not discuss layout algorithms. They do not discuss network analysis. The connection to a graph viewer is at the implementation layer, not the algorithm layer.

If you came to the references shelf hoping for foundational papers on graph drawing, the papers will not give you that. The demos index and the random graph layout note are the right starting points for layout questions.

The papers are about how to build the engine. The demos are about how to drive it.

Why this matters today

The C++ template work in these papers is now widely understood. Modern C++ libraries take many of the techniques for granted. That does not make the papers less interesting. The papers are the record of how the techniques were discovered and what problems they were originally trying to solve.

For someone reading them today, the value is twofold:

  • They show the work behind the abstractions that current C++ libraries rely on.
  • They are still good worked examples of how to think about generic programming for performance.

Neither of those is unique to a graph viewer. The connection is just that a viewer of any reasonable size benefits from the same techniques.

Where this connects in the rest of the site