DIMACS TR: 95-15
LINK: A Combinatorics and Graph Theory Workbench for Applications a
nd Research
Authors: Jon Berry, Nathaniel Dean, Patricia Fasel, Mark Goldberg, Elizabeth Jo
hnson, John MacCuish, Gregory Shannon, Steven Skiena
ABSTRACT
LINK is a set of C++ class libraries that supports applications in discrete
mathematics. The libraries include a commandline interpreter and a graphical
user interface that allow access to basic data structures such as \Sets\
and \Lists, and a graph hierarchy that includes undirected, directed, and
``mixed'' graph may contain both directed and undirected edges. Many standard
data structures including arrays, lists, heaps and binary search trees are
within a \Container\ hierarchy. \Sets\ and \Sequences\ are supported within
a \Collection\ hierarchy. The data structure hierarchies enable the user to
experiment with competing data structure implementations, and with more complex
and sophisticated data structures. If an algorithm has several possible
choices of a data structure to be used, a single object can be created that
is templated with the particular data structure desired. LINK also contains
a set of graph generators, layout algorithms for hypergraphs and binary graphs,
and numerous graph algorithms.
Interactive visulation of hypergraphs, graphs, and subgraphs is included in
LINKGUI, the research tool application for combinatorics and graph theory built
on top of the LINK libraries. LINKGUI is a collection of libraries that
includes a Motif-based graphical user interface and Tcl-based command-line
interface. The ability to select, contract and expand subgraphs and nested
subgraphs in either hypergraphs or binary graphs is included in LINKGUI.
LINKGUI enables a user to perform unary operations, such as complement, on a
particular graph or to combine graphs via binary operations such as graph
union or intersection. The resulting graphs can be displayed in multiple
windows. Algorithms can be run on graphs where subgraphs have been contracted
into single vertices. Other LINK applications can be developed by using
various parts of the library code and adding code specific to the application.
This new code can include an entirely different interface from that supplied
by LINKGUI.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-15.ps.gz
DIMACS Home Page