Google Answers Logo
View Question
 
Q: Java Code question ( Answered 4 out of 5 stars,   0 Comments )
Question  
Subject: Java Code question
Category: Computers > Programming
Asked by: tokes-ga
List Price: $30.00
Posted: 01 Dec 2004 17:44 PST
Expires: 31 Dec 2004 17:44 PST
Question ID: 436873
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.
Answer  
Subject: Re: Java Code question
Answered By: dogbite-ga on 02 Dec 2004 04:48 PST
Rated:4 out of 5 stars
 
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
tokes-ga rated this answer:4 out of 5 stars

Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy