CS3Graph (Graph)

Class CS3Graph<E>

java.lang.Object
  Graph<E>
      CS3Graph<E>

public class CS3Graph<E>
extends Graph<E>
extends Graph<E>

Implementation of concrete graph class for CS3.

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

Constructor Summary
`CS3Graph(boolean isDirected)` Boolean-parameter constructor.
`CS3Graph(Graph orig)` Copy constructor.

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

CS3Graph

public CS3Graph(boolean isDirected)

Boolean-parameter constructor. Constructed Graph contains no vertices and no edges.

Parameters:: isDirected - true if Graph is to be directed; false if undirected

CS3Graph

public CS3Graph(Graph orig)

Copy constructor.

Parameters:: orig - the original Graph to be copied
Throws:: NullPointerException - if the specified Graph is null

Method Detail

addEdge

public 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.

Specified by:: addEdge in class Graph<E>

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 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.

Specified by:: addEdge in class Graph<E>

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 void addVertex(E vertex)

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

Specified by:: addVertex in class Graph<E>

Parameters:: vertex - the label that identifies the vertex

breadthFirst

public 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.)

Specified by:: breadthFirst in class Graph<E>

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 void clear()

Remove all vertices and edges from this graph.

Specified by:: clear in class Graph<E>

costOfPath

public int costOfPath(List<E> path)

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

Specified by:: costOfPath in class Graph<E>

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 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.)

Specified by:: depthFirst in class Graph<E>

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 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.

Specified by:: equals in class Graph<E>

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

getNeighbors

public List<E> getNeighbors(E vertex)

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

Specified by:: getNeighbors in class Graph<E>

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 int getNumberOfEdges()

Returns the number of edges in this graph.

Specified by:: getNumberOfEdges in class Graph<E>

Returns:: the number of edges

getNumberOfVertices

public int getNumberOfVertices()

Returns the number of vertices in this graph.

Specified by:: getNumberOfVertices in class Graph<E>

Returns:: the number of vertices

getVertices

public List<E> getVertices()

Returns a list of the vertices in this graph.

Specified by:: getVertices in class Graph<E>

Returns:: list of vertices

getWeightOfEdge

public int getWeightOfEdge(E startVertex,
                           E endVertex)

Returns the weight associated with an edge in this graph.

Specified by:: getWeightOfEdge in class Graph<E>

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 int inDegree(E vertex)

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

Specified by:: inDegree in class Graph<E>

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 boolean isDirected()

Returns whether or not this graph is directed.

Specified by:: isDirected in class Graph<E>

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

minimumSpanningTree

public Graph<E> minimumSpanningTree()

Determine a minimum spanning tree of this graph.

Specified by:: minimumSpanningTree in class Graph<E>

Returns:: a minimum spanning subgraph of this graph

outDegree

public int outDegree(E vertex)

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

Specified by:: outDegree in class Graph<E>

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 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.)

Specified by:: removeEdge in class Graph<E>

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

removeVertex

public 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.

Specified by:: removeVertex in class Graph<E>

Parameters:: vertex - the label that identifies the vertex

topologicalSort

public List<E> topologicalSort()

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

Specified by:: topologicalSort in class Graph<E>

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

toStringAdjacencyMatrix

public 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 |   |
 --+---+---+---+---+---+

Specified by:: toStringAdjacencyMatrix in class Graph<E>

Returns:: the graph rendered as an adjacency matrix