Seeing the good for the trees

We put a lot of effort into trying to ensure that our numerical libraries are available on the platforms that are most popular with our users. For each library, this leads to a proliferation of implementations, each of which is targeted at a specific combination of compute processor, operating system and compiler. The details of current implementations are on our website - for example, here is the list for the NAG Fortran Library, which also includes download links for each implementation. Although this list - which currently features forty-nine implementations - is an impressive array (and the fruits of a great deal of careful work on the part of our implementation team), its presentation could perhaps be viewed as being tricky to navigate by those who are searching for the appropriate implementation for their particular system.

Recently I was asked if I could produce a more intelligible representation of pages like this. I was reminded initially of a decision tree, mainly because we already make use of these tools in our documentation as a way to help users select the most appropriate algorithm (or NAG routine) for the solution of their problem. For example, figure 1 shows one of the decision trees which is part of the documentation for chapter D01 of the NAG Fortran Library, which deals with numerical integration, or quadrature.

This chapter currently contains twenty-nine routines, each of which is tailor-made for a different type of problem (e.g. integrands defined as a set of points or a function, functions that contain singularities, integration intervals that are finite, semi-infinite or infinite, etc), and the decision tree guides the user to a correct choice by asking questions about their problem.

Recasting the implementation list as a decision tree (with questions such as "what platform?", "what operating system?", "what compiler?") seemed, then, to be the way forward. However, I was conscious that I didn't want something which was as as set in stone as figure 1; for one thing, I was unsure about the initial layout of my tree. I also knew that the tree would require maintenance as new implementations became available - for example, the latest release of the NAG Fortran Library is currently being made available on more platforms, and the picture (and the list) will have to be periodically updated to reflect this. In addition, because the tree only contains branching nodes (points at which the path diverges) and leaf nodes (points at which the path terminates) but no converging nodes (points at which several paths come together), it could quickly become very large, and difficult to draw by hand.

Fortunately, there are a range of options for the display of decision trees. Some of these - for example, this one and this one - also incorporate the calculation of the tree itself (for use in machine learning applications), but this isn't necessary in the present example because we already have the structure of our tree. The display of trees and graphs is an active research area (see, for example, here) and there is a variety of freely-available applications (for example this one and this one) which can be used. In the end, I chose prefuse, which is a Java-based toolkit for building interactive applications in information visualization, chiefly because their treeview demo appeared to be close to what I wanted to do.

I downloaded the prefuse distribution and, after some only limited success with the supplied build script, followed the advice of the documentation and built it from within the Eclipse IDE (more specifically, their advice was to use Eclipse "if you are a Java novice", which certainly rang a bell with me). Adapting the treeview demo to my purposes was very straightforward because the tree structure and node names are read in as an XML file whose format is very simple (there are essentially just three elements: tree, branch and leaf; these are labelled via attributes). Figure 2 is a screen shot of the treeview demo running as a Java applet in the browser, displaying the implementation information for the NAG Fortran Library (i.e., based on the information presented here).

The instructions at the bottom of the web page give the details of the applet's interface: how the user can pan, zoom and also change the orientation of the tree from its default left-to-right ordering. Clicking on any of the nodes expands the tree from that point (and collapses any expanded node at the same level) which facilitates navigation. Figure 3 shows the applet being used to determine the appropriate implementation of the NAG Fortran Library for applications built on machines having the Sun X64 architecture, and using the Sun Studio 11 compiler; its NAG product code is FLSA622DCL.

In a similar fashion, Figure 4 is a partial screenshot of the applet being used to select the correct implementation of the NAG Fortran Library for applications built on machines having the AMD64 architecture, and using the GNU Fortran compiler with the ILP64 data model; its NAG product code is FLL6A22DHL. Note that, in this screenshot, the orientation of the tree has been switched to a top-to-bottom ordering, which might be easier to navigate for some users.

The applet is currently being tested internally at NAG, but initial feedback seems to indicate that its presentation of the implementation data represents a helpful supplement to the list format which has been in use up until now.


  1. Hello
    Have you considered even a simpler representation than trees? For example, just filtering the list?

    I think that a tree representation is very useful for "heterogeneous data" where branches of the tree look different, for example, one choice (optimization->local) opens other possibilities then the other (optimization->global). If you have several criteria and (more or less) all combinations make sense it is often useful to offer choices in a different manner.

    How would filering look like?
    Imagine that, by default, you would see all the implementations on the page (as you can see now) but there would be a pulldown menu above each column which would filter out everything except the chosen item.
    The categories could be "platform/architecture" "mark" "compiler" or even more dynamically loaded to refine your search.

    The advantage would be:
    * no enforced order of choices (you don't need to start with architecture, you can ask "what architectures are available for the latest mark" or "what libraries are available for my compiler")
    * no need to load Java applet, which took over 20s with the demo example
    * in general faster and more portable (because not everyone allows Java to run)
    * you don't need to narrow the search to the last leaf/single item


  2. Thanks for that, Jan. You make a good argument for the advantages of just filtering the list, which I hadn't previously considered - largely because, having thought of the tree (and discovered an easy-to-use implementation of it), I stopped looking for alternative representations. However, I think the final say on utility will come from the internal users at NAG; I'll bear your suggestion in mind if they end up seeking other alternatives to the list representation.


Post a Comment

NAG moderates all replies and reserves the right to not publish posts that are deemed inappropriate.

Popular posts from this blog

Implied Volatility using Python's Pandas Library

C++ wrappers for the NAG C Library

ParaView, VTK files and endianness