Class MysteryUnweightedGraphImplementation

java.lang.Object
  MysteryUnweightedGraphImplementation

All Implemented Interfaces:

Graph, UnweightedGraph

public class MysteryUnweightedGraphImplementation
extends java.lang.Object
implements UnweightedGraph

An implementation of the Unweighted Graph ADT. This class can represent both directed and undirected graphs, but the choice must be made at construction time, and is final. Technically, this implementation supports self-loops; it makes no effort to prevent these. Any method that takes one or more vertex IDs as arguments may throw an IndexOutOfBoundsException if any input ID is out of bounds.

Constructor Summary

MysteryUnweightedGraphImplementation()
Default constructor: an empty directed graph.

MysteryUnweightedGraphImplementation(boolean directed)
Constructs an empty graph with the specified directedness.

MysteryUnweightedGraphImplementation(boolean directed, int N)
Constructs a graph with N vertices and the specified directedness.

Method Summary

boolean	addEdge(int begin, int end) Adds an edge between two vertices.
int	addVertex() Adds a new vertex.
void	clear() Removes all vertices and edges from the graph.
int	getDegree(int v) Returns the out-degree of the specified vertex.
int	getInDegree(int v) Returns the in-degree of the specified vertex.
java.lang.Iterable<java.lang.Integer>	getNeighbors(int v) Returns an iterator over the neighbors of the specified vertex.
boolean	hasEdge(int begin, int end) Checks whether an edge exists between two vertices.
boolean	isDirected() Returns true if the graph is directed.
boolean	isEmpty() Returns true if there are no vertices in the graph.
int	numEdges() Returns the number of edges in the graph.
int	numVerts() Returns the number of vertices in the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

MysteryUnweightedGraphImplementation

public MysteryUnweightedGraphImplementation()

Default constructor: an empty directed graph.

MysteryUnweightedGraphImplementation

public MysteryUnweightedGraphImplementation(boolean directed)

Constructs an empty graph with the specified directedness.

MysteryUnweightedGraphImplementation

public MysteryUnweightedGraphImplementation(boolean directed,
                                            int N)

Constructs a graph with N vertices and the specified directedness.

Method Detail

addVertex

public int addVertex()

Adds a new vertex.

Specified by:

addVertex in interface Graph

Returns:

the ID of the added vertex.

addEdge

public boolean addEdge(int begin,
                       int end)

Adds an edge between two vertices. In an undirected graph, this has the same effect as addEdge(end, begin).

Specified by:

addEdge in interface UnweightedGraph

Returns:

false if the edge was already in the graph.

hasEdge

public boolean hasEdge(int begin,
                       int end)

Checks whether an edge exists between two vertices. In an undirected graph, this returns the same as hasEdge(end, begin).

Specified by:

hasEdge in interface Graph

Returns:

true if there is an edge from begin to end.

getDegree

public int getDegree(int v)

Returns the out-degree of the specified vertex.

Specified by:

getDegree in interface Graph

getInDegree

public int getInDegree(int v)

Returns the in-degree of the specified vertex.

Specified by:

getInDegree in interface Graph

getNeighbors

public java.lang.Iterable<java.lang.Integer> getNeighbors(int v)

Returns an iterator over the neighbors of the specified vertex. In particular, the vertex u is included in the returned iterator's sequence if and only if there is an edge from v to u in the graph.

Specified by:

getNeighbors in interface Graph

numVerts

public int numVerts()

Returns the number of vertices in the graph.

Specified by:

numVerts in interface Graph

numEdges

public int numEdges()

Returns the number of edges in the graph. The result does *not* double-count edges in undirected graphs.

Specified by:

numEdges in interface Graph

isDirected

public boolean isDirected()

Returns true if the graph is directed.

Specified by:

isDirected in interface Graph

isEmpty

public boolean isEmpty()

Returns true if there are no vertices in the graph.

Specified by:

isEmpty in interface Graph

clear

public void clear()

Removes all vertices and edges from the graph.

Specified by:

clear in interface Graph