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.
--
Best regards,
Andrzej Bialecki <><
___. ___ ___ ___ _ _ __________________________________
[__ || __|__/|__||\/| Information Retrieval, Semantic Web
___|||__|| \| || | Embedded Unix, System Integration
http://www.sigram.com Contact: info at sigram dot com
