skip to content

Faculty of Mathematics and Natural Sciences

Abteilung für Informatik

VBCTOOL - a graphical interface for Visualization of Branch Cut algorithms

The Tree Interface Version 1.0.1

Author: Sebastian Leipert

The Tree Interface is a graphical tool specially designed to draw binary and general rooted trees, as they occur during an algorithmic process. It can be used in three different contexts.

  • Simple drawing of trees.
  • Drawing a tree during a computational process.
  • Emulating a tree growing process after the computation is finished.
expand:

Simple drawing of trees

As a result of an algorithmic process, a nonordered, rooted tree may have been stored in a file, along with some information for every node. In order to take a look at the tree simply load the file into the Tree Interface. The interface draws the tree and offers the ability to display the information of the nodes and to display different types of nodes in different shapes and colours.

Drawing a tree during a computational process

This is the most interesting feature of the Tree Interface and can be used in two different ways.

  • Piping the output of any process that specifies a tree to the Tree Interface.
  • Adapting one or more algorithms to the Tree Interface, start them via a mouse button click in the menu bar of the interface window and instantly pursue the growth of the tree.

Both features are easy to realize. The first one needs only the adaption of the users program output. It uses identifiers to indicate if a new node is added to the tree, a node changes its type and should be drawn in a different colour or a node receives new or extra information.

The second option means including the users program into the environment of the Tree Interface such that the program can be started by clicking on a button in the menu bar. This possibility involves some work for the user and is restricted to C++ implementations only, but offers a nice handling. The necessary changes that need to be programmed are described in detail in the User Manual. For realizing this option we provide in a package all include files and libraries concerning the Tree Interface, the Graph Interface, the GFE and the Motif Appplication Framework. The only library that is not included in our package is the X/Motif Libraries that has to be provided by the reader.

A typical application for this feature is the Visualization of Branch and Cut trees.

A Branch and Cut tree with 217 nodes.

Emulating a tree growing process after the computation is finished

The Tree Interface includes a tool for emulating the process that grew the tree after the process is finished. This might be preferred before a runtime simulation for several reasons. On the one hand, a process might last to long and the user is forced to keep an eye on the screen while nothing actually happens. On the other hand, a process might be very fast and produces a large tree, so that it is not possible to follow the action that takes place. Instead of drawing the tree during the computational process, emulate the visualization of the process afterwards and then either speed this visualization up or slow it down. The Tree Interface provides a comfortable tool which enables the user to reproduce such visualizations.

Furthermore situations may occur, where it is not possible at all to visualize a process. This eg. is typical for parallel algorithms which are run on multiple processor machines. Here the user has no other choice but emulating the process after it has been finished.

Graphical Features of the Tree Interface

The Tree Interface provides all necessary features of a graphical interface, such as area zoom, mouse dragging, print command and a colour, font and size chooser. Furhtermore, it provides features designed to adapt the layout of trees to the aesthetical preferences of the user.

Trees are layed out according to an algorithm of Walker (A Node-positioning Algorithm for General Trees, Software Practice and Experience, 20(7) 1990 pp. 685-705). This algorithm provides good layout solutions for binary, nonordered, rooted trees as well as general, nonordered rooted trees.

In general, the nodes of a tree carry informations. The Tree Interface allows to store the information for every node and to look it up by a simple mouseclick on the node. Clicking on a node will pop up a window, displaying all informations of the specified node. The layout of the information displayed in window may be influenced by the user. Furthermore, the Tree Interface provides a browser mode that displays a small part of the information within the display area of the Tree Interface window. This part of the information is specified by the user and makes browsing for certain nodes even in large trees very simple.

We offer executables for the following systems:

Downloading the VBCTOOL

vbcSolaris.tgz
(tgz)
vbcSunOS.tgz
(tgz)
vbcLinux.tgz
(tgz)

All executables are available in a package along with some files needed by the Tree Interface. The exectuables have been statically linked including the libraries of GFE, Graph Interface, Motif Application Framework and the X/Motif Libraries.

All features of the Tree Interface are explicitly described in the user manual:

vbcUserManual.ps.gz
(gz)

For adapting programs to the Tree Interface we also offer a library for the following systems:

vbcLibSolaris.tgz
(tgz)
vbcLibSunOS.tgz
(tgz)
vbcLibLinux_old.tgz
(tgz)

You can also download the source code and build the application yourself:

VBCTool sourcecode, including the TreeInterface, GraphInterface and the GFE (available under the GPL).
(gz)
Source code of the Motif Application Framework (copyright to Douglas Young)
(gz)
Build instruction
()

For testing the Tree Interface, we offer a package of samples. With these examples all utilities of the Tree Interface can be tested. Observe the file README enclosed in the package, that explains all samples and their application.

Samples
(tgz)

Technical Backgrounds

The implementation of the Tree Interface is based on the Graph Interface written by Joachim Kupke that itself is based on the Graphical Front End GFE Version 1.0 written by Joachim Kupke and Martin Diehl in C++. GFE itself is a library based on the MotifApp Application Framework a library written for OSF/Motif by Young (Object Oriented Programming with C++ and OSF/MOTIF, Prentice Hall, 1992). For accurate manipulating and deriving our source code, we expect the user to have the library libApp.a, written by Young, the GFE and the Graph Interface library written by Kupke and Diehl and of course the X/Motif Libraries. All Libraries are available in our packages, except the X/Motif Libraries.

Copyright

The files included in the VBCTool package may be freely copied and distributed under the GPL.  The authors have tried their best to produce correct and useful programs, in order to help promote computer science research, but no warranty of any kind should be assumed. The Motif Application Framework is part of the book

Object-Oriented Programming with C++ and OSF/Motif by
Douglas Young
Prentice Hall, 1992
ISBN 0-13-630252-1

Permission to use, copy, modify, and distribute this software for any purpose except publication and without fee is granted, provided  that the above copyright notice appear in all copies of the software.

expand:

Involved Authors

The software presented here has been developed in the group of Prof. Dr. Jünger at the Institut für Informatik of the Universität zu Köln: Martin Diehl, Michael Jünger, Joachim Kupke, and Sebastian Leipert.