Graph.java

import java.util.*;

/**
 * Class to represent an undirected graph as an adjacency list
 */
public class Graph<E>{

    private Map<E,List<E>> graph;

    /**
     * A small utility class to encode a "marker"
     * for a node, consisting of its dfsNum and "back"
     */
    private static class Pair<E> {
        private E dfsnum,back;
        Pair(E dfsnum, E back) {
            this.dfsnum = back;
            this.back = back;
        }
        @Override
        public String toString() {
            return String.format("(%s,%s)", dfsnum,back);
        }
    }

    public Graph() {
        this.graph = new HashMap<>();
    }

    /**
     * method that adds nodes and edges to our graph
     * @param item an item to add to the graph
     * @param otherItem item to connect first argument to
     */
    public void addEdge(E item, E otherItem) {
        if(this.graph.containsKey(item)) {
            this.graph.get(item).add(otherItem);
            if (this.graph.containsKey(otherItem)) {
                this.graph.get(otherItem).add(item);
            } else {
                this.graph.put(otherItem, new ArrayList<E>(Arrays.asList(item)));
            }
        } else {
            this.graph.put(item, new ArrayList<E>(Arrays.asList(otherItem)));
            if (this.graph.containsKey(otherItem)) {
                this.graph.get(otherItem).add(item);
            } else {
                this.graph.put(otherItem, new ArrayList<E>(Arrays.asList(item)));
            }
        }
    }

    /**
     * marks graph with dfsNum and back values and returns marking
     * @param startNode node at which to start the DFS
     * @return an association between nodes and markers
     */
    public Map<E,Pair<Integer>> markGraph(E startNode) {
        Map<E,Pair<Integer>> visited = new HashMap<>();
        Stack<E> s = new Stack<>();
        // TODO: Determine whether startNode is a connector
        // there is some edge case stuff that you might have
        // to do here to determine if startNode is a connector
        s.push(startNode);
        int dfsNum = 0;
        while(!s.empty()) {
            E current = s.pop();
            if (!visited.containsKey(current)) {
                visited.put(current, new Pair<Integer>(dfsNum,dfsNum));
            } else {
                // TODO: Implement logic to update back and assess
                //       whether or not it meets connector criteria
                // this is the scenario in which we've already 
                // visited a node, and we want to see whether to 
                // update "back" or to declare that the node is a 
                // connector
            }
            if (this.graph.containsKey(current)) {
                Iterator<E> it = this.graph.get(current).iterator();
                while (it.hasNext()) {
                    E c = it.next();
                    if (!visited.containsKey(c)) s.push(c);
                }
            }
            dfsNum++;
        }
        return visited;
    }

    @Override
    public String toString() {
        return this.graph.toString();
    }

    public static void main(String[] args) {
        Graph<Character> g = new Graph<>();
        g.addEdge('a','b');
        g.addEdge('b','c');
        g.addEdge('b','d');
        System.out.println(g);
        System.out.println(g.markGraph('a'));
        System.out.println(g.markGraph('b'));
    }
}