hadoop-common-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Derek Anderson <pub...@kered.org>
Subject Re: Finding longest path in a graph
Date Thu, 29 Jan 2009 22:06:35 GMT
2 questions.  first, why are you storing the direction?  isn't that 
implied in (V1,V2,dist)?  (direction: V1->V2) unless you're storing each 
edge twice for some caching purpose i'm not seeing?

second, by definition the longest path in a cyclic graph is infinitely 
long.  you need to convert it into a DAG.

once you've done that, the Bellman-Ford algorithm for shortest path will 
work.  just invert your distance values.

derek


Andrzej Bialecki wrote:
> Hi,
> 
> I'm looking for an advice. I need to process a directed graph encoded as 
> a list of <from, to> pairs. The goal is to compute a list of longest 
> paths in the graph. There is no guarantee that the graph is acyclic, so 
> there should be some mechanism to detect cycles.
> 
> Currently I'm using a simple approach consisting of the following: I 
> encode the graph as <vertex, <neighbor, direction, distance>>, and 
> extending the paths by one degree at a time. This means that in order to 
> find the longest path of degree N it takes N + 1 map-reduce jobs.
> 
> Are you perhaps aware of a smarter way to do it? I would appreciate any 
> pointers.
> 


Mime
View raw message