To provide an environment for illustrating graph (network) algorithms, the NetWorKs program must contain a graph, and it must also provide a set of methods (functions) for algorithms to access and manipulate the graph's vertices and edges. Storage and access is provided by the GraphPanel, Graph, Edge, and Vertex classes.
A Graph stores Vertex and Edge objects using two Java library HashTable objects which grow dynamically. Vertex objects also use a HashTable to store incident Edges, and Edges contain incident Vertex objects. Since using a HashTable requires a hash code for Vertex and Edge objects, it is particularly convenient that the Java library String class has a built in method which produces a hash code from a String. The hash code for a Vertex is based on a String representing a unique internal vertex number. The hash code for an Edge is based on a String representing its two vertices. For example, the String ``3'' would be used for a Vertex numbered 3, and the String ``3 7'' would be used for an Edge containing Vertex objects numbered 3 and 7. This arrangement provides a unique String for each Edge because the Graph class does not permit multi-edges; however, note that this requires that Vertex objects have a unique, fixed vertex number.
The GraphPanel contains a SimpleGraph (directed) and a SimpleUndirectedGraph. These are both extensions of (based on) the Graph class, and so are used in exactly the same way as a Graph. The GraphPanel is responsible for adding and deleting Edge and Vertex objects to and from the Graphs. To secure a unique natural number for each Vertex, the GraphPanel class uses an unused natural number list (UNNL). A UNNL produces a sequence of natural numbers which have either not been used, or have been returned for reuse. A UNNL is actually a modified stack with get() and reuse() methods (functions). When a UNNL is empty, its get() method returns the next unused natural number. Otherwise, the UNNL behaves just like a stack. In fact, the UNNL class is an extension of the Java library Stack class.
Graph algorithms cannot directly access the HashTables containing Vertex and Edge objects. Instead, the Graph class provides get(), put(), and delete() methods for access. This means that storage can easily be modified to use some other data structure without changing how graph algorithms access Vertex and Edge objects. But because Graph objects use HashTables for storage, the get(), put(), and delete() methods provide average O(1) access to vertices and edges.
Requesting access to an individual edge or vertex is not always convenient because some graph algorithms consider vertices or edges in a specific order. For example, Kruskal's algorithm for finding minimum weight spanning trees considers edges by weight. At each step the algorithm selects the minimum weight edge that would not add a cycle to the previously selected edge set. Kruskal's algorithm is called edge-based. On the other hand, Dijkstra's shortest path algorithm works in a vertex-based manner. At each step the algorithm selects the vertex ``closest'' to the previously selected vertex set. Not all algorithms are edge-based or vertex-based. Also, an edge-based algorithm might be implemented in a vertex-based manner, or the reverse.
To provide access to graph algorithms which consider edges or vertices in various orders, the Graph class has edges() and vertices() methods which create arrays of its Vertex or Edge objects. The Vertex class can also produce arrays of incident edges through inEdges(), outEdges(), and edges() methods. Each of these arrays may be sorted by any of their attributes using a HeapSort() method from the Sort class.