Interface Graph

All Known Subinterfaces:

UnweightedGraph, WeightedGraph

All Known Implementing Classes:

MysteryUnweightedGraphImplementation, MysteryWeightedGraphImplementation

public interface Graph

A common Java interface for the Graph ADT, encompassing graphs both unweighted and weighted, undirected and directed. Note that an object of Graph type can't add edges to itself; the sub-interfaces UnweightedGraph and WeightedGraph contain the necessary methods for adding edges.

Note that this particular interface explicitly refers to vertices by a consecutive set of integral vertex IDs, from 0 to N-1 (where N is the number of vertices), and conceives of edges only in terms of their endpoints. This is the canonical conception of a graph for standard graph algorithms, but lacks common features for modeling, e.g., a road network.

To represent metadata like vertex labels, it is recommended that the user maintain their own dictionaries mapping between vertex IDs (or pairs thereof, for edges) and the desired values.

Any method that takes one or more vertex IDs as arguments may throw an IndexOutOfBoundsException if any input ID is out of bounds.

Method Summary

Modifier and Type	Method and Description
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.

Method Detail

addVertex

int addVertex()

Adds a new vertex.

Returns:

the ID of the added vertex.

hasEdge

boolean hasEdge(int begin,
                int end)

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

getDegree

int getDegree(int v)

Returns the out-degree of the specified vertex.

getInDegree

int getInDegree(int v)

Returns the in-degree of the specified vertex.

getNeighbors

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

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.

numVerts

int numVerts()

Returns the number of vertices in the graph.

numEdges

int numEdges()

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

isDirected

boolean isDirected()

Returns true if the graph is directed.

isEmpty

boolean isEmpty()

Returns true if there are no vertices in the graph.

clear

void clear()

Removes all vertices and edges from the graph.