James Cipar wrote:
>
> 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?
I think I'm interested in paths that don't pass the same vertex more
than once  see below.
>
> 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
> NPcomplete, 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.
I'm working with web graphs. One type of a graph is where vertices are
URLs, and edges represent HTTP redirects (or content redirects 
doesn't matter). I'm interested in resolving the final URL, given a
starting URL, so a more precise statement is that I don't need to know
the complete path, only the start and end of a path.
Such graphs are not acyclic  as you are no doubt aware there are pages
that redirect to themselves, or ones that redirect in cycles, sometimes
spanning several intermediate pages.
Another type of a graph is the common web graph where vertices are URLs
and edges are outlinks. In this case I'm more interested in detecting
cycles of a given size than in finding the longest path.
>
> 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 mapreduce. 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 odddegree
> vertices).
I don't think this helps in my situation, as far as I understand you ...
> Good luck,
This doesn't sound too optimistic ;)
Thanks!

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