Oh, hail to the creator of Luke!Mark On Thu, Jan 29, 2009 at 11:20 AM, Andrzej Bialecki <[email protected]> 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. > > -- > Best regards, > Andrzej Bialecki <>< > ___. ___ ___ ___ _ _ __________________________________ > [__ || __|__/|__||\/| Information Retrieval, Semantic Web > ___|||__|| \| || | Embedded Unix, System Integration > http://www.sigram.com Contact: info at sigram dot com > >
