Introduction to Graphs

In the real world, there will be objects that have relationships with one another. For example, you (an object) are in friendships (relation) with peers on Facebook. Can we represent this relation using a data structure? In order to best represent these relationship of objects, we may use the graph data structure.

What are graphs?

Graphs are a particular data structure that define vertices, connected to one another via edges. Mathematically, a graph is represented by G = (V, E). The vertices (V) can be drawn in as nodes, while the edges (E) connect the nodes together.

Examples of graphs in the real world

There are plenty of instances where the use of a graph can be used in the real world.

• A network of friends in social media.
• A map - each intersection is a node, and each street/road is an edge.
• Websites - each website is a node and each external link is an edge to another site.

Example graph

Vertices are represented by the vector V, and edges are displayed as E. The number of vertices in a graph is |V|, and the number of edges |E|. Edges may or may not have a direction. In the example above, they do. Graphs with edges that have a direction are known as digraphs, and those without are known as undirected.

Graph terms

Here are a list of basic graph terms you may come across.

Self-loop

An edge that starts and ends at the same vertex.

The vertex 1 has a self-loop in our example above.

Neighbor

Vertex A is a neighbor of B if there exists an edge connecting A to B.

The neighbors of 1 include 0,1,2,3,4 and 5.

Connected

A graph is connected is there exists a path from every vertex to every other vertex in the graph.

Our example is not connected since there it is directed and there is no path that visits every point on the graph.

In-degree

The number of edges pointing into a vertex.

The in-degree of vertex 1 is 4.

Out-degree

The number of edges pointing out of a vertex.

The out-degree of vertex 1 is also 4.

Degree Sequence

An ordered sequence of each vertices' degrees (in-degree + out-degree) in decreasing order.

Parallel edges

Two edges that connect to the same pair of vertices.

There are no parallel edges in our graph.

Multigraph

A graph containing parallel edges.

Simple Graph

A graph containing no parallel edges.

Our example graph is a simple graph.

Dense/Sparse

Dense if lots of vertices are connected to one another. The opposite of a dense graph is a sparse one.

Bipartite graph

A graph whose vertices that can be divided into two sets such that all edges connect a vertex in one set with a vertex in the other set.

Path

A sequence of vertices connected by edges. Its length is represented by the number of edges.

Simple path

A path with no repeat visits of vertices.

Cycle

A path in which with at least one edge where the first and last vertices are the same.

Simple Cycle

Cycle with no repeated edges or vertices.

We can specify a graph with V vertices with numbers 0 to V-1.

Types of graphs

There exists four types of graphs:

Undirected

Connections edges are undirected.

Directed

Each edge has a direction.

Edge-weighted

Each connection has a weight.

Edge-weighted digraph

Each connection has a direction and a weight.

Now that we understand what graphs are, let's look at how we would implement them in Java.

There are several ways to represent graphs, so let's start with an abstract base class.

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public abstract class Graph {
    private int numVertices;
    private int numEdges;
    public Graph() {
        numVertices = 0;
        numEdges = 0;
    }
    public int getNumVertices() {
        return numVertices;
    }
    public int getNumEdges() {
        return numEdges;
    }
 
    public void setNumVertices(int v) {
        numVertices = v;
    }
    public void setNumEdges(int e) {
        numEdges = e;
    }
    public abstract boolean inEdgeExists(int v, int w) throws VertexOutOfBoundsException;
    public abstract boolean outEdgeExists(int v, int w) throws VertexOutOfBoundsException;
    public abstract void addVertex();
    public abstract void addEdge(int v, int w) throws VertexOutOfBoundsException;
    public abstract void removeVertex() throws VertexOutOfBoundsException;
    public abstract void removeEdge(int v, int w) throws VertexOutOfBoundsException;
    public abstract int getInDegree(int v) throws VertexOutOfBoundsException;
    public abstract int getOutDegree(int v) throws VertexOutOfBoundsException;
    public abstract List<Integer> getNeighbors(int v) throws VertexOutOfBoundsException;
    public abstract List<Integer> getNeighborsTwoApart(int v) throws VertexOutOfBoundsException;
    
    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;
    }
}

Our implementation of different types of graphs should extend this abstract Graph class. In addition to this class, let's also define our own custo exception:

import java.lang.Exception;
public class VertexOutOfBoundsException extends Exception {
  public VertexOutOfBoundsException() {
    super();
  }
  public VertexOutOfBoundsException(String message) {
    super(message);
  }
}

In the next lesson, let's learn how to extend this base class to implement a graph structure with an adjacency matrix.

subgraph - subset of a graph's edges. acyclic graph = graph w no cycles disjoint set of trees = forest spanning tree = subgraph that contains al of the graph's vertices and is a single tree spanning forest = union of spanning trees of its connected components

Trees

A tree is a particular type of graph where the following statements hold:

1. Trees have V-1 edges and no cycles.
2. Each edge is connected.
3. Removing any one edge disconnects the tree.
4. The graph G is acyclic, but adding any edge creates a cycle.
5. There exists exactly one simple path that connects each pair of vertices in G.

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.

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|² 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|² 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!

Adjacency List

In an adjacency list implementation, we have an array of |V| vertices. Within each array cell, we place a list containing all of that vertex's neighbors.

In this implementation, we can see how easy it is to add vertices and remove them. In a sparse graph, the efficiency is on average O(1).

The space it takes it O(E+V), much less than adjacency matrix implementation.

Adding a Vertex

Adding a vertex is simple. Just append a new vertex containing an empty list to the end of our ArrayList.

public void addVertex() {
    int v = getNumVertices();
    ArrayList<Integer> neighbors = new ArrayList<Integer>();
    adjListsMap.put(v, neighbors);
    setNumVertices(v+1);
}

Deleting a Vertex

To deleting a vertex, we remove the last ArrayList in our Map.

public void removeVertex() throws VertexOutOfBoundsException {
    // Remove the vertex at the end
    int numV = getNumVertices();
    if (numV == 0)
      throw new VertexOutOfBoundsException();
    adjListsMap.remove(numV);
    setNumVertices(numV+1);
}

Adding an Edge

To add an edge, simply retrieve the ArrayList corresponding to the beginning vertex in our Map, then append the value of the end vertex.

public void addEdge(int v, int w) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v || numV <= w) {
    throw new VertexOutOfBoundsException();
  }
    (adjListsMap.get(v)).add(w);
    setNumEdges(getNumEdges()+1);
}

Removing an Edge

To remove an edge that starts from v and goes to w, remove it from the vertex's list.

public void removeEdge(int v, int w) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v || numV <= w) throw new VertexOutOfBoundsException();
    // Remove edge that starts from v to w
    (adjListsMap.get(v)).remove(w);
    setNumEdges(getNumEdges()+1);
}

Finding in/out-degree

To find the in-degree, find the size of the corresponding vertex in the adjacency list. For out-degree, we must traverse through all ArrayLists in the entire adjacency list and count the number of times our vertex appears.

public int getInDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
    int count = 0;
    for (int i = 0; i < getNumVertices(); i++) {
        if ( (adjListsMap.get(i)).contains(v) ) {
            count++;
        }
    }
    return count;
}
public int getOutDegree(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
    return (adjListsMap.get(v)).size();
}

Finding degree sequence

The degree sequence is the same as the Adjacency Matrix implementation.

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 obtain a list of all adjacent neighbors, simply return a copy of the list stored in our List.

public List<Integer> getNeighbors(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
  
    List<Integer> neighbors = new ArrayList<Integer>();
    for (Integer x : adjListsMap.get(v)) {
      neighbors.add(x);
    }
    
    return neighbors;
}

Getting all two-distanced neighbors

For getting all two-distanced neighbors, find all one-distanced neighbors, then find the neighbors of those.

public List<Integer> getNeighborsTwoApart(int v) throws VertexOutOfBoundsException {
  int numV = getNumVertices();
  if (numV <= v) throw new VertexOutOfBoundsException();
  
    List<Integer> oneApart = getNeighbors(v);
    ArrayList<Integer> twoApart = new ArrayList<Integer>();
    // For each integer within one hop of v...
    for (int i = 0; i < oneApart.size(); i++) {
        for (Integer x : oneApart) {
            twoApart.add(x);
        }
    }
    return twoApart;
}

Calculate the efficiencies of these operations and compare them to our Adjacency Matrix implementation!