All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class rpi.goldsd.graph.Path

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

public class Path

extends Object

implements Cloneable, Drawable

Version:

2.0, 4/19/98

Author:

David Goldschmidt

See Also:

GraphBase

path

A Vector representing this path.

Path()

Constructs an empty path.

Path(int)

Constructs an empty path with the initial path capacity.

Path(Path)

Constructs a path by copying another path.

Path(Vertex)

Constructs a path with a given start vertex.

add(Edge)

Adds an edge and its corresponding destination vertex to the end of this path.

add(Vertex)

Adds an edge and its corresponding destination vertex to the end of this path.

addStartVertex(Vertex)

Initializes this path and adds the starting vertex to this path.

backtrack()

Removes the last vertex and edge from this path.

clone()

Clones this path.

concat(Path)

Concatenates the given path with this path by adding all elements of the given path to the end of this path.

contains(Edge)

Tests if a given edge exists in this path.

contains(Vertex)

Tests if a given vertex exists in this path.

edges()

Returns an enumeration of the edges in this path.

elements()

Returns an enumeration of the vertices and edges in this path.

firstVertex()

Returns a reference to the first vertex in this path.

graph()

Returns a reference to the graph associated with this path.

insertAfter(Path, Vertex)

Inserts a given path into this path after the first occurrence of the given vertex in this path.

isCycle()

Tests if this path is a cycle.

isReachable(Vertex, Vertex)

Tests if the given endVertex is reachable from the startVertex in this path.

lastVertex()

Returns a reference to the last vertex in this path.

length()

Returns the number of edges in this path.

name()

Returns the name of the graph this path is associated with.

occurrences(Edge)

Returns the number of occurrences of a given edge in this path.

occurrences(Vertex)

Returns the number of occurrences of a given vertex in this path.

pathCopyHelper(Path, Path)

This protected static method performs a deep copy of all edges and vertices in the path source to the path target.

toString()

Returns a String representation of this path.

vertices()

Returns an enumeration of the vertices of this path.

weight()

Returns the weight of this path, which is simply the sum of all weighted edges of this path.

 protected Vector path

A Vector representing this path. This Vector contains an alternating series of vertices and edges. Note that this Vector must begin and end with a Vertex object, thus the size() of the Vector will always be odd (unless it is zero).

 public Path(int capacity)

Constructs an empty path with the initial path capacity. If used, this value should indicate the number of vertices and edges making up this path, including the start and end vertices.

Parameters:

capacity - the initial capacity for the vector used to represent the path of alternating vertices and edges.

 public Path(Vertex startVertex) throws IllegalArgumentException

Constructs a path with a given start vertex.

Parameters:

startVertex - the initial start vertex of this path.

Throws: IllegalArgumentException

if the start vertex argument is not in a graph.

 public Path(Path P)

Constructs a path by copying another path.

Parameters:

P - the path to be copied.

 public Path()

Constructs an empty path.

 public Object clone()

Clones this path.

Returns:

a new path that is a clone of this path.

Overrides:

clone in class Object

 protected static final void pathCopyHelper(Path target,
                                            Path source)

This protected static method performs a deep copy of all edges and vertices in the path source to the path target. Note that the target path is assumed to be constructed.

Parameters:

target - the target path object (should be an empty path).

source - the source path object.

 public boolean contains(Edge E)

Tests if a given edge exists in this path.

Parameters:

E - the edge to test.

Returns:

true if the given edge E is in this path; false otherwise.

 public boolean contains(Vertex V)

Tests if a given vertex exists in this path.

Parameters:

V - the vertex to test.

Returns:

true if the given vertex V is in this path; false otherwise.

 public Enumeration edges()

Returns an enumeration of the edges in this path.

Returns:

an enumeration of the edges in this path.

 public Enumeration elements()

Returns an enumeration of the vertices and edges in this path. Note that the nextElement() method of the enumeration returns alternating vertex and edge objects.

Returns:

an enumeration of the vertices and edges in this path.

 public Vertex firstVertex()

Returns a reference to the first vertex in this path.

Returns:

a reference to the first vertex in this path.

 public GraphBase graph()

Returns a reference to the graph associated with this path.

Returns:

a reference to the graph associated with this path; or null if this path is not associated with a graph (which implies that the path is empty).

 public boolean isCycle()

Tests if this path is a cycle.

Returns:

true if the first and last vertices are the same; false otherwise.

 public boolean isReachable(Vertex startVertex,
                            Vertex endVertex)

Tests if the given endVertex is reachable from the startVertex in this path. Note that if this path is a cycle, then if the two given vertices exist in this path, then this method returns true. Also note that if duplicate vertices appear in the path, then the first occurrence of the startVertex is used as a starting place.

Parameters:

startVertex - the vertex to start the traversal from.

endVertex - the destination vertex.

Returns:

true if endVertex is reachable from startVertex; false otherwise.

 public Vertex lastVertex()

Returns a reference to the last vertex in this path.

Returns:

a reference to the last vertex in this path.

 public int length()

Returns the number of edges in this path.

Returns:

the number of edges in this path.

 public String name()

Returns the name of the graph this path is associated with.

Returns:

the name of the graph this path is associated with.

 public int occurrences(Edge E)

Returns the number of occurrences of a given edge in this path.

Returns:

the number of occurrences of the given edge E in this path.

 public int occurrences(Vertex V)

Returns the number of occurrences of a given vertex in this path.

Returns:

the number of occurrences of the given vertex V in this path.

 public String toString()

Returns a String representation of this path. The String begins with "Path: " and then makes use of the toString() method of each of the vertices of this path, separating each vertex with "->" to represent an edge.

Returns:

a String representation of this path.

Overrides:

toString in class Object

 public Enumeration vertices()

Returns an enumeration of the vertices of this path.

Returns:

an enumeration of the vertices of this path.

 public double weight()

Returns the weight of this path, which is simply the sum of all weighted edges of this path.

Returns:

the weight of this path.

 public void add(Edge E) throws IllegalArgumentException

Adds an edge and its corresponding destination vertex to the end of this path. The edge must be associated with the last vertex of this path. Note that this method actually adds two references to the end of this path: first the given edge E, and second the destination vertex found by traversing E from the last vertex of this path.

Parameters:

E - the edge to be added.

Throws: IllegalArgumentException

if the edge is not associated with the last vertex of this path.

 public void add(Vertex V) throws IllegalArgumentException

Adds an edge and its corresponding destination vertex to the end of this path. The edge must be associated with the last vertex of this path. Note that this method actually adds two references to the end of this path: first the given edge, and second the given destination vertex.

Parameters:

V - the vertex to be added.

Throws: IllegalArgumentException

if there is no edge connecting the last vertex of this path and the given vertex argument.

 public void addStartVertex(Vertex V) throws IllegalArgumentException

Initializes this path and adds the starting vertex to this path. Note that this method removes all elements from the existing path, if any.

Parameters:

V - the starting vertex of this path.

Throws: IllegalArgumentException

if the Vertex argument is not in a graph object.

 public Edge backtrack()

Removes the last vertex and edge from this path.

Returns:

the edge removed from this path; or null if the path contains no edges.

 public void concat(Path P) throws IllegalArgumentException

Concatenates the given path with this path by adding all elements of the given path to the end of this path. Note that the last vertex of this path must be the same as the first vertex of the given path P.

Parameters:

P - the path to be added to this path.

Throws: IllegalArgumentException

if the last vertex of this path is not the first vertex of the given Path object.

 public void insertAfter(Path P,
                         Vertex V) throws IllegalArgumentException, VertexNotFoundException

Inserts a given path into this path after the first occurrence of the given vertex in this path. The vertex V must exist in this path and be the first and last vertex in the given path P (i.e. the given path P must be a cycle).

Parameters:

P - the path to be inserted.

V - the vertex after which the path P is to be inserted.

Throws: IllegalArgumentException

if the given Path object is not a cycle, or if the given Vertex object does not begin the given Path object.

Throws: VertexNotFoundException

if the given Vertex object is not in this path.

All Packages  Class Hierarchy  This Package  Previous  Next  Index