## Interface Graph<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 you can supply a meaningless type for E (such as Void) and can avoid passing any extra information when adding edges to the graph.
All Known Implementing Classes:
AbstractGraph, SearchableGraph

`public interface Graph<V,E>`
A Graph is a collection of vertices and edges between vertices. A graph can be directed or undirected (indicating whether edges are one-directional or bidirectional, respectively), and weighted or unweighted (indicating whether edges have different or uniform cost, respectively).

A Graph does not allow null vertices, but it does allow null edges, which corresponds to an edge with no extra information stored in it.

A Graph can have at most one edge with the same start and end vertex; in other words, it is not permitted to have two edges between the same vertices, except in a directed graph it is allowed to have an edge A,B and an edge B,A. Loops (edges from a vertex directly back to itself) are prohibited; an IllegalArgumentException will be thrown on an attempt to add a loop.

Implementations of the Graph interface do not allow edges with negative weights. If a negative edge weight is passed, an IllegalArgumentException is thrown. A weight of 0 is allowed.

• ### 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.
`void` `clear()`
Removes all vertices and edges from this graph.
`void` `clearEdges()`
Removes all edges from 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 all edges in this graph.
`int` ```edgeWeight(V v1, V v2)```
Returns the weight of the edge between vertices v1 and v2, if one exists.
`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` ```isReachable(V v1, V v2)```
Returns true if there is any path in this graph that leads from the given starting vertex v1 to the given ending vertex v2.
`boolean` `isWeighted()`
Returns true if this is a weighted graph and false if it is unweighted.
`java.util.List<V>` ```minimumWeightPath(V v1, V v2)```
Returns a list of vertices representing a minimum-weight path from vertex v1 to vertex v2.
`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 any edge(s) that exist with the given extra info stored in it/them.
`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.util.List<V>` ```shortestPath(V v1, V v2)```
Returns the path in this graph with the least number of vertices that leads from the given starting vertex v1 to the given ending vertex v2.
`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.
`java.util.Set<V>` `vertices()`
Returns a collection of the vertices in this graph.
• ### Method Detail

```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.
Parameters:
`v1` - Starting vertex.
`v2` - Ending vertex.
Throws:
`java.lang.IllegalArgumentException` - If either vertex is not part of the graph, or if v1 and v2 are the same (a loop).
`java.lang.NullPointerException` - If any object parameter is null.

```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.
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, or if v1 and v2 are the same (a loop).
`java.lang.NullPointerException` - If any object parameter is null.

```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.
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, if v1 and v2 are the same (a loop), 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.

```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.
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, if v1 and v2 are the same (a loop), 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.

`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.
Parameters:
`v` - The vertex to add.
Throws:
`java.lang.NullPointerException` - If the vertex is null.
• #### clear

`void clear()`
Removes all vertices and edges from this graph.
• #### clearEdges

`void clearEdges()`
Removes all edges from this graph.
• #### containsEdge

`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.
• #### containsEdge

```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.
• #### containsVertex

`boolean containsVertex(V v)`
Returns whether this graph contains the given vertex. If the vertex passed is null, returns false.
Parameters:
`v` - The vertex.
• #### cost

`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.
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

`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.
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

```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.
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

`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 unique 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.
• #### edges

`java.util.Collection<E> edges()`
Returns a collection of all 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. But edges can be removed, cleared, etc.
• #### edgeWeight

```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.
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.
• #### inDegree

`int inDegree(V v)`
Returns the number of incoming edges to the given vertex.
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

`boolean isDirected()`
Returns true if this is a directed graph, and false if it is undirected.
• #### isEmpty

`boolean isEmpty()`
Returns true if this graph does not contain any vertices or edges.
• #### isReachable

```boolean isReachable(V v1,
V v2)```
Returns true if there is any path in this graph that leads from the given starting vertex v1 to the given ending vertex v2. Uses the Depth-First Search (DFS) algorithm to find the path. If there is no path to v2 from v1, the method returns false.
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.
• #### isWeighted

`boolean isWeighted()`
Returns true if this is a weighted graph and false if it is unweighted.
• #### minimumWeightPath

```java.util.List<V> minimumWeightPath(V v1,
V v2)```
Returns a list of vertices representing a minimum-weight path from vertex v1 to vertex v2. If v2 is not reachable from v1, returns null. Uses Dijkstra's Algorithm to find a minimum-weight path.
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.
• #### neighbors

`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.
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

`int outDegree(V v)`
Returns the number of outgoing edges from the given vertex.
Parameters:
`v` - The vertex to examine.
• #### removeEdge

`void removeEdge(E e)`
Removes any edge(s) that exist with the given extra info stored in it/them. If multiple edges have the given extra info, all are removed. If null is passed, removes any edges that have no extra info stored in them. 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, so it is inefficient.
Parameters:
`e` - The edge extra info of the edge to remove.
• #### removeEdge

```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.
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

`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.
Parameters:
`v` - The vertex to remove.
Throws:
`java.lang.NullPointerException` - If the vertex is null.
• #### shortestPath

```java.util.List<V> shortestPath(V v1,
V v2)```
Returns the path in this graph with the least number of vertices that leads from the given starting vertex v1 to the given ending vertex v2. Uses the Breadth-First Search (BFS) algorithm to find the path. If v2 is not reachable from v1, the method returns null.
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.
• #### toString

`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)}}".
Overrides:
`toString` in class `java.lang.Object`
• #### toStringDetailed

`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) }"
• #### vertexCount

`int vertexCount()`
Returns the number of vertices in this graph.
• #### vertices

`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.