When you say that you want to avoid cycles, do you mean that the path
cannot pass through the same vertex more than once, or cannot pass
through the same edge more than once?
If you mean that it can't pass through the same vertex, I don't think
there is an easy solution. If there is a Hamiltonian path in the
graph , your algorithm will find it, so your algorithm cannot be
better than the best Hamiltonian path algorithm. Finding a
Hamiltonian path is NP-complete, so map reduce will probably not help
you. Perhaps your graphs have some extra structure that could be
exploited? There are efficient solutions for DAGs, but you
specifically said the graph may have cycles.
If you mean that it can't pass through the same edge more than once,
then it is probably easier, but I can't imagine how all of it would
work in map-reduce. A path that visits each edge exactly once is
simple to compute, assuming such a path exists. The path exists in
every connected graph with either 0, or 2 vertices with odd degree.
So maybe you can find connected components, give each vertex a value
that is its degree rounded down to the nearest integer, and pick the
component with the largest total value (adding 2 to the value if it
has at least 2 odd degree vertices). Then you just have to find the
Eulerian path in that component (by first eliminating edges from all
but two odd-degree vertices).
Good luck,
Jim
On Jan 29, 2009, at 12:36 PM, Miles Osborne wrote:
this is perhaps worth watching:
http://www.youtube.com/watch?v=BT-piFBP4fE&feature=channel
it deals with finding the shortest path in a graph using MR. here at
work i don't have audio working so i'm not 100% sure that this is the
best way to do it, but it is a start.
Miles
2009/1/29 Mark Kerzner <[email protected]>:
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
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.
