I am trying to write code that will compute the longest path in a
directed acyclic graph.  I am trying to keep the time complexity to
not exceed O(n^2), with 'n' being the number of vertices in the graph.
I think recursion is the best way to approach this type of problem but
i am having trouble with this approach. What would the code be? Must
be in java.

Hi tokes-ga,

There are two keys to the solution.  The first is, as you suggest,
recursion.  The second is memoization, where we'll save computed
answers so we don't have to compute them again in the future.
Memoization is a programming trick that trades space (memory needed by
the program) for time (computation effort).  This allows us to achieve
the O(n^2) time bound that you desire.

To grasp the recursion, observe that the longest path starting from
any particular vertex, v, is the maximum longest path starting from a
neighboring vertex v', plus the single step from v to v'.

Turning to the Java code, assume you have a Vertex class that
represents a single vertex in the graph.  An array of each vertex's
neighbors is retrieved with the Vertex class's method:

public Vertex[] getNeighbors()

We'll put our code within a Graph class that contains a private
variable that is an array of Vertex objects.  I imagine that you have
already written these classes with similar methods, along with code
for initializing them.  Then we can write the following code:

public class Graph {

  import java.util.*;

  private Vertex[] vertices;


  // your constructor and initialization code goes here.  it will
  // initialize the vertices array.


  // the public method that looks for the longest path starting
  // from each vertex in the graph
  public LinkedList findLongestPath() {

    LinkedList longestPath = null;
    Hashtable memo = new Hashtable();

    for (int i = 0; i < vertices.length; i++) {

      LinkedList tmpPath = findLongestPathFromVertex(vertices[i], memo);

      if ((longestPath = null) ||
          (tmpPath.size() > longestPath.size())) {

        longestPath = tmpPath;
      }
    }
    return longestPath;
  }

  // a recursive function to find the longest path from a
  // particular vertex in the graph.
  private LinkedList findLongestPathFromVertex(Vertex v, Hashtable memo) {

    // we might have already computed the answer
    LinkedList longestPath = (LinkedList) memo.get(v);

    // if we didn't, we'll compute it now
    if (longestPath == null) {
      LinkedList longestNeighborPath = null;
      Vertex[] neighbors = v.getneighbors();

      for (int i = 0; i < neighbors.length; i++) {

        // this is the recursive step
        LinkedList tmpPath = findLongestPathFromVertex(neighbors[i], memo);

        // we only want to keep the maximum longest neighbor path
        if ((longestNeighborPath == null) ||
            (tmpPath.size() > longestNeighborPath.size())) {
          longestNeighborPath = tmpPath;
        }
      }

      if (longestNeighborPath != null) {
        longestPath = longestNeighborPath.clone();
      }
      else {
        // this covers the case for when there are no neighbors
        longestPath = new LinkedList();
      }

      // here we add the current vertex to the longest path at a neighbor
      longestPath.addFirst(v);

      // and we record the result, which is the second key, memoization
      memo.put(v, longestPath);
    }

    return longestPath;
  }

}


I hope this answers your question.

Sincerely,
dogbite-ga
Google Answers Researcher