A graph can be represented mainly in three different ways: adjacency matrix, adjacency list, and incidence matrix.
An adjacency matrix is a matrix, a table of values, where each value represents an edge and both the rows are the columns that represent the vertices. The values in a matrix can be the members of the entry. The values of the edges can be stored in the matrix itself. There could also be a special value for representing the absence of an edge. The following image shows an adjacency matrix for the graph in Figure 1, where the value of the edge represents the number of edges between the corresponding vertices:
The following things can be noted about an adjacency matrix:
The following code provides an implementation of the graph ADT with the adjacency matrix. We use a two-dimensional array to store the matrix. The ID of any vertex is directly used as the index of the array. This is true for both the array to store the values stored within the vertices and the values stored in the edges, or even the existence of the edges. When we remove a vertex, we don't free its space; we do this so that the IDs of the newer vertices don't get shifted. This improves lookup performance but is wasteful in terms of resources:
public class AdjacencyMatrixGraphWithSparseVertex<V,E> implements Graph<V, E> {
private static class NullEdgeValue{};We create two special objects to signify an edge and a vertex; these objects do not yet hold a value. A null reference refers to the edge or vertex that does not exist:
private NullEdgeValue nullEdge = new NullEdgeValue();
private NullEdgeValue nullVertex = new NullEdgeValue();
Object [][] adjacencyMatrix = new Object[0][];
Object[] vertexValues = new Object[0];A flag determines whether the graph is undirected:
boolean undirected;
public AdjacencyMatrixGraphWithSparseVertex(boolean undirected){
this.undirected = undirected;
}Adding a vertex involves creating a new matrix and an array of vertex values and copying all the older values into it:
@Override
public int addVertex() {
int numVertices = adjacencyMatrix.length;
Object [][] newAdjacencyMatrix = new Object[numVertices+1][];
for(int i=0;i<numVertices;i++){
newAdjacencyMatrix[i] = new Object[numVertices+1];
System.arraycopy(adjacencyMatrix[i],0, newAdjacencyMatrix[i], 0, numVertices);
}
newAdjacencyMatrix[numVertices] = new Object[numVertices+1];
adjacencyMatrix = newAdjacencyMatrix;
Object [] vertexValuesNew = new Object[vertexValues.length+1];
System.arraycopy(vertexValues,0, vertexValuesNew, 0, vertexValues.length);
vertexValuesNew[vertexValues.length] = nullVertex;
vertexValues = vertexValuesNew;
return numVertices;
}Since we don't free any space, removing a vertex simply involves setting values to null. Note that removing a vertex has to be accompanied by the removal of all the associated edges, which is done in a loop:
@Override
public void removeVertex(int id) {
vertexValues[id] = null;
for(int i=0;i<adjacencyMatrix.length;i++){
adjacencyMatrix[id][i] = null;
adjacencyMatrix[i][id] = null;
}
}Adding an edge involves setting a particular position in the adjacency matrix. If the graph is undirected, there will be two updates. This is because the source and target could be interchanged and the adjacency matrix is always symmetric:
@Override
public void addEdge(int source, int target) {
if(adjacencyMatrix[source][target] == null){
adjacencyMatrix[source][target] = nullEdge;
if(undirected){
adjacencyMatrix[target][source] = nullEdge;
}
}else{
throw new IllegalArgumentException("Edge already exists");
}
}The following operation is the simplest of all as it involves setting only one edge to null. In the case of an undirected graph, there would be a corresponding update that would interchange the source and target:
@Override
public void removeEdge(int source, int target) {
adjacencyMatrix[source][target] = null;
if(undirected){
adjacencyMatrix[target][source] = null;
}
}The following is a trivial operation of checking the adjacency matrix:
@Override
public boolean isAdjacent(int source, int target) {
return adjacencyMatrix[source][target] != null;
}For any given source, find all the edges in the same row of the matrix and add them to a linked list that we can return. Note that in a directed graph, it traverses the edges only in the forward direction:
@Override
public LinkedList getNeighbors(int source) {
LinkedList<Integer> neighborList = new LinkedList<>();
for(int i=0;i<adjacencyMatrix.length;i++){
if(adjacencyMatrix[source][i]!=null){
neighborList.appendLast(i);
}
}
return neighborList;
}We store all the values of the vertices in a different array:
@Override
public void setVertexValue(int vertex, V value) {
vertexValues[vertex] = value;
}
@Override
public V getVertexValue(int vertex) {
if(vertexValues[vertex]!=nullVertex)
return (V)vertexValues[vertex];
else
throw new IllegalArgumentException("Vertex "+vertex
+" does not exist");
}The values stored in the edges can be stored in the adjacency matrix itself:
@Override
public void setEdgeValue(int source, int target, E value) {
adjacencyMatrix[source][target] = value;
if(undirected){
adjacencyMatrix[target][source] = value;
}
}
@Override
public E getEdgeValue(int source, int target) {
if(adjacencyMatrix[source][target] != nullEdge) {
return (E) adjacencyMatrix[source][target];
}else {
return null;
}
}
@Override
public boolean isUndirected() {
return undirected;
}
@Override
public BinarySearchTree<Integer> getAllVertices() {
BinarySearchTree<Integer> allVertices = new RedBlackTree<>();
for(int i=0;i<vertexValues.length;i++){
if(vertexValues[i]!=null){
allVertices.insertValue(i);
}
}
return allVertices;
}
@Override
public int maxVertexID() {
return vertexValues.length-1;
}
}Now let's analyze the complexity of the operations we have already discussed:
- Add vertex: Adding a vertex requires us to create a new two-dimensional array with length and w the complexities of the idth |V| and then copy the entire old content to the new array. Here, |V| represents the cardinality of the set V of the vertices. What is the size of the adjacency matrix then? It's a square matrix whose length or width equals |V|, so its size is |V|2. Hence, adding a new edge has this complexity: θ(|V|2).
- Remove Vertex: Removing a vertex involves removing all the edges that correspond to the given vertex. The maximum number of edges that can be associated with a single vertex is |V|, which is the length of a row or column in the adjacency matrix. We must set all the values in the row and column containing the vertex being deleted, so the number of values that need to be changed is calculated as 2|V| - 1. The "minus one" part comes from the fact that the row and column have one edge in common, the edge representing a loop on the node that is being deleted. The common edge is counted twice, both in the row and the column. So one of them must be stopped. Therefore, the complexity of this operation is θ(2|V| - 1) = θ(|V|).
- Add edge and Remove edge: Adding an edge is as simple as setting a special value at a single entry in the adjacency matrix. It has this complexity: θ(1). Removing an edge is just setting null at the same position.
- Adjacent: This operation involves checking whether an edge exists between the given source and target. It checks one entry in the adjacency matrix, hence this complexity: θ(1).
- Neighbors: This operation requires reading all the values in the row of an adjacency matrix. So it requires reading |V| values and possibly adding them to a linked list. Therefore, the complexity of this operation is θ( |V| ).
- Setting and getting values at vertices and edges: These operations require reading/setting a single value into/from the adjacency matrix. These operations are all θ(1).
- Get all vertices: This involves scanning through all the vertices and inserting them in a binary search tree. So this operation is θ( |V| lg |V|).
The trouble with the above graph implementation is that we are unable to recover any space when vertices are deleted. The problem with recovering space is that it changes the indexes of the vertices that are added later. To avoid this, we can choose to have an ID of a vertex that is separate from its index position in the arrays. If we do this, we need to be able to search the index of a vertex with the given ID. This mapping can be done with a self-balancing binary search tree, which is what we are going to do here.
First, we create a separate class that represents a graph vertex. The idea is to allow a comparison to exist on the ID of a vertex. Different graph implementations can then extend this class to accommodate additional data in the graph vertex:
public class GraphVertex<V> implements Comparable<GraphVertex<V>>{
int id;
V value;
public GraphVertex(int id, V value) {
this.id = id;
this.value = value;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
GraphVertex<?> that = (GraphVertex<?>) o;
return id == that.id;
}
@Override
public int hashCode() {
return id;
}
@Override
public int compareTo(GraphVertex<V> o) {
return id - o.id;
}
}With this class available, we can implement our adjacency-matrix-based graph implementation with a dense vertex and edge representation:
public class AdjacencyMatrixGraphWithDenseVertex<V,E> implements Graph<V, E> {First, we extend the GraphVertex class to include an addition field that stores the index of a vertex in the adjacency matrix as well as in the array meant for storing the values of the vertices:
class Vertex extends GraphVertex<V>{
int internalIndex;
public Vertex(int id, V value, int internalIndex) {
super(id, value);
this.internalIndex = internalIndex;
}
public int getInternalIndex() {
return internalIndex;
}
public void setInternalIndex(int internalIndex) {
this.internalIndex = internalIndex;
}
}The nextId variable is used to store the next ID that would be used:
private int nextId;
Special values to represent empty vertices and edges:
private static class NullValue {};
private NullValue nullEdge = new NullValue();
Object [][] adjacencyMatrix = new Object[0][];The following is the binary search tree that stores the vertices with their indexes in the arrays:
RedBlackTree<GraphVertex<V>> vertices = new RedBlackTree<>();
boolean undirected;
public AdjacencyMatrixGraphWithDenseVertex(boolean undirected){
this.undirected = undirected;
}The process of adding involves the same operations as before apart from the extra operation of generating a new ID and storing an entry in the search tree:
@Override
public int addVertex() {
int id = nextId++;
int numVertices = adjacencyMatrix.length;
Object [][] newAdjacencyMatrix = new Object[numVertices+1][];
for(int i=0;i<numVertices;i++){
newAdjacencyMatrix[i] = new Object[numVertices+1];
System.arraycopy(adjacencyMatrix[i],0, newAdjacencyMatrix[i], 0, numVertices);
}
newAdjacencyMatrix[numVertices] = new Object[numVertices+1];
vertices.insertValue(new Vertex(id, null, adjacencyMatrix.length));
adjacencyMatrix = newAdjacencyMatrix;
return numVertices;
}The removal of a vertex now actually involves creating a smaller adjacency matrix and copying all the edges, except the ones associated with the vertex that is being deleted:
@Override
public void removeVertex(int id) {
BinaryTree.Node<GraphVertex<V>> node = vertices.searchValue(new GraphVertex<V>(id, null));
if(node!=null){
int internalId = ((Vertex)(node.getValue())).getInternalIndex();
int numVertices = adjacencyMatrix.length;
Object [][] newAdjacencyMatrix = new Object[numVertices-1][];First, copy all the rows before the one for the vertex being deleted:
for(int i=0;i<internalId;i++){
newAdjacencyMatrix[i] = new Object[numVertices-1];
System.arraycopy(adjacencyMatrix[i],0, newAdjacencyMatrix[i], 0, internalId);
System.arraycopy(adjacencyMatrix[i],internalId+1, newAdjacencyMatrix[i], internalId, numVertices-internalId-1);
}Then, copy all the rows after the one for the vertex being deleted:
for(int i=internalId+1;i<numVertices;i++){
newAdjacencyMatrix[i-1] = new Object[numVertices-1];
System.arraycopy(adjacencyMatrix[i],0, newAdjacencyMatrix[i-1], 0, internalId);
System.arraycopy(adjacencyMatrix[i],internalId+1, newAdjacencyMatrix[i-1], internalId, numVertices-internalId-1);
}
adjacencyMatrix = newAdjacencyMatrix;Now adjust all the indexes of the vertices added after the one that is deleted. We do this by traversing the tree in preorder and updating only when appropriate:
vertices.traverseDepthFirstNonRecursive((gv)->{
if(((Vertex)gv).getInternalIndex()>internalId)
((Vertex)gv).setInternalIndex(((Vertex)gv).getInternalIndex()-1);
}, BinaryTree.DepthFirstTraversalType.PREORDER);
vertices.deleteValue(new GraphVertex<>(id, null));
}else{
throw new IllegalArgumentException("Vertex with id "+id
+" does not exist");
}
}Adding an edge involves setting an entry in the adjacency matrix. However, before doing this, we need to look up the index of the vertex:
@Override
public void addEdge(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode = vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode = vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode!=null && tNode!=null) {
int s = ((Vertex)(sNode.getValue())).getInternalIndex();
int t = ((Vertex)(tNode.getValue())).getInternalIndex();
if(adjacencyMatrix[s][t] == null){
adjacencyMatrix[s][t] = nullEdge;
if(undirected){
adjacencyMatrix[t][s] = nullEdge;
}
}else{
throw new IllegalArgumentException("Edge already exists");
}
}else{
throw new IllegalArgumentException("Non-existent ID");
}
}This is the same as adding an edge, other than the fact that we change the corresponding entry in the adjacency matrix to null:
@Override
public void removeEdge(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode = vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode = vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode!=null && tNode!=null) {
int s = ((Vertex)(sNode.getValue())).getInternalIndex();
int t = ((Vertex)(tNode.getValue())).getInternalIndex();
adjacencyMatrix[s][t] = null;
}else{
throw new IllegalArgumentException("Non-existent ID");
}
}Checking whether two vertices are adjacent involves looking up a value in the adjacency matrix like before. But again, we must first look up the indexes of the vertices:
@Override
public boolean isAdjacent(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode = vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode = vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode!=null && tNode!=null) {
int s = ((Vertex)(sNode.getValue())).getInternalIndex();
int t = ((Vertex)(tNode.getValue())).getInternalIndex();
return adjacencyMatrix[s][t] != null;
}else{
throw new IllegalArgumentException("Non-existent ID");
}
}Getting the list of neighbors is a little trickier. We don't have a search mechanism that lets us search by index to look up the ID. So instead of reading a row in the adjacency matrix, we simply preorder traverse the search tree and check whether there is an edge for the vertex in the adjacency matrix. We add a vertex only when there is an edge between the source vertex and the vertex in question:
@Override
public LinkedList<Integer> getNeighbors(int source) {
BinaryTree.Node<GraphVertex<V>> node = vertices.searchValue(
new GraphVertex<V>(source, null));
if(node!=null){
LinkedList<Integer> neighborsList = new LinkedList<>();
int sourceInternalIndex = ((Vertex) node.getValue()).getInternalIndex();
vertices.traverseDepthFirstNonRecursive((gv)->{
int targetInternalIndex = ((Vertex) gv).getInternalIndex();
if(adjacencyMatrix[sourceInternalIndex][targetInternalIndex]!=null)
neighborsList.appendLast(gv.getId());
}, BinaryTree.DepthFirstTraversalType.INORDER);
return neighborsList;
}else{
throw new IllegalArgumentException("Vertex with id "+source+" does not exist");
}
}The process of setting and getting values into/from the edges and vertices is the same as before, except that we need to look up the index from the ID of the vertex before using it:
@Override
public void setVertexValue(int vertex, V value) {
BinaryTree.Node<GraphVertex<V>> node =
vertices.searchValue(
new GraphVertex<V>(vertex, null));
if(node!=null){
node.getValue().setValue(value);
}else{
throw new IllegalArgumentException("Vertex with id "+vertex+" does not exist");
}
}
@Override
public V getVertexValue(int vertex) {
BinaryTree.Node<GraphVertex<V>> node =
vertices.searchValue(
new GraphVertex<V>(vertex, null));
if(node!=null){
return node.getValue().getValue();
}else{
throw new IllegalArgumentException("Vertex with id "+vertex+" does not exist");
}
}
@Override
public void setEdgeValue(int source, int target, E value) {
BinaryTree.Node<GraphVertex<V>> sNode = vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode = vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode!=null && tNode!=null) {
int s = ((Vertex)(sNode.getValue())).getInternalIndex();
int t = ((Vertex)(tNode.getValue())).getInternalIndex();
adjacencyMatrix[s][t] = value;
if (undirected) {
adjacencyMatrix[t][s] = value;
}
}else{
throw new IllegalArgumentException("Non-existent ID");
}
}
@Override
public E getEdgeValue(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode = vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode = vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode!=null && tNode!=null) {
int s = ((Vertex)(sNode.getValue())).getInternalIndex();
int t = ((Vertex)(tNode.getValue())).getInternalIndex();
return (E) adjacencyMatrix[s][t];
}else{
throw new IllegalArgumentException("Non-existent ID");
}
}
@Override
public boolean isUndirected() {
return undirected;
}
@Override
public BinarySearchTree<Integer> getAllVertices() {
BinarySearchTree<Integer> allVertices = new RedBlackTree<>();
vertices.traverseDepthFirstNonRecursive(
(v) -> allVertices.insertValue(v.getId()),
BinaryTree.DepthFirstTraversalType.PREORDER);
return allVertices;
}
@Override
public int maxVertexID() {
return nextId-1;
}
}The following are the complexities of the operations we just discussed in a dense adjacency-matrix-based graph:
- Add vertex: Addition still has the same θ(|V|2) operation for creating a new adjacency matrix and copying all the old values. The additional operation of inserting a new vertex in the search tree is θ(lg |V|). So the entire operation is still θ(|V|2).
- Remove vertex: The removal of a vertex here follows the same operation of recreating an adjacency matrix and copying all the old values, which is θ(|V|2). The operation of removing a vertex from the search tree is θ(lg |V|). So the entire operation is θ(|V|2).
- Add edge and remove edge: The operation of updating an entry in the adjacency matrix is still θ(1). However, now we need to have two lookups in the search tree to figure out the indexes of the source and target. Both these searches are θ(lg |V|). So the entire operation is θ(lg |V|).
- Adjacent: This is also θ(lg |V|) due to the same reason mentioned in the preceding bullet point.
- Neighbors: Traversing the search tree is θ(|V|), and for each of the vertices thus traversed, we create a constant number of operations. Looking up the index of the source vertex is θ(lg |V|). Hence, the entire operation is still θ(|V|).
- Setting and getting values at vertices and edges: These operations require a fixed number of lookups (one or two) and then a constant time operation for setting or getting the appropriate value. The lookups are θ(lg |V|), so the entire operations are also θ(lg |V|).
- Get all vertices: Just like the previous implementation, this operation is θ( |V| lg |V|).
An adjacency list is a more space-efficient graph representation of sparse graphs. A sparse graph is a graph that has a very few edges as compared to the number of edges in a complete graph with the same number of vertices. A complete graph has |V| ( |V| - 1) / 2 = θ (|V| 2 ) edges, and the memory space required to store a graph as an adjacency matrix is also θ (|V| 2 ). So, in the case of a dense (almost complete) graph, it makes sense to store it as an adjacency matrix. However, this is not true for a sparse graph.
In an adjacency list representation, vertices are stored in an array or some other data structure, and edges are stored along with the vertices in some list or some other structure. First, we will consider an adjacency-list-based representation where the vertices are stored in an array indexed by their IDs, as in the case of a sparse adjacency matrix representation. It has the same problem: we cannot reduce the size of the array of vertices when a vertex is deleted. However, in this case, the list of edges are deleted, and this makes it way more space-efficient than what we encountered in an adjacency matrix:
public class AdjacencyListGraphWithSparseVertex<V,E> implements Graph<V,E> {
boolean undirected;
public AdjacencyListGraphWithSparseVertex(boolean undirected) {
this.undirected = undirected;
}The Edge class stores the details of the target and the value of an edge originating from a vertex. The vertex stores a collection of the associated edges. We make the edge comparable based of the ID of the target so that we can store them in a binary search tree to easily look it up based on the ID:
class Edge implements Comparable<Edge>{
E value;
int target;To improve the performance of the getNeighbors operation, we store a list of neighbors in the node. We store a pointer in the node that corresponds to the target of this node in the targetNode state variable:
DoublyLinkedList.DoublyLinkedNode<Integer> targetNode;
public Edge(int target) {
this.target = target;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Edge edge = (Edge) o;
return target == edge.target;
}
@Override
public int hashCode() {
return target;
}
@Override
public int compareTo(Edge o) {
return target - o.target;
}
}The Vertex class is used to store a vertex along with its associated edges. The edges are stored in a red black tree:
class Vertex extends GraphVertex<V>{
RedBlackTree<Edge>
edges = new RedBlackTree<>();
DoublyLinkedList<Integer> neighbors = new DoublyLinkedList<>();
public Vertex(int id, V value) {
super(id, value);
}
}The vertices are then stored in an array:
Object[] vertices = new Object[0];
Adding a vertex does not require us to copy any edges; it just ensures that the vertices are copied to a newly created array of bigger size:
@Override
public int addVertex() {
Object[] newVertices = new Object[vertices.length+1];
System.arraycopy(vertices, 0, newVertices, 0, vertices.length);
newVertices[vertices.length] = new Vertex(vertices.length, null);
vertices=newVertices;
return newVertices.length-1;
}Removing a vertex requires that you first set the vertex to null at its position. However, you must also remove all the edges from all the other vertices for which the deleted vertex was the target:
@Override
public void removeVertex(int id) {
Vertex sVertex = (Vertex) vertices[id];
if(sVertex==null){
throw new IllegalArgumentException("Vertex "+ id +" does not exist");
}
LinkedList<Integer> neighbors = getNeighbors(id);
Edge dummyEdgeForId = new Edge(id);We must remove all the edges associated with the vertex being deleted:
for(int t:neighbors){
Edge e = ((Vertex)vertices[t]).edges.deleteValue(dummyEdgeForId).getValue();
((Vertex)vertices[t]).neighbors.removeNode(e.targetNode);
}
vertices[id] = null;
}Adding an edge requires making corresponding entries in the vertices associated with it:
@Override
public void addEdge(int source, int target) {
Vertex sVertex = (Vertex) vertices[source];
Edge sEdge = sVertex.edges.insertValue(new Edge(target)).getValue();
sEdge.targetNode = (DoublyLinkedList.DoublyLinkedNode<Integer>)
sVertex.neighbors.appendLast(sEdge.target);
if(undirected){
Vertex tVertex = (Vertex) vertices[target];
Edge tEdge = tVertex.edges.insertValue(new Edge(source)).getValue();
tEdge.targetNode = (DoublyLinkedList.DoublyLinkedNode<Integer>)
tVertex.neighbors.appendLast(tEdge.target);
}
}Removing an edge requires removing the corresponding entries in the associated vertices:
@Override
public void removeEdge(int source, int target) {
Vertex sVertex = (Vertex) vertices[source];
Edge deletedEdge = sVertex.edges.deleteValue(new Edge(target)).getValue();
sVertex.neighbors.removeNode(deletedEdge.targetNode);
if(undirected){
Vertex tVertex = (Vertex) vertices[target];
deletedEdge = tVertex.edges.deleteValue(new Edge(source)).getValue();
tVertex.neighbors.removeNode(deletedEdge.targetNode);
}
}Checking adjacency involves looking up the source vertex first and then looking up an edge for the target in the corresponding red black tree:
@Override
public boolean isAdjacent(int source, int target) {
Vertex sVertex = (Vertex) vertices[source];
return sVertex.edges.searchValue(new Edge(target))!=null;
}We have the list of neighbors precomputed, so we simply return this list:
@Override
public LinkedList<Integer> getNeighbors(int source) {s
Vertex sVertex = (Vertex) vertices[source];
return sVertex.neighbors;
}The process of setting and getting the values of a vertex or an edge are self-explanatory:
@Override
public void setVertexValue(int vertex, V value) {
Vertex sVertex = (Vertex) vertices[vertex];
if(sVertex==null){
throw new IllegalArgumentException("Vertex "+ vertex
+ "does not exist");
}else{
sVertex.setValue(value);
}
}
@Override
public V getVertexValue(int vertex) {
Vertex sVertex = (Vertex) vertices[vertex];
if(sVertex==null){
throw new IllegalArgumentException("Vertex "+ vertex
+ "does not exist");
}else{
return sVertex.getValue();
}
}
@Override
public void setEdgeValue(int source, int target, E value) {
Vertex sVertex = (Vertex) vertices[source];
Vertex tVertex = (Vertex) vertices[target];
if(sVertex==null){
throw new IllegalArgumentException("Vertex "+ source
+ "does not exist");
}else if(tVertex==null){
throw new IllegalArgumentException("Vertex "+ target
+ "does not exist");
}else{
BinaryTree.Node<Edge> node = sVertex.edges.searchValue(new Edge(target));
if(node==null){
throw new IllegalArgumentException("Edge between "+ source + "and" + target + "does not exist");
}else{
node.getValue().value = value;
}
}
}
@Override
public E getEdgeValue(int source, int target) {
Vertex sVertex = (Vertex) vertices[source];
Vertex tVertex = (Vertex) vertices[target];
if(sVertex==null){
throw new IllegalArgumentException("Vertex "+ source
+ "does not exist");
}else if(tVertex==null){
throw new IllegalArgumentException("Vertex "+ target
+ "does not exist");
}else{
BinaryTree.Node<Edge> node =
sVertex.edges.searchValue(new Edge(target));
if(node==null){
throw new IllegalArgumentException("Edge between "+ source + "and" + target + "does not exist");
}else{
return node.getValue().value;
}
}
}
@Override
public boolean isUndirected() {
return undirected;
}
@Override
public BinarySearchTree<Integer> getAllVertices() {
BinarySearchTree<Integer> allVertices = new RedBlackTree<>();
for(int i=0;i<vertices.length;i++){
if(vertices[i]!=null){
allVertices.insertValue(i);
}
}
return allVertices;
}
@Override
public int maxVertexID() {
return vertices.length-1;
}
}The following lists the complexities of the operations we have discussed in an adjacency-list-based graph:
- Add vertex: Addition of a vertex requires that you create a new array first and then copy all the vertices to it. So it is θ(|V|).
- Remove Vertex: The removal process does not change the array of the vertices. However, this operation involves checking each vertex to remove the edges which has the vertex being deleted as the target. So this operation is θ(|V|) as well.
- Add edge and remove edge: The first step of this operation is to look up the source vertex, which is constant time. The second step is to add or remove an edge in a red black tree, so it is θ(lg |V|). So the entire operation of adding/deleting an edge is θ(lg |V|).
- Adjacent: The first step of this operation is to look up the source vertex, which is constant time. The second step is to look up the edge in a red black tree, so it is θ(lg |V|). So the entire operation of adding/deleting an edge is θ(lg |V|).
- Neighbors: Since the list of neighbors is precomputed, the complexity is the same as that for looking up a vertex, which is constant time.
- Setting and Getting values at vertices: These operations require looking up the vertex first, which is constant time. The second step is setting/getting the value. These operations are θ(1).
- Setting and Getting values at edges: These operations require looking up the source vertex first and then looking up the particular edge. The first is θ(1) and the second is θ(lg |V|). At the end, setting or getting the value of an edge is θ(l). Hence, the total operation is θ(lg |V|).
- Get all vertices: This operation is θ( |V| lg |V| ), just like the previous implementations.
Just as in the case of an adjacency-matrix-based graph, dense storage of vertices can be done using a search tree instead of an array. This allows us to recover space when we delete a vertex without affecting the IDs of the other vertices. Everything else remains the same as the array-based storage of the vertices:
public class AdjacencyListGraphWithDenseVertex<V,E> implements Graph<V,E> {The nextId variable stores the value that would be the ID of the next vertex that is inserted:
int nextId;
boolean undirected;We have the Edge and Vertex class as before:
class Edge implements Comparable<Edge>{
E value;
int target;
DoublyLinkedList.DoublyLinkedNode<Integer> targetNode;
public Edge(int target) {
this.target = target;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Edge edge = (Edge) o;
return target == edge.target;
}
@Override
public int hashCode() {
return target;
}
@Override
public int compareTo(Edge o) {
return target - o.target;
}
}
class Vertex extends GraphVertex<V>{
RedBlackTree<Edge> edges = new RedBlackTree<Edge>();
DoublyLinkedList<Integer> neighbors
= new DoublyLinkedList<>();
public Vertex(int id, V value) {
super(id, value);
}
}
public AdjacencyListGraphWithDenseVertex(boolean undirected) {
this.undirected = undirected;
}Now, instead of using an array to store the vertices, use a red black tree:
RedBlackTree<GraphVertex<V>> vertices = new RedBlackTree<>();
Adding a new vertex means inserting a new one in the red black tree:
@Override
public int addVertex() {
vertices.insertValue(new Vertex(nextId++, null));
return nextId;
}The removal process, as before, involves not only removing the vertex but also going through all the other vertices and deleting every edge that has the vertex that is being deleted as the target:
@Override
public void removeVertex(int id) {
vertices.deleteValue(new GraphVertex<V>(id, null));
vertices.traverseDepthFirstNonRecursive((gv)->{
BinaryTree.Node<Edge> edgeNode = ((Vertex) gv).edges.deleteValue(new Edge(id));
if(edgeNode!=null){
Edge edge = edgeNode.getValue();
((Vertex) gv)
.neighbors.removeNode(edge.targetNode);
}
},
BinaryTree.DepthFirstTraversalType.INORDER);
}The first step is to find the source and the target node to confirm that they exist. After this, add an edge to the collection of edges of the source node. If the graph is undirected, add an edge to the collection of edges in the target node as well:
@Override
public void addEdge(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode =
vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID "+source+" does not exist");
}else if(tNode == null){
throw new IllegalArgumentException("Vertex ID "+target+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
Vertex tVertex = (Vertex) tNode.getValue();
Edge tEdge = new Edge(target);
sVertex.edges.insertValue(tEdge);
tEdge.targetNode = (DoublyLinkedList.DoublyLinkedNode<Integer>) sVertex.neighbors
.appendLast(tVertex.getId());
if(undirected) {
Edge sEdge = new Edge(source);
tVertex.edges.insertValue(sEdge);
sEdge.targetNode = (DoublyLinkedList.DoublyLinkedNode<Integer>) tVertex.neighbors
.appendLast(sVertex.getId());
}
}
}The first step is the same as that of the previous one. After this, the edge is removed from the collection of the edges of the source node. If the graph is undirected, the edge is also removed from the collection of edges in the target node:
@Override
public void removeEdge(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode =
vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID "+source+" does not exist");
}else if(tNode == null){
throw new IllegalArgumentException("Vertex ID "+target+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
Edge deletedEdge = sVertex.edges.deleteValue(new Edge(target)).getValue();
sVertex.neighbors.removeNode(deletedEdge.targetNode);
if(undirected) {
Vertex tVertex = (Vertex) tNode.getValue();
deletedEdge = tVertex.edges.deleteValue(new Edge(source)).getValue();
tVertex.neighbors.removeNode(deletedEdge.targetNode);
}
}
}The first step is the same as that of the previous one. After this, the edge with the correct target is looked up. If the edge is found, the vertices are adjacent:
@Override
public boolean isAdjacent(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode =
vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID "
+source+" does not exist");
}else if(tNode == null){
throw new IllegalArgumentException("Vertex ID "
+target+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
return sVertex.edges.searchValue(
new Edge(target)) != null;
}
}We just look up the vertex and then return our precomputed list of neighbors:
@Override
public LinkedList<Integer> getNeighbors(int source) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(source, null));
if(sNode == null){
throw new IllegalArgumentException(
"Vertex ID "+source+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
return sVertex.neighbors;
}
}The process of setting and getting values is the same as before, except that we need to look up the vertex/vertices in the red black tree instead of the array before setting up the values:
@Override
public void setVertexValue(int vertex, V value) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(vertex, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID "
+vertex+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
sVertex.setValue(value);
}
}
@Override
public V getVertexValue(int vertex) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(vertex, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID "
+vertex+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
return sVertex.getValue();
}
}
@Override
public void setEdgeValue(int source, int target, E value) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode =
vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID
"+source+" does not exist");
}else if(tNode == null){
throw new IllegalArgumentException("Vertex ID
"+target+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
BinaryTree.Node<Edge> edgeNode =
sVertex.edges.searchValue(new Edge(target));
if(edgeNode!=null) {
edgeNode.getValue().value = value;
if (undirected) {
Vertex tVertex = (Vertex) tNode.getValue();
edgeNode = tVertex.edges
.searchValue(new Edge(source));
edgeNode.getValue().value = value;
}
}else{
throw new IllegalArgumentException(
"No edge exists between the vertices "
+ source + " and " + target);
}
}
}
@Override
public E getEdgeValue(int source, int target) {
BinaryTree.Node<GraphVertex<V>> sNode =
vertices.searchValue(
new GraphVertex<V>(source, null));
BinaryTree.Node<GraphVertex<V>> tNode =
vertices.searchValue(
new GraphVertex<V>(target, null));
if(sNode == null){
throw new IllegalArgumentException("Vertex ID
"+source+" does not exist");
}else if(tNode == null){
throw new IllegalArgumentException("Vertex ID
"+target+" does not exist");
}else{
Vertex sVertex = (Vertex) sNode.getValue();
BinaryTree.Node<Edge> edgeNode =
sVertex.edges.searchValue(new Edge(target));
if(edgeNode!=null) {
return edgeNode.getValue().value;
}else{
throw new IllegalArgumentException(
"No edge exists between the vertices "
+ source + " and " + target);
}
}
}
@Override
public boolean isUndirected() {
return undirected;
}
@Override
public BinarySearchTree<Integer> getAllVertices() {
BinarySearchTree<Integer> allVertices
= new RedBlackTree<>();
vertices.traverseDepthFirstNonRecursive(
(v) -> allVertices.insertValue(v.getId()),
BinaryTree.DepthFirstTraversalType.PREORDER);
return allVertices;
}
@Override
public int maxVertexID() {
return nextId -1;
}
}The complexity of the operations of an adjacency-list-based graph is as follows:
- Add vertex: Addition of a vertex requires insertion of one in the red black tree. So this operation is θ(lg |V|).
- Remove Vertex: The removal process requires deletion of the vertex from the red black tree, which is θ(lg |V|). However, this operation involves checking each vertex to remove the edges which has the vertex being deleted as the target. So this operation is θ(|V|) as well.
- Add edge and remove edge: The first step of this operation is to look up the source vertex, which is θ(lg |V|). The second step is to add or remove an edge to/from a red black tree, so this is also θ(lg |V|). Therefore, the entire operation of adding/deleting an edge is θ(lg |V|).
- Adjacent: The first step of this operation is to look up the source vertex, which is θ(lg |V|). The second step is to look up the edge in a red black tree, which is θ(lg |V|) too. Therefore, the entire operation of adding/deleting an edge is θ(lg |V|).
- Neighbors: The list of neighbors is precomputed, so the complexity of this operation is the same as that of searching a vertex, which is θ(lg |V|).
- Setting and getting values at vertices: These operations require you to first look up the vertex, which is θ(lg |V|). The second step is to set/get the value. These operations are θ(lg |V|).
- Setting and getting values at edges: These operations require you to first look up the source vertex and then the particular edge. Both of these operations are θ(lg |V|). At the end, setting or getting the value of an edge is θ(l). Hence, the total operation is θ(lg |V|).
- Get all vertices: Here too, this operation is θ( |V| lg |V|).