Here is my code which implements a simple directed graph in Java 8. Here are some of the things I am unsure about:
I am fairly new to Java 8 concepts. Have I used the new API correctly (and not increased the running time of the operations)?
In the current implementation, there is no way to iterate over the list of the edges. Is this a shortcoming? How can I fix it?
Right now, adding new operations like DFS or weighted shortest path, I will have to change the Graph.java class. How can I improve the design such that adding graph algorithms, does not require changing the graph data class? (Or is there no need to do this)
General comments on code, if any.
Graph.java-
public class Graph<T> {
private Map<T, Node<T>> adjacencyList;
public Graph() {
adjacencyList = new HashMap<>();
}
/**
* Adds a vertex to the graph.
* @param vertex vertex to add
*/
public boolean addVertex(T vertex) {
if (adjacencyList.containsKey(vertex)) {
return false;
}
adjacencyList.put(vertex, new Node<>(vertex));
return true;
}
/**
* Adds a directed edge between two vertices in the graph.
* @param vertex1 vertex where the (directed) edge begins
* @param vertex2 vertex where the (directed) edge ends
*/
public boolean addEdge(T vertex1, T vertex2) {
return addEdge(vertex1, vertex2, 0);
}
/**
* Adds a weighted directed edge between two vertices in the graph.
* @param vertex1 vertex where the (directed) edge begins
* @param vertex2 vertex where the (directed) edge ends
* @param weight weight of the edge
*/
public boolean addEdge(T vertex1, T vertex2, int weight) {
if (!containsVertex(vertex1) || !containsVertex(vertex2)) {
throw new RuntimeException("Vertex does not exist");
}
// add the edge
Node<T> node1 = getNode(vertex1);
Node<T> node2 = getNode(vertex2);
return node1.addEdge(node2, weight);
}
/**
* Remove a vertex from the graph.
* @param vertex vertex to be removed
* @return true if the vertex was removed, false if no such vertex was found.
*/
public boolean removeVertex(T vertex) {
if (!adjacencyList.containsKey(vertex)) {
return false;
}
// get node to be removed
final Node<T> toRemove = getNode(vertex);
// remove all incoming edges to node
adjacencyList.values().forEach(node -> node.removeEdge(toRemove));
// remove the node
adjacencyList.remove(vertex);
return true;
}
/**
* Method to remove a directed edge between two vertices in the graph.
* @param vertex1 vertex where the (directed) edge begins
* @param vertex2 vertex where the (directed) edge ends
* @return true if the edge was removed, false if no such edge was found.
*/
public boolean removeEdge(T vertex1, T vertex2) {
if (!containsVertex(vertex1) || !containsVertex(vertex2)) {
return false;
}
return getNode(vertex1).removeEdge(getNode(vertex2));
}
/**
* Method to get the number of vertices in the graph.
* @return count of vertices
*/
public int vertexCount() {
return adjacencyList.keySet().size();
}
/**
* Method to get the number of edges in the graph.
* @return count of edges
*/
public int edgeCount() {
return adjacencyList.values()
.stream()
.mapToInt(Node::getEdgeCount)
.sum();
}
/**
* Method to check if a vertex exists in the graph.
* @param vertex vertex which is to be checked
* @return returns true if the graph contains the vertex, false otherwise
*/
public boolean containsVertex(T vertex) {
return adjacencyList.containsKey(vertex);
}
/**
* Method to check if an edge exists in the graph.
* @param vertex1 vertex where the (directed) edge begins
* @param vertex2 vertex where the (directed) edge ends
* @return returns true if the graph contains the edge, false otherwise
*/
public boolean containsEdge(T vertex1, T vertex2) {
if (!containsVertex(vertex1) || !containsVertex(vertex2)) {
return false;
}
return getNode(vertex1).hasEdge(getNode(vertex2));
}
/**
* Method to get the shortest path from startVertex to endVertex.
* @param startVertex vertex where the path begins
* @param endVertex vertex where the path ends
* @return list of vertices in the shortest path from startVertex to endVertex,
* null if no such path exists.
*/
@Nullable
public List<T> shortestPath(T startVertex, T endVertex) {
// if nodes not found, return empty path
if (!containsVertex(startVertex) || !containsVertex(endVertex)) {
return null;
}
// run bfs on the graph
runBFS(startVertex);
List<T> path = new ArrayList<>();
// trace path back from end vertex to start
Node<T> end = getNode(endVertex);
while (end != null && end != getNode(startVertex)) {
path.add(end.vertex());
end = end.parent();
}
// if end is null, node not found
if (end == null) {
return null;
}
else {
Collections.reverse(path);
}
return path;
}
private void runBFS(T startVertex) {
if (!containsVertex(startVertex)) {
throw new RuntimeException("Vertex does not exist.");
}
// reset the graph
resetGraph();
// init the queue
Queue<Node<T>> queue = new LinkedList<>();
Node<T> start = getNode(startVertex);
queue.add(start);
// explore the graph
while (!queue.isEmpty()) {
Node<T> first = queue.remove();
first.setVisited(true);
first.edges().forEach(edge -> {
Node<T> neighbour = edge.toNode();
if (!neighbour.isVisited()) {
neighbour.setParent(first);
queue.add(neighbour);
}
});
}
}
private Node<T> getNode(T value) {
return adjacencyList.get(value);
}
private void resetGraph() {
adjacencyList.keySet().forEach(key -> {
Node<T> node = getNode(key);
node.setParent(null);
node.setVisited(false);
});
}
}
Node.java
public class Node<T> {
private T vertex;
private List<Edge<T>> edges;
private Node<T> parent;
private boolean isVisited;
public Node(T vertex) {
this.vertex = vertex;
this.edges = new ArrayList<>();
}
public T vertex() {
return vertex;
}
public boolean addEdge(Node<T> node, int weight) {
if (hasEdge(node)) {
return false;
}
Edge<T> newEdge = new Edge<>(this, node, weight);
return edges.add(newEdge);
}
public boolean removeEdge(Node<T> node) {
Optional<Edge<T>> optional = findEdge(node);
if (optional.isPresent()) {
return edges.remove(optional.get());
}
return false;
}
public boolean hasEdge(Node<T> node) {
return findEdge(node).isPresent();
}
private Optional<Edge<T>> findEdge(Node<T> node) {
return edges.stream()
.filter(edge -> edge.isBetween(this, node))
.findFirst();
}
public List<Edge<T>> edges() {
return edges;
}
public int getEdgeCount() {
return edges.size();
}
public Node<T> parent() {
return parent;
}
public boolean isVisited() {
return isVisited;
}
public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}
public void setParent(Node<T> parent) {
this.parent = parent;
}
}
Edge.java
public class Edge<T> {
private Node<T> node1;
private Node<T> node2;
private int weight;
public Edge(Node<T> node1, Node<T> node2, int weight) {
this.node1 = node1;
this.node2 = node2;
this.weight = weight;
}
public Node<T> fromNode() {
return node1;
}
public Node<T> toNode() {
return node2;
}
public boolean isBetween(Node<T> node1, Node<T> node2) {
return (this.node1 == node1 && this.node2 == node2);
}
}
