Graphs/Java/Adjacency Map Lite

Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.

The Classes

A lightweight implementation of the adjacency map still requires three classes, but can skimp on infrastructure. The three classes are:

• Graph
• Vertex
• Edge

Class Implementations

Following is a list of methods and fields that each of the above classes should implement

Graph class:

• Fields: list of vertices, list of edges
• Constructor: initializes list of vertices, list of edges
• Init: given a number of vertices N, this creates each vertex and populates the list of vertices with them
• Add vertex method (identified by integers, which are used to access the list of vertices)
• Add edge method (takes two integers)
• Note that depth first search and other related functionality is usually implemented separately, as a standalone function
• Method: toString()

Vertex class:

• Map of Vertex objects to Edge objects, to store connecting edges (neighbor list)
• Integer (element/identifier)
• Method: get edges connecting to this vertex
• Method: add new neighbor to this vertex
• Method: get element
• Method: toString()

Edge class:

• List of Vertex objects
• (Optional) int array (element/identifier)
• Constructor: two vertices (integer indexes), set as endpoints
• Method: has endpoints (check if a vertex is one of this edge's endpoints)
• Method: get opposite (pass one endpoint, get the opposite endpoint)
• Method: get element
• Method: toString()

Static Classes

To keep things simple, bundle everything as a single single class, and make the Graph, Vertex, and Edge classes static. The main objective here is implementing the algorithm and data structure, rather than coordinating permissions and access.

Exceptions

See Java/Exceptions

Easiest way to do this is to raise new IllegalArgumentException("Error message here")

Java Code

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

Here is the Graph class:

public class RoadsAndLibraries {

    static class Graph {
        ArrayList<Vertex> vertexList;
        ArrayList<Edge> edgeList;

        public Graph() {
            vertexList = new ArrayList<>();
            edgeList = new ArrayList<>();
        }

        public void init(int n) { 
            for(int i=0; i<n; i++) { 
                Vertex v = new Vertex(i+1);
                vertexList.add(v);
            }
        }

        public void addEdge(int i, int j) { 
            // To add an edge:
            // - get the two endpoints, 
            // - then create the edge, 
            // - then add vertex i and vertex j as neighbors. 
            Vertex vi = vertexList.get(i-1);
            Vertex vj = vertexList.get(j-1);
            Edge e = new Edge(vi, vj);
            vi.addNeighbor(vj, e);
            vj.addNeighbor(vi, e);
            edgeList.add(e);
        }

        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("Vertices:\n");
            for(int i=0; i<vertexList.size(); i++) { 
                sb.append("    ");
                sb.append(i);
                sb.append("\n");
            }
            sb.append("Edges:\n");
            for( Edge e : edgeList ) { 
                ArrayList<Vertex> endpoints = e.getEndpoints();
                sb.append("    ");
                sb.append(endpoints.get(0).getElement());
                sb.append("-");
                sb.append(endpoints.get(1).getElement());
                sb.append("\n");
            }
            return sb.toString();
        }
    }

The Vertex class:

    static class Vertex {
        private int element;
        private HashMap<Vertex, Edge> neighborList;
        public Vertex(int element) { 
            this.element = element;
            neighborList = new HashMap<>();
        }
        public Collection<Edge> outgoingEdges() {
            return neighborList.values();
        }
        public void addNeighbor(Vertex v, Edge e) { 
            neighborList.put(v, e);
        }
        public int getElement() {
            return this.element;
        }
        public String toString() {
            return Integer.toString(element);
        }
    }

Finally, here is the Edge class:

    static class Edge {
        ArrayList<Vertex> endpoints;
        public Edge(Vertex i, Vertex j) {
            endpoints = new ArrayList<>();
            endpoints.add(i);
            endpoints.add(j);
        }
        public ArrayList<Vertex> getEndpoints() { 
            return endpoints;
        }
        public boolean hasEndpoint(Vertex v) {
            if(v.getElement() == endpoints.get(0).getElement() ) {
                return true;
            } else if(v.getElement() == endpoints.get(1).getElement() ) {
                return true;
            } else {
                return false;
            }
        }
        public Vertex getOpposite(Vertex v) { 
            if(v.getElement() == endpoints.get(0).getElement() ) {
                return endpoints.get(1);
            } else if(v.getElement() == endpoints.get(1).getElement() ) {
                return endpoints.get(0);
            } else {
                System.out.println("Endpoint 0: "+endpoints.get(0));
                System.out.println("Endpoint 1: "+endpoints.get(1));
                System.out.println("Checking for vertex: "+v.getElement());
                throw new IllegalArgumentException("Vertex not an endpoint of this edge.");
            }
        }
        public String toString() {
            StringBuffer sb = new StringBuffer();
            sb.append("(Edge ");
            sb.append(endpoints.get(0).getElement());
            sb.append("-");
            sb.append(endpoints.get(1).getElement());
            sb.append(")");
            return sb.toString();
        }
    }

Algorithms

Depth first search and friends

Depth first search is one of the most useful and versatile of all graph algorithms, so we first illustrate it using the simple graph objects given above, then illustrate its use in other algorithms.

Depth first search

To implement a depth-first search on a graph, we use recursion.

Following the Graphs/Depth_First_Traversal#Pseudocode section of the DFS page, we can implement DFS as follows:

• Maintain a list of known/visited vertices in known (alternatively, we could implement a boolean flag in the Vertex class and mark them as visited that way)
• Begin the depth-first search at a root node, which is NOT included in the discovered map
• The discovered map contains each vertex of the given component of the graph, except the root of the component (the original Vertex u in the original dfs() call)
• The map discovered is a map from Vertex v to the Edge e that discovered it

Remember that, because of the nature of DFS, the resulting map MUST contain the shortest path that visits all nodes.

    /** Recursive depth-first search that populates HashMap discovered 
     * with all edges/vertices discoverable from u.*/
    public static void dfs(Graph g, Vertex u, 
                           HashSet<Vertex> known,
                           HashMap<Vertex, Edge> discovered) {
        known.add(u);
        for(Edge e : u.outgoingEdges()) { 
            Vertex v = e.getOpposite(u);
            if(!known.contains(v)) {
                // e = edge that discovered v
                discovered.put(v,e);
                dfs(g, v, known, discovered);
            }
        }
    }

Counting connected components with DFS

One of the applications of implementing a DFS is to count the number of connected components on a graph. To do this, we need to wrap the DFS with another method that will ensure we visit all components.

This method utilizes the fact that the root node of each graph component is NOT included in the discovered map that is populated by the DFS.

This fact is useful, because we can ensure every component of the graph is visited, and then count the number of root nodes that are left out of the discovered map.

This returns the DFS forest - that is, a series of Vertex-Edge pairs that form individual trees. If there are multiple components on the graph, each component is a separate tree - hence the forest term - but all Vertex-Edge pairs are contained in the map forest.

To compute the number of connected components on a graph, we can compute the difference between the size of the forest, and the number of vertices on the entire graph. (If there is only one component, there will only be one root node missing from it, so the number of components will be 1. If there are two components on the graph, there will be two root nodes, one for each component, missing from the forest, so the component size will be 2. And so on...)

    /** Return a map representing DFS forest. 
     * If a vertex is missing from this map, 
     * it serves as a root in this forest.
     * Number of connected components is equal to:
     *
     * > g.vertexList.size() - forest.size()
     *
     */
    public static HashMap<Vertex, Edge> dfsConnected(Graph g) {
        HashSet<Vertex> known = new HashSet<>();
        HashMap<Vertex, Edge> forest = new HashMap<>();
        for(Vertex u : g.vertexList) {
            if(!known.contains(u)) {
                dfs(g, u, known, forest);
            }
        }
        return forest;
    }

Finding edges in minimum path covering all nodes with DFS

Another property of the forest that results from a DFS is that it composes the shortest path that connects all vertices on the graph.

That means we can obtain the number of edges in the shortest path - if, as in the HackerRank question roads and libraries, you want to compute something based on the minimum number of edges that connect all components.

It also means we can obtain the length, or weight, of the shortest path - if each edge has a particular weight, and we have all the edges that compose the shortest path, we can simply iterate over each edge and add up the weights to get the weight of the shortest path connecting all vertices.

This can be done for a single component, or (in combination with the method above) for all components on the graph.

Example:

                HashMap<Vertex, Edge> forest = dfsConnected(g);
                int nComponents = g.vertexList.size() - forest.size();
                int nEdges = forest.size();