LINK (w/STk interface)

From: berryj <>
Date: Wed, 30 Oct 1996 11:12:48 -0500 (EST)

This message is really aimed at the Discrete Math/Theoretical CS
communities, but the system it describes has an STk interface
with a few thousand lines of STklos code, so it might be of
interest to this mailing list.
        Jon Berry
LINK, a software environment for discrete mathematical computation
and visualization with an emphasis on graphs and hypergraphs, is
now freely available from The Center for Discrete Mathematics
and Theoretical Computer Science (DIMACS) at Rutgers University.
See the following URL for information and retrieving the software:
It is also available via anonymous ftp at

relies upon: STk (free software: info available at the
                     LINK web page )


        * A prototyping and educational tool in which graph and
          hypergraph algorithm animations can be developed and
          viewed at a very high level.

        * A computing environment in which students and researchers
          can make queries and carry out experiments at several
          different levels: GUI, Scheme command language, and C++.

        * A collaborative effort of DIMACS, Elon College, Los Alamos
          National Laboratory, Indiana University, Rensselaer
          Polytechnic Institute, The State University of New York,
          Stony Brook, and Bell Laboratories Innovations.

        * An extendible system which will continue to be developed.

        * freely available (under a copyright very similar to Tcl/Tk)
          with user's and programmer's manuals.

        * Portable to SunOs, Linux, and probably many other Unix
          platforms using the GNU C++ compiler.

        * A system for viewing massive quantities of data. The
          interface is interpretive as a result of a conscious
          trade off of speed for flexibility.

        * Portable to Windows or Macintosh (though we will be
          working on this.).

        * A polished, completed system. There are bugs, holes in the
          algorithms library and other avenues for improvement.
          These will be addressed in future releases. However, the
          current release is usable. Also, a mailing list is in
          place to deal with problems.

The Link System Consists of:
        * A set of templated C++ libraries including collection,
          graph, and hypergraph objects and algorithms, graph
          generating routines, and layout routines. The system
          provides a makefile for building stand-alone C++
          applications which use these libraries and
          either include the GUI described below or do not.

        * A computing environment complete with an easily-extendible,
          menu-driven GUI (written with STk, not X/Motif) with graph
          editing features and an object-oriented Scheme interface
          which makes manipulation of graphs and their attributes
          high-level operations. For example, the following lines
          create a graph, find a minimum spanning tree,
          then color the tree's edges red:

                (define g (graph '(1 2 3) '((1 2) (2 3) (3 1))))
                (define gv (show-graph
                                (graph (vertices g) (kruskal g))))
                (map (lambda(x) (set! (color x) "red")) (edges gv))

        * A useful animation tool which can be used by students or
          prototypers to construct graph animations.
          These can be developed using the C++
          libraries and then viewed using an animation controller
          which allows the user to step through the algorithm
          forwards or backwards, set breakpoints,
          continue, and rerun the animation as often as desired.
          Simple animations can also be developed in Scheme.

        * A 170+ page combination user's/programmer's manual
          complete with installation instructions and dozens of

Space Requirements
Compiling LINK without optimization flags set requires roughly
70Mb. The stripped executable file is approximately 5Mb, and
the rest of the space is taken by libraries and object files
which may be deleted if desired. Compiling with optimizations
can reduce the total requirements to around 27Mb. In either case,
building the system on PCs with 16Mb RAM or less running Linux
requires an increase in swap space (i.e., optimization will
increase compilation time dramatically on small memory machines).
        * LINK has been supported by NSF grant CR92-14487,
          ONR award 400x116yip01, Los Alamos National Laboratory, and
          DIMACS (funded under NSF grant STC--91--19999).

        * LINK was conceived by the following team of researchers:
          Nathaniel Dean, then of Bellcore, now
          at Lucent/Bell Laboratories, Mark Goldberg of Rensselaer
          Polytechnic Institute, Gregory Shannon, then of Indiana
          University, now Chief Scientist at MilkyWay Technologies,
          Steven Skiena of SUNY Stony Brook, and the late Daniel
          Gorenstein, founding director of DIMACS.

        * The LINK project has been led from DIMACS since 1995 by
          Jonathan Berry, who will continue to lead the effort
          from Elon College in North Carolina.

Dr. Jonathan W. Berry Office: Whitley 204
Assistant Professor, Computing Sciences Campus Box: 2130
Elon College, N.C. Office Phone: (910)584-2290
Received on Fri Nov 01 1996 - 06:43:27 CET

This archive was generated by hypermail 2.3.0 : Mon Jul 21 2014 - 19:38:59 CEST