(updated 06/27/2005)
DIMACS Projects: LINK
LINK: A Software System for Discrete Mathematics
Latest version: 1.5.
LINK is a software system designed to be a general-purpose, extendible
computing environment in which discrete mathematical objects representing
real world problems can be easily manipulated and visualized. The system
features a full Scheme interpreter
with access to the Tk graphics toolkit (STk), a flexible GUI, and
a rich variety of Collection and Graph
objects which are grouped into C++ libraries. This computing environment
offers access at levels ranging from point-and-click to command-line
manipulation and query writing to large-scale systems development.
LINK is ideal for quick and easy creation, manipulation,
loading, and storing of graphs, hypergraphs, and their attributes.
This power will encourage experimentation with algorithms
and properties of graphs.
Link has been designed primarily
as an educational tool and research tool, though it could be a useful
prototyping tool for industry. Since the system uses an interpretive, object-
oriented graphics package, viewing graphs of more than 1000 vertices and
edges is not currently practical, though future work can improve that
number somewhat.
LINK 1.5 is currently available
(see below).
The LINK project is currently led by Dr. Jonathan Berry, a
technical staff member at Sandia National Laboratories, and
one of LINK's primary designers. The software is freely available.
The original primary investigators of LINK are: Nathaniel Dean, then of
Lucent / Bell
Laboratories, Mark Goldberg of Rensselaer Polytechnic Institute,
Greg Shannon, then of MilkyWay Technologies, and Steven Skiena of
SUNY Stony Brook. These researchers, each of whom had previous
experience in the design of software packages for discrete mathematics,
gathered together at DIMACS
in July, 1991 and proposed LINK, a system which would be designed to
emphasize the strengths of the respective systems and overcome their
weaknesses.
LINK has been partially funded by NSF grant CCR-9214487 and
ONR award 400x116yip01. LINK is a cooperative project of DIMACS at
Rutgers University, Los Alamos National Laboratory,
Indiana University, Rensselaer Polytechnic
Institute, and The State University of New York at Stony Brook.
LINK Tutorial: Using LINK to Tour Discrete Mathematics
A document is currently under development to introduce discrete
mathematics via LINK.
Click here for the current version
postscript
LINK Publications:
-
J. Berry and N. Dean and M. Goldberg and G. Shannon and
S. Skiena, Graph Computation with LINK
Software Practice and Experience, Sep., 2000.
-
J. Berry, Improving Discrete Mathmatics and
Algorithms Curricula with LINK
(proceedings of the
ACM's 1997 SIGCSE/SIGCUE
Conference on Integrating Technology into Computer Science Education )
-
J. Berry, LINK: A System for Experimentation with Graphs and
Hypergraphs in SIAM Discrete Mathematics Newsletter, vol. 2, #7, 1997.
-
J. Berry and N. Dean, Market Basket Analysis Using LINK,
Congressus Numerantium, 124:5-13, 1997.
-
J. Berry and N. Dean and M. Goldberg and G. Shannon and
S. Skiena, Graph Drawing and Manipulation with LINK
In Lecture Notes in Computer Science, 1353, pages 425-437.
Springer Verlag, 1997.
-
LINK on-line manual (still a rough draft).
LINK Software
LINK Mailing List
LINK Images:
- image of a water network with sensors LINK
was used to visualize and to analyzing sensor placements in water networks
in the paper
J. Berry and L. Fleischer and W. E. Hart and C. Phillips
, Sensor Placement in Municipal Water Networks in Proceedings of the 2003
World Water and Environmental Resources Congress. Environmental & Water
Resources Institute, 2003. LINK was used to visualize the network (green
means residential, blue means town, brown means industry), and to compute
the "distance" between two sensor placements. It was possible to collapse
sectors (town, industry, etc.) into single vertices to obtain coarser-grain
views of the network. The two scheme files that implemented this are
daily-flow.stklos and
water.stklos
- illustration of embedding K5 on a torus This
example shows the flexibility of the user interface. To serve DIMACS's DREI98
conference, the vertex and edge bindings were changed so that adding, moving,
or changing the attributes of a vertex in any of 9 windows added, moved, or
updated a copy in the other 8. Edges could be introduced either within or
between windows. It was possible to confine these customizations to a single
Scheme file, included in its entirety: hollywood.stklos .
- The fanoplane,
a special example of a hypergraph where
each edge has exactly three vertices. This hypergraph contains the
minimum number
of triples necessary to guarantee that any two-coloring of the vertices
leaves at least one triple (edge) "monochromatic," i.e., containing vertices
of only one color.
- The animation controller
- A Latka Tournament,
defined by Dr. Brenda Latka of Lafeyette College.
LINK has been used to make several
interesting conjectures related to parital orderings of these tournaments.
Each edge in the graph shown in this image is colored according to the
number of directed triangles in which it participates.
- An induced subgraph of the Latka
tournament extracted by pointing and clicking.
- An isomorphism test using Brendan
McKay's nauty.
- The results of the test.
- An example Scheme/Tk session
which sets edge weights, finds a minimum spanning tree, then
highlights it.
Contacts:
- Jonathan Berry,
jberry@sandia.gov ,
Sandia National Laboratorie , 505 284-4021
- Nathaniel Dean,
nate@caam.rice.edu, Texas Southern University
- Mark Goldberg,
goldberg@cs.rpi.edu , Rensselaer Polytechnic Institute, 518-276-2609
- Greg Shannon,
shannon@spanning.com, Spanning Tree Technologies.
- Steven Skiena,
skiena@cs.sunysb.edu, SUNY Stony Brook.
Contact: 
