Class MysteryWeightedGraphImplementation

java.lang.Object

MysteryWeightedGraphImplementation

All Implemented Interfaces:

Graph, WeightedGraph

public class MysteryWeightedGraphImplementation
extends java.lang.Object
implements WeightedGraph

A mysterious implementation of the Weighted Graph ADT!

This class can represent both directed and undirected graphs, but the choice must be made at construction time, and is final.

Another choice that must be made at construction time is that of the "sentinel" value for weights. This is the value that getWeight() returns for edges that are not in the graph. The default is Double.POSITIVE_INFINITY, but other common choices are negative infinity, zero, or NaN.

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
MysteryWeightedGraphImplementation() Default constructor: an empty directed graph.
MysteryWeightedGraphImplementation(boolean directed) Constructs an empty graph with the specified directedness, with a sentinel value of Double.POSITIVE_INFINITY.
MysteryWeightedGraphImplementation(boolean directed, int N) Constructs a graph with N vertices and the specified directedness, with a sentinel value of Double.POSITIVE_INFINITY.
MysteryWeightedGraphImplementation(boolean directed, int N, double sentinelWeight) Constructs a graph with N vertices and the specified directedness and sentinel value.

Method Summary

Modifier and Type	Method and Description
boolean	addEdge(int begin, int end, double weight) Adds a weighted 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.
double	getWeight(int begin, int end) Gets the weight of the edge between two vertices.
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.
double	missingEdgeSentinel() Returns the "sentinel" weight value for edges not in the graph.
int	numEdges() Returns the number of edges in the graph.
int	numVerts() Returns the number of vertices in the graph.
boolean	setWeight(int begin, int end, double weight) Sets the weight of an edge already 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

MysteryWeightedGraphImplementation

public MysteryWeightedGraphImplementation()

Default constructor: an empty directed graph. Creates an empty directed graph, with a sentinel value of Double.POSITIVE_INFINITY.

MysteryWeightedGraphImplementation

public MysteryWeightedGraphImplementation(boolean directed)

Constructs an empty graph with the specified directedness, with a sentinel value of Double.POSITIVE_INFINITY.

MysteryWeightedGraphImplementation

public MysteryWeightedGraphImplementation(boolean directed,
                                          int N)

Constructs a graph with N vertices and the specified directedness, with a sentinel value of Double.POSITIVE_INFINITY.

MysteryWeightedGraphImplementation

public MysteryWeightedGraphImplementation(boolean directed,
                                          int N,
                                          double sentinelWeight)

Constructs a graph with N vertices and the specified directedness and sentinel value.

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,
                       double weight)

Description copied from interface: WeightedGraph

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

Specified by:

addEdge in interface WeightedGraph

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

setWeight

public boolean setWeight(int begin,
                         int end,
                         double weight)

Description copied from interface: WeightedGraph

Sets the weight of an edge already in the graph.

Specified by:

setWeight in interface WeightedGraph

Returns:

false if the edge is not in the graph.

getWeight

public double getWeight(int begin,
                        int end)

Description copied from interface: WeightedGraph

Gets the weight of the edge between two vertices. In an undirected graph, this returns the same as getWeight(end, begin).

Specified by:

getWeight in interface WeightedGraph

Returns:

the weight of the edge from begin to end, or the sentinel value if no such edge exists.

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

missingEdgeSentinel

public double missingEdgeSentinel()

Description copied from interface: WeightedGraph

Returns the "sentinel" weight value for edges not in the graph.

Specified by:

missingEdgeSentinel in interface WeightedGraph

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object