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:
- There is insufficient test coverage with no evidence of Test Driven Development (TDD).
- There are quite a number of unused methods.
- Methods are unnecessarily long, and almost all logic is in the
Graphclass.
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"));
}
}
