02. Adjacency Matrices

We will now implement a graph in Java using adjacency matrices. Look back to the previous lesson to see our abstract base class Graph.

Example graph data structure.
Example of a digraph. We'll use this instance to explain graphs.

Adjacency Matrices

One way to represent graphs is through adjacency matrices. Given a graph with |V| vertices, we create an |V| x |V| 2d matrix.

If there exists an edge from one vertex (column) to another (row), we place a 1 there. If not, then we place a 0. If we had a weighted graph, we can place any non-zero element in lieu of 1.

    0 1 2 3 4 5 6
  ---------------
0 | 0 1 1 0 0 0 0
1 | 0 1 0 1 1 1 0 
2 | 0 0 0 0 0 0 0 
3 | 0 0 0 0 0 0 0
4 | 0 0 0 0 0 0 0 
5 | 0 1 0 0 0 0 1
6 | 0 0 0 0 0 0 0

Let's consider some basic efficiencies. Storing this graph would take |V|2 space. Finding whether or not an edge exists, or adding an edge between two vertices would take O(1) time since all we have to do is a quick lookup.

Checking if an edge exists

Below are two functions that check whether two vertices are connected. The inEdgeExists(int v, int w) method checks if there exists an edge that goes from w to v. The outEdgeExists(int v, int w) function checks if an edge goes from w to v.

| public boolean inEdgeExists(int v, int w) throws VertexOutOfBoundsException {
|     return outEdgeExists(w,v);
| }
| 
| public boolean outEdgeExists(int v, int w)  throws VertexOutOfBoundsException {
|   int numV = getNumVertices();
|   if (v >= numV || w >= numV) {
|     throw new VertexOutOfBoundsException();
|   }
|     return adjMatrix[w][v] != 0;
| }

The runtime efficiency is just O(1) since we just need to access a single cell in the array.

Adding a Vertex

Adding a vertex is more tedious. A naive approach to this problem would be creating a new 2d array of |V|+1 size each time a new vertex is added. We can then copy all the old elements to this new array.

A better way of doing this would be to anticipate the addition of more vertices and create a new array of 2*|V| size everytime we fill up more than 1/2 the current array. This will limit the number of instances where we have to resize our matrix.

public void addVertex() {
    // If the number of vertices is more than half the size of our matrix, 
    // double the size of our matrix
    int numV = getNumVertices();
    if (numV > 0.5 * size) {
        size = 2*size;
        int[][] newAdjMatrix = new int[size][size];
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < adjMatrix[0].length; j++) {
                newAdjMatrix[i][j] = adjMatrix[i][j];
            }
        }
        adjMatrix = newAdjMatrix;
    }
    setNumVertices(numV+1);
}

Deleting a Vertex

Conversely, when deleting a vertex, we can shrink our matrix's dimensions to half its original size to save space.

public void removeVertex() throws VertexOutOfBoundsException {
    int numV = getNumVertices();
    if (numV == 0) {
      throw new VertexOutOfBoundsException();
    }
    if (size < 0.5 * numV) {
        size = (int) 0.5*size;
        int[][] newAdjMatrix = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                newAdjMatrix[i][j] = adjMatrix[i][j];
            }
        }
        adjMatrix = newAdjMatrix;
    }
    setNumVertices(numV-1);
}

Both adding and removing a vertex can take up to |V|2 time.

Adding an Edge

Adding an edge is as simple as inserting a value into our array matrix.

public void addEdge(int v, int w) throws VertexOutOfBoundsException {
    int numV = getNumVertices();
    if (v >= numV || w >= numV) {
      throw new VertexOutOfBoundsException();
    }
    adjMatrix[v][w] = 1;
    setNumEdges(getNumEdges()+1);
}

Removing an Edge

To remove an edge, simply set that edge's cell to zero.

public void removeEdge(int v, int w) throws VertexOutOfBoundsException {
    int numV = getNumVertices();
    if (v >= numV || w >= numV) {
      throw new VertexOutOfBoundsException();
    }
    adjMatrix[v][w] = 0;
    setNumEdges(getNumEdges()-1);
}

Finding in/out-degree

Finding the in or out-degree of a node takes just |V| time. Simply add 1 for every non-zero element in the corresponding column or row.

public int getInDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (v >= numV) {
    throw new VertexOutOfBoundsException();
  }
    // Count the number of in-degrees
    int count = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if (adjMatrix[i][v] != 0) {
            count++;
        }
    }
    return count;
}
 
public int getOutDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (v >= numV) {
    throw new VertexOutOfBoundsException();
  }
    // Count the number of in-degrees
    int count = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if (adjMatrix[v][i] != 0) {
            count++;
        }
    }
    return count;
}

Finding degree sequence

The degree sequence of a graph is an ordered descending list containing the degrees of each vertex in the graph. The degree sequence is an invariant of the graph can may be used to analyze graph properties.

To find the degree sequence, we have to sum up the in and out-degrees, add them to a list, then sort them in descending order. We can place this in our abstract Graph class.

public List<Integer> getDegreeSeq() throws VertexOutOfBoundsException {
    List<Integer> degreeSeq = new ArrayList<Integer>();
    int degrees = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        degrees = getInDegree(i) + getOutDegree(i);
        degreeSeq.add(degrees);
    }
    Collections.sort(degreeSeq);
    Collections.reverse(degreeSeq);
    return degreeSeq;
} 

Getting all Adjacent Neighbors

To find all neighbors of a vertex, find all non-zero elements in that vertex's row and column.

public List<Integer> getNeighbors(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (v >= numV) {
    throw new VertexOutOfBoundsException();
  }
    List<Integer> neighbors = new ArrayList<Integer>();
    for (int i = 0; i < getNumVertices(); i++) {
        if (adjMatrix[v][i] != 0) {
            neighbors.add(i);
        }
    }
    return neighbors;
}

Getting all two-distanced neighbors

To find all neighbors two nodes apart, we could use the neighbors() method twice...or...we can use a special property of matrices and square the adjacent matrix. All non-zero elements in this squared matrix contains the two-distanced neighbors! Neat! We can even cube our matrix to find all three-distanced neighbors and so on.

public List<Integer> getNeighborsTwoApart(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (v >= numV) {
    throw new VertexOutOfBoundsException();
  }
    List<Integer> neighbors = new ArrayList<Integer>();
    int[][] sqMatrix = new int[size][size];
    for (int i = 0; i < numV; i++)
        for (int j = 0; j < numV; j++)
            for (int k = 0; k < numV; k++)
                sqMatrix[i][j] += adjMatrix[i][k] * adjMatrix[k][j];
    for (int i = 0; i < numV; i++) {
        if (sqMatrix[i][v] != 0 || sqMatrix[v][i] != 0) {
            neighbors.add(i);
        }
    }
    return neighbors; 
}

Notice any ways you can improve this implementation? Comment below!

Ace your Technical Interview

Programming Interviews: Exposed

Ace your Technical Interview Try Algorithms

In today's tight job market, competition for programming jobs is hotter than ever. This third edition of a popular guide to programming interviews includes new code examples, information on the latest languages, new chapters on sorting and design patterns, tips on using LinkedIn, and a downloadable app to help prepare applicants for the interview.

$ Check price
29.9929.99Amazon 4.5 logo(94+ reviews)

More Algorithms resources

Aching back from coding all day?

Inversion Therapy Table

Aching back from coding all day? Try Back Problems

Stretch out your back and relieve your back muscles with inversion therapy. This device counteracts the forces of gravity on the body by decompressing and elongating the spine. By using this product just ten minutes a day, you can be well on your way to improved circulation and posture while relieving muscle aches, back pain and stress.

$$ Check price
119.98119.98Amazon 4.5 logo(1,700+ reviews)

More Back Problems resources

Ad