Parallelization of Boruvka's Algorithm

[Adarsh Kishore]

Hi everyone, 

I was going through the file `SAGE_ROOT/src/sage/graphs/spanning_tree.pyx` and I found this in the TODO section

I read up on Boruvka's algorithm for finding the minimum spanning tree of a graph and have implemented a serialized version of it in Python. Can someone link me to resources on how to parallelize this algorithm?

[Adarsh Kishore]

I think I might get how to do it. Can I open a ticket for this?

[jonatha...@googlemail.com]

Sure. Since this is written in cython, using https://cython.readthedocs.io/en/latest/src/userguide/parallelism.html might be a good choice.

This is also used in `src/sage/geometry/polyhedron/combinatorial_polyhedron/face_iterator.pyx`. Note the first two lines of the file. With those lines, you can just do `from cython.parallel cimport ...` and use it.

If your computer has `OpenMP`, this should parallelize.

But depends a bit on the details. You can just cc me (gh-kliem) on the ticket and we can discuss the details from there.

And make sure to mention the ticket number here, so anyone interested can just take a look.

[Adarsh Kishore]

Thanks! I have opened https://trac.sagemath.org/ticket/33703 and CCed you