Using Graphs in Java

There are many libraries to do this, but let’s build a class from scratch. We’ll be using an adjacency list to store the information of the graph.

Class
import java.util.*;

public class Graph {
    // Number of nodes within graph
    private int nodes;
    // Linked List to represent edges on graph
    /*
     * Reminder: Each value in a linked list points to another value
     * So, we can make an array of linked lists to represent all the connections to a node
     * BONUS: Why is this more efficient than a 2D Array List?
     */
    private LinkedList<Integer>[] adjacencyList;

    // Constructor
    public Graph(int nodes) {
        this.nodes = nodes;
        // Create list LinkedLists of size nodes
        adjacencyList = new LinkedList[nodes];

        // Instantiate adjacency list with new LinkedLists
        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }
}
Population and Display

Now, we have a representation. However, we need a way to populate the graph with data. So, we need an addEdge method. We also will need a way to display the graph.

import java.util.*;

public class Graph {

    private int nodes;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int nodes) {
        this.nodes = nodes;
        adjacencyList = new LinkedList[nodes];

        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // addEdge
    /*
     * Popcorn Hack #2
     * Is this addEdge method for a directed or directionless graph?
     * How can we make it the other type of graph?
     */
    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source);
    }

    // Display Graph
    public void displayGraph() {
        System.out.println("Graph adjacency list:");
        // Iterate through every node
        for (int i = 0; i < nodes; i++) {
            // header
            System.out.print(i + " -> ");
            for (int neighbor : adjacencyList[i]) {
                // print out every adjacent node
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    
    public void addNode() {
        this.nodes++;
        LinkedList<Integer>[] newAdj = new LinkedList[nodes];
        for (int i = 0; i < nodes - 1; i++) { // copying the skibdi old to new version, then make new
            newAdj[i] = adjacencyList[i];
        }
        newAdj[nodes - 1] = new LinkedList<>();
        adjacencyList = newAdj;
    }

    public void removeEdge(int source, int destination) {
        adjacencyList[source].remove(destination);
        adjacencyList[destination].remove(source);
    }

}

// Sample Usage
Graph graph = new Graph(7);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);
graph.displayGraph();

graph.addNode();
graph.addEdge(7, 0);
graph.addEdge(7, 1);
graph.removeEdge(0, 1);

graph.displayGraph();

Graph adjacency list:
0 -> 1 2 
1 -> 0 3 4 
2 -> 0 5 
3 -> 1 6 
4 -> 1 
5 -> 2 
6 -> 3 
Graph adjacency list:
0 -> 1 7 
1 -> 3 4 7 
2 -> 0 5 
3 -> 1 6 
4 -> 1 
5 -> 2 
6 -> 3 
7 -> 0 1

Homework - Part 2

The above class for graphs works for the purpose of what we’re going to explain. However, in real usage, the following methods are likely needed. Please implement them.

  1. addNode
    • Adds a node to the graph
    • No connections be default
  2. removeEdge
    • Removes a specified edge from the graph
    • Does NOT remove the nodes

Answer: See the above code cell. I have modified it to add and test the new methods.