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:

• Constructor: initializes list of vertices, list of edges
• Add vertex method (identified by integers)
• Add edge method (takes two integers)
• (Optional) Depth first search (or any other methods/algorithms required specifically by the problem)

Vertex class:

• Map of Vertex objects to Edge objects, to store connecting edges
• Integer (element/identifier)
• Method: get neighbors
• Method: get element

Edge class:

• List of Vertex objects
• (Optional) int array (element/identifier)
• Constructor: two vertices, set as endpoints
• Method: get endpoints
• Method: get element

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 {

    static class Graph {
        HashMap<Integer, Vertex> vertexMap;
        ArrayList<Edge> edgeList;

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

        public void addVertex(int i) { 
            // To add a vertex, just add it to the master vertex map
            // along with its identifying integer.
            Vertex v = new Vertex(i);
            vertexMap.put(i,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 = vertexMap.get(i);
            Vertex vj = vertexMap.get(j);
            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( Integer i : vertexMap.keySet() ) {
                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();
        }
    }

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

    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 Vertex getOpposite(Vertex v) { 
            if(v.equals(endpoints.get(0))) {
                return endpoints.get(1);
            } else if(v.equals(endpoints.get(1))) { 
                return endpoints.get(0);
            } else {
                throw new IllegalArgumentException("Vertex not an endpoint of this edge.");
            }
        }
    }
}

Algorithms

// u is an empty dictionary
def dfs_connected(g):
    forest is empty dictionary
    for each vertex u in graph:
        if u not in forest:
            forest[u] = None
            do_dfs(g, u, forest)
    return forest

// complementary method: do depth first search
def do_dfs(g, u, discovered):
    for e in g.incident_edges(u):
        if v not in discovered:
            discovered[v] = e
            do_dfs(g, v, discovered)