structure
Interface Graph

All Superinterfaces:

Structure

All Known Implementing Classes:

GraphList, GraphListDirected, GraphListUndirected, GraphMatrix, GraphMatrixDirected, GraphMatrixUndirected

public interface Graph
extends Structure

The interface describing all Graph objects. Graphs are collections of vertices connected by a set of edges. Edges may or may not be directed. Portions of the graph may be marked visited to support iterative algorithms. Iteration is provided over vertices, edges, and vertices adjacent to a particular vertex

See Also:

GraphList, GraphMatrix

Method Summary

void	add(java.lang.Object label) Add a vertex to the graph
void	addEdge(java.lang.Object vtx1, java.lang.Object vtx2, java.lang.Object label) Add an edge between two vertices within the graph.
void	clear() Remove all vertices (and thus, edges) of the graph.
boolean	contains(java.lang.Object label) Test for vertex membership.
boolean	containsEdge(java.lang.Object vLabel1, java.lang.Object vLabel2) Test for edge membership.
int	degree(java.lang.Object label) Determine out degree of vertex.
int	edgeCount() Determine the number of edges in graph.
java.util.Iterator	edges() Construct an iterator over all edges.
java.lang.Object	get(java.lang.Object label) Get reference to actual label of vertex.
Edge	getEdge(java.lang.Object label1, java.lang.Object label2) Get reference to actual edge.
boolean	isDirected() Determine if graph is directed.
boolean	isEmpty() Determine if graph is empty.
boolean	isVisited(java.lang.Object label) Return visited flag of vertex.
boolean	isVisitedEdge(Edge e) Return visited flag of edge.
java.util.Iterator	iterator() Construct vertex iterator.
java.util.Iterator	neighbors(java.lang.Object label) Construct an adjacent vertex iterator.
java.lang.Object	remove(java.lang.Object label) Remove a vertex from the graph.
java.lang.Object	removeEdge(java.lang.Object vLabel1, java.lang.Object vLabel2) Remove possible edge between vertices labeled vLabel1 and vLabel2.
void	reset() Clear visited flags of edges and vertices.
int	size() Determine number of vertices within graph.
boolean	visit(java.lang.Object label) Test and set visited flag of vertex
boolean	visitEdge(Edge e) Test and set visited flag of edge.

Methods inherited from interface structure.Structure

elements, values

Method Detail

add

void add(java.lang.Object label)

Add a vertex to the graph

Specified by:

add in interface Structure

Parameters:

label - Label of the vertex; should be non-null

Precondition:

label is a non-null label for vertex

Postcondition:

a vertex with label is added to graph if vertex with label is already in graph, no action

addEdge

void addEdge(java.lang.Object vtx1,
             java.lang.Object vtx2,
             java.lang.Object label)

Add an edge between two vertices within the graph. Edge is directed iff graph is directed. Duplicate edges are silently replaced. Labels on edges may be null.

Parameters:

vtx1 - First (or source, if directed) vertex.

vtx2 - Second (or destination, if directed) vertex.

label - Label associated with the edge.

Precondition:

vtx1 and vtx2 are labels of existing vertices

Postcondition:

an edge (possibly directed) is inserted between vtx1 and vtx2.

remove

java.lang.Object remove(java.lang.Object label)

Remove a vertex from the graph. Associated edges are also removed. Non-vertices are silently ignored.

Specified by:

remove in interface Structure

Parameters:

label - The label of the vertex within the graph.

Returns:

The label associated with the vertex.

Precondition:

label is non-null vertex label

Postcondition:

vertex with "equals" label is removed, if found

removeEdge

java.lang.Object removeEdge(java.lang.Object vLabel1,
                            java.lang.Object vLabel2)

Remove possible edge between vertices labeled vLabel1 and vLabel2. Directed edges consider vLabel1 to be the source.

Parameters:

vLabel1 - First (or source, if directed) vertex.

vLabel2 - Second (or destination, if directed) vertex.

Returns:

The label associated with the edge removed.

Precondition:

vLabel1 and vLabel2 are labels of existing vertices

Postcondition:

edge is removed, its label is returned

get

java.lang.Object get(java.lang.Object label)

Get reference to actual label of vertex. Vertex labels are matched using their equals method, which may or may not test for actual equivalence. Result remains part of graph.

Parameters:

label - The label of the vertex sought.

Returns:

The actual label, or null if none is found.

Postcondition:

returns actual label of indicated vertex

getEdge

Edge getEdge(java.lang.Object label1,
             java.lang.Object label2)

Get reference to actual edge. Edge is identified by the labels on associated vertices. If edge is directed, the label1 indicates source.

Parameters:

label1 - The first (or source, if directed) vertex.

label2 - The second (or destination, if directed) vertex.

Returns:

The edge, if found, or null.

Postcondition:

returns actual edge between vertices

contains

boolean contains(java.lang.Object label)

Test for vertex membership.

Specified by:

contains in interface Structure

Parameters:

label - The label of the vertex sought.

Returns:

True iff vertex with matching label is found.

Postcondition:

returns true iff vertex with "equals" label exists

containsEdge

boolean containsEdge(java.lang.Object vLabel1,
                     java.lang.Object vLabel2)

Test for edge membership. If edges are directed, vLabel1 indicates source.

Parameters:

vLabel1 - First (or source, if directed) vertex.

vLabel2 - Second (or destination, if directed) vertex.

Returns:

True iff the edge exists within the graph.

Postcondition:

returns true iff edge with "equals" label exists

visit

boolean visit(java.lang.Object label)

Test and set visited flag of vertex

Parameters:

label - Label of vertex to be visited.

Returns:

Previous value of visited flag on vertex.

Postcondition:

sets visited flag on vertex, returns previous value

visitEdge

boolean visitEdge(Edge e)

Test and set visited flag of edge.

Parameters:

e - Edge object that is part of graph.

Returns:

Previous value of the Edge's visited flag.

Precondition:

sets visited flag on edge; returns previous value

isVisited

boolean isVisited(java.lang.Object label)

Return visited flag of vertex.

Parameters:

label - Label of vertex.

Returns:

True if vertex has been visited.

Postcondition:

returns visited flag on labeled vertex

isVisitedEdge

boolean isVisitedEdge(Edge e)

Return visited flag of edge.

Parameters:

e - Edge of graph to be considered.

Returns:

True if the edge has been visited.

Postcondition:

returns visited flag on edge between vertices

reset

void reset()

Clear visited flags of edges and vertices.

Postcondition:

resets visited flags to false

size

int size()

Determine number of vertices within graph.

Specified by:

size in interface Structure

Returns:

The number of vertices within graph.

Postcondition:

returns the number of vertices in graph

degree

int degree(java.lang.Object label)

Determine out degree of vertex.

Parameters:

label - Label associated with vertex.

Returns:

The number of edges with this vertex as source.

Precondition:

label labels an existing vertex

Postcondition:

returns the number of vertices adjacent to vertex

edgeCount

int edgeCount()

Determine the number of edges in graph.

Returns:

Number of edges in graph.

Postcondition:

returns the number of edges in graph

iterator

java.util.Iterator iterator()

Construct vertex iterator. Vertices are not visited in any guaranteed order.

Specified by:

iterator in interface Structure

Returns:

Iterator traversing vertices in graph.

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Postcondition:

returns iterator across all vertices of graph

neighbors

java.util.Iterator neighbors(java.lang.Object label)

Construct an adjacent vertex iterator. Adjacent vertices (those on destination of edge, if directed) are considered, but not in any guaranteed order.

Parameters:

label - Label of the vertex.

Returns:

Iterator traversing the adjacent vertices of labeled vertex.

Precondition:

label is label of vertex in graph

Postcondition:

returns iterator over vertices adj. to vertex each edge beginning at label visited exactly once

edges

java.util.Iterator edges()

Construct an iterator over all edges. Every directed/undirected edge is considered exactly once. Order is not guaranteed.

Returns:

Iterator over edges.

Postcondition:

returns iterator across edges of graph iterator returns edges; each edge visited once

clear

void clear()

Remove all vertices (and thus, edges) of the graph.

Specified by:

clear in interface Structure

Postcondition:

removes all vertices from graph

isEmpty

boolean isEmpty()

Determine if graph is empty.

Specified by:

isEmpty in interface Structure

Returns:

True iff there are no vertices in graph.

Postcondition:

returns true if graph contains no vertices

isDirected

boolean isDirected()

Determine if graph is directed.

Returns:

True iff the graph is directed.

Postcondition:

returns true if edges of graph are directed