edu.colorado.graphs
Class Graph

java.lang.Object
  edu.colorado.graphs.Graph

All Implemented Interfaces:

java.lang.Cloneable

public class Graph
extends java.lang.Object
implements java.lang.Cloneable

A Graph is a labeled graph with a fixed number of vertices.

Java Source Code for this class:

http://www.cs.colorado.edu/~main/EDU/colorado/collections/Graph.java

Constructor Summary

Graph(int n)
Initialize a Graph with n vertices, no edges, and null labels.

Method Summary

void	addEdge(int source, int target) Add a new edge to this Graph.
java.lang.Object	clone() Generate a copy of this Graph.
static void	depthFirstPrint(Graph g, int start) Static method to print the labels of a graph with a depth-first search.
static void	depthFirstRecurse(Graph g, int v, boolean[] marked) Recursive method to carry out the work of depthFirstPrint.
java.lang.Object	getLabel(int vertex) Accessor method to get the label of a vertex of this Graph.
boolean	isEdge(int source, int target) Accessor method to determine whether this Graph contains a specified edge.
int[]	neighbors(int vertex) Accessor method to obtain a list of neighbors of a specified vertex of this Graph
void	removeEdge(int source, int target) Remove an edge from this Graph.
void	setLabel(int vertex, java.lang.Object newLabel) Modification method to change the label of a vertex of this Graph.
int	size() Determine the number of vertices in this Graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

Graph

public Graph(int n)

Initialize a Graph with n vertices, no edges, and null labels.

Parameters:

n - the number of vertices for this Graph

Precondition:

n is nonnegative.

Postcondition:

This Graph has n vertices, numbered 0 to n-1. It has no edges and all vertex labels are null.

Throws:

java.lang.OutOfMemoryError - Indicates insufficient memory for the specified number of nodes.

java.lang.NegativeArraySizeException - Indicates that n is negative.

Method Detail

addEdge

public void addEdge(int source,
                    int target)

Add a new edge to this Graph.

Parameters:

source - the vertex number of the source of the new edge

target - the vertex number of the target of the new edge

Precondition:

Both source and target are nonnegative and less than size().

Postcondition:

This Graph has all the edges that it originally had plus another edge from the specified source to the specified target. (If the edge was already present, then this Graph is unchanged.)

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the source or target was not a valid vertex number.

clone

public java.lang.Object clone()

Generate a copy of this Graph.

Overrides:

clone in class java.lang.Object

Parameters:

- - none

Returns:

The return value is a copy of this Graph. Subsequent changes to the copy will not affect the original, nor vice versa. Note that the return value must be type cast to a Graph before it can be used.

Throws:

java.lang.OutOfMemoryError - Indicates insufficient memory for creating the clone.

depthFirstPrint

public static void depthFirstPrint(Graph g,
                                   int start)

Static method to print the labels of a graph with a depth-first search.

Parameters:

g - a nonnull Graph

start - a vertex number from the Graph g

Precondition:

start is nonnegative and less than g.size().

Postcondition:

A depth-first search of g has been conducted, starting at the specified start vertex. Each vertex visited has its label printed using System.out.println. Note that vertices that are not connected to the start will not be visited.

Throws:

java.lang.NullPointerException - Indicates that g is null.

java.lang.ArrayIndexOutOfBoundsException - Indicates that the vertex was not a valid vertex number.

java.lang.OutOfMemoryError - Indicates that there is insufficient memory for an array of boolean values used by this method.

depthFirstRecurse

public static void depthFirstRecurse(Graph g,
                                     int v,
                                     boolean[] marked)

Recursive method to carry out the work of depthFirstPrint.

Parameters:

g - a nonnull Graph

v - a vertex number from the Graph g

marked - an array to indicate which vertices of g have already been visited

Precondition:

v is nonnegative and less than g.size(). marked.length is equal to g.size(); for each vertex x of g, marked[x] is true if x has already been visited by this search; otherwise marked[x] is false. The vertex v is an unmarked vertex that the search has just arrived at.

Postcondition:

The depth-first search of g has been continued through vertex v and beyond to all vertices that can be reached from v via a path of unmarked vertices. Each vertex visited has its label printed using System.out.println.

Throws:

java.lang.NullPointerException - Indicates that g is null.

java.lang.ArrayIndexOutOfBoundsException - Indicates that the vertex was not a valid vertex number, or marked was the wrong size.

getLabel

public java.lang.Object getLabel(int vertex)

Accessor method to get the label of a vertex of this Graph.

Parameters:

vertex - a vertex number

Precondition:

vertex is nonnegative and less than size().

Returns:

the label of the specified vertex in this Graph

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the vertex was not a valid vertex number.

isEdge

public boolean isEdge(int source,
                      int target)

Accessor method to determine whether this Graph contains a specified edge.

Parameters:

source - the vertex number of the source of the specified edge

target - the vertex number of the target of the specified edge

Precondition:

Both source and target are nonnegative and less than size().

Returns:

The return value is true if this Graph has an edge from the specified source to the specified target. Otherwise the return value is false.

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the source or target was not a valid vertex number.

neighbors

public int[] neighbors(int vertex)

Accessor method to obtain a list of neighbors of a specified vertex of this Graph

Parameters:

vertex - a vertex number

target - a vertex number

Precondition:

Both source and target are nonnegative and less than size().

Precondition:

vertex is nonnegative and less than size().

Returns:

The return value is an array that contains all the vertex numbers of vertices that are targets for edges with a source at the specified vertex.

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the source or target was not a valid vertex number.

removeEdge

public void removeEdge(int source,
                       int target)

Remove an edge from this Graph.

Parameters:

source - the vertex number of the source of the removed edge

target - the vertex number of the target of the removed edge

Precondition:

Both source and target are nonnegative and less than size().

Postcondition:

This Graph has all the edges that it originally had minus the edge from the specified source to the specified target. (If the edge was not present, then this Graph is unchanged.)

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the source or target was not a valid vertex number.

setLabel

public void setLabel(int vertex,
                     java.lang.Object newLabel)

Modification method to change the label of a vertex of this Graph.

Parameters:

vertex - a vertex number

newLabel - a new label (which may be null)

Precondition:

vertex is nonnegative and less than size().

Postcondition:

The label of the specified vertex in this Graph has been changed to the newLabel.

Throws:

java.lang.ArrayIndexOutOfBoundsException - Indicates that the vertex was not a valid vertex number.

size

public int size()

Determine the number of vertices in this Graph.

Parameters:

- - none

Returns:

the number of vertices in this Graph