[Haskell-cafe] example

[Flavio Villanustre]

Marat,

There are many ways to truly parallelize (and distribute) the execution of
graph algorithms, but it largely depends on what you are trying to do with
that graph. For example, if you are interested in graph traversal (find the
shortest path from point A to point B in a DAG), and you want to reduce the
runtime complexity of that path traversal algorithm to a simple O(log n)
lookup (n being the number of nodes) so that you can efficiently perform
many of these lookups in parallel in a graph that doesn't necessarily fit
in RAM, you could:

1. represent the graph as an adjacency matrix;
2. multiply that square matrix by itself to obtain the matrix representing
the next degree of separation (this can be done in parallel using Strassen,
for example);
3. materialize those matrices as b-trees. Each b-tree will represent an
association at x degrees of separation between nodes. If your graph adheres
to a small world, you only need 4 of these matrices to traverse any path up
to 8 degrees of separation

Of course, this is for unlabeled associations. If your associations are
typed, you'll need a tensor structure rather.

Another option would be to use an adjacency list and just use relational
join operations (also parallelizable) to perform the same task. Keep in
mind that graphs are isomorphic to adjacency matrices and adjacency lists.

The lookups themselves could also be performed in parallel.

This is just an example, you could also calculate things like centrality
and connectedness in parallel with a little ingenuity.

I hope this helps, even though it's not Haskell specific,

Flavio



Flavio Villanustre

On Thu, Feb 12, 2015 at 8:24 AM, Закиров Марат <marat61 at gmail.com> wrote:

> Hi all,
>
> Algorithms on graphs in my opinion is something bad for parallel execution
> (especially  such of them which have O(n) comlexity). So if I haskell give
> me an advantage in some graph application it will be great benchmark.
> Recently I tried to think about well-known by compiler people - so called
> "topologic-sort" or reverse post order numeration, but I gave up... There
> are just nothing to execute in parallel. Currently I am searching for graph
> (compiler) algorithm example written in haskell with persistent data
> structures which can be executed in parallel. And in the same time this
> example written in imperative style must not have good parallel execution
> form.
>
> Summarizing: I want to find example of data_persistence&functional style
> killer graph (compiler) application.
>
> Do you know such an example?
>
> --
>
> *Regards, Marat.*
> *С уважением Марат.*
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20150213/c47d40db/attachment.html>