Class CarlWeightedGraph

java.lang.Object

CarlWeightedGraph

All Implemented Interfaces:

Graph, WeightedGraph

public class CarlWeightedGraph
extends java.lang.Object
implements WeightedGraph

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

Methods inherited from class java.lang.Object

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

Constructor Detail

CarlWeightedGraph

public CarlWeightedGraph()

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

CarlWeightedGraph

public CarlWeightedGraph(boolean directed)

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

CarlWeightedGraph

public CarlWeightedGraph(boolean directed,
                         int N)

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

CarlWeightedGraph

public CarlWeightedGraph(boolean directed,
                         int N,
                         double sentinel)

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

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

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)

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.

setWeight

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

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)

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)

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

missingEdgeSentinel

public double missingEdgeSentinel()

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

Specified by:

missingEdgeSentinel in interface WeightedGraph