The GraphAlgorithm and Algorithms classes allow the NetWorKs program to access GraphAlgorithm extensions. It is also necessary for GraphAlgorithms to access objects within the NetWorKs program. NetWorks includes a large number of objects, but not all of these are relevant to GraphAlgorithms. From the perspective of a GraphAlgorithm, the NetWorKs program has an instruction set comprised of selected methods and constants from the GraphPanel, Graph, Edge, Vertex, and General classes. This instruction set constitutes the NetWorKs side of the interface.
Recall from the discussion of data structures that the GraphPanel contains the Graphs. Also, recall that the GraphAlgorithm init() and step() methods are passed a GraphPanel argument. GraphAlgorithms may use the GraphPanels methods, variables, and constants listed below in order to access the Graphs.
public class GraphPanel extends Panel
public Graph graphA[], // the two graphs
graph // the currently displayed graph
public UNNL numsA[], // UNNLs for setting vertex numbers
nums // the UNNL for the currently displayed graph
public static final int Simple, // used by currentGraph() methods
SimpleUndirected // to identify graphs
public int currentGraph() // returns Simple or SimpleUndirected
public void currentGraph(int g) // swaps the display to graph g
public boolean load(String str) // loads a graph from str into the
// appropriate graph, which then becomes
// the currently displayed graph
The graphA array contains a SimpleGraph and a SimpleUndirectedGraph, which are treated exactly the same as Graph objects. Although the GraphAlgorithm may access either of these Graphs, the graph variable is the Graph that the GraphAlgorithm typically manipulates.
Note that a GraphPanel contains a UNNL for each Graph. This is used to maintain a list of unused natural numbers to number Vertex
objects. GraphAlgorithm extensions which add or delete Vertex objects are responsible for securing and/or returning Vertex numbers from and/or to the
appropriate UNNL. Also note that a GraphAlgorithm can use the GraphPanel load() method to load a new Graph.
By using the graph variable, GraphAlgorithms may use many of the Graph class methods. Most of these allow access to edges and vertices.
public class Graph public Graph() // Constructor public Graph(Edge[] eA, Vertex[] vA) // Constructor public int numEdges() public int numVertices() public String toString() // text representation public Graph put(int v, Vertex V) // insert V as the number v vertex public Graph put(Vertex V) // insert V with its current v number public Graph put(Vertex[] VA) // insert the vertices in VA[] public Graph put(int u, int v, Edge E) // insert E from u to v (or between) public Graph put(Edge E) // insert E using its current u,v public Graph put(Edge[] eA) // insert the edges in EA public Vertex get(Vertex V) // get the Vertex with V's number public Vertex get(int v) // get the Vertex numbered v public Edge get(Edge E) // get the Edge with E's u,v public Edge get(int u, int v) // get the u,v Edge public Graph delete(Vertex V) // delete the Vertex with V's number public Graph delete(int v) // delete the Vertex numbered v public Graph delete(Edge E) // delete the Edge with E's u,v public Graph delete(int u, int v) // delete the u,v Edge public void deleteAll() // delete every Edge and Vertex public Vertex[] vertices() // returns an array of all vertices public Edge[] edges() // returns an array of all edges public boolean isVertex(int v) public boolean isEdge(int u, int v) public void mergeVertexColors(int oldColor, int newColor) public void mergeEdgeColors(int oldColor, int newColor) public void mergeColors(int oldColor, int newColor) public int uncolor() // sets all edges, vertices to the default color public boolean contains(xPoint p) // true if an Edge or Vertex contains p public boolean beenSelected() // true if an Edge or Vertex is selected public Object selectedPart() // selected Vertex or Edge (or null) public void unselect() // unselect any selected Vertex or Edge public Edge select(int u, int v) // select the u,v Edge public Vertex select(int v) // select the number v Vertex public Object select(xPoint p) // select the Vertex or Edge containing pNote that the Graph class methods mergeVertexColors(), mergeEdgeColors(), mergeColors() and uncolor() manipulate the colors of the vertices and edges. This could be done by accessing each edge and vertex individually, but the Graph class can do so more efficiently. The other attributes of the Edge and Vertex objects in a Graph must be manipulated directly.
GraphAlgorithms may use Edge methods to access and modify the color, weight, flow, capacity, and minimum attributes of any Edge in the Graph. The Edge class also provides a precedes() method that allows an array of Edge objects to be sorted by any of these attributes. GraphAlgorithms may create Edges to insert in a Graph, and the U() and V() methods return the Vertex objects contained in an Edge. Here are the Edge methods and constants which may be used by GraphAlgorithms.
public class Edge implements Cloneable, Sortable
// Constructors - missing values are set to defaults
public Edge(int colorNum,int weight, int flow, int capacity, int minimum)
public Edge(int colorNum,int weight, int flow, int capacity)
public Edge(int colorNum,int weight, int capacity)
public Edge(int colorNum,int weight)
public Edge(int colorNum)
// sort orders recognized by the Edge.precedes() method
public static final int weightOrderA, // A = ascending
weightOrderD, // D = descending
VvNumOrderA,
VvNumOrderD,
UvNumOrderA,
UvNumOrderD,
capacityOrderA,
capacityOrderD,
flowOrderA,
flowOrderD,
colorNumOrderA,
colorNumOrderD,
minimumOrderA,
minimumOrderD
public final Edge beenSelected(boolean tf)
public final boolean beenSelected()
public final Edge colorNum(int cNum)
public final int colorNum()
public final Vertex U() // returns the u vertex
public final Vertex V() // returns the v vertex
public final boolean directed()
public final int weight()
public final Edge weight(int wt)
public final int flow()
public final Edge flow(int f)
public final int minimum()
public final Edge minimum(int low)
public final int capacity()
public final Edge capacity(int cap)
public Object clone() // returns a copy
public boolean contains(xPoint p)
public boolean precedes(Sortable s, int order)
Vertex objects may also be manipulated by GraphAlgorithms. The Vertex class provides methods to access color, demand and vName (label) attributes. It also provides a precedes() method which allows an array of Vertex objects to be sorted by any of these attributes. GraphAlgorithms may create Vertex objects to insert in a Graph. Note that a Vertex can produce arrays of in-incident, out-incident, or incident edges. The following methods and constants may be used by GraphAlgorithms.
public final class Vertex implements Cloneable, Sortable
// Constructors - missing values are set to defaults
public Vertex(int vNum, String vName, int demand, int colorNum, int x, int y)
public Vertex(int vNum, String vName)
public Vertex(int vNum)
// sort orders recognized by the Vertex.precedes() method
public final static int vNumOrderA // A = ascending
vNumOrderD // D = descending
demandOrderA,
demandOrderD,
vNameOrderA,
vNameOrderD,
colorNumOrderA,
colorNumOrderD
public Edge[] edges() // returns an array of all incident edges
public Edge[] inEdges() // returns an array of all in-incident edges
public Edge[] outEdges() // returns an array of all out-incident edges
public final boolean beenSelected()
public final Vertex beenSelected(boolean tf)
public final xPoint center()
public final Vertex center(xPoint p)
public final Vertex center(int x, int y)
public final int degree()
public final int inDegree()
public final int outDegree()
public final Vertex colorNum(int cNum)
public final int colorNum()
public final int demand()
public final Vertex demand(int d)
public final Vertex vName(String vName)
public final String vName()
public final Vertex vNum() // The vNum of a Vertex in a Graph can be
// accessed but cannot be changed
public Object clone() // produces a copy
public boolean contains(xPoint p)
public boolean precedes(Sortable s, int order)
In addition to the GraphPanel, Graph, Edge and Vertex classes, GraphAlgorithms may also access the General class. This class contains data relevant to a variety of the NetWorKs classes. Most of the data and methods in the General class are not relevant to GraphAlgorithms; however, the following constants may be useful.
static final int defaultColorNum=0,
defaultWeight=1,
defaultFlow=0,
defaultCapacity=999,
defaultMinimum=0,
defaultDemand=0
Many of the methods, variables, and constants from the GraphPanel, Graph, Edge, Vertex, and General classes were used in writing the GraphAlgorithms currently available in the NetWorKs program. These provide examples of how to access objects within the NetWorKs program, and how to write GraphAlgorithms. See section 6 on GraphAlgorithm Class Extensions for source code and documentation.