Class MysteryUnweightedGraphImplementation

java.lang.Object

MysteryUnweightedGraphImplementation

All Implemented Interfaces:

Graph, UnweightedGraph

public class MysteryUnweightedGraphImplementation
extends java.lang.Object
implements UnweightedGraph

A mysterious 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

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
boolean	addEdge(int begin, int end) Adds an unweighted 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 iterable object that allows iteration over the neighbors of the specified vertex.
boolean	hasEdge(int begin, int end) Returns 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.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, 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()

Description copied from interface: Graph

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)

Description copied from interface: UnweightedGraph

Adds an unweighted 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)

Description copied from interface: Graph

Returns 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

getDegree

public int getDegree(int v)

Description copied from interface: Graph

Returns the out-degree of the specified vertex.

Specified by:

getDegree in interface Graph

getInDegree

public int getInDegree(int v)

Description copied from interface: Graph

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)

Description copied from interface: Graph

Returns an iterable object that allows iteration over the neighbors of the specified vertex. In particular, the vertex u is included in the 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()

Description copied from interface: Graph

Returns the number of vertices in the graph.

Specified by:

numVerts in interface Graph

numEdges

public int numEdges()

Description copied from interface: Graph

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

Description copied from interface: Graph

Returns true if the graph is directed.

Specified by:

isDirected in interface Graph

isEmpty

public boolean isEmpty()

Description copied from interface: Graph

Returns true if there are no vertices in the graph.

Specified by:

isEmpty in interface Graph

clear

public void clear()

Description copied from interface: Graph

Removes all vertices and edges from the graph.

Specified by:

clear in interface Graph

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object