Graph Data Structures

Read Algorithms 4.1 and Algorithms 4.2

Here is a video lecture for today's lesson.

The video contains sections on

1. Adjacency list (0:34)
2. Adjacency matrix (9:52)
3. Visualizations (16:36)
4. Implementing a Graph class (19:39)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=083f8239-928a-4429-b957-acdb016f0384

After this lesson you will be able to

1. Describe two data structures for representing graphs: the adjacency list and the adjacency matrix
2. Choose the appropriate data structure based on graph properties and desired operations
3. Implement an adjacency list in Java

• Assign each node a number from 0 to \(|V|-1\)
• Represent graph as an array of length \(|V|\) in which each entry stores a list of all adjacent vertices (e.g., linked list)

• Running time to:
  • Get all of a vertex's out-edges: \(O(d)\) where \(d\) is out-degree of vertex
  • Get all of a vertex's in-edges: \(O(|E|)\) (but could keep a second adjacency list for this!)
  • Decide if some edge exists: \(O(d)\) where \(d\) is out-degree of source
  • Insert an edge: \(O(1)\) (unless you need to check if it's there)
  • Delete an edge: \(O(d)\) where \(d\) is out-degree of source
• Space requirements: \(O(|V|+|E|)\)
• Best for dense or sparse graphs?
  • Best for sparse graphs (so lists of neighbors are short)

• Assign each node a number from 0 to \(|V|-1\)
• Represent the graph as a \(|V| \times |V|\) matrix (i.e., 2-D array) of Booleans (or 1 vs. 0)
• If M is the matrix, then M[u][v] being true means there is an edge from u to v

• Running time to:
  • Get a vertex's out-edges: \(O(|V|)\)
  • Get a vertex's in-edges: \(O(|V|)\)
  • Decide if some edge exists: \(O(1)\)
  • Insert an edge: \(O(1)\)
  • Delete an edge: \(O(1)\)
• Space requirements: \(|V|^2\) matrix entries
• Best for sparse or dense graphs?
  • Best for dense graphs (the matrix can handle large numbers of edges more efficiently than the adjacency list)

https://visualgo.net/en/graphds

For this implementation of an adjacency list, I use hash tables (HashMap and HashSet) instead of an array of linked lists to make the coding easier. This is a tradeoff of space (a HashSet may have unused spots in its internal array whereas a LinkedList would not) for time (checking whether an edge exists becomes \(O(1)\) instead of \(O(d)\)). The logic of the data structure remains the same.

/**
 * An implementation of an undirected graph using an adjacency list 
 * Vertex labels are strings 
 * (c) 2021 Aaron Bauer
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Graph {
    Map<String, Set<String>> adjList; // maps vertices to a set of their neighbors

    public Graph() {
        adjList = new HashMap<>();
    }

    public void addVertex(String v) {
        if (!adjList.containsKey(v)) {
            adjList.put(v, new HashSet<String>());
        }
    }

    public void addEdge(String u, String v) {
        // adding an edge will also add the vertices to the graph if needed
        addVertex(u);
        addVertex(v);
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }

    // return a set of the vertices in the graph
    public Set<String> V() {
        // construct a new HashSet that's a copy of the key set for adjList
        // so that changes to the returned set don't affect the graph
        return new HashSet<>(adjList.keySet());
    }

    public Iterable<String> neighbors(String v) {
        // construct a new HashSet that's a copy of the set of neighbors
        // so that changes to the returned set don't affect the graph
        return new HashSet<>(adjList.get(v));
    }

    public void removeVertex(String v) {
        for (String u : neighbors(v)) {
            adjList.get(u).remove(v);
        }
        adjList.remove(v);
    }

    public void removeEdge(String u, String v) {
        adjList.get(u).remove(v);
        adjList.get(v).remove(u);
    }

    public boolean containsVertex(String v) {
        return adjList.containsKey(v);
    }

    public boolean containsEdge(String u, String v) {
        return containsVertex(u) && containsVertex(v) && adjList.get(u).contains(v);
    }
}  

1. Draw the adjacency matrix and list representations of the following (undirected and complete) graph:

   

2. Draw the adjacency matrix and list representations of the following (directed) graph:

   

3. Draw the adjacency matrix and list representations of a full binary tree with seven nodes and undirected edges.
4. Compare and contrast the performance of the adjacency list and adjacency matrix implementations of graphs.

• Lab 7 posted later today
• A little behind on some of the grading, should get caught up this week
• More information about the take-home final exam coming this week
• Summary
  • Two primary ways to represent a graph
    • Adjacency list
      • For each vertex, keep a list of its neighbors
      • Time efficient for get-all-out-edges, space efficient for sparse graphs
    • Adjacency matrix
      • Keep a \(|V| \times |V|\) grid where each entry indicates whether there is an edge between a pair of vertices
      • Time efficient for does-this-edge-exist, space efficient for dense graphs
  • Java implementation of an adjacency list
• Questions?
• Form question
  • Discuss in pods
• Exercise in pods
  • Using the adjacency list implementation above as a starting point, implement a Graph class that uses an adjacency matrix
  • The type for a 2D array in Java is TYPE[][], such as boolean[][] matrix
  • Really just an array of arrays (not a matrix in the mathematical sense)
  • matrix = new boolean[10][10]; would create a 10-by-10 2D array of booleans
  • You access element in row i and column j like matrix[i][j]
  • Your constructor can take in the number of vertices (e.g., you don't need to support adding or removing vertices, just edges)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class GraphMatrix {
    private Map<String, Integer> indexLookup;
    private Map<Integer, String> reverseLookup;
    private int nextIndex;
    private boolean[][] adjMatrix;

    public GraphMatrix(int V) {
        adjMatrix = new boolean[V][V];
        indexLookup = new HashMap<>();
        reverseLookup = new HashMap<>();
        nextIndex = 0;
    }

    private int validateVertex(String v) {
        if (nextIndex == adjMatrix.length) {
            throw new IndexOutOfBoundsException("More than " + adjMatrix.length + " vertices have been added to the graph");
        }
        if (!indexLookup.containsKey(v)) {
            indexLookup.put(v, nextIndex++);
            reverseLookup.put(indexLookup.get(v), v);
        }
        return indexLookup.get(v);
    }

    public void addEdge(String u, String v) {
        int i = validateVertex(u);
        int j = validateVertex(v);
        adjMatrix[i][j] = true;
    }

    public void removeEdge(String u, String v) {
        int i = validateVertex(u);
        int j = validateVertex(v);
        adjMatrix[i][j] = false;
    }

    // return an iterable of the vertices neighboring v
    public Iterable<String> neighbors(String v) {
        int i = validateVertex(v);
        ArrayList<String> result = new ArrayList<>();
        for (int j = 0; j < adjMatrix.length; j++) {            
            if (adjMatrix[i][j])
                result.add(reverseLookup.get(j));
        }
        return result;
    }

    // return the degree of vertex v
    public int degree(String v) {
        int i = validateVertex(v);
        int result = 0;
        for (int j = 0; j < adjMatrix.length; j++) {
            if (adjMatrix[i][j])
                result++;
        }
        return result;
    }
}