All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class rpi.goldsd.graph.Algorithms

java.lang.Object
   |
   +----rpi.goldsd.graph.Algorithms

public class Algorithms

extends Object

Version:

2.1, 4/20/98

Author:

David Goldschmidt

See Also:

GraphBase

FRINGE

Used by methods of the static Algorithms class to label a Vertex or Edge object as being a fringe vertex or edge.

IN_TREE_OR_PATH

Used by methods of the static Algorithms class to label a Vertex or Edge object as being part of a tree or path.

TRAVERSED

Used by methods of the static Algorithms class to label an Edge object as being traversed.

UNSEEN

Used by methods of the static Algorithms class to label a Vertex or Edge object as being unseen.

Algorithms()

breadthFirstTraversal(Graph)

Returns a breadth-first traversal tree for the given graph starting at an arbitrary vertex.

breadthFirstTraversal(Vertex)

Returns a breadth-first traversal tree for the graph starting from the given vertex.

cloneEdge(Vertex, Vertex, Edge)

Since the Edge class does not implement the Cloneable interface, the static cloneEdge() exists for copying both directed and undirected edges.

complement(GraphBase)

Returns a graph that is the complement of the given graph.

depthFirstTraversal(Graph)

Returns a depth-first traversal tree for the given graph starting at an arbitrary vertex.

depthFirstTraversal(Vertex)

Returns a depth-first traversal tree for the graph starting from the given vertex.

displayBicomponents(Graph)

After invoking the findBicomponents() method, this method simply displays the biconnected components of the given Graph object.

findBicomponents(Graph)

Finds the biconnected components of the given Graph object by using a depth-first traversal and the utility fields of the Vertex class.

findBicomponents(Graph, Algorithms. backtrackNode, Vertex)

Finds the biconnected components of the given Graph object by using a depth-first traversal and the utility fields of the Vertex class.

findEulerPath(Graph)

Attempts to find an Euler Path in a connected graph starting from an arbitrary vertex of the given graph.

findEulerPath(Vertex)

Attempts to find an Euler Path in a connected graph starting from a given vertex.

findLongestPath(Vertex, Vertex)

Using a simple greedy approach, this method attempts to approximate the longest path between two vertices.

findLongestPath2(Vertex, Vertex, int)

Using an algorithm involving stratified greed, this method attempts to approximate the longest path between two vertices.

findMaxWeightEdge(GraphBase)

The findMaxWeightEdge() method performs a linear search through the edges of the given graph to find the edge with the maximum weight.

findMinWeightEdge(GraphBase)

The findMinWeightEdge() method performs a linear search through the edges of the given graph to find the edge with the minimum weight.

findShortestPath(Vertex, Vertex)

The findShortestPath() method uses Dijkstra's Shortest Path algorithm as presented in Sara Baase's Computer Algorithms book (see reference [BAAS89]).

toGraphDraw(Drawable)

Returns a String that contains all edges of the given Drawable object.

toGraphDraw(Drawable, String)

Creates an HTML file that contains the edge-representation of the given Drawable object.

 public static final int IN_TREE_OR_PATH

Used by methods of the static Algorithms class to label a Vertex or Edge object as being part of a tree or path.

 public static final int FRINGE

Used by methods of the static Algorithms class to label a Vertex or Edge object as being a fringe vertex or edge.

 public static final int UNSEEN

Used by methods of the static Algorithms class to label a Vertex or Edge object as being unseen.

 public static final int TRAVERSED

Used by methods of the static Algorithms class to label an Edge object as being traversed.

 public Algorithms()

 public static final Tree breadthFirstTraversal(Vertex startVertex) throws IllegalArgumentException

Returns a breadth-first traversal tree for the graph starting from the given vertex. Note that the vertex must be associated with an existing graph.

Parameters:

startVertex - the vertex to start the breadth-first traversal from.

Returns:

a breadth-first traversal tree for the associated graph.

Throws: IllegalArgumentException

if the given vertex is not associated with any graph.

 public static final Tree breadthFirstTraversal(Graph G) throws IllegalArgumentException

Returns a breadth-first traversal tree for the given graph starting at an arbitrary vertex.

Parameters:

G - the graph to perform the breadth-first traversal on.

Returns:

a breadth-first traversal tree for the given graph.

Throws: IllegalArgumentException

if the given graph is empty (i.e. contains no vertices).

 public static final Edge cloneEdge(Vertex startVertex,
                                    Vertex endVertex,
                                    Edge originalEdge)

Since the Edge class does not implement the Cloneable interface, the static cloneEdge() exists for copying both directed and undirected edges.

Parameters:

startVertex - the first endpoint vertex of the new edge.

endVertex - the second endpoint vertex of the new edge.

originalEdge - the edge to copy.

Returns:

the new Edge or DirectedEdge object.

 public static final Graph complement(GraphBase H)

Returns a graph that is the complement of the given graph. The new graph contains a clone of all vertices of the given graph.

Parameters:

H - the given graph.

Returns:

a graph that is the complement of the given graph.

 public static final Tree depthFirstTraversal(Vertex startVertex)

Returns a depth-first traversal tree for the graph starting from the given vertex. Note that the vertex must be associated with an existing graph.

Parameters:

startVertex - the vertex to start the depth-first traversal from.

Returns:

a depth-first traversal tree for the associated graph.

 public static final Tree depthFirstTraversal(Graph G)

Returns a depth-first traversal tree for the given graph starting at an arbitrary vertex.

Parameters:

G - the graph to perform the depth-first traversal on.

Returns:

a depth-first traversal tree for the given graph.

Throws: IllegalArgumentException

if the given graph is empty (i.e. contains no vertices).

 public static final void displayBicomponents(Graph G)

After invoking the findBicomponents() method, this method simply displays the biconnected components of the given Graph object.

Parameters:

G - the graph in which the biconnected components are to be determined.

 public static final Stack findBicomponents(Graph G)

Finds the biconnected components of the given Graph object by using a depth-first traversal and the utility fields of the Vertex class.

Parameters:

G - the graph in which the biconnected components are to be determined

Returns:

a Stack representing the set of biconnected components.

 public static final Stack findBicomponents(Graph G,
                                            Algorithms. backtrackNode N,
                                            Vertex goal)

Finds the biconnected components of the given Graph object by using a depth-first traversal and the utility fields of the Vertex class. This method is used by the findLongestPath2() method and therefore contains two additional arguments: N and goal.

Parameters:

G - the graph in which the biconnected components are to be determined

N - the backtrackNode representing the set of vertices and edges in the backtrack tree.

goal - the goal Vertex object.

Returns:

a Stack representing the set of biconnected components.

 public static final Path findEulerPath(Graph G) throws IllegalArgumentException

Attempts to find an Euler Path in a connected graph starting from an arbitrary vertex of the given graph.

Parameters:

G - the given graph.

Returns:

a Path object that traverses all edges of the given graph exactly once.

Throws: IllegalArgumentException

if the given graph is empty (i.e. contains no vertices).

 public static final Path findEulerPath(Vertex startVertex) throws IllegalArgumentException, PathDoesNotExistException

Attempts to find an Euler Path in a connected graph starting from a given vertex.

Parameters:

startVertex - the Vertex object at which to begin the Euler Path.

Returns:

a Path object that traverses all edges of the given graph exactly once.

Throws: IllegalArgumentException

if the graph associated with the given Vertex object is not a Graph object, or if the graph is not connected.

 public static final Path findLongestPath(Vertex startVertex,
                                          Vertex endVertex) throws IllegalArgumentException, PathDoesNotExistException

Using a simple greedy approach, this method attempts to approximate the longest path between two vertices.

Parameters:

startVertex - the source vertex.

endVertex - the target or goal vertex.

Returns:

a Path object representing the longest path.

Throws: IllegalArgumentException

if the Vertex arguments are in different graphs, or if the graph is not positively weighted, or if the Vertex arguments refer to the same vertex.

Throws: PathDoesNotExistException

if this method fails to find a valid path between the startVertex and endVertex vertices.

 public static final Path findLongestPath2(Vertex startVertex,
                                           Vertex endVertex,
                                           int width) throws IllegalArgumentException, PathDoesNotExistException

Using an algorithm involving stratified greed, this method attempts to approximate the longest path between two vertices. This method typically out-performs the original findLongestPath() method in terms of the path produced.

Parameters:

startVertex - the source vertex.

endVertex - the target or goal vertex.

width - the width is defined as the number of candidate vertices and edges to maintain at each stratum.

Returns:

a Path object representing the longest path.

Throws: IllegalArgumentException

if the Vertex arguments are in different graphs, or if the graph is not positively weighted, or if the Vertex arguments refer to the same vertex, or if the width argument is less than 1.

Throws: PathDoesNotExistException

if this method fails to find a valid path between the startVertex and endVertex vertices.

 public static final Edge findMaxWeightEdge(GraphBase G) throws IllegalArgumentException

The findMaxWeightEdge() method performs a linear search through the edges of the given graph to find the edge with the maximum weight.

Parameters:

G - the graph to be examined.

Returns:

the Edge object with the maximum weight.

Throws: IllegalArgumentException

if the given graph contains no edges or is not a weighted graph.

 public static final Edge findMinWeightEdge(GraphBase G) throws IllegalArgumentException

The findMinWeightEdge() method performs a linear search through the edges of the given graph to find the edge with the minimum weight.

Parameters:

G - the graph to be examined.

Returns:

the Edge object with the minimum weight.

Throws: IllegalArgumentException

if the given graph contains no edges or is not a weighted graph.

 public static final Path findShortestPath(Vertex startVertex,
                                           Vertex endVertex) throws IllegalArgumentException, PathDoesNotExistException

The findShortestPath() method uses Dijkstra's Shortest Path algorithm as presented in Sara Baase's Computer Algorithms book (see reference [BAAS89]).

Currently, graphs with edges of negative or zero weights are not accepted (an IllegalArgumentException is thrown).

Parameters:

startVertex - the source vertex.

endVertex - the target or goal vertex.

Returns:

a Path object representing the shortest path.

Throws: IllegalArgumentException

if the Vertex arguments are in different graphs, or if the graph is not positively weighted.

Throws: PathDoesNotExistException

if this method fails to find a valid path between the startVertex and endVertex vertices.

 public static final String toGraphDraw(Drawable G)

Returns a String that contains all edges of the given Drawable object. The format of the generated string is "v1-v2,v2-v3,v3-v4" and so on. Note that there are no spaces between the commas and that the edges are represented by the '-' character. Also note that the resulting String represents directed edges, therefore undirected edges are represented as pairs of edges: "v1-v2,v2-v1".

Also note that the Graph Draw applet does not support edges that are self-loops. Using the notation "v5-v5" does not indicate a loop; instead, if a vertex does not contain any edges, including such a String will produce a lone vertex in the Graph Draw applet.

Parameters:

G - the Drawable graph or other graph-related object.

Returns:

a String that contains all edges of the given Drawable object.

 public static final void toGraphDraw(Drawable G,
                                      String filename)

Creates an HTML file that contains the edge-representation of the given Drawable object. The HTML file, when loaded into a browser, loads the Graph Draw applet and presents the edges of the given Drawable object.

Parameters:

G - the Drawable graph or other graph-related object.

filename - the name of the HTML file to be created.

All Packages  Class Hierarchy  This Package  Previous  Next  Index