structure
Class GraphMatrix

java.lang.Object
  |
  +--structure.AbstractStructure
        |
        +--structure.GraphMatrix

All Implemented Interfaces:

Graph, Structure

Direct Known Subclasses:

GraphMatrixDirected, GraphMatrixUndirected

public abstract class GraphMatrix

extends AbstractStructure

implements Graph

Implementation of graph using adjacency matrices. User must commit to maximum size of graph (in vertices); it may be smaller. Edges are stored in matrix. Not suitable for large graphs. Class is abstract: you must use GraphMatrixDirected or GraphMatrixUndirected to construct particular instances of graphs. Typical usage:

     Graph g = new GraphMatrixUndirected();
     g.add("harry");
     g.add("sally");
     g.addEdge("harry","sally","unfriendly");
     ...
 

See Also:

GraphMatrixDirected, GraphMatrixUndirected, GraphList

Field Summary

protected Edge[][]	data The edge data.
protected Map	dict Translation between vertex labels and vertex structures.
protected boolean	directed Whether or not graph is directed.
protected List	freeList List of free vertex indices within graph.
protected int	size Number of vertices in graph.

Constructor Summary

protected

GraphMatrix(int size, boolean dir) Constructor of directed/undirected GraphMatrix.

Method Summary

void	add(Object label) Add a vertex to the graph.
abstract void	addEdge(Object v1, Object v2, Object label) Add an edge between two vertices within the graph.
void	clear() Remove all vertices (and thus, edges) of the graph.
boolean	contains(Object label) Test for vertex membership.
boolean	containsEdge(Object vLabel1, Object vLabel2) Test for edge membership.
int	degree(Object label) Determine out degree of vertex.
abstract int	edgeCount() Determine the number of edges in graph.
abstract Iterator	edges() Construct an traversal over all edges.
Object	get(Object label) Get reference to actual label of vertex.
Edge	getEdge(Object label1, Object label2) Get reference to actual edge.
boolean	isDirected() Determine if graph is directed.
boolean	isEmpty() Determine if graph is empty.
boolean	isVisited(Object label) Return visited flag of vertex.
boolean	isVisitedEdge(Edge e) Return visited flag of edge.
Iterator	iterator() Construct vertex traversal.
Iterator	neighbors(Object label) Construct an adjacent vertex traversal.
Object	remove(Object label) Remove a vertex from the graph.
abstract Object	removeEdge(Object vLabel1, 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(Object label) Test and set visited flag of vertex.
boolean	visitEdge(Edge e) Test and set visited flag of edge.

Methods inherited from class structure.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure.Structure

elements, values

Field Detail

size

protected int size

Number of vertices in graph.

data

protected Edge[][] data

The edge data. Every edge appears on one (directed) or two (undirected) locations within graph.

dict

protected Map dict

Translation between vertex labels and vertex structures.

freeList

protected List freeList

List of free vertex indices within graph.

directed

protected boolean directed

Whether or not graph is directed.

Constructor Detail

GraphMatrix

protected GraphMatrix(int size,
                      boolean dir)

Constructor of directed/undirected GraphMatrix. Protected constructor.

Parameters:

size - Maximum size of graph.

dir - True if graph is to be directed.

Method Detail

add

public void add(Object label)

Add a vertex to the graph.

Specified by:

add in interface Graph

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

public abstract void addEdge(Object v1,
                             Object v2,
                             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.

Specified by:

addEdge in interface Graph

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

public Object remove(Object label)

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

Specified by:

remove in interface Graph

Parameters:

label - The label of the vertex within the graph.

Precondition:

label is non-null vertex label

Postcondition:

vertex with "equals" label is removed, if found

Returns:

The label associated with the vertex.

removeEdge

public abstract Object removeEdge(Object vLabel1,
                                  Object vLabel2)

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

Specified by:

removeEdge in interface Graph

Parameters:

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

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

Precondition:

vLabel1 and vLabel2 are labels of existing vertices

Postcondition:

edge is removed, its label is returned

Returns:

The label associated with the edge removed.

get

public Object get(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.

Specified by:

get in interface Graph

Parameters:

label - The label of the vertex sought.

Postcondition:

returns actual label of indicated vertex

Returns:

The actual label, or null if none is found.

getEdge

public Edge getEdge(Object label1,
                    Object label2)

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

Specified by:

getEdge in interface Graph

Parameters:

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

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

Postcondition:

returns actual edge between vertices

Returns:

The edge, if found, or null.

contains

public boolean contains(Object label)

Test for vertex membership.

Specified by:

contains in interface Graph

Overrides:

contains in class AbstractStructure

Parameters:

label - The label of the vertex sought.

Postcondition:

returns true iff vertex with "equals" label exists

Returns:

True iff vertex with matching label is found.

containsEdge

public boolean containsEdge(Object vLabel1,
                            Object vLabel2)

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

Specified by:

containsEdge in interface Graph

Parameters:

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

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

Postcondition:

returns true iff edge with "equals" label exists

Returns:

True iff the edge exists within the graph.

visit

public boolean visit(Object label)

Test and set visited flag of vertex.

Specified by:

visit in interface Graph

Parameters:

label - Label of vertex to be visited.

Postcondition:

sets visited flag on vertex, returns previous value

Returns:

Previous value of visited flag on vertex.

visitEdge

public boolean visitEdge(Edge e)

Test and set visited flag of edge.

Specified by:

visitEdge in interface Graph

Parameters:

e - Edge object that is part of graph.

Precondition:

sets visited flag on edge; returns previous value

Returns:

Previous value of the Edge's visited flag.

isVisited

public boolean isVisited(Object label)

Return visited flag of vertex.

Specified by:

isVisited in interface Graph

Parameters:

label - Label of vertex.

Postcondition:

returns visited flag on labeled vertex

Returns:

True if vertex has been visited.

isVisitedEdge

public boolean isVisitedEdge(Edge e)

Return visited flag of edge.

Specified by:

isVisitedEdge in interface Graph

Parameters:

e - Edge of graph to be considered.

Postcondition:

returns visited flag on edge between vertices

Returns:

True if the edge has been visited.

reset

public void reset()

Clear visited flags of edges and vertices.

Specified by:

reset in interface Graph

Postcondition:

resets visited flags to false

size

public int size()

Determine number of vertices within graph.

Specified by:

size in interface Graph

Postcondition:

returns the number of vertices in graph

Returns:

The number of vertices within graph.

degree

public int degree(Object label)

Determine out degree of vertex.

Specified by:

degree in interface Graph

Parameters:

label - Label associated with vertex.

Precondition:

label labels an existing vertex

Postcondition:

returns the number of vertices adjacent to vertex

Returns:

The number of edges with this vertex as source.

edgeCount

public abstract int edgeCount()

Determine the number of edges in graph.

Specified by:

edgeCount in interface Graph

Postcondition:

returns the number of edges in graph

Returns:

Number of edges in graph.

iterator

public Iterator iterator()

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

Specified by:

iterator in interface Graph

Postcondition:

returns traversal across all vertices of graph

Returns:

AbstractIterator traversing vertices in graph.

neighbors

public Iterator neighbors(Object label)

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

Specified by:

neighbors in interface Graph

Parameters:

label - Label of the vertex.

Precondition:

label is label of vertex in graph

Postcondition:

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

Returns:

AbstractIterator traversing the adjacent vertices of labeled vertex.

edges

public abstract Iterator edges()

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

Specified by:

edges in interface Graph

Postcondition:

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

Returns:

AbstractIterator over edges.

clear

public void clear()

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

Specified by:

clear in interface Graph

Postcondition:

removes all vertices from graph

isEmpty

public boolean isEmpty()

Determine if graph is empty.

Specified by:

isEmpty in interface Graph

Overrides:

isEmpty in class AbstractStructure

Postcondition:

returns true if graph contains no vertices

Returns:

True iff there are no vertices in graph.

isDirected

public boolean isDirected()

Determine if graph is directed.

Specified by:

isDirected in interface Graph

Postcondition:

returns true if edges of graph are directed

Returns:

True iff the graph is directed.