public class BasicGraph<V,E> extends Object implements Graph<V,E>
Constructor and Description |
---|
BasicGraph()
Constructs a new empty undirected, unweighted graph.
|
BasicGraph(boolean directed,
boolean weighted)
Constructs a new empty graph that can be directed or undirected,
weighted or unweighted.
|
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.
|
protected static void |
checkForNegative(double value)
Tests the given integer to see whether it is negative.
|
protected static void |
checkForNegative(int value)
Tests the given integer to see whether it is negative.
|
protected static void |
checkForNull(Object... args)
Tests the given arguments for null.
|
protected void |
checkVertex(String vertex)
Tests the given vertex for null and for membership in the graph.
|
protected void |
checkVertex(Vertex<V> vertex) |
protected void |
checkVertexes(String v1,
String v2)
Tests the given vertices for null and for membership in the graph.
|
protected void |
checkVertexes(Vertex<V> v1,
Vertex<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.
|
void |
clearEdges(String v) |
void |
clearEdges(Vertex<V> v) |
protected void |
clearVertexInfo()
Resets all distance / previous / visited markings from vertex info
objects in 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.
|
protected void |
corruptVertexInfo()
Sets some of the distance / previous / visited markings from vertex info
objects in this graph to have various random values, to test whether
a student's code properly clears the info between calls.
|
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.
|
boolean |
equals(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(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.
|
Set<Vertex<V>> |
inverseNeighbors(String v) |
Set<Vertex<V>> |
inverseNeighbors(Vertex<V> v) |
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.
|
protected Vertex<V> |
vertexInfo(String v)
Returns the Vertex object associated with the given vertex.
|
protected Map<String,Vertex<V>> |
vertexInfos()
Returns a read-only view of all internal data about vertex information.
|
public BasicGraph()
public BasicGraph(boolean directed, boolean weighted)
public final void addEdge(String v1, String v2)
public final void addEdge(String v1, String v2, double weight)
public final void addEdge(Vertex<V> v1, Vertex<V> v2)
public final void addEdge(Vertex<V> v1, Vertex<V> v2, double weight)
public final void addVertex(String v)
public final void clear()
public final void clearEdges()
clearEdges
in interface Graph<V,E>
public final void clearEdges(String v)
public final boolean containsEdge(String v1, String v2)
containsEdge
in interface Graph<V,E>
public final boolean containsEdge(Vertex<V> v1, Vertex<V> v2)
containsEdge
in interface Graph<V,E>
public final boolean containsPath(List<String> path)
containsPath
in interface Graph<V,E>
path
- The list of vertices representing the path to check.public final boolean containsVertex(String v)
containsVertex
in interface Graph<V,E>
v
- The vertex.public final boolean containsVertex(Vertex<V> v)
containsVertex
in interface Graph<V,E>
v
- The vertex.public final double cost(List<String> path)
public final int degree(String v)
public final int degree(Vertex<V> v)
public final Edge<V,E> edge(String v1, String v2)
public final Edge<V,E> edge(Vertex<V> v1, Vertex<V> v2)
public final int edgeCount()
public final Collection<Edge<V,E>> edges()
public final double edgeWeight(String v1, String v2)
edgeWeight
in interface Graph<V,E>
v1
- The starting vertex.v2
- The ending vertex.public final double edgeWeight(Vertex<V> v1, Vertex<V> v2)
edgeWeight
in interface Graph<V,E>
v1
- The starting vertex.v2
- The ending vertex.public boolean equals(Object o)
public int hashCode()
public final int inDegree(String v)
public final int inDegree(Vertex<V> v)
public final boolean isDirected()
isDirected
in interface Graph<V,E>
public final boolean isEmpty()
public final boolean isWeighted()
isWeighted
in interface Graph<V,E>
public final Set<Vertex<V>> neighbors(String v)
public final Set<Vertex<V>> neighbors(Vertex<V> v)
public final int outDegree(String v)
public final int outDegree(Vertex<V> v)
public final void removeEdge(Edge<V,E> e)
removeEdge
in interface Graph<V,E>
e
- The edge extra info of the edge to remove.public final void removeEdge(String v1, String v2)
removeEdge
in interface Graph<V,E>
v1
- The starting vertex of the edge.v2
- The ending vertex of the edge.public final void removeEdge(Vertex<V> v1, Vertex<V> v2)
removeEdge
in interface Graph<V,E>
v1
- The starting vertex of the edge.v2
- The ending vertex of the edge.public final void removeVertex(String v)
removeVertex
in interface Graph<V,E>
v
- The vertex to remove.public final void removeVertex(Vertex<V> v)
removeVertex
in interface Graph<V,E>
v
- The vertex to remove.public final void resetData()
public final String toString()
public final String toStringDetailed()
toStringDetailed
in interface Graph<V,E>
public Vertex<V> vertex(String name)
Graph
public final int vertexCount()
vertexCount
in interface Graph<V,E>
public final Collection<Vertex<V>> vertexes()
protected static void checkForNegative(double value)
value
- The integer to examine.IllegalArgumentException
- If the value is negative.protected static void checkForNegative(int value)
value
- The integer to examine.IllegalArgumentException
- If the value is negative.protected static void checkForNull(Object... args)
args
- The arguments to examine.NullPointerException
- If any argument is null.protected final void checkVertex(String vertex)
vertex
- The vertex to examine.IllegalArgumentException
- If the vertex is not part of this graph.NullPointerException
- If the vertex is null.protected final void checkVertexes(String v1, String v2)
v1
- The first vertex to examine.v2
- The second vertex to examine.IllegalArgumentException
- If any vertex is not part of this graph.NullPointerException
- If any vertex is null.protected final void checkVertexes(Vertex<V> v1, Vertex<V> v2)
v1
- The first vertex to examine.v2
- The second vertex to examine.IllegalArgumentException
- If any vertex is not part of this graph.NullPointerException
- If any vertex is null.protected final void clearVertexInfo()
protected final void corruptVertexInfo()
protected final Vertex<V> vertexInfo(String v)
v
- The vertex to examine.IllegalArgumentException
- If any vertex is not part of this graph.NullPointerException
- If any vertex is null.