Graph (Graph)

Class Graph<E>

java.lang.Object
  Graph<E>

Direct Known Subclasses:: CS3Graph

public abstract class Graph<E>
extends Object
extends Object

Abstract class for directed and undirected graphs.

Graphs are comprised of vertices and edges.

Each vertex is identified by its label, which is a reference to an object of the element type E. Every vertex label must be unique.

In undirected graphs, all edges are undirected. In directed graphs, all edges are directed. At most one edge may exist with the same start and end vertices.

Every edge has a weight associated with it. If no weight is specified, the edge has "unit" weight (weight equal to 1).

Implementation classes that extend Graph need to provide a boolean-parameter constructor and a copy constructor. The boolean-parameter constructor accepts a boolean parameter that indicates if the graph is directed (true) or undirected (false); for example, public ConcreteGraph(boolean directed). The copy constructor accepts a Graph parameter and creates a copy of the graph, utilizing the same label references.

Version:: 12 March 2006
Author:: Dr. Jody Paul

Constructor Summary
`Graph()`

Method Summary
`abstract void`	`addEdge(E startVertex, E endVertex)` Add an edge to this graph.
`abstract void`	`addEdge(E startVertex, E endVertex, int weight)` Add a weighted edge to this graph.
`abstract void`	`addVertex(E vertex)` Add a vertex to this graph.
`abstract List<E>`	`breadthFirst(E startVertex)` Perform a breadth first traversal of the graph, starting at `startVertex`.
`abstract void`	`clear()` Remove all vertices and edges from this graph.
`abstract int`	`costOfPath(List<E> path)` Determine the cost of a path (the sum of the weights of the edges).
`abstract List<E>`	`depthFirst(E startVertex)` Perform a depth first traversal of the graph, starting at `startVertex`.
`abstract boolean`	`equals(Graph<E> graph)` Determine if this graph is equivalent to another graph.
`abstract List<E>`	`getNeighbors(E vertex)` Returns a list of the vertices that are adjacent to a given vertex.
`abstract int`	`getNumberOfEdges()` Returns the number of edges in this graph.
`abstract int`	`getNumberOfVertices()` Returns the number of vertices in this graph.
`abstract List<E>`	`getVertices()` Returns a list of the vertices in this graph.
`abstract int`	`getWeightOfEdge(E startVertex, E endVertex)` Returns the weight associated with an edge in this graph.
`abstract int`	`inDegree(E vertex)` Returns the number of edges that have the given vertex as a destination.
`abstract boolean`	`isDirected()` Returns whether or not this graph is directed.
`abstract Graph<E>`	`minimumSpanningTree()` Determine a minimum spanning tree of this graph.
`abstract int`	`outDegree(E vertex)` Returns the number of edges that have the given vertex as a source.
`abstract void`	`removeEdge(E startVertex, E endVertex)` Remove an edge from this graph.
`abstract void`	`removeVertex(E vertex)` Remove a vertex and all incident edges from this graph.
`abstract List<E>`	`topologicalSort()` Perform a topological sort of this graph.
`abstract String`	`toStringAdjacencyMatrix()` The graph represented as an adjacency matrix rendered as a `String`.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

Graph

public Graph()

Method Detail

addEdge

public abstract void addEdge(E startVertex,
                             E endVertex)

Add an edge to this graph. If the graph is directed, a directed edge is added from startVertex to endVertex. If the graph is undirected, an undirected edge is added between startVertex and endVertex. If startVertex or endVertex is not already in this graph, that vertex is added to the graph. If an edge between startVertex and endVertex already exists in this graph, no new edge is added and the existing edge remains unchanged. If a new edge is added to the graph, its weight is set to 1.

Parameters:: startVertex - the label that identifies the start vertex; endVertex - the label that identifies the end vertex
Throws:: NullPointerException - if one or both of the specified vertices is null

addEdge

public abstract void addEdge(E startVertex,
                             E endVertex,
                             int weight)

Add a weighted edge to this graph. If the graph is directed, a directed edge is added from startVertex to endVertex. If the graph is undirected, an undirected edge is added between startVertex and endVertex. If startVertex or endVertex is not already in this graph, that vertex is added to the graph. If an edge between startVertex and endVertex already exists in this graph, no new edge is added. Rather, the weight specified by the parameter replaces the weight associated with the existing edge.

Parameters:: startVertex - the label that identifies the start vertex; endVertex - the label that identifies the end vertex; weight - the weight associated with the edge
Throws:: NullPointerException - if one or both of the specified vertices is null

addVertex

public abstract void addVertex(E vertex)

Add a vertex to this graph. If the vertex already exists within the graph, no change occurs to this graph.

Parameters:: vertex - the label that identifies the vertex

breadthFirst

public abstract List<E> breadthFirst(E startVertex)

Perform a breadth first traversal of the graph, starting at startVertex. (Note that the entire graph is traversed even if it is unconnected.)

Parameters:: startVertex - the label that identifies the starting vertex
Returns:: list of vertices in the order visited using a breadth-first traversal
Throws:: IllegalArgumentException - if vertex does not exist in the graph; NullPointerException - if the specified vertex is null

clear

public abstract void clear()

Remove all vertices and edges from this graph.

costOfPath

public abstract int costOfPath(List<E> path)

Determine the cost of a path (the sum of the weights of the edges).

Parameters:: path - an ordered list of vertices that specify the path in this graph
Returns:: the sum of the weights of the edges specified by the path
Throws:: IllegalArgumentException - if path is not a valid path in this graph

depthFirst

public abstract List<E> depthFirst(E startVertex)

Perform a depth first traversal of the graph, starting at startVertex. (Note that the entire graph is traversed even if it is unconnected.)

Parameters:: startVertex - the label that identifies the starting vertex
Returns:: list of vertices in the order visited using a depth-first traversal
Throws:: IllegalArgumentException - if vertex does not exist in the graph; NullPointerException - if the specified vertex is null

equals

public abstract boolean equals(Graph<E> graph)

Determine if this graph is equivalent to another graph. Two graphs are equivalent if they have the same vertices and edges.

Parameters:: graph - the Graph to be compared to this Graph
Returns:: true if the parameter is isomorphic to this graph

getNeighbors

public abstract List<E> getNeighbors(E vertex)

Returns a list of the vertices that are adjacent to a given vertex.

Parameters:: vertex - the label that identifies the vertex
Returns:: list of adjacent vertices; empty list if specified vertex is null
Throws:: IllegalArgumentException - if vertex does not exist in the graph

getNumberOfEdges

public abstract int getNumberOfEdges()

Returns the number of edges in this graph.

Returns:: the number of edges

getNumberOfVertices

public abstract int getNumberOfVertices()

Returns the number of vertices in this graph.

Returns:: the number of vertices

getVertices

public abstract List<E> getVertices()

Returns a list of the vertices in this graph.

Returns:: list of vertices

getWeightOfEdge

public abstract int getWeightOfEdge(E startVertex,
                                    E endVertex)

Returns the weight associated with an edge in this graph.

Parameters:: startVertex - the label that identifies the start vertex; endVertex - the label that identifies the end vertex
Returns:: the weight of an edge from startVertex to endVertex;
Throws:: IllegalArgumentException - if no such edge exists in this graph

inDegree

public abstract int inDegree(E vertex)

Returns the number of edges that have the given vertex as a destination.

Parameters:: vertex - the label that identifies the vertex
Returns:: the in-degree of the vertex; 0 if specified vertex is null
Throws:: IllegalArgumentException - if vertex does not exist in the graph

isDirected

public abstract boolean isDirected()

Returns whether or not this graph is directed.

Returns:: true if this graph is directed; false if this graph is undirected

minimumSpanningTree

public abstract Graph<E> minimumSpanningTree()

Determine a minimum spanning tree of this graph.

Returns:: a minimum spanning subgraph of this graph

outDegree

public abstract int outDegree(E vertex)

Returns the number of edges that have the given vertex as a source.

Parameters:: vertex - the label that identifies the vertex
Returns:: the out-degree of the vertex; 0 if specified vertex is null
Throws:: IllegalArgumentException - if vertex does not exist in the graph

removeEdge

public abstract void removeEdge(E startVertex,
                                E endVertex)

Remove an edge from this graph. If the edge does not exist within this graph, no change occurs to the graph. (Note that no exceptions are thrown in the events either or both vertices are null or not present in the graph.)

Parameters:: startVertex - the label that identifies the start vertex; endVertex - the label that identifies the end vertex

removeVertex

public abstract void removeVertex(E vertex)

Remove a vertex and all incident edges from this graph. If the vertex does not exist within this graph, no change occurs to the graph.

Parameters:: vertex - the label that identifies the vertex

topologicalSort

public abstract List<E> topologicalSort()

Perform a topological sort of this graph. Graph must be directed.

Returns:: list of vertices in topological sort order
Throws:: UnsupportedOperationException - if invoked on an undirected graph

toStringAdjacencyMatrix

public abstract String toStringAdjacencyMatrix()

The graph represented as an adjacency matrix rendered as a String. For example,

   | a | b | c | d | e |
 --+---+---+---+---+---+
 a |   | 2 |   | 3 |   |
 --+---+---+---+---+---+
 b |   |   | 4 |   |   |
 --+---+---+---+---+---+
 c | 1 |   |   | 3 | 2 |
 --+---+---+---+---+---+
 d |   | 5 |   |   |   |
 --+---+---+---+---+---+
 e | 6 |   |   | 1 |   |
 --+---+---+---+---+---+

Returns:: the graph rendered as an adjacency matrix