Java DFS Implementation that tracks time and parent node

Question

I have a project where I'm to implement a DFS using a direct graph. The implementation should print the currently visited vertex, the parent (the node from which the current node was reached), and the discovery and finish time for each node.

Using these graph values:

int[] vertices = {1,2,3,4,5,6,7};
int[][] edges = {{1,2},{1,6},{2,3},{2,4},{2,5},{3,5},{4,5},{5,1},{6,4},{6,7}};

I get these results:

Vertex: 5 Parent: 3 Discovery: 0 Finished: 0
Vertex: 3 Parent: 3 Discovery: 0 Finished: 1
Vertex: 4 Parent: 2 Discovery: 2 Finished: 2
Vertex: 2 Parent: 2 Discovery: 0 Finished: 3
Vertex: 6 Parent: 1 Discovery: 4 Finished: 4
Vertex: 1 Parent: 1 Discovery: 0 Finished: 5

I think my implementation is correct, but I'm very new to graphs and would appreciate a review of my implementation.

Here is the actual code:

DfsSimulator

public class DfsSimulator {

   public static void main(String[] args) {
      int[] vertices = {1,2,3,4,5,6,7};
      int[][] edges = {{1,2},{1,6},{2,3},{2,4},{2,5},{3,5},{4,5},{5,1},{6,4},{6,7}};

      Graph graph = new AdjacencyList(vertices.length);
      for(int i = 0; i < edges.length; i++) {
         graph.addEdge(edges[i][0], edges[i][1]);
      }

      Searcher search = new Searcher(graph);
      search.dfs(graph.getAdj(), vertices[0]);
   }
}

Graph

import java.util.List;
import java.util.ArrayList;

public interface Graph {

   public void addEdge(int i, int j);
   public void removeEdge(int i, int j);
   public boolean hasEdge(int i, int j);
   public List<Integer> outEdges(int i);
   public List<Integer> inEdges(int i);
   public int getNumberVertices();
   public ArrayList<ArrayList<Integer>> getAdj();
}

AdjacencyList

import java.util.List;
import java.util.ArrayList;

public class AdjacencyList implements Graph {

   private int numOfVertices;
   private ArrayList<ArrayList<Integer>> adj;

   public AdjacencyList(int numOfVertices) {
      this.numOfVertices = numOfVertices;

      adj = new ArrayList<ArrayList<Integer>>(numOfVertices);
      for(int i = 0; i < numOfVertices; i++) {
         adj.add(new ArrayList<Integer>());
      }
   }

   @Override
   public void addEdge(int i, int j) {
      adj.get(i).add(j);
   }

   @Override
   public void removeEdge(int i, int j) {
      List<Integer> edges = adj.get(i);
      for(Integer integer : edges) {
         if(integer == j) { 
            edges.remove(integer);
            return;
         }
      }
   }

   @Override
   public boolean hasEdge(int i, int j) {
      return adj.get(i).contains(j);
   }

   @Override
   public List<Integer> outEdges(int i) {
      return adj.get(i);
   }

   @Override
   public List<Integer> inEdges(int i) {
      List<Integer> edges = new ArrayList<Integer>();
      for(int j = 0; j < numOfVertices; j++) {
         if(adj.get(j).contains(i)) {
            edges.add(j);
         }
      }
      return edges;
   }

   @Override
   public int getNumberVertices() { 
      return numOfVertices;
   }

   @Override
   public ArrayList<ArrayList<Integer>> getAdj() {
      return adj;
   }
}

Searcher

import java.util.List;
import java.util.ArrayList;

public class Searcher {

   private int time = 0;
   private int[] d;
   private int[] f;
   private int parent;

   public Searcher(Graph graph) {
      d = new int[graph.getNumberVertices()];
      f = new int[graph.getNumberVertices()];
   }

   public void dfs(ArrayList<ArrayList<Integer>> adj, int r) {
      int n = adj.size();
      boolean[] visited = new boolean[n];
      dfs(adj, r, visited);
   }

   private void dfs(ArrayList<ArrayList<Integer>> adj, int i, boolean[] visited) {
      visited[i] = true; 
      d[i] = time;
      for(int j : adj.get(i)) {
         if(j == adj.size()) { continue; }
         if(!visited[j]) {
            parent = i;
            dfs(adj, j, visited);
         }
      }
      f[i] = time;
      time++;
      System.out.println("Vertex: " + i + " Parent: " + parent +
         " Discovery: " + d[i] + " Finished: " + f[i]);
   }

   public int getTime() { return time; }
   public int[] getDiscoveryTimes() { return d; }
   public int[] getFinishTimes() { return f; }

Answer 1

Bug: Vertex numbering

Right now, your program has a bug because it doesn't show the output for vertex 7. I traced this bug to the fact that in AdjacencyList.java you create an ArrayList of size 7, but your vertices are numbered 1-7 so you actually don't have any information for vertex 7. I think you need to either:

1. Number your vertices using a 0-based numbering system, from 0..6.
2. Rewrite AdjancencyList.java keep a map of the actual vertex numbers to 0..6.

This also shows that there was a suspicious line in Searcher.java that can be removed once you fixed the vertex numbering:

     if(j == adj.size()) { continue; }

When to advance time

It's not clear from your problem specification what "time" means. But right now, you have multiple vertices discovered at the same time. It doesn't make sense to me that you can discover two vertices at the same time. I think you should advance your time every time you move up or down the tree. So you should add another time++ line here at the top of your function:

  d[i] = time;
  time++;

With this change (plus renumbering the vertices to be 0-based), the output becomes:

Vertex: 4 Parent: 2 Discovery: 3 Finished: 4
Vertex: 2 Parent: 2 Discovery: 2 Finished: 5
Vertex: 3 Parent: 1 Discovery: 6 Finished: 7
Vertex: 1 Parent: 1 Discovery: 1 Finished: 8
Vertex: 6 Parent: 5 Discovery: 10 Finished: 11
Vertex: 5 Parent: 5 Discovery: 9 Finished: 12
Vertex: 0 Parent: 5 Discovery: 0 Finished: 13

This makes more sense to me because now I can see how it moved through the tree at each step.

Answer 2

It looks pretty good. Only a couple of comments:

• I don't like lists of lists. I'd introduce a class Vertex to hold the adjacency list of a single vertex, then make the Graph have a list of these.
• Your interface Graph leaks implementation details, I.e. that you're using an ArrayList to store your vertices. It should probably use the more general List interface instead.
• The way the Graph interface is defined, there don't seem to be any other possible implementations. I'd consider just having a single class rather than an interface here, for the sake of simplicity.