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


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