public interface Graph<V,E>
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.
Modifier and Type | Method and Description |
---|---|
void |
addEdge(String v1,
String v2)
Adds an edge between the given two vertices, if none already exists.
|
void |
addEdge(String v1,
String v2,
double weight)
Adds an edge between the given two vertices, if none already exists.
|
void |
addEdge(Vertex<V> v1,
Vertex<V> v2)
Adds an edge between the given two vertices, if none already exists.
|
void |
addEdge(Vertex<V> v1,
Vertex<V> v2,
double weight)
Adds an edge between the given two vertices, if none already exists.
|
void |
addVertex(String 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(String v1,
String v2)
Returns whether this graph contains an edge between the given vertices.
|
boolean |
containsEdge(Vertex<V> v1,
Vertex<V> v2)
Returns whether this graph contains an edge between the given vertices.
|
boolean |
containsPath(List<String> path)
Returns true if the given list of vertices represents a path that can
be formed by walking edges between those vertices in this graph,
walking from the start to the end of the list.
|
boolean |
containsVertex(String v)
Returns whether this graph contains the given vertex.
|
boolean |
containsVertex(Vertex<V> v)
Returns whether this graph contains the given vertex.
|
double |
cost(List<String> 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(String v)
Returns the number of outgoing edges from the given vertex.
|
int |
degree(Vertex<V> v)
Returns the number of outgoing edges from the given vertex.
|
Edge<V,E> |
edge(String v1,
String v2)
Returns the extra information stored in the edge between vertices v1 and v2, if one exists.
|
Edge<V,E> |
edge(Vertex<V> v1,
Vertex<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.
|
Collection<Edge<V,E>> |
edges()
Returns a collection of all edges in this graph.
|
double |
edgeWeight(String v1,
String v2)
Returns the weight of the edge between vertices v1 and v2, if one exists.
|
double |
edgeWeight(Vertex<V> v1,
Vertex<V> v2)
Returns the weight of the edge between vertices v1 and v2, if one exists.
|
int |
inDegree(String v)
Returns the number of incoming edges to the given vertex.
|
int |
inDegree(Vertex<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.
|
Set<Vertex<V>> |
neighbors(String v)
Returns a collection containing all neighbors, that is, all vertices that are
directly connected to the given vertex by an outgoing edge.
|
Set<Vertex<V>> |
neighbors(Vertex<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(String v)
Returns the number of outgoing edges from the given vertex.
|
int |
outDegree(Vertex<V> v)
Returns the number of outgoing edges from the given vertex.
|
void |
removeEdge(Edge<V,E> e)
Removes any edge(s) that exist with the given extra info stored in it/them.
|
void |
removeEdge(String v1,
String v2)
Removes any edge that exists from vertex v1 to vertex v2.
|
void |
removeEdge(Vertex<V> v1,
Vertex<V> v2)
Removes any edge that exists from vertex v1 to vertex v2.
|
void |
removeVertex(String v)
Removes the given vertex from this graph, along with all edges that were
touching it.
|
void |
removeVertex(Vertex<V> v)
Removes the given vertex from this graph, along with all edges that were
touching it.
|
void |
resetData()
Clears out any data stored in each vertex.
|
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)}}".
|
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)
}"
|
Vertex<V> |
vertex(String name)
Returns the structure of information about the vertex with the given name.
|
int |
vertexCount()
Returns the number of vertices in this graph.
|
Collection<Vertex<V>> |
vertexes()
Returns a collection of the vertices in this graph.
|
void addEdge(String v1, String v2)
v1
- Starting vertex.v2
- Ending vertex.IllegalArgumentException
- If either vertex is not part of the graph,
or if v1 and v2 are the same (a loop).NullPointerException
- If any object parameter is null.void addEdge(Vertex<V> v1, Vertex<V> v2)
v1
- Starting vertex.v2
- Ending vertex.IllegalArgumentException
- If either vertex is not part of the graph,
or if v1 and v2 are the same (a loop).NullPointerException
- If any object parameter is null.void addEdge(String v1, String v2, double weight)
v1
- Starting vertex.v2
- Ending vertex.weight
- Edge's weight.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.NullPointerException
- If any object parameter is null.void addEdge(Vertex<V> v1, Vertex<V> v2, double weight)
v1
- Starting vertex.v2
- Ending vertex.weight
- Edge's weight.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.NullPointerException
- If any object parameter is null.void addVertex(String v)
v
- The vertex to add.NullPointerException
- If the vertex is null.void clear()
void clearEdges()
boolean containsEdge(String v1, String v2)
boolean containsEdge(Vertex<V> v1, Vertex<V> v2)
boolean containsPath(List<String> path)
path
- The list of vertices representing the path to check.NullPointerException
- If the list or any of its elements is null.boolean containsVertex(String v)
v
- The vertex.boolean containsVertex(Vertex<V> v)
v
- The vertex.double cost(List<String> path)
path
- The list of vertices in the path to examine.IllegalArgumentException
- If any vertex in the path is not part of this graph,
or if there is not an edge between any two neighboring
vertices in the path.NullPointerException
- If the path or any vertex in it is null.int degree(String v)
v
- The vertex.IllegalArgumentException
- If the vertex is not part of the graph.NullPointerException
- If any object parameter is null.int degree(Vertex<V> v)
v
- The vertex.IllegalArgumentException
- If the vertex is not part of the graph.NullPointerException
- If any object parameter is null.Edge<V,E> edge(String v1, String v2)
v1
- The starting vertex.v2
- The ending vertex.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.Edge<V,E> edge(Vertex<V> v1, Vertex<V> v2)
v1
- The starting vertex.v2
- The ending vertex.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.int edgeCount()
Collection<Edge<V,E>> edges()
double edgeWeight(String v1, String v2)
v1
- The starting vertex.v2
- The ending vertex.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.double edgeWeight(Vertex<V> v1, Vertex<V> v2)
v1
- The starting vertex.v2
- The ending vertex.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.int inDegree(String v)
v
- The vertex to examine.IllegalArgumentException
- If the vertex is not part of the graph.NullPointerException
- If any object parameter is null.int inDegree(Vertex<V> v)
v
- The vertex to examine.IllegalArgumentException
- If the vertex is not part of the graph.NullPointerException
- If any object parameter is null.boolean isDirected()
boolean isEmpty()
boolean isWeighted()
Set<Vertex<V>> neighbors(String v)
v
- The vertex to examine.IllegalArgumentException
- If the vertex is not part of this graph.NullPointerException
- If the vertex is null.Set<Vertex<V>> neighbors(Vertex<V> v)
v
- The vertex to examine.IllegalArgumentException
- If the vertex is not part of this graph.NullPointerException
- If the vertex is null.int outDegree(String v)
v
- The vertex to examine.int outDegree(Vertex<V> v)
v
- The vertex to examine.void removeEdge(Edge<V,E> e)
e
- The edge extra info of the edge to remove.void removeEdge(String v1, String v2)
v1
- The starting vertex of the edge.v2
- The ending vertex of the edge.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.void removeEdge(Vertex<V> v1, Vertex<V> v2)
v1
- The starting vertex of the edge.v2
- The ending vertex of the edge.IllegalArgumentException
- If either vertex is not part of the graph.NullPointerException
- If any object parameter is null.void removeVertex(String v)
v
- The vertex to remove.NullPointerException
- If the vertex is null.void removeVertex(Vertex<V> v)
v
- The vertex to remove.NullPointerException
- If the vertex is null.void resetData()
String toString()
String toStringDetailed()
Vertex<V> vertex(String name)
int vertexCount()
Collection<Vertex<V>> vertexes()