Graphs and networks arise in the modeling and analysis of a variety of systems. These include computer networks, transportation systems, electrical circuits, and distribution systems. In general, a graph G is mathematical construct typically defined as G=(V,E) where 
is a set of vertices, and 
is a set of undirected edges. The edge 
is incident with its vertices, 
and 
. The degree of vertex is the number of edges which are incident with . If G represents a directed graph, then 
and the edge 
is directed from to . The edge 
is said to be incident from , and incident to . The out-degree of vertex is the number of edges incident from .
The in-degree of vertex is the number of edges incident to . Some graphs are defined to allow multi-edges, but graphs defined as above contain at most one 
edge. G is called simple if it has no loops, 
. A network G is a graph (V,E) in which quantitative information is associated with the vertices and/or edges. A vertex may have a demand 
, and an edge or may have a cost (weight) 
, and a flow 
. There may also be lower bounds (minima) 
and upper bounds (capacities) 
on flows. Frequently, the networks attributes are integers, i.e. 
, and we will make this assumption here as well. One of the appeals of using graphs (and networks) for modeling is in providing a concise visual representation of a system: whether it is a configuration of computers, a city street system, or a sequence of moves in a board game. As a part of this representation, vertices and edges may be colored. These colors are typically denoted as natural numbers in the mathematical construct.
Not only do graphs provide a clearly grasped representation of certain problems, but this representation often affords a more efficient means of solving a given problem. For example, shortest paths are more easily found by applying an algorithm (a finite sequence of operations which accomplish a specific task) to the underlying network itself than by applying the techniques of linear programming. Since textbook descriptions of a network algorithm are sometimes overly terse or abstract, there is definite virtue in visually illustrating such an algorithm by a series of operations on the network itself. In this way, the computer animated illustration of graph and network algorithms promises to be a valuable teaching tool.
The objective of this project was to design and implement a graphically oriented computer program which provides an environment for illustrating/animating graph and network theoretic algorithms. In particular the environment should allow users to create and manipulate graphs, and to then request that an algorithm be performed on the resulting graph. In addition to a graphical user interface (GUI), the environment should provide a rich set of instructions available to programmers for writing algorithms, and it should provide a simple mechanism for adding new algorithms to the environment. The current project includes several algorithms to test the GUI, to demonstrate how algorithms may be added, and to assess the instruction set available for writing algorithms.
The programming language Java was selected to implement this project for several reasons. First, Java is object oriented, and the object oriented paradigm is pervasive among GUI based programs. Java includes a abstract window toolkit package called the awt, which includes ready made buttons, checkboxes, menus, etc. Also, Java offers the opportunity to develop platform independent programs, and Java applets--special limited programs--may be placed on a web page and run over the Internet. This certainly makes the project more accessible.
The remainder of this document describes a set of Java classes--templates for objects--and an application called NetWorKs which satisfies the project objectives. NetWorKs includes a Java applet that can run on a web page and may be used over the Internet. The application provides text based file I/O, and a small future modification to the applet will allow users to read files. Applets are not generally permitted to write to files because of security related issues. The NetWorKs applet may be viewed via http://www.math.clemson.edu/
kellyw .
The algorithms currently available are: