4
\$\begingroup\$

I think many here are familiar with the graph data structure. Not very long ago, I implemented as an exercise a supposedly simple Graph application that does some traversals. To note, the most complex operations in this class are those that exhaustively find Paths: findDirectPaths, findPathsWithMaximumDistance, and findPathsWithMaximumStops.

Other collaborators such as Node, and Edge have very simple structure that the reader should be able to guess from their usage in this class. However, for those who are curious about the overall structure of this application, they can check out the public repository on GitHub.

My work has recently been assessed, and I was given remarks similar to the following:

  1. There is insufficient test coverage with no evidence of Test Driven Development (TDD).
  2. There are quite a number of unused methods.
  3. Methods are unnecessarily long, and almost all logic is in the Graph class.

Further, according to the people who reviewed it, while my solution works and has basic test coverage, the methods are large and difficult to follow. They encourage me to follow clean code principles, and demonstrate object oriented design.

Now, I'd like for other people to review my code and see what else should be improved here and how. I'd also like to know if the assessments above are well grounded because I don't necessarily agree with them.

To the first point, I'm not really sure what kind of evidence anyone can present that there was actually TDD involved in building the solution. Isn't that there are tests for almost every method proof enough that there actually was TDD involved here (regardless of whether it was done properly, or not)? My code base was sent in as a compressed directory so version control data was removed, which should have illustrated the step by step building of each of the methods, in chronological order. I make it a habit to commit changes after test-fail-code-pass sequence.

As for the unused methods, I had to review my code using my IDE (since I don't have automated analysis tools at the moment), and each method so far has at least one reference in some other classes. The only ones I can think of that can be considered unused in the sense that they're not used outside of testing are the hasEdge methods.

Lastly, I'm not really sure how much more compact I can make the methods that traverse the graph exhaustively based on different criteria; I'm not sure if they're unnecessarily long. Each method that finds paths exhaustively employs depth first search with the aid of 2 stacks, one for moving forward, and one for backtracking. Each of these methods moves forward, and backtracks differently from one another. In terms of lines of code, which I think is a good unit of measure of length in this case, each of them takes less than 50 LOC. Also, I don't understand why it's necessarily a bad thing for most of the logic to be in the Graph class when it's at the core of the entire solution. Are there behaviors in the Graph class that should have been placed somewhere else?

I have added some comments in places where I think some refactoring is in order. I was looking forward to discuss them with the people who reviewed my code, but we've already practically cut communications at this point.

Graph Class

public class Graph {

    //TODO: restrict creation of Graph to just the create method so that nodeMap
    //this is so that any Graph object has nodeMap correctly built as expected
    private Map<String, Node> nodeMap = new HashMap<>();

    private Map<Node, List<Edge>> graphMap = new HashMap<>();

    public static Graph create(String... inputEdges) {
        Graph graph = new Graph();
        Pattern pattern = Pattern.compile("(\\p{Alpha})(\\p{Alpha})(\\p{Digit}+)");
        for (String input : inputEdges) {
            Matcher matcher = pattern.matcher(input);
            if (matcher.matches()) {
                //TODO: move the requirement for upper case names to Node class itself
                String originName = matcher.group(1).toUpperCase();
                Node origin = graph.nodeMap.get(originName);
                if (origin == null) {
                    origin = new Node(originName);
                    graph.nodeMap.put(originName, origin);
                }

                String destinationName = matcher.group(2).toUpperCase();
                Node destination = graph.nodeMap.get(destinationName);
                if (destination == null) {
                    destination = new Node(destinationName);
                    graph.nodeMap.put(destinationName, destination);
                }

                String distance = matcher.group(3);
                graph.addEdge(origin, destination, parseInt(distance));
            }
        }
        return graph;
    }

    public Edge addEdge(Node origin, Node destination, int distance) {
        Edge edge = new Edge(origin, destination, distance);
        List<Edge> edges = graphMap.get(origin);
        if (edges == null) {
            edges = new ArrayList<>();
            graphMap.put(origin, edges);
        }
        edges.add(edge);
        List<Edge> destinationEdges = graphMap.get(destination);
        if (destinationEdges == null) graphMap.put(destination, new ArrayList<Edge>());
        return edge;
    }

    public Path getPath(Node... nodes) {
        List<Edge> edges = new ArrayList<>();
        int index = 0;
        for (Node node : nodes) {
            if (index < nodes.length - 1) {
                Edge edge = findEdge(node, nodes[index + 1]);
                if (edge != null) edges.add(edge);
                else break;
            } else {
                break;
            }
            index++;
        }
        return (index == nodes.length - 1) ? new Path(edges.toArray(new Edge[0])) : null;
    }

    public Path getPath(String... nodeNames) {
        List<String> names = asList(nodeNames);
        //TODO: reuse nodeMap field here (once constructor is restricted to creator method)
        Map<String, Node> nodeMap = new HashMap<>();
        for (Node node : graphMap.keySet()) {
            if (names.contains(node.getName())) nodeMap.put(node.getName(), node);
        }

        Node[] nodes = new Node[nodeNames.length];
        for (int index = 0; index < nodeNames.length; index++) {
            nodes[index] = nodeMap.get(nodeNames[index]);
        }
        return getPath(nodes);
    }

    private Edge findEdge(Node origin, Node destination) {
        Edge edge = null;
        List<Edge> edges = graphMap.get(origin);
        for (Edge candidateEdge : edges) {
            if (candidateEdge.getDestination().equals(destination)) edge = candidateEdge;
            if (edge != null) break;
        }
        return edge;
    }

    public Edge findEdge(String originName, String destinationName) {
        Node[] nodes = findOriginAndDestination(originName, destinationName);
        Node origin = nodes[0];
        Node destination = nodes[1];
        return findEdge(origin, destination);
    }

    public boolean hasEdge(Node origin, Node destination) {
        return findEdge(origin, destination) != null;
    }

    public boolean hasEdge(String originName, String destinationName) {
        return findEdge(originName, destinationName) != null;
    }

    public List<Path> findPathsWithMaximumStops(String originName, String destinationName, int maximumStops) {
        List<Path> paths = new ArrayList<>();

        Node[] nodes = findOriginAndDestination(originName, destinationName);
        Node origin = nodes[0];
        Node destination = nodes[1];

        Stack<Edge> stack = new Stack<>();
        Stack<Integer> branching = new Stack<>();
        List<Edge> pathEdges = new ArrayList<>();
        Node currentNode = origin;
        for (Edge edge : graphMap.get(currentNode)) stack.push(edge);
        do {
            Edge currentEdge = stack.pop();
            if (pathEdges.size() == maximumStops) {
                while (!branching.isEmpty()) {
                    int currentBranch = branching.pop() - 1;
                    if (currentBranch < 1 && !pathEdges.isEmpty()) {
                        pathEdges.remove(pathEdges.size() - 1);
                    } else if (currentBranch >= 1) {
                        branching.push(currentBranch);
                        break;
                    }
                }
            } else {
                currentNode = currentEdge.getDestination();
                List<Edge> edges = graphMap.get(currentNode);
                for (Edge edge : edges) stack.push(edge);
                branching.push(edges.size());
                pathEdges.add(currentEdge);
                if (currentEdge.getDestination().equals(destination)) {
                    paths.add(new Path(pathEdges.toArray(new Edge[0])));
                }
            }
        } while (!stack.isEmpty());

        return paths;
    }

    public List<Path> findPathsWithMaximumDistance(String originName, String destinationName, int maxDistance) {
        ArrayList<Path> paths = new ArrayList<>();

        Node[] endPoints = findOriginAndDestination(originName, destinationName);
        Node origin = endPoints[0];
        Node destination = endPoints[1];

        Stack<Edge> stack = new Stack<>();
        Stack<Integer> backtracker = new Stack<>();

        for (Edge edge : graphMap.get(origin)) stack.push(edge);
        List<Edge> pathEdges = new ArrayList<>();
        Node nextNode = null;
        int totalDistance = 0;
        do {
            Edge currentEdge = stack.pop();
            if (totalDistance < maxDistance) {
                pathEdges.add(currentEdge);
                totalDistance += currentEdge.getDistance();

                nextNode = currentEdge.getDestination();
                List<Edge> edges = graphMap.get(nextNode);
                for (Edge edge : edges) stack.push(edge);
                backtracker.push(edges.size());

                if (currentEdge.getDestination().equals(destination)) {
                    if (totalDistance < maxDistance) paths.add(new Path(pathEdges.toArray(new Edge[0])));
                }
            } else {
                int branching = 0;
                while (!backtracker.isEmpty()) {
                    branching = backtracker.pop() - 1;
                    if (branching < 1) {
                        Edge removedEdge = pathEdges.remove(pathEdges.size() - 1);
                        totalDistance -= removedEdge.getDistance();
                    } else {
                        backtracker.push(branching);
                        break;
                    }
                }
            }
        } while (!stack.isEmpty());

        return paths;
    }

    private List<Path> findDirectPaths(String originName, String destinationName) {
        List<Path> directPaths = new ArrayList<>();
        Node[] nodes = findOriginAndDestination(originName, destinationName);
        Node origin = nodes[0];
        Node destination = nodes[1];

        Stack<Edge> stack = new Stack<>();
        Stack<Integer> backtracker = new Stack<>();
        for (Edge edge : graphMap.get(origin)) stack.push(edge);
        List<Edge> pathEdges = new ArrayList<>();
        Set<Node> visitedNodes = new HashSet<>();
        Node nextNode = null;
        do {
            Edge currentEdge = stack.pop();
            if (currentEdge.getDestination().equals(destination)) {
                pathEdges.add(currentEdge);
                backtracker.push(0);
                directPaths.add(new Path(pathEdges.toArray(new Edge[0])));

                int branching = 0;
                while (!backtracker.isEmpty()) {
                    branching = backtracker.pop() - 1;
                    if (branching < 1) {
                        Edge removedEdge = pathEdges.remove(pathEdges.size() - 1);
                        visitedNodes.remove(removedEdge.getDestination());
                    } else {
                        backtracker.push(branching);
                        break;
                    }
                }
            } else {
                pathEdges.add(currentEdge);
                nextNode = currentEdge.getDestination();
                visitedNodes.add(nextNode);

                int branching = 0;
                for (Edge edge : graphMap.get(nextNode)) {
                    if (!visitedNodes.contains(edge.getDestination())) {
                        stack.push(edge);
                        branching++;
                    }
                }
                if (branching > 0) backtracker.push(branching);
            }
        } while (!stack.isEmpty());

        return directPaths;
    }

    public Path findShortestPath(String originName, String destinationName) {
        List<Path> directPaths = findDirectPaths(originName, destinationName);
        Path shortestPath = null;
        if (!directPaths.isEmpty()) shortestPath = directPaths.get(0);
        for (int index = 1; index < directPaths.size(); index++) {
            Path currentPath = directPaths.get(index);
            if (currentPath.getTotalDistance() < shortestPath.getTotalDistance()) {
                shortestPath = currentPath;
            }
        }
        return shortestPath;
    }

    private Node[] findOriginAndDestination(String originName, String destinationName) {
        Node origin = null;
        Node destination = null;
        //TODO: reuse nodeMap field once retriction on constructor is applied
        for (Node node : graphMap.keySet()) {
            if (node.getName().equalsIgnoreCase(originName)) origin = node;
            if (node.getName().equalsIgnoreCase(destinationName)) destination = node;
            if (origin != null && destination != null) break;
        }
        return new Node[] {origin, destination};
    }

}

Unit Test

public class GraphTest {

    @Test
    public void testAddEdge() {
        //given:
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");

        //and:
        Graph graph = new Graph();

        //when:
        Edge edgeAB = graph.addEdge(a, b, 10);
        Edge edgeBA = graph.addEdge(b, a, 17);

        //and:
        graph.addEdge(b, c, 2);

        //then:
        assertNotNull(edgeAB);
        assertEquals(10, edgeAB.getDistance());
        assertTrue(graph.hasEdge(a, b));

        //and:
        assertNotNull(edgeBA);
        assertEquals(17, edgeBA.getDistance());
        assertTrue(graph.hasEdge(b, a));

        //and:
        assertFalse(graph.hasEdge(a, c));
        assertTrue(graph.hasEdge(b, c));
    }

    //TODO: add checks for duplicate edges?

    @Test
    public void testGetPath() {
        //given:
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("D");

        //and:
        Graph graph = new Graph();
        graph.addEdge(a, b, 5);
        graph.addEdge(b, c, 4);

        //when:
        Path existentPath = graph.getPath(a, b, c);
        Path nonExistentPath = graph.getPath(a, b, c, d);

        //then:
        assertNotNull(existentPath);
        assertEquals(a, existentPath.getStation(0));

        //and:
        assertNull(nonExistentPath);
    }

    @Test
    public void testGetPathByNodeNames() {
        //given:
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");

        //and:
        Graph graph = new Graph();
        graph.addEdge(b, a, 9);
        graph.addEdge(c, b, 10);
        graph.addEdge(c, a, 7);

        //when:
        Path path = graph.getPath("C", "B", "A");

        //then:
        assertNotNull(path);
        assertEquals(19, path.getTotalDistance());
    }

    @Test
    public void testFindPathsWithMaximumStops() {
        //given:
        Graph graph = Graph.create("AB5", "BC4", "CD8", "DC8", "DE6", "AD5",
                "CE2", "EB3", "AE7");

        //when:
        List<Path> pathsMax3 = graph.findPathsWithMaximumStops("C", "C", 3);
        List<Path> pathsMax2 = graph.findPathsWithMaximumStops("C", "C", 2);
        List<Path> nonExistent = graph.findPathsWithMaximumStops("E", "A", 10);

        //then:
        assertNotNull(pathsMax3);
        assertEquals(2, pathsMax3.size());
        List<Integer> expectedDistances = asList(16, 9);
        for (Path path :pathsMax3) {
            assertTrue("Total distance should be any of the expected.",
                    expectedDistances.contains(path.getTotalDistance()));
        }

        //and:
        assertNotNull(pathsMax2);
        assertEquals(1, pathsMax2.size());
        Path path = pathsMax2.get(0);
        assertEquals("C", path.getStation(0).getName());
        assertEquals("D", path.getStation(1).getName());
        assertEquals("C", path.getStation(2).getName());

        //and:
        assertNotNull(nonExistent);
        assertTrue(nonExistent.isEmpty());
    }

    @Test
    public void testFindPathsWithMaximumDistance() {
        //given:
        Graph graph = Graph.create("AB5", "BC4", "CD8", "DC8", "DE6", "AD5",
                "CE2", "EB3", "AE7");

        //when:
        List<Path> paths = graph.findPathsWithMaximumDistance("C", "C", 30);

        //then:
        assertNotNull(paths);
        assertEquals(7, paths.size());

        //and:
        for (Path path : paths) {
            assertTrue(path.getTotalDistance() < 30);
            assertEquals("C", path.getStation(0).getName());
            assertEquals("C", path.getStation(path.countStops()).getName());
        }
    }

    @Test
    public void testFindShortestPath() {
        //given:
        Graph graph = Graph.create("AB5", "BC4", "CD8", "DC8", "DE6", "AD5",
                "CE2", "EB3", "AE7");

        //when:
        Path pathAC = graph.findShortestPath("A", "C");
        Path pathBB = graph.findShortestPath("B", "B");
        Path nonExistent = graph.findShortestPath("D", "A");

        //then:
        assertNotNull(pathAC);
        assertEquals(9, pathAC.getTotalDistance());

        //and:
        assertNotNull(pathBB);
        assertEquals(9, pathBB.getTotalDistance());

        //and:
        assertNull(nonExistent);
    }

    @Test
    public void testCreate() {
        //given:
        Graph graph = Graph.create("AB5", "BC4", "CD8", "DC8", "DE6");

        //expect:
        assertNotNull(graph);

        //and:
        assertTrue(graph.hasEdge("A", "B"));
        assertTrue(graph.hasEdge("B", "C"));
        assertTrue(graph.hasEdge("C", "D"));
        assertTrue(graph.hasEdge("D", "C"));
        assertTrue(graph.hasEdge("D", "E"));

        //and:
        assertEquals(5, graph.findEdge("A", "B").getDistance());
        assertEquals(4, graph.findEdge("B", "C").getDistance());
        assertEquals(8, graph.findEdge("C", "D").getDistance());
        assertEquals(8, graph.findEdge("D", "C").getDistance());
        assertEquals(6, graph.findEdge("D", "E").getDistance());

        //and:
        assertFalse(graph.hasEdge("D", "A"));
        assertFalse(graph.hasEdge("E", "B"));
    }

    @Test
    public void testCreateWithVaryingCase() {
        //given:
        Graph graph = Graph.create("aB9", "bc10", "CD2");

        //expect:
        assertTrue(graph.hasEdge("A", "b"));
        assertTrue(graph.hasEdge("B", "C"));
        assertTrue(graph.hasEdge("c", "d"));
    }

    //TODO update create method to check for correct inputs

    @Test
    public void testFindEdge() {
        //given:
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");

        //and:
        Graph graph = new Graph();
        graph.addEdge(a, b, 2);
        graph.addEdge(b, c, 4);
        graph.addEdge(c, b, 5);

        //and:
        Edge edgeBA = graph.addEdge(b, a, 7);

        //expect:
        assertEquals(edgeBA, graph.findEdge("B", "A"));
        assertNull(graph.findEdge("A", "C"));
    }

}
\$\endgroup\$
3
\$\begingroup\$

So the first thing I noticed:

if (destinationEdges == null) graphMap.put(destination, new ArrayList<Edge>());
return edge;

I thought why return edge if edge == null
Then I noticed you use multiple styles. That got me really confused.

I would have assumed it to be like this instead based on the style you use:

if (destinationEdges == null) 
    graphMap.put(destination, new ArrayList<Edge>());

return edge;

hasEdge is clearly something you used for unit testing, and should not exist in the main class.

Also why are the findEdge functions not both private or public?

And the following functions are way to big in my opinion.
Sometimes this is unavoidable, but I don't feel that this is the case:

  • findPathsWithMaximumStops
  • findPathsWithMaximumDistance
  • findDirectPaths

I feel that in the functions above the big Loops could partly be split of into a single function, making it easier to read and reuse.

\$\endgroup\$
  • \$\begingroup\$ Thanks for chiming in. hasEdge methods are designed to answer a specific question about the object's state, and there's no one else more qualified to do that than the object itself. Both hasEdge and findEdge classes of methods were primarily designed to expose the object's state for testing. One of the findEdge methods is set private because it's not used outside the Graph class but was separately defined to tidy up code. I think it's a "necessary evil" to have these methods because there's no other way to check state. \$\endgroup\$ – Psycho Punch May 23 '16 at 11:39
  • \$\begingroup\$ The problem with the methods that find paths is that they don't traverse the graph exactly in the same manner. True, traversing involves basically the same operations like move forward, build path, backtrack, etc. However, as noted in my question, they behave differently depending on the given criteria. I agree, however, that they can be refactored further to improve readability. But then again, since these methods have quite a number of method-specific states, the resulting methods will suffer from long argument lists. \$\endgroup\$ – Psycho Punch May 23 '16 at 12:03
  • \$\begingroup\$ Addendum to my previous comment: stackoverflow.com/a/476253/404604 \$\endgroup\$ – Psycho Punch May 23 '16 at 12:37

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.