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() {
        nodes++;
        LinkedList<Integer>[] newAdjacencyList = new LinkedList[nodes];
        for (int i = 0; i < nodes - 1; i++) {
            newAdjacencyList[i] = adjacencyList[i];
        }
        newAdjacencyList[nodes - 1] = new LinkedList<>();
        adjacencyList = newAdjacencyList;
    }

    public void removeEdge(int source, int destination) {
        adjacencyList[source].remove(Integer.valueOf(destination));
        adjacencyList[destination].remove(Integer.valueOf(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();
//test case for new functions
Graph graph = new Graph(3);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.displayGraph();

graph.addNode(); // adds node 3
graph.addEdge(2, 3);
graph.displayGraph();

graph.removeEdge(1, 2);
graph.displayGraph();

Graph adjacency list:
0 -> 1 
1 -> 0 2 
2 -> 1 
Graph adjacency list:
0 -> 1 
1 -> 0 2 
2 -> 1 3 
3 -> 2 
Graph adjacency list:
0 -> 1 
1 -> 0 
2 -> 3 
3 -> 2

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

added above