2
\$\begingroup\$

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:

Graph

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ To solve the last problem, I think I'm just going to abandon the idea of copying the Graph inside the method. If the caller doesn't want their graph messed with, they can pass in a copy. \$\endgroup\$ – Carcigenicate Jul 6 '15 at 2:07
  • \$\begingroup\$ Also, you can ignore the two ifs: if (nextVisitable == null) { and the one after it that can be combined into a if...else. I should have caught that before posting, but I can't change it now. \$\endgroup\$ – Carcigenicate Jul 6 '15 at 2:15
  • \$\begingroup\$ You should review what is an Eulerian Tour first. After that the solution becomes way too easy. \$\endgroup\$ – Dietr1ch Jul 6 '15 at 4:36
  • \$\begingroup\$ I'm assuming that we should treat this as a homework question. \$\endgroup\$ – 200_success Jul 6 '15 at 5:50
  • \$\begingroup\$ @200_success Yes. Sorry, I thought the first paragraph made that clear. \$\endgroup\$ – Carcigenicate Jul 6 '15 at 10:53
3
\$\begingroup\$

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".

\$\endgroup\$
  • \$\begingroup\$ Thank you. For cases like hasEdge and addDirectedEdgd, in case the user passes in an "unknown" vertex, would your say it's more appropriate to throw, or ignore? \$\endgroup\$ – Carcigenicate Jul 6 '15 at 10:51
  • \$\begingroup\$ And I thought once you declare another constructor, Java no longer supplies a default constructor. I don't have my IDE in front of me to test this though. Is this not the case? \$\endgroup\$ – Carcigenicate Jul 6 '15 at 10:52
  • \$\begingroup\$ You're right about the default constructor, I overlooked the place where you use it, so yes, you still need it, I removed that from my post. \$\endgroup\$ – janos Jul 6 '15 at 11:28
  • \$\begingroup\$ I'm not sure what is an "unknown" vertex. If such parameter doesn't make sense, then it's better to throw, to alert the programmer. Doing nothing can be more harmful, causing confusing or unpredictable behavior later, when it will be harder to understand and debug. \$\endgroup\$ – janos Jul 6 '15 at 11:30
  • \$\begingroup\$ By "unknown vertex", I mean, say the Graph consists of vertical labelled a-f, and someone wants to check for an edge between a and Z (Z doesn't exist). Should I throw, or ignore that and just return false? I don't want to hide any potential errors (like the fact that someone is looking for a vertex that doesn't exist), but I don't want to throw if it's overkill and unnecessary. \$\endgroup\$ – Carcigenicate Jul 6 '15 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.