Graph, and a search that visits each edge exactly once in each direction

Question

My assignment was to write a method that is capable of visiting each edge in a graph in each direction exactly once.

With it, I included a basic Graph class to test it with.

What I'd like a review of:

• This is like my 1000th attempt after trying everything I could think of. This is the first version that I've had that passes every test case I've presented it, so I'm pretty happy with it. I'm sure through all my refactoring though, I've made messes that I'm used to now. If anything could be simplified, I'd like to know.

• Are the comments appropriate?

• Is the Graph itself set-up well? This is my first time dealing with graphs, and while I'm fairly happy with it, I'm sure there are possible improvements.

• I want to return the path taken, but I also need to show that the resulting graph has been fully traversed. I can't easily return both without using a POD class. What are my options? I'd obviously like to avoid printing inside the method.

The graph I'm using in the example main is:

and the method in question is visitEachEdgeTwice. It works by constantly traversing un-touched edges, backtracking if necessary. To track which edges have been traversed, the edges are removed from a copy of the graph after they're traversed; disallowing them from being used again.

Graph.java:

package comp272.a3.q5;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

public class Graph<Vertex> {

    // A map between a source vertex, and a list of targets that it connects to.
    private HashMap<Vertex, HashSet<Vertex>> adj = new HashMap<Vertex, HashSet<Vertex>>();

    public Graph() {

    }

    public Graph(Graph<Vertex> oldGraph) {
        adj = new HashMap<Vertex, HashSet<Vertex>>(oldGraph.adj);
    }

    public Set<Vertex> getVertices() {
        return adj.keySet();
    }

    public void addVertex(Vertex vertex) {
        adj.put(vertex, new HashSet<Vertex>());
    }

    public void addVertices(List<Vertex> vertices) {
        for (Vertex v : vertices) {
            addVertex(v);
        }
    }

    // Adds a directed (one-way) edge to the given vertex.
    public void addDirectedToVertex(Vertex source, Vertex target) {
        if (!adj.containsKey(target)) {
            addVertex(target);
        }

        HashSet<Vertex> targets = adj.get(source);
        if (targets != null) {
            targets.add(target);

        } else {
            throw new NoSuchElementException(
                "Vertex " + source + " doesn't exist.");
        }
    }

    // Adds an undirected (two-way) edge to the given vertices by adding 2
    // directed edges between each vertex.
    public void addUndirectedToVertex(Vertex source, Vertex target) {
        addDirectedToVertex(source, target);
        addDirectedToVertex(target, source);
    }

    // A convenience method for the question.
    public void addUndirectedToVertex(Vertex source, List<Vertex> targets) {
        for (Vertex target : targets) {
            addUndirectedToVertex(source, target);
        }
    }

    // A helper to remove all directed edges leading to a vertex.
    private void removeAllEdgesTo(Vertex vertex) {
        for (HashSet<Vertex> vs : adj.values()) {
            vs.remove(vertex);
        }
    }

    // Removes a vertex from the list; removing any edges associated with it.
    public void removeVertex(Vertex vertex) {
        adj.remove(vertex);
        removeAllEdgesTo(vertex);
    }

    // Removes the edge going from the source to the target (if any).
    public void removeDirectedEdge(Vertex source, Vertex target) {
        HashSet<Vertex> targets = adj.get(source);

        if (targets != null) {
            targets.remove(target);

        } else {
            throw new NoSuchElementException(
                "Vertex " + source + " doesn't exist.");
        }
    }

    // Removes all edges going between the source and the target.
    public void removeUndirectedEdge(Vertex source, Vertex target) {
        removeDirectedEdge(source, target);
        removeDirectedEdge(target, source);
    }

    // Returns whether or not the given edge exists.
    public boolean hasEdge(Vertex source, Vertex target) {
        HashSet<Vertex> targets = adj.get(source);

        if (targets == null) {
            return false;

        } else {
            return targets.contains(target);
        }
    }

    // Returns a list of outgoing edges from the given vertex.
    public List<Vertex> outEdges(Vertex source) {
        HashSet<Vertex> targets = adj.get(source);

        List<Vertex> outEdges = new ArrayList<Vertex>();

        if (targets != null) {
            outEdges.addAll(targets);
        }

        return outEdges;
    }

    // Returns a list of incoming edges to the given vertex.
    public List<Vertex> inEdges(Vertex target) {
        List<Vertex> inEdges = new ArrayList<Vertex>();

        for (Vertex source : adj.keySet()) {
            if (adj.get(source).contains(target)) {
                inEdges.add(source);
            }
        }

        return inEdges;
    }

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

    //Returns the last (top-most/most recent) navigatable vertex on the stack, or none if
    // there are no vertices available.
    public Vertex getLastAvailOnStack(Vertex currentVertex, Deque<Vertex> stack) {  
        Iterator<Vertex> it = stack.descendingIterator();

        while (it.hasNext()) {
            Vertex next = it.next();
            if (hasEdge(currentVertex, next)) {
                return next;
            }
        }

        return null;
    }

    //Traverses each edge in each direction once.
    //It ends by printing the edges remaining to be seen (not optimal),
    // and returns the path that it took.
    public static <Vertex> List<Vertex> visitEachEdgeTwice(Graph<Vertex> graph, Vertex startVertex) {
        List<Vertex> path = new LinkedList<Vertex>();

        //So we can prioritize unseen vertices over backtracking.
        Deque<Vertex> stack = new ArrayDeque<Vertex>();

        //To keep track of which vertices have been traversed.
        graph = new Graph<Vertex>(graph);

        stack.push(startVertex);

        Vertex currentVertex = startVertex;

        while (!stack.isEmpty()) {
            Vertex  nextVisitable = null;

            for (Vertex target : graph.outEdges(currentVertex)) {
                if (graph.hasEdge(currentVertex, target)) {
                    if (!stack.contains(target)) {
                        nextVisitable = target;
                    }
                }

            }

            //Backtrack if we don't have any other choice.
            //We're going to pick the neighboring vertex that is farthest away
            // from our "root" (bottom of stack).
            if (nextVisitable == null) {
                nextVisitable = graph.getLastAvailOnStack(currentVertex, stack);
            }

            //If we have a next node, traverse the edge to it, removing it from
            // the graph.
            if (nextVisitable != null) {
                graph.removeDirectedEdge(currentVertex, nextVisitable);
                path.add(currentVertex);
                stack.add(currentVertex);

                currentVertex = nextVisitable;

            } else {
                stack.pop();
            }
        }

        //Poor form, but it would be awkward to return with the path, and we
        // need to see the graph to ensure all the edges were traversed.
        System.out.println(graph);

        path.add(currentVertex);

        return path;
    }

    public static void main(String[] args) {
        Graph<Character> g = new Graph<Character>();

        // The edgeless graph from the question:
        List<Character> vertices = Arrays.asList('A', 'B', 'C', 'D', 'E', 'F',
                'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P');

        g.addVertices(vertices);

        // Manually add the edges:
        // There's some edge duplication here, but I'd rather be doubly sure
        // I'm representing every edge than to accidentally forget one.
        // They won't be duplicated in the graph itself.
        g.addUndirectedToVertex('A', Arrays.asList('B', 'E', 'F'));
        g.addUndirectedToVertex('B', Arrays.asList('A', 'C'));
        g.addUndirectedToVertex('C', Arrays.asList('B', 'D', 'F'));
        g.addUndirectedToVertex('D', Arrays.asList('C', 'G'));
        g.addUndirectedToVertex('E', Arrays.asList('A', 'I'));
        g.addUndirectedToVertex('F', Arrays.asList('A', 'J', 'C'));
        g.addUndirectedToVertex('G', Arrays.asList('J', 'K', 'H', 'D'));
        g.addUndirectedToVertex('H', Arrays.asList('G', 'O'));
        g.addUndirectedToVertex('I', Arrays.asList('E', 'J', 'M'));
        g.addUndirectedToVertex('J', Arrays.asList('I', 'F', 'G'));
        g.addUndirectedToVertex('K', Arrays.asList('G', 'O'));
        g.addUndirectedToVertex('L', Arrays.asList('P'));
        g.addUndirectedToVertex('M', Arrays.asList('I'));
        g.addUndirectedToVertex('N', Arrays.asList('I', 'O'));
        g.addUndirectedToVertex('O', Arrays.asList('N', 'K', 'H', 'P'));
        g.addUndirectedToVertex('P', Arrays.asList('O', 'L'));

        List<Character> path = visitEachEdgeTwice(g, 'B');

        System.out.println(path);
    }
}

Answer 1

Refer to types by interface instead of implementation

Instead of this:

HashMap<Vertex, HashSet<Vertex>> adj = new HashMap<Vertex, HashSet<Vertex>>();

This is preferable:

Map<Vertex, Set<Vertex>> adj = new HashMap<Vertex, Set<Vertex>>();

Make fields final when possible

The member variable adj is never reassigned, therefore it can be final.

Validate first before other operations

In addDirectedToVertex, you first add target to the graph if it's not there yet, and then check if source is valid or not, otherwise throw exception. It would be letter to change the order of operations, do the validation first.

A javadoc string about the unchecked exception would be nice too.

Simplify hasEdge

The if-else can be simplified with a ternary:

return targets != null && targets.contains(target)

Inconsistent handling of invalid parameters

In outEdges, if the specified source doesn't exist, you return an empty list. But such source is effectively invalid, and many of your other methods throw an exception in such situations. It would be good to be consistent and so likewise here.

It's also not great to give a variable the same name as that of a method.

Using a POD class vs printing

Using a POD class is clearly the lesser evil. Don't use printing to verify "with your eyes".