Graph Heuristics - Java and Graphs

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();
        }
    }

}

// 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 adjacency list:
0 -> 1 2 
1 -> 0 3 4 
2 -> 0 5 
3 -> 1 6 
4 -> 1 
5 -> 2 
6 -> 3 

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

import java.util.*;

public class Graph {
    private int nodes;
    private LinkedList<Integer>[] adjacencyList;

    // Constructor
    public Graph(int nodes) {
        this.nodes = nodes;
        adjacencyList = new LinkedList[nodes];
        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // Add an undirected edge between source and destination
    public void addEdge(int source, int destination) {
        if (source >= nodes || destination >= nodes) {
            System.out.println("Invalid node index.");
            return;
        }
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source);
    }

    // Remove the edge between source and destination
    public void removeEdge(int source, int destination) {
        if (source >= nodes || destination >= nodes) {
            System.out.println("Invalid node index.");
            return;
        }
        adjacencyList[source].remove(Integer.valueOf(destination));
        adjacencyList[destination].remove(Integer.valueOf(source));
    }

    // Add a new node to the graph
    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;
    }

    // Display the adjacency list of the graph
    public void displayGraph() {
        System.out.println("Graph adjacency list:");
        for (int i = 0; i < nodes; i++) {
            System.out.print(i + " -> ");
            for (int neighbor : adjacencyList[i]) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(3);

        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.displayGraph();

        System.out.println("\nAdding a new node...");
        graph.addNode();
        graph.displayGraph();

        System.out.println("\nAdding edge between 2 and 3...");
        graph.addEdge(2, 3);
        graph.displayGraph();

        System.out.println("\nRemoving edge between 1 and 2...");
        graph.removeEdge(1, 2);
        graph.displayGraph();
    }
}
Main.main(null);

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

Adding a new node...
Graph adjacency list:
0 -> 1 
1 -> 0 2 
2 -> 1 
3 -> 

Adding edge between 2 and 3...
Graph adjacency list:
0 -> 1 
1 -> 0 2 
2 -> 1 3 
3 -> 2 

Removing edge between 1 and 2...
Graph adjacency list:
0 -> 1 
1 -> 0 
2 -> 3 
3 -> 2