Class AbstractGraph<V,E>

java.lang.Object

AbstractGraph<V,E>

Type Parameters:

V - The type of data to associate with each vertex.

E - The type of data, if any, to store inside each edge. Some graphs do not need to store any extra information in each edge, in which case they can supply any type for E (such as Object) and can avoid passing any extra information when adding edges to the graph.

All Implemented Interfaces:

Graph<V,E>

Direct Known Subclasses:

SearchableGraph

public abstract class AbstractGraph<V,E>
extends java.lang.Object
implements Graph<V,E>

AbstractGraph represents a mostly-complete implementation of the Graph interface. The only functionality missing is the three path-searching algorithms represented by the isReachable, minimumWeightPath, and shortestPath methods.

Constructor Summary

Constructors

Constructor and Description
AbstractGraph() Constructs a new empty undirected, unweighted graph.
AbstractGraph(boolean directed, boolean weighted) Constructs a new empty graph that can be directed or undirected, weighted or unweighted.

Method Summary

Methods

Modifier and Type	Method and Description
void	addEdge(V v1, V v2) Adds an edge between the given two vertices, if none already exists.
void	addEdge(V v1, V v2, E e) Adds an edge between the given two vertices, if none already exists, storing the given information in the edge.
void	addEdge(V v1, V v2, E e, int weight) Adds an edge with the given information and weight between the given two vertices, storing the given information in the edge.
void	addEdge(V v1, V v2, int weight) Adds an edge between the given two vertices, if none already exists.
void	addVertex(V v) Adds the given element as a vertex in this graph.
protected static void	checkForNegative(int value) Tests the given integer to see whether it is negative.
protected static void	checkForNull(java.lang.Object... args) Tests the given arguments for null.
protected void	checkVertex(V vertex) Tests the given vertex for null and for membership in the graph.
protected void	checkVertices(V v1, V v2) Tests the given vertices for null and for membership in the graph.
void	clear() Removes all vertices and edges from this graph.
void	clearEdges() Removes all edges from this graph.
protected void	clearVertexInfo() Resets all distance / previous / visited markings from vertex info objects in this graph.
boolean	containsEdge(E e) Returns whether this graph contains at least one edge with the given information stored in it.
boolean	containsEdge(V v1, V v2) Returns whether this graph contains an edge between the given vertices.
boolean	containsVertex(V v) Returns whether this graph contains the given vertex.
int	cost(java.util.List<V> path) Returns the total cost of following the given path of vertices in this graph, which is the sum of the edge weights between the path's vertices from start to end.
int	degree(V v) Returns the number of outgoing edges from the given vertex.
E	edge(V v1, V v2) Returns the extra information stored in the edge between vertices v1 and v2, if one exists.
int	edgeCount() Returns the total number of edges in this graph.
java.util.Collection<E>	edges() Returns a collection of information about all unique edges in this graph.
int	edgeWeight(V v1, V v2) Returns the weight of the edge between vertices v1 and v2, if one exists.
boolean	equals(java.lang.Object o) Returns true if o refers to a graph with the same vertices, edges, and other properties (directed vs.
int	hashCode() Returns an integer code for placing this graph into a hash-based collection.
int	inDegree(V v) Returns the number of incoming edges to the given vertex.
boolean	isDirected() Returns true if this is a directed graph, and false if it is undirected.
boolean	isEmpty() Returns true if this graph does not contain any vertices or edges.
boolean	isWeighted() Returns true if this is a weighted graph and false if it is unweighted.
java.util.Set<V>	neighbors(V v) Returns a collection containing all neighbors, that is, all vertices that are directly connected to the given vertex by an outgoing edge.
int	outDegree(V v) Returns the number of outgoing edges from the given vertex.
void	removeEdge(E e) Removes a single edge that exists with the given extra info stored in it.
void	removeEdge(V v1, V v2) Removes any edge that exists from vertex v1 to vertex v2.
void	removeVertex(V v) Removes the given vertex from this graph, along with all edges that were touching it.
java.lang.String	toString() Returns a string representation of this graph and its vertices and edges, such as "{V={A, B, C}, E={(A, B), (A, C)}}".
java.lang.String	toStringDetailed() Returns a detailed multi-line string representation of this graph and its vertices, such as "Graph{ vertices: A -> neighbors: [B, C] B -> neighbors: [A] C -> neighbors: [A] edges: (A,B,weight=2) (A,C) }"
int	vertexCount() Returns the number of vertices in this graph.
protected Vertex<V>	vertexInfo(V v) Returns the Vertex object associated with the given vertex.
protected java.util.Map<V,Vertex<V>>	vertexInfos() Returns a read-only view of all internal data about vertex information.
java.util.Set<V>	vertices() Returns a collection of the vertices in this graph.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Graph

isReachable, minimumWeightPath, shortestPath

Constructor Detail

AbstractGraph

public AbstractGraph()

Constructs a new empty undirected, unweighted graph.

AbstractGraph

public AbstractGraph(boolean directed,
             boolean weighted)

Constructs a new empty graph that can be directed or undirected, weighted or unweighted.

Method Detail

addEdge

public void addEdge(V v1,
           V v2)

Adds an edge between the given two vertices, if none already exists. The edge will be given a default weight of 1. No extra information will be stored in the edge. If an edge already exists between these vertices, its extra information will be cleared and its weight is updated to 1. If this graph is undirected, the two vertices can be passed in either order.

Specified by:

addEdge in interface Graph<V,E>

Parameters:

v1 - Starting vertex.

v2 - Ending vertex.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

addEdge

public void addEdge(V v1,
           V v2,
           E e)

Adds an edge between the given two vertices, if none already exists, storing the given information in the edge. The edge will be given a default weight of 1. If an edge already exists between these vertices, its information will be updated to the given edge info and its weight is updated to 1. If this graph is undirected, the two vertices can be passed in either order.

Specified by:

addEdge in interface Graph<V,E>

Parameters:

v1 - Starting vertex.

v2 - Ending vertex.

e - Information to store in the edge.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

addEdge

public void addEdge(V v1,
           V v2,
           int weight)

Adds an edge between the given two vertices, if none already exists. The edge will be given a default weight of 1. No extra information will be stored in the edge. If an edge already exists between these vertices, its extra information will be cleared and its weight is updated to 1. If this graph is undirected, the two vertices can be passed in either order.

Specified by:

addEdge in interface Graph<V,E>

Parameters:

v1 - Starting vertex.

v2 - Ending vertex.

weight - Edge's weight.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph, if edge weight is negative, or if this is an unweighted graph and an edge weight other than 1 is passed.

java.lang.NullPointerException - If any object parameter is null.

addEdge

public void addEdge(V v1,
           V v2,
           E e,
           int weight)

Adds an edge with the given information and weight between the given two vertices, storing the given information in the edge. If an edge already exists between these vertices, its information will be updated to the given edge info and its weight is updated to the given weight. If this graph is undirected, the two vertices can be passed in either order.

Specified by:

addEdge in interface Graph<V,E>

Parameters:

v1 - Starting vertex.

v2 - Ending vertex.

e - Information to store in the edge.

weight - Edge's weight.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph, if edge weight is negative, or if this is an unweighted graph and an edge weight other than 1 is passed.

java.lang.NullPointerException - If any object parameter is null.

addVertex

public void addVertex(V v)

Adds the given element as a vertex in this graph. If the given element is already a vertex in this graph, no change is made.

Specified by:

addVertex in interface Graph<V,E>

Parameters:

v - The vertex to add.

Throws:

java.lang.NullPointerException - If the vertex is null.

clear

public void clear()

Removes all vertices and edges from this graph.

Specified by:

clear in interface Graph<V,E>

clearEdges

public void clearEdges()

Removes all edges from this graph.

Specified by:

clearEdges in interface Graph<V,E>

containsEdge

public boolean containsEdge(E e)

Returns whether this graph contains at least one edge with the given information stored in it. If the value passed is null, returns true if at least one edge in the graph does not have any extra information stored in it.

Specified by:

containsEdge in interface Graph<V,E>

containsEdge

public boolean containsEdge(V v1,
                   V v2)

Returns whether this graph contains an edge between the given vertices. If either vertex is not part of this graph, returns false.

Specified by:

containsEdge in interface Graph<V,E>

containsVertex

public boolean containsVertex(V v)

Returns whether this graph contains the given vertex. If the vertex passed is null, returns false.

Specified by:

containsVertex in interface Graph<V,E>

Parameters:

v - The vertex.

cost

public int cost(java.util.List<V> path)

Returns the total cost of following the given path of vertices in this graph, which is the sum of the edge weights between the path's vertices from start to end.

Specified by:

cost in interface Graph<V,E>

Parameters:

path - The list of vertices in the path to examine.

Throws:

java.lang.IllegalArgumentException - If any vertex in the path is not part of this graph.

java.lang.NullPointerException - If the path or any vertex in it is null.

degree

public int degree(V v)

Returns the number of outgoing edges from the given vertex. This method is an alias for outDegree; it is provided because undirected graphs generally just think of vertices as having one overall degree and not a separate in- and out- degree.

Specified by:

degree in interface Graph<V,E>

Parameters:

v - The vertex.

Throws:

java.lang.IllegalArgumentException - If the vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

edge

public E edge(V v1,
     V v2)

Returns the extra information stored in the edge between vertices v1 and v2, if one exists. If this graph is undirected, the two vertices can be passed in either order. Returns null if there is no edge between the given vertices or if the edge between the given vertices contains no extra information.

Specified by:

edge in interface Graph<V,E>

Parameters:

v1 - The starting vertex.

v2 - The ending vertex.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

edgeCount

public int edgeCount()

Returns the total number of edges in this graph. Note that this does not necessarily equal edges().size() because edges() returns a set of edge information values stored in each edge, excluding nulls (edges without any extra information stored in them), while this method returns a count of all edges including ones without any information stored in them and ones with information that is a duplicate of that stored in some other edge.

Specified by:

edgeCount in interface Graph<V,E>

edges

public java.util.Collection<E> edges()

Returns a collection of information about all unique edges in this graph. The collection is a shallow 'view' of the edges. Any changes made to it are written back to the graph. (New edges cannot be added directly to the collection returned by this method, because it would not know which vertices to associate the edge with.)

Specified by:

edges in interface Graph<V,E>

edgeWeight

public int edgeWeight(V v1,
             V v2)

Returns the weight of the edge between vertices v1 and v2, if one exists. If this graph is undirected, the two vertices can be passed in either order. Returns -1 if there is no edge between the given vertices.

Specified by:

edgeWeight in interface Graph<V,E>

Parameters:

v1 - The starting vertex.

v2 - The ending vertex.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

equals

public boolean equals(java.lang.Object o)

Returns true if o refers to a graph with the same vertices, edges, and other properties (directed vs. undirected, weighted vs. unweighted, etc.) as this graph.

Overrides:

equals in class java.lang.Object

Parameters:

o - The object to compare against.

hashCode

public int hashCode()

Returns an integer code for placing this graph into a hash-based collection.

Overrides:

hashCode in class java.lang.Object

inDegree

public int inDegree(V v)

Returns the number of incoming edges to the given vertex.

Specified by:

inDegree in interface Graph<V,E>

Parameters:

v - The vertex to examine.

Throws:

java.lang.IllegalArgumentException - If the vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

isDirected

public boolean isDirected()

Returns true if this is a directed graph, and false if it is undirected.

Specified by:

isDirected in interface Graph<V,E>

isEmpty

public boolean isEmpty()

Returns true if this graph does not contain any vertices or edges.

Specified by:

isEmpty in interface Graph<V,E>

isWeighted

public boolean isWeighted()

Returns true if this is a weighted graph and false if it is unweighted.

Specified by:

isWeighted in interface Graph<V,E>

neighbors

public java.util.Set<V> neighbors(V v)

Returns a collection containing all neighbors, that is, all vertices that are directly connected to the given vertex by an outgoing edge. The collection is a shallow 'view' of the neighboring vertices. Any changes made to it are written back to the graph. New vertices cannot be added directly to the collection returned by this method. But vertices can be removed, cleared, etc.

Specified by:

neighbors in interface Graph<V,E>

Parameters:

v - The vertex to examine.

Throws:

java.lang.IllegalArgumentException - If the vertex is not part of this graph.

java.lang.NullPointerException - If the vertex is null.

outDegree

public int outDegree(V v)

Returns the number of outgoing edges from the given vertex.

Specified by:

outDegree in interface Graph<V,E>

Parameters:

v - The vertex to examine.

removeEdge

public void removeEdge(E e)

Removes a single edge that exists with the given extra info stored in it. If multiple edges have the given extra info, an arbitrary one of them is removed. If null is passed, removes an arbitrary single edge that has no extra info stored in it. If no edge exists in this graph with the given extra info, has no effect. This implementation must examine all edges in the graph to find the specified edge.

Specified by:

removeEdge in interface Graph<V,E>

Parameters:

e - The edge extra info of the edge to remove.

removeEdge

public void removeEdge(V v1,
              V v2)

Removes any edge that exists from vertex v1 to vertex v2. If this graph is undirected, the two vertices can be passed in either order. If no edge exists in this graph between the two given vertices, has no effect.

Specified by:

removeEdge in interface Graph<V,E>

Parameters:

v1 - The starting vertex of the edge.

v2 - The ending vertex of the edge.

Throws:

java.lang.IllegalArgumentException - If either vertex is not part of the graph.

java.lang.NullPointerException - If any object parameter is null.

removeVertex

public void removeVertex(V v)

Removes the given vertex from this graph, along with all edges that were touching it. If the given vertex is not part of this graph, has no effect.

Specified by:

removeVertex in interface Graph<V,E>

Parameters:

v - The vertex to remove.

Throws:

java.lang.NullPointerException - If the vertex is null.

toString

public java.lang.String toString()

Returns a string representation of this graph and its vertices and edges, such as "{V={A, B, C}, E={(A, B), (A, C)}}".

Specified by:

toString in interface Graph<V,E>

Overrides:

toString in class java.lang.Object

toStringDetailed

public java.lang.String toStringDetailed()

Returns a detailed multi-line string representation of this graph and its vertices, such as "Graph{ vertices: A -> neighbors: [B, C] B -> neighbors: [A] C -> neighbors: [A] edges: (A,B,weight=2) (A,C) }"

Specified by:

toStringDetailed in interface Graph<V,E>

vertexCount

public int vertexCount()

Returns the number of vertices in this graph.

Specified by:

vertexCount in interface Graph<V,E>

vertices

public final java.util.Set<V> vertices()

Returns a collection of the vertices in this graph. The collection is a shallow 'view' of the vertices. Any changes made to it are written back to the graph. Vertices can be added, removed, cleared, etc. on this collection.

Specified by:

vertices in interface Graph<V,E>

checkForNegative

protected static void checkForNegative(int value)

Tests the given integer to see whether it is negative.

Parameters:

value - The integer to examine.

Throws:

java.lang.IllegalArgumentException - If the value is negative.

checkForNull

protected static void checkForNull(java.lang.Object... args)

Tests the given arguments for null.

Parameters:

args - The arguments to examine.

Throws:

java.lang.NullPointerException - If any argument is null.

checkVertex

protected void checkVertex(V vertex)

Tests the given vertex for null and for membership in the graph.

Parameters:

vertex - The vertex to examine.

Throws:

java.lang.IllegalArgumentException - If the vertex is not part of this graph.

java.lang.NullPointerException - If the vertex is null.

checkVertices

protected void checkVertices(V v1,
                 V v2)

Tests the given vertices for null and for membership in the graph.

Parameters:

v1 - The first vertex to examine.

v2 - The second vertex to examine.

Throws:

java.lang.IllegalArgumentException - If any vertex is not part of this graph.

java.lang.NullPointerException - If any vertex is null.

clearVertexInfo

protected void clearVertexInfo()

Resets all distance / previous / visited markings from vertex info objects in this graph.

vertexInfo

protected Vertex<V> vertexInfo(V v)

Returns the Vertex object associated with the given vertex.

Parameters:

v - The vertex to examine.

Throws:

java.lang.IllegalArgumentException - If any vertex is not part of this graph.

java.lang.NullPointerException - If any vertex is null.

vertexInfos

protected java.util.Map<V,Vertex<V>> vertexInfos()

Returns a read-only view of all internal data about vertex information.