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:
http://dimacs.rutgers.edu/Projects/LINK.html.
It is also available via anonymous ftp at
ftp://dimacs.rutgers.edu/pub/berryj
files: link_manual.ps
link.tar.gz
relies upon: STk (free software: info available at the
LINK web page )
WHAT LINK IS AND IS NOT
------------------------
LINK IS:
--------
* 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.
LINK IS NOT:
------------
* 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
examples.
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).
Acknowledgements
----------------
* 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