exe
Class VisualGraph

java.lang.Object
  exe.VisualGraph

Direct Known Subclasses:

GAIGSgraph

public class VisualGraph
extends java.lang.Object

This class is a tool for storing and manipulating graphs. A VisualGraph is composed of vertices of type VisNode and edges of type VisEdge. Methods are provided for creating specific types of graphs, manipulating these graphs to produce algorithm visualizations, and writing these graphs to the showfiles used by the GAIGS visualizer.

Each vertex in a VisualGraph can have any unique alphanumeric (A-Z, a-z, 0-9) value as its label. Therefore, the maximum number of nodes in a VisualGraph is 62, which results in a maximum of 3844 edges. If the VisualGraph is a heuristic graph, the heuristic value for each vertex will be printed beneath the node's label when it is displayed in the GAIGS visualizer.

In order to use any of these graph classes in a script-producing program, the script-producing program must import the package exe.

Field Summary

protected boolean	directed Tracks whether this VisualGraph has directed edges or if all edges are undirected.
protected double	font_size Holds the minimum font size for this VisualGraph when drawn in the new GAIGS XML format.
protected boolean	heuristics Maitains whether this VisualGraph contains heuristic values or whether it has no heuristic information.
protected static int	MAX_NODES Stores the maximum number of nodes for this VisualGraph.
protected VisEdge[][]	my_edgeset Stores the list of all possible edges in this VisualGraph.
protected VisNode[]	my_nodeset Maintains the list of all possible nodes in this VisualGraph.
protected int	num_edges Contains the current number of activated edges in this VisualGraph.
protected int	num_nodes Tracks the current number of activated nodes in this VisualGraph.
protected boolean	weighted Maintains whether this VisualGraph has weighted or unweighted edges.
protected double	x1 Stores the left-most x-bound for this VisualGraph within the normalized [0,1] space.
protected double	x2 Stores the right-most x-bound for this VisualGraph within the normalized [0,1] space.
protected double	y1 Stores the lower y-bound for this VisualGraph within the normalized [0,1] space.
protected double	y2 Stores the upper y-bound for this VisualGraph within the normalized [0,1] space.

Constructor Summary

VisualGraph()
Constucts a VisualGraph with default information.

VisualGraph(boolean weighted, boolean directed, boolean heuristics)
Constructs a VisualGraph by specifying whether or not it has edge weights, directed edges, and heuristic values for nodes.

Method Summary

void	addEdge(char start, char end, double weight, java.lang.String my_col) Adds a new edge to this VisualGraph by specifying its start start node, end node, weight, and color.
void	addNode(char c, double my_x, double my_y, java.lang.String my_col) Adds a new node to this VisualGraph by specifying its label, coordinates, and color.
void	addNode(char c, java.lang.String my_col) Adds a new node to this VisualGraph by specifying its label and color.
java.util.Enumeration	allAdjacentNodes(char c) Returns an Enumeration of all the nodes in this VisualGraph that are connected to the given node via an edge.
java.util.Enumeration	allNodes() Returns an Enumeration of all the nodes in this VisualGraph.
void	clearGraph() Clears this VisualGraph by returning the data for all nodes and edges to their default values.
boolean	edgeExists(char start, char end) Indicates if the specified edge is activated in this VisualGraph.
double	edgeWeight(char start, char end) Returns the weight of the specified edge in this VisualGraph.
boolean	empty() Indicates whether this VisualGraph is empty or contains some data.
boolean	full() Indicates whether the maximum number of nodes has been reached or if there are still unused nodes available in this VisualGraph.
boolean	fullEdge() Indicates whether the maximum number of edges has been reached or if there are still unused edges available in this VisualGraph.
void	gaigsChangeHexEdgeColors(java.lang.String search, java.lang.String replace) Changes any edges in this VisualGraph with the color indicated by search to have the color specified by replace.
void	gaigsChangeHexNodeColors(java.lang.String search, java.lang.String replace) Changes any nodes in this VisualGraph with the color indicated by search to have the color specified by replace.
double	gaigsDistPoints(double x1, double y1, double x2, double y2) Returns the Euclidean distance between two points specified by their Cartesian coordinates.
boolean	gaigsIsOverlap() Checks to make sure this VisualGraph's layout does not have any overlaps.
VisEdge[][]	getEdges() Returns my_edgeset so that a script-producing program can access the VisEdge objects that comprise this VisualGraph.
char	getNextNode() Gives the char name/label for the next unactivated node.
VisNode[]	getNodes() Returns my_nodeset so that a script-producing program can access the VisNode objects that comprise this VisualGraph.
int	getNumEdges() Returns the number of edges that are currently activated in this VisualGraph.
int	getNumNodes() Returns the number of nodes that are currently activated in this VisualGraph.
boolean	hasHeuristics() Indicates if this VisualGraph contains or does not contain heuristic values.
void	initializeEdgeWeights() Initializes the edge weights based on the the Euclidean distances between their start and goal nodes.
void	initializeHValues(int g) Initializes the heuristic values of the nodes based on their Euclidean distances from the specified goal node.
boolean	isDirected() Tells if this VisualGraph has directed or bidirectional edges.
boolean	isWeighted() Tells if this VisualGraph has weighted or unweighted edges.
boolean	nodeExists(char c) Indicates if the specified node is activated in this VisualGraph.
void	OLDrandomDAcyclicGraph(int node_c, int edge_c, boolean self_loop, boolean weights, double min_weight, double max_weight)
void	organizeCircle() Organizes the nodes of this VisualGraph around a unit circle to produce a more readable layout.
void	organizeGraph() Executes the Kamada Algorithm on the nodes and edges currently in this VisualGraph to produce a readable layout.
char	randomActiveNode() Returns the name/label for a randomly selected activated node.
int[]	randomAStarSearchGraph(int node_c, int edge_c) Clears this VisualGraph and produces a randomly generated sparsely connected heuristic graph that demonstrates the unique feature of the A* Algorithm, namely the reopening of a closed node when a poor heuristic value caused the node to be closed with a greater-than-optimal cost.
void	randomCompleteGraph(int node_c, boolean self_loop, boolean weights, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated complete graph according to the supplied constraints.
void	randomConnectedGraph(int node_c, int edge_c, boolean self_loop, boolean weights, boolean dircted, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated connected graph according to the supplied constraints.
void	randomDAcyclicGraph(int node_c, int edge_c, boolean self_loop, boolean weights, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated directed acyclic graph according to the supplied constraints.
void	randomGAIGSGraph(int numNodes, int numEdges, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated sparsely connected graph suitable for many algorithm visualizations.
void	randomGraph(int node_c, int edge_c, boolean self_loop, boolean weights, boolean dircted, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated graph according to the supplied constraints.
void	randomHamiltonianGraph(int node_c, int edge_c, boolean self_loop, boolean weights, boolean dircted, double min_weight, double max_weight) Clears this VisualGraph and produces a randomly generated graph containing a Hamiltonian Cycle according to the supplied constraints.
int[]	randomHeuristicGraph(int node_c, int edge_c) Clears this VisualGraph and produces a randomly generated sparsely connected graph with heuristic values for the nodes.
char	randomNewNode() Returns the name/label for a randomly selected unactivated node.
char	randomNode() Returns the name/label for a randomly selected node.
void	readGAIGSXMLGraph(java.lang.String filename) Reads in a showfile and extracts the information contained within the first set of <graph> tags to initialize this VisualGraph.
int[]	readStartGoal(java.lang.String filename) Reads in a showfile in order to extract the start and goal nodes from the first <title> element in the showfile.
void	removeEdge(char start, char end) Removes an edge from this VisualGraph by giving its starting and ending nodes.
void	removeNode(char c) Removes a node from this VisualGraph by giving its label.
void	resetNodes() Reinitializes the nodes after running a test algorithm for layout purposes.
java.lang.String	runAStar(char start, char goal) Runs the A* Algorithm on this VisualGraph to find the shortest path to the specified goal node from the indicated start node.
void	setBounds(double x1, double y1, double x2, double y2) Sets the bounds in which this VisualGraph is to be drawn.
void	setDirected() Indicates that this VisualGraph has at least one directed edge.
void	setEdgeColor(char start, char end, java.lang.String my_col) Modifies the color for the specified edge in this VisualGraph.
void	setEdgeWeight(char start, char end, double new_weight) Changes the edge weight for the specified edge in this VisualGraph.
void	setFontSize(double size) Sets the minimum font size to keep the fonts in this VisualGraph readable.
void	setHeuristics(boolean h) Sets whether this VisualGraph uses or does not use heuristic values.
void	setLimitedNodePos(char index, double x, double y) Changes the coordinates for the specified node in this VisualGraph.
void	setNodeColor(char c, java.lang.String my_col) Modifies the color for the specified node in this VisualGraph.
void	setNodePos(char index, double x, double y) Changes the coordinates for the specified node in this VisualGraph.
void	setUndirected() Indicates that this VisualGraph has only bidirectional edges.
void	setUnweighted() Specifies that this VisualGraph has unweighted edges.
void	setWeighted() Specifies that this VisualGraph has weighted edges.
java.lang.String	testAStar(char start, char goal) Runs the A* Algorithm on this VisualGraph to monitor if the algorithm will have to reopen a closed node to find the shortest path to the specified goal node from the indicated start node.
int	translateCharIndex(char c) Returns the my_nodeset index that corresponds to the specified name/label value.
char	translateIndexChar(int index) Returns the name/label of the node at the specified index in my_nodeset.
void	writeGAIGSGraph(java.io.PrintWriter out, java.lang.String title) Writes this VisualGraph to the given PrintWriter output stream using the original GAIGS specifications for Graphs/Networks.
void	writeGAIGSXMLGraph(java.io.PrintWriter out) Writes this VisualGraph to the given PrintWriter output stream using the new GAIGS XML format.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MAX_NODES

protected static final int MAX_NODES

Stores the maximum number of nodes for this VisualGraph.

See Also:

Constant Field Values

my_nodeset

protected VisNode[] my_nodeset

Maintains the list of all possible nodes in this VisualGraph. Initialized with all VisNode objects in the default, unactivated state. See default VisNode constructor for details.

my_edgeset

protected VisEdge[][] my_edgeset

Stores the list of all possible edges in this VisualGraph. Initialized with all VisEdge objects in the default, unactivated state. See default VisEdge constructor for details.

num_nodes

protected int num_nodes

Tracks the current number of activated nodes in this VisualGraph. Note that these activated nodes may not be consecutive within my_nodeset.

num_edges

protected int num_edges

Contains the current number of activated edges in this VisualGraph.

x1

protected double x1

Stores the left-most x-bound for this VisualGraph within the normalized [0,1] space. Defaults to 0.0 if no bounds are set. The bounds variables can be used to localize this VisualGraph in a section of the drawing window in the new GAIGS XML format to allow multiple structures to appear in the same snapshot.

y1

protected double y1

Stores the lower y-bound for this VisualGraph within the normalized [0,1] space. Defaults to 0.0 if no bounds are set. The bounds variables can be used to localize this VisualGraph in a section of the drawing window in the new GAIGS XML format to allow multiple structures to appear in the same snapshot.

x2

protected double x2

Stores the right-most x-bound for this VisualGraph within the normalized [0,1] space. Defaults to 1.0 if no bounds are set. The bounds variables can be used to localize this VisualGraph in a section of the drawing window in the new GAIGS XML format to allow multiple structures to appear in the same snapshot.

y2

protected double y2

Stores the upper y-bound for this VisualGraph within the normalized [0,1] space. Defaults to 1.0 if no bounds are set. The bounds variables can be used to localize this VisualGraph in a section of the drawing window in the new GAIGS XML format to allow multiple structures to appear in the same snapshot.

font_size

protected double font_size

Holds the minimum font size for this VisualGraph when drawn in the new GAIGS XML format. Used to specify a font size that will be readable when this VisualGraph is drawn in a smaller portion of the screen.

weighted

protected boolean weighted

Maintains whether this VisualGraph has weighted or unweighted edges. A value of true means that the edges are labeled with weights, and false indicates they do not have labels.

directed

protected boolean directed

Tracks whether this VisualGraph has directed edges or if all edges are undirected. A value of true means that there is at least one directed edge, and false indicates that all edges are bidirectional.

heuristics

protected boolean heuristics

Maitains whether this VisualGraph contains heuristic values or whether it has no heuristic information. A value of true means heuristics are used, and false indicates there are no heuristic values.

Constructor Detail

VisualGraph

public VisualGraph()

Constucts a VisualGraph with default information.

VisualGraph

public VisualGraph(boolean weighted,
                   boolean directed,
                   boolean heuristics)

Constructs a VisualGraph by specifying whether or not it has edge weights, directed edges, and heuristic values for nodes. The bounds and font size are assigned default values and must be set via separate method calls.

Parameters:

weighted - Indicates if this VisualGraph has weighted edges. A value of true means that the edges have weights that are displayed near the edges; false indicates that no edge weights are present.

directed - Specifies whether the edges of this VisualGraph are directed or bidirectional. A value of true indicates directed edges, and false means that all edges are bidirectional.

heuristics - Indicates if this VisualGraph contains heuristic values. A value of true means that the nodes have heuristic values that are displayed under the node labels; false indicates that no heuristic values should be shown.

Method Detail

clearGraph

public void clearGraph()

Clears this VisualGraph by returning the data for all nodes and edges to their default values.

setBounds

public void setBounds(double x1,
                      double y1,
                      double x2,
                      double y2)

Sets the bounds in which this VisualGraph is to be drawn. These bounds specify the area in the normalized [0,1] space within which this VisualGraph should appear in the snapshot. Used to draw this VisualGraph in a portion of the viewing window so that multiple structures can appear in a snapshot in the new GAIGS XML format.

Parameters:

x1 - Sets the left-most bound on the horizontal axis.

y1 - Sets the lower bound on the vertical axis.

x2 - Sets the right-most bound on the horizontal axis.

y2 - Sets the upper bound on the vertical axis.

setFontSize

public void setFontSize(double size)

Sets the minimum font size to keep the fonts in this VisualGraph readable. Used to upsize the font when drawing this VisualGraph in a portion of the viewing window in the new GAIGS XML format.

Parameters:

size - Indicates the minimum font size for the fonts in this VisualGraph.

setWeighted

public void setWeighted()

Specifies that this VisualGraph has weighted edges. After calling this method, edges are labeled with their weights when this VisualGraph is written to a showfile.

setUnweighted

public void setUnweighted()

Specifies that this VisualGraph has unweighted edges. After calling this method, edges will not have labels when this VisualGraph is written to a showfile.

setDirected

public void setDirected()

Indicates that this VisualGraph has at least one directed edge.

If there are already edges activated in this VisualGraph, this method returns without doing anything.

setUndirected

public void setUndirected()

Indicates that this VisualGraph has only bidirectional edges. Note that, after calling this method, this VisualGraph can have no directed edges.

If there are already edges activated in this VisualGraph, this method returns without doing anything.

setHeuristics

public void setHeuristics(boolean h)

Sets whether this VisualGraph uses or does not use heuristic values.

Parameters:

h - Indicates if heuristic values are used. A value of true means that heuristic values are displayed under the node labels, and false causes no heuristic values to be shown.

isWeighted

public boolean isWeighted()

Tells if this VisualGraph has weighted or unweighted edges.

Returns:

Gives true if the edges are displayed with weights and false if the edges are shown without weights

isDirected

public boolean isDirected()

Tells if this VisualGraph has directed or bidirectional edges.

Returns:

Gives true if there is at least one directed edge in this VisualGraph and false if all edges are bidirectional.

hasHeuristics

public boolean hasHeuristics()

Indicates if this VisualGraph contains or does not contain heuristic values.

Returns:

Yields true if heuristic values are shown under the node labels and false if no heuristic values are displayed.

getNumNodes

public int getNumNodes()

Returns the number of nodes that are currently activated in this VisualGraph. Note that these activated nodes do not necessarily occupy consecutive indices within my_nodeset, the list of all possible nodes in the graph.

Returns:

Gives the number of activated nodes in this VisualGraph.

getNumEdges

public int getNumEdges()

Returns the number of edges that are currently activated in this VisualGraph.

Returns:

Gives the number of activated edges in this VisualGraph.

getNodes

public VisNode[] getNodes()

Returns my_nodeset so that a script-producing program can access the VisNode objects that comprise this VisualGraph. This allows convenient and efficient manipulation of the coloring and other attributes of the nodes so that the showfile produced by this VisualGraph matches the state of the script-producing program.

Returns:

Gives a reference to my_nodeset.

getEdges

public VisEdge[][] getEdges()

Returns my_edgeset so that a script-producing program can access the VisEdge objects that comprise this VisualGraph. This allows convenient and efficient manipulation of the coloring and other attributes of the edges so that the showfile produced by this VisualGraph matches the state of the script-producing program.

Returns:

Gives a reference to my_edgeset.

addNode

public void addNode(char c,
                    double my_x,
                    double my_y,
                    java.lang.String my_col)

Adds a new node to this VisualGraph by specifying its label, coordinates, and color. The indicated node in the graph is activated and modified according to the values given. If the node with this label is already activated, this method returns without doing anything.

Parameters:

c - Indicates which node is to be activated by giving its unique name/label. The node with this character is activated and modified according to the other parameters.

my_x - Sets the Cartesian x-coordinate of the center of this node in [0,1] space.

my_y - Sets the Cartesian y-coordinate of the center of this node in [0,1] space.

my_col - Indicates the color of this newly activated node. The value must be a six-digit hexadecimal color String of the form #123456. The symbol '#' must be included.

addNode

public void addNode(char c,
                    java.lang.String my_col)

Adds a new node to this VisualGraph by specifying its label and color. The indicated node in the graph is activated and modified according to the values given. If the node with this label is already activated, this method returns without doing anything.

Parameters:

c - Indicates which node is to be activated by giving its unique name/label. The node with this character is activated and modified according to the other parameter.

my_col - Indicates the color of this newly activated node. The value must be a six-digit hexadecimal color String of the form #123456. The symbol '#' must be included.

addEdge

public void addEdge(char start,
                    char end,
                    double weight,
                    java.lang.String my_col)

Adds a new edge to this VisualGraph by specifying its start start node, end node, weight, and color. The indicated edge in the graph is activated and modified according to the values given. If the graph is directed, only the specified edge is added; however, if the graph is not directed, the corresponding edge from end to start is activated as well. If the edge with these start and end nodes is already activated, this method returns without doing anything.

Parameters:

start - Gives the label of the starting node for this edge.

end - Gives the label of the ending node for this edge.

weight - Specifies the weight for this new edge. This value is ignored for an unweighted graph.

my_col - Indicates the color of this newly activated edge. The value must be a six-digit hexadecimal color String of the form #123456. The symbol '#' must be included.

removeNode

public void removeNode(char c)

Removes a node from this VisualGraph by giving its label. The indicated node is deactivated, along with any edges connected to it. If the node is already deactivated, this method returns without doing anything.

Parameters:

c - Indicates which node is to be deactivated by giving its unique name/label. This node is deactivated so that it will not be displayed.

removeEdge

public void removeEdge(char start,
                       char end)

Removes an edge from this VisualGraph by giving its starting and ending nodes. The given edge is deactivated so that it will not be displayed with the graph. If the graph is directed, only the specified edge is removed; however, if the graph is not directed, the corresponding edge from end to start is deactivated as well. If the edge with these start and end nodes is already deactivated, this method returns without doing anything.

Parameters:

start - Gives the label for the starting node for this edge.

end - Gives the label for the ending node for this edge.

setNodeColor

public void setNodeColor(char c,
                         java.lang.String my_col)

Modifies the color for the specified node in this VisualGraph. If the indicated node is not activated, this method returns without doing anything.

Parameters:

c - Indicates the node that should be changed by giving its unique name/label.

my_col - Gives the new color for this node. The value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

setEdgeColor

public void setEdgeColor(char start,
                         char end,
                         java.lang.String my_col)

Modifies the color for the specified edge in this VisualGraph. If the indicated edge is not activated, this method returns without doing anything.

Parameters:

start - Indicates the starting node for the edge that should be changed.

end - Indicates the ending node for the edge that should be changed.

my_col - Gives the new color for this edge. The value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

setEdgeWeight

public void setEdgeWeight(char start,
                          char end,
                          double new_weight)

Changes the edge weight for the specified edge in this VisualGraph. If the indicated edge is not activated, this method returns without doing anything.

Parameters:

start - Indicates the starting node for the edge that should be changed.

end - Indicates the ending node for the edge that should be changed.

new_weight - Gives the new weight for the indicated edge.

setNodePos

public void setNodePos(char index,
                       double x,
                       double y)

Changes the coordinates for the specified node in this VisualGraph. Any edges connected to this node are adjusted so that they will still properly connect to this node. If the indicated node is not activated, this method returns without doing anything.

Parameters:

index - Indicates the node that should be changed by giving its unique name/label.

x - Gives the new Cartesian x-coordinate for the center of this node in [0,1] space.

y - Gives the new Cartesian y-coordinate for the center of this node in [0,1] space.

setLimitedNodePos

public void setLimitedNodePos(char index,
                              double x,
                              double y)

Changes the coordinates for the specified node in this VisualGraph. The coordinate values are limited to [0,1]. Therefore, if the value given is greater than 1.0, it will be changed to 1.0, and, if the value given is less than 0.0, it will be changed to 0.0. Any edges connected to this node are adjusted so that they will still properly connect to this node. If the indicated node is not activated, this method returns without doing anything.

Parameters:

index - Indicates the node that should be changed by giving its unique name/label.

x - Gives the new Cartesian x-coordinate for the center of this node in [0,1] space.

y - Gives the new Cartesian y-coordinate for the center of this node in [0,1] space.

edgeWeight

public double edgeWeight(char start,
                         char end)

Returns the weight of the specified edge in this VisualGraph. The value returned for an unactivated edge will always be 0.0.

Parameters:

start - Indicates the starting node for the edge whose weight is to be returned.

end - Indicates the ending node for the edge whose weight is to be returned.

Returns:

Gives the weight of the edge from start to end.

edgeExists

public boolean edgeExists(char start,
                          char end)

Indicates if the specified edge is activated in this VisualGraph.

Parameters:

start - Indicates the starting node for the edge whose existence is in question.

end - Indicates the ending node for the edge whose existence is in question.

Returns:

Gives a value of true if the specified edge is activated; otherwise, false is returned.

nodeExists

public boolean nodeExists(char c)

Indicates if the specified node is activated in this VisualGraph.

Parameters:

c - Indicates the node whose existence is in question.

Returns:

Gives a value of true if the specified node is activated; otherwise, false is returned.

allNodes

public java.util.Enumeration allNodes()

Returns an Enumeration of all the nodes in this VisualGraph.

Returns:

Gives an Enumeration that contains all the nodes in this VisualGraph.

allAdjacentNodes

public java.util.Enumeration allAdjacentNodes(char c)

Returns an Enumeration of all the nodes in this VisualGraph that are connected to the given node via an edge.

Parameters:

c - Indicates the node for which the connecting nodes should be enumerated.

Returns:

Gives an Enumeration that contains all the nodes in this VisualGraph with an edge from c.

empty

public boolean empty()

Indicates whether this VisualGraph is empty or contains some data.

Returns:

Yields a value of true if there are no nodes and no edges in this VisualGraph; otherwise, false is returned.

full

public boolean full()

Indicates whether the maximum number of nodes has been reached or if there are still unused nodes available in this VisualGraph.

Returns:

Yields a value of true if the maximum number of nodes has been reached; otherwise, false is returned.

fullEdge

public boolean fullEdge()

Indicates whether the maximum number of edges has been reached or if there are still unused edges available in this VisualGraph.

Returns:

Gives a value of true if the maximum number of edges has been reached; otherwise, false is returned.

organizeGraph

public void organizeGraph()
                   throws java.io.IOException

Executes the Kamada Algorithm on the nodes and edges currently in this VisualGraph to produce a readable layout.

This method uses the following formulas:

m = current node for which to calculate
dm = Delta(m) = sqrt(Eq7^2 + Eq8^2)

max_dm = max(Delta(m))

(In the following, i is an iterative variable)

diffx = x(m) - x(i)

diffy = y(m) - y(m)

ndist = sqrt({x(m) - x(i)}^2 + {y(m) - y(i)}^2)

Eq7 = dE/dx(m) = Sum(i): k(mi) * (diffx - l(mi) * diffx / ndist)

Eq8 = dE/dy(m) = Sum(i): k(mi) * (diffy - l(mi) * diffy / ndist)

Eq13 = d^2E/dx(m)^2

= Sum(i): k(mi) * [1 - (l(mi) * diffy^2)/ndist^3]

Eq14 = d^2E/dx(m)dy(m)

= Sum(i): k(mi) * [1 - (l(mi) * diffx * diffy)/ndist^3]

Eq16 = d^2E/dy(m)^2

= Sum(i): k(mi) * [1 - (l(mi) * diffx^2)/ndist^3]

deltay = (Eq14 * Eq7 - Eq13 * Eq8) / (Eq13 * Eq16 - Eq14^2)

deltax = -1 * (Eq16 * deltay + Eq8) / Eq14

Throws:

java.io.IOException - Indicates that an error occurred while organizing the graph. The graph may be left in an unreliable state.

organizeCircle

public void organizeCircle()

Organizes the nodes of this VisualGraph around a unit circle to produce a more readable layout. Note that the graph must have more than three nodes to use this method.

gaigsIsOverlap

public boolean gaigsIsOverlap()

Checks to make sure this VisualGraph's layout does not have any overlaps. This involves three steps:

Check to see if the graph has any nodes that fall within a parabola calculated around every edge.

Check to make sure all edge lengths meet a minimum length requirement.

Check to make sure no edge centers are too close together.

The tolerances for the above checks can be adjusted by changing NODE_TOEDGE_MIN, EDGE_LENGTH_MIN, and EDGE_CENTER_MIN respectively.

Returns:

Gives a value of true if one of the above checks finds an overlap in the graph layout; otherwise, false is returned.

randomGraph

public void randomGraph(int node_c,
                        int edge_c,
                        boolean self_loop,
                        boolean weights,
                        boolean dircted,
                        double min_weight,
                        double max_weight)
                 throws java.lang.RuntimeException

Clears this VisualGraph and produces a randomly generated graph according to the supplied constraints.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated.

self_loop - Specifies if edges with the same start and goal node are possible. A value of true indicates that self-loops are allowed, and false means they are not.

weights - Specifies if the edges in the graph should be weighted. Passing true results in a weighted graph, and false yields an unweighted graph.

dircted - Indicates if the edges in the graph should be directed. Giving a value of true means that edges can be unidirectional, and false makes all edges bidirectional.

min_weight - Specifies the minimum weight for edges in the graph. Ignored if the graph is to be unweighted.

max_weight - Specifies the maximum weight for edges in the graph. Ignored if the graph is to be unweighted.

Throws:

java.lang.RuntimeException - Indicates a problem finding a random edge. This VisualGraph will be in an unreliable state, and this method should be called again to generate the desired random graph.

randomCompleteGraph

public void randomCompleteGraph(int node_c,
                                boolean self_loop,
                                boolean weights,
                                double min_weight,
                                double max_weight)

Clears this VisualGraph and produces a randomly generated complete graph according to the supplied constraints.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

self_loop - Specifies if edges with the same start and goal node are possible. A value of true indicates that self-loops are allowed, and false means they are not.

weights - Specifies if the edges in the graph should be weighted. Passing true results in a weighted graph, and false yields an unweighted graph.

min_weight - Specifies the minimum weight for edges in the graph. Ignored if the graph is to be unweighted.

max_weight - Specifies the maximum weight for edges in the graph. Ignored if the graph is to be unweighted.

randomHamiltonianGraph

public void randomHamiltonianGraph(int node_c,
                                   int edge_c,
                                   boolean self_loop,
                                   boolean weights,
                                   boolean dircted,
                                   double min_weight,
                                   double max_weight)
                            throws java.lang.RuntimeException

Clears this VisualGraph and produces a randomly generated graph containing a Hamiltonian Cycle according to the supplied constraints.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated.

self_loop - Specifies if edges with the same start and goal node are possible. A value of true indicates that self-loops are allowed, and false means they are not.

weights - Specifies if the edges in the graph should be weighted. Passing true results in a weighted graph, and false yields an unweighted graph.

dircted - Indicates if the edges in the graph should be directed. Giving a value of true means that edges can be unidirectional, and false makes all edges bidirectional.

min_weight - Specifies the minimum weight for edges in the graph. Ignored if the graph is to be unweighted.

max_weight - Specifies the maximum weight for edges in the graph. Ignored if the graph is to be unweighted.

Throws:

java.lang.RuntimeException - Indicates a problem finding a random edge. This VisualGraph will be in an unreliable state, and this method should be called again to generate the desired random graph.

randomConnectedGraph

public void randomConnectedGraph(int node_c,
                                 int edge_c,
                                 boolean self_loop,
                                 boolean weights,
                                 boolean dircted,
                                 double min_weight,
                                 double max_weight)
                          throws java.lang.RuntimeException

Clears this VisualGraph and produces a randomly generated connected graph according to the supplied constraints.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated. Note that more edges than specified may have to be added to make the graph connected.

self_loop - Specifies if edges with the same start and goal node are possible. A value of true indicates that self-loops are allowed, and false means they are not.

weights - Specifies if the edges in the graph should be weighted. Passing true results in a weighted graph, and false yields an unweighted graph.

dircted - Indicates if the edges in the graph should be directed. Giving a value of true means that edges can be unidirectional, and false makes all edges bidirectional.

min_weight - Specifies the minimum weight for edges in the graph. Ignored if the graph is to be unweighted.

max_weight - Specifies the maximum weight for edges in the graph. Ignored if the graph is to be unweighted.

Throws:

java.lang.RuntimeException - Indicates a problem finding a random edge. This VisualGraph will be in an unreliable state, and this method should be called again to generate the desired random graph.

randomDAcyclicGraph

public void randomDAcyclicGraph(int node_c,
                                int edge_c,
                                boolean self_loop,
                                boolean weights,
                                double min_weight,
                                double max_weight)

Clears this VisualGraph and produces a randomly generated directed acyclic graph according to the supplied constraints.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated. Note that more or fewer edges than specified may have to be added to produce a directed acyclic graph.

self_loop - Specifies if edges with the same start and goal node are possible. A value of true indicates that self-loops are allowed, and false means they are not.

weights - Specifies if the edges in the graph should be weighted. Passing true results in a weighted graph, and false yields an unweighted graph.

min_weight - Specifies the minimum weight for edges in the graph. Ignored if the graph is to be unweighted.

max_weight - Specifies the maximum weight for edges in the graph. Ignored if the graph is to be unweighted.

OLDrandomDAcyclicGraph

public void OLDrandomDAcyclicGraph(int node_c,
                                   int edge_c,
                                   boolean self_loop,
                                   boolean weights,
                                   double min_weight,
                                   double max_weight)

randomGAIGSGraph

public void randomGAIGSGraph(int numNodes,
                             int numEdges,
                             double min_weight,
                             double max_weight)

Clears this VisualGraph and produces a randomly generated sparsely connected graph suitable for many algorithm visualizations.

Parameters:

numNodes - Indicates the number of nodes to appear in the graph. Note that, unlike the other graph generation methods, a value of 0 does not indicate that a random number of nodes should be added.

numEdges - Indicates the number of edges to appear in the graph. This number may be changed to produce a connected graph. Note that, unlike the other graph generation methods, a value of -1 does not indicate that a random number of edges should be added.

min_weight - Specifies the minimum weight for edges in the graph.

max_weight - Specifies the maximum weight for edges in the graph.

randomHeuristicGraph

public int[] randomHeuristicGraph(int node_c,
                                  int edge_c)

Clears this VisualGraph and produces a randomly generated sparsely connected graph with heuristic values for the nodes. This method uses the A* Algorithm to test for the shortest path through this graph that has the greatest number of nodes. It then initializes the heuristic values for the nodes based on their Euclidean distances from the goal node for this path and returns the start and goal nodes for this path.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated.

Returns:

Gives a two-element array containing the start and goal nodes for the shortest path through the graph that has the greatest number of nodes. The value in index 0 is the start node for this path, and the value in index 1 is the goal node for this path to which the heuristic values have been initialized. These values are both ints that give the nodes' indices in my_nodeset.

randomAStarSearchGraph

public int[] randomAStarSearchGraph(int node_c,
                                    int edge_c)

Clears this VisualGraph and produces a randomly generated sparsely connected heuristic graph that demonstrates the unique feature of the A* Algorithm, namely the reopening of a closed node when a poor heuristic value caused the node to be closed with a greater-than-optimal cost. It then returns the start and goal nodes for this path.

Parameters:

node_c - Indicates the number of nodes to appear in the graph. A value of 0 means that a random number of nodes should be generated.

edge_c - Indicates the number of edges to appear in the graph. A value of -1 means that a random number of edges should be generated.

Returns:

Gives a two-element array containing the start and goal nodes for the shortest path through the graph that has the greatest number of nodes and demonstrates the unique feature of the A* Algorithm. The value in index 0 is the start node for this path, and the value in index 1 is the goal node for this path to which the heuristic values have been initialized. These values are both ints that give the nodes' indices in my_nodeset.

randomNode

public char randomNode()

Returns the name/label for a randomly selected node. The node chosen may be activated or unactivated.

Returns:

Yields the char name/label value for a randomly chosen node.

randomActiveNode

public char randomActiveNode()

Returns the name/label for a randomly selected activated node.

Returns:

Gives the char name/label value for a randomly chosen activated node. If there are currently no activated nodes, the value returned is the invalid char '~'.

randomNewNode

public char randomNewNode()

Returns the name/label for a randomly selected unactivated node.

Returns:

Gives the char name/label value for a randomly chosen unactivated node. If there are currently no unactivated nodes, the value returned is the invalid char '~'.

translateCharIndex

public int translateCharIndex(char c)

Returns the my_nodeset index that corresponds to the specified name/label value.

Parameters:

c - Indicates the name/label of the node for which the index is to be found.

Returns:

Yields the index of the specified node in my_nodeset. If the value passed to c is not a valid node name/label, this method returns -1.

translateIndexChar

public char translateIndexChar(int index)

Returns the name/label of the node at the specified index in my_nodeset.

Parameters:

index - Indicates the index in my_nodeset for which the name/label is to be found.

Returns:

Gives the name/label of the node at index in my_nodeset. If the value passed to index is invalid, this method returns '~'.

getNextNode

public char getNextNode()

Gives the char name/label for the next unactivated node.

Returns:

Yields the char value that serves as the unique name/label for the next unactivated node in this VisualGraph. Returns '~' if all available nodes are already activated.

gaigsChangeHexNodeColors

public void gaigsChangeHexNodeColors(java.lang.String search,
                                     java.lang.String replace)

Changes any nodes in this VisualGraph with the color indicated by search to have the color specified by replace.

Parameters:

search - Gives the color that should be changed to the new color. This value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

replace - Indicates the new color for the nodes that should be changed. This value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

gaigsChangeHexEdgeColors

public void gaigsChangeHexEdgeColors(java.lang.String search,
                                     java.lang.String replace)

Changes any edges in this VisualGraph with the color indicated by search to have the color specified by replace.

Parameters:

search - Gives the color that should be changed to the new color. This value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

replace - Indicates the new color for the edges that should be changed. This value must be a six-digit hexadecimal String of the form #123456. The symbol '#' must be included.

gaigsDistPoints

public double gaigsDistPoints(double x1,
                              double y1,
                              double x2,
                              double y2)

Returns the Euclidean distance between two points specified by their Cartesian coordinates.

Parameters:

x1 - Indicates the x-coordinate of the first point for which the Euclidean distance is to be found.

y1 - Specifies the y-coordinate of the first point for which the Euclidean distance is to be found.

x2 - Indicates the x-coordinate of the second point for which the Euclidean distance is to be found.

y2 - Specifies the y-coordinate of the second point for which the Euclidean distance is to be found.

initializeHValues

public void initializeHValues(int g)

Initializes the heuristic values of the nodes based on their Euclidean distances from the specified goal node.

Parameters:

g - Indicates the goal node for which the heuristic values should be initialized. This value is the goal node's index in my_nodeset.

initializeEdgeWeights

public void initializeEdgeWeights()

Initializes the edge weights based on the the Euclidean distances between their start and goal nodes. The weights are partially based on Euclidean distance and partly determined randomly.

Note that this method sets edge weights bidirectionally and is not intended for directed graphs.

resetNodes

public void resetNodes()

Reinitializes the nodes after running a test algorithm for layout purposes. This entails setting each node to be the color #FFFFFF (white), making each node's closed data member false, setting each node's cost to be a large number, and reseting each node's pred to the default value. Heuristic values are left unchanged because it is assumed that any changes to heuristic values are meant to bring about the desired operation when the actual script-producing program is run.

testAStar

public java.lang.String testAStar(char start,
                                  char goal)

Runs the A* Algorithm on this VisualGraph to monitor if the algorithm will have to reopen a closed node to find the shortest path to the specified goal node from the indicated start node. After calling this method, the nodes in the graph will contain the information from running the search. Therefore, resetNodes() should be called before running the script-producing program to produce the GAIGS animation so that the script-producing program will execute correctly.

Parameters:

start - Indicates the start node for this A* Search by giving its name/label.

goal - Specifies the goal node for this A* Search by giving its name/label.

Returns:

If a node was reopened, gives the shortest path from the start node to the goal node in the form "ABC" (the path from A to B to C). If a node was not reopened to find the shortest path, returns the empty String, "".

runAStar

public java.lang.String runAStar(char start,
                                 char goal)

Runs the A* Algorithm on this VisualGraph to find the shortest path to the specified goal node from the indicated start node. After calling this method, the nodes in the graph will contain the information from running the search. Therefore, resetNodes() should be called before running the script-producing program to produce the GAIGS animation so that the script-producing program will execute correctly.

Parameters:

start - Indicates the start node for this A* Search by giving its name/label.

goal - Specifies the goal node for this A* Search by giving its name/label.

Returns:

Gives the shortest path from the start node to the goal node in the form "ABC" (the path from A to B to C).

writeGAIGSGraph

public void writeGAIGSGraph(java.io.PrintWriter out,
                            java.lang.String title)

Writes this VisualGraph to the given PrintWriter output stream using the original GAIGS specifications for Graphs/Networks. If the graph is weighted, a Network structure will be produced; otherwise, a Graph structure will be printed to the indicated output stream. This method also takes the slide's title so that it can be inserted into the appropriate place in the snapshot.

Parameters:

out - Specifies the output stream to which the Graph/Network snapshot is to be written.

title - Indicates the title for the Graph/Network snapshot that is written to this output stream.

writeGAIGSXMLGraph

public void writeGAIGSXMLGraph(java.io.PrintWriter out)

Writes this VisualGraph to the given PrintWriter output stream using the new GAIGS XML format. This method only writes the <graph> portion of a snapshot so that other structures can accompany the graph in the snapshot.

Parameters:

out - Indicates the output stream to which the graph should be written.

readGAIGSXMLGraph

public void readGAIGSXMLGraph(java.lang.String filename)
                       throws java.io.FileNotFoundException,
                              java.io.IOException

Reads in a showfile and extracts the information contained within the first set of <graph> tags to initialize this VisualGraph. Note that this method is meant to read in a graph that was written to the showfile using writeGAIGSXMLGraph and may not work for graph showfiles produced in another manner because it assumes that all attributes will be explicitly listed.

Parameters:

filename - Indicates the file from which the graph should be read.

Throws:

java.io.FileNotFoundException - Indicates that the file specified by filename could not be found when trying to open it.

java.io.IOException - Indicates that the format of the <graph> specification was not as expected. This method is only assured to work with showfiles produced using writeGAIGSXMLGraph.

readStartGoal

public int[] readStartGoal(java.lang.String filename)
                    throws java.io.FileNotFoundException,
                           java.io.IOException,
                           java.util.NoSuchElementException

Reads in a showfile in order to extract the start and goal nodes from the first <title> element in the showfile. This method was intended to accompany the readGAIGSXMLGraph method for the AStarSearch, BestFirstSearch, and LeastCostSearch programs. It will only be useful to find the start and goal nodes in a graph-search showfile if the first title in the show is of the form: ". . . Start Node {start node's name} . . . Goal Node {goal node's name} . . .".

Parameters:

filename - Indicates the file from which the title should be read.

Returns:

Returns the indices in my_nodeset of the start and goal nodes in a two-element array. The first element is the start node's index, and the second element is the goal node's index.

Throws:

java.io.FileNotFoundException - Indicates that the file specified by filename could not be found when trying to open it.

java.io.IOException - Indicates that the first title was not in the correct format for this method to extract the start and goal nodes.

java.util.NoSuchElementException - Indicates that the first title was not in the correct format for this method to extract the start and goal nodes.