VBCTOOL - a graphical interface for Visualization of Branch Cut algorithms
The Tree Interface Version 1.0.1
by 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.
A Branch and Cut tree with 101 nodes.
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.
Downloading the VBCTOOL
We offer executables for the following systems:
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
For adapting programs to the Tree Interface we
also offer a library for the following systems:
Every library is available in a package containing
the headerfiles of Tree Interface,
GFE, Graph Interface and the Motif Application Framework.
The library in every
package contains the library of each of the named applications.
Observe that the package does not include the X/Motif
Libraries.
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.
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
(kupke@informatik.uni-koeln.de)
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 packages may by freely copied and
distributed, provided that no changes whatsover are made. All users
are asked to help keep the Tree Interface files consistent and
uncorrupted, identical everywhere in the world. Changes are
permissible only where explicitly allowed or if the modified file is
given a new name. 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 copyright to Young. The GFE is copyright
to Martin Diehl and
Joachim Kupke,
(kupke@informatik.uni-koeln.de)
Institut für
Informatik, Universität zu
Köln and the Graph Interface is
copyright to Joachim Kupke. The Tree Interface is copyright to
Sebastian Leipert,
Institut für Informatik, Universität zu Köln.
A visualization of a PQ-tree with 409 nodes.
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 (kupke@informatik.uni-koeln.de)
Sebastian Leipert
...back to Home Page
April, 2nd, 1997
Sebastian Leipert