<div dir="ltr">Marat,<div><br></div><div>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:</div><div><br></div><div>1. represent the graph as an adjacency matrix;</div><div>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);</div><div>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</div><div><br></div><div>Of course, this is for unlabeled associations. If your associations are typed, you'll need a tensor structure rather.</div><div><br></div><div>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.</div><div><br></div><div>The lookups themselves could also be performed in parallel.</div><div><br></div><div>This is just an example, you could also calculate things like centrality and connectedness in parallel with a little ingenuity.<br></div><div><br></div><div>I hope this helps, even though it's not Haskell specific,</div><div><br></div><div>Flavio</div><div><br></div><div><br></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature">Flavio Villanustre</div></div>
<br><div class="gmail_quote">On Thu, Feb 12, 2015 at 8:24 AM, Закиров Марат <span dir="ltr"><<a href="mailto:marat61@gmail.com" target="_blank">marat61@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi all,<div><br></div><div>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. </div><div><br></div><div>Summarizing: I want to find example of data_persistence&functional style killer graph (compiler) application.</div><div><br></div><div>Do you know such an example?<span class="HOEnZb"><font color="#888888"><br></font></span></div><span class="HOEnZb"><font color="#888888"><div><div><br></div>-- <br><div><div dir="ltr"><div><font size="4" face="courier new, monospace"><i>Regards, Marat.<br></i></font></div><font size="4" face="courier new, monospace"><i>С уважением Марат.</i></font></div></div>
</div></font></span></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>