search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.27k stars 435 forks source link

Parallelization of Boruvka's algorithm #33703

Open a5cff67d-07f8-46a5-a0b6-93601583e2f7 opened 2 years ago

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago

As per the discussion on https://groups.google.com/g/sage-devel/c/R3r3G_Qrllo, opening this ticket to parallelize Boruvka's algorithm.

CC: @kliem

Component: graph theory

Author: Adarsh Kishore

Issue created by migration from https://trac.sagemath.org/ticket/33703

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago

Author: Adarsh Kishore

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+As per the discussion on https://groups.google.com/g/sage-devel/c/R3r3G_Qrllo, opening this ticket to parallelize Boruvka's algorithm.
a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:2

So what I was thinking is based on this excellent video I found - https://www.coursera.org/lecture/concurrent-programming-in-java/demonstration-parallelization-of-boruvkas-minimum-spanning-tree-algorithm-yaOEz?utm_source=link&utm_medium=page_share&utm_content=vlp&utm_campaign=top_button

This is done in Java, but the concepts are clear to me. I am planning to implement mutex locks in Cython and use them in a similar manner.

Do you think this will work?

kliem commented 2 years ago
comment:3

For reference:

https://stackoverflow.com/questions/71851885/implementing-multiple-mutex-locks-in-cython

kliem commented 2 years ago
comment:4

Actually, sage isn't just written in Python and Cython and also you can use many things from C++ in cython (one example of what does not work, is templates using integers, e.g. https://en.cppreference.com/w/cpp/utility/bitset/bitset) and there is even pure C or C++.

One advantage/disadvantage of using parallelism via cython is that one needs to release the GIL. So first of all one needs to evaluate what data type is our input and what operations do we need to do. And is the conversion of the input worth the effort.

However, the current algorithm also takes a complete copy of the graph and then proceeds, so for the input conversion, I believe we are good.

I would recommend not to reinvent the wheel. So definitely go with DavidWs suggested and use https://en.cppreference.com/w/cpp/thread/mutex.

The lock part is pretty much clear to me. What is not clear to me is the following:

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:5

Replying to @kliem:

Actually, sage isn't just written in Python and Cython and also you can use many things from C++ in cython (one example of what does not work, is templates using integers, e.g. https://en.cppreference.com/w/cpp/utility/bitset/bitset) and there is even pure C or C++.

One advantage/disadvantage of using parallelism via cython is that one needs to release the GIL. So first of all one needs to evaluate what data type is our input and what operations do we need to do. And is the conversion of the input worth the effort.

However, the current algorithm also takes a complete copy of the graph and then proceeds, so for the input conversion, I believe we are good.

I would recommend not to reinvent the wheel. So definitely go with DavidWs suggested and use https://en.cppreference.com/w/cpp/thread/mutex.

The lock part is pretty much clear to me. What is not clear to me is the following:

  • What data structure do we use, e.g. what is a vertex?
  • What happens at the merge.

Thank you for these resources. I will go through them properly. As for the parts that are not clear, I was planning to modify the already present boruvka function in SAGE_ROOT/src/graphs/spanning_tree.pyx to use mutex locks and multithreading. Thus the vertex and merging will be as done in that algorithm, unless I feel there is need for changing that.

kliem commented 2 years ago
comment:6

In cython parallel code, you cannot use anything that requires the GIL. So no dict, no DisjointSet_of_hashables etc. So there is a bit of work to be done with the data structures.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:7

For starters, I will try to remove all Python objects from the section that I want to Cythonize. For example, for dict I can use map from C++, for list I can use a vector, again from C++, or a numpy array.

DisjointSet_of_hashtables might require more thought, but I think implementing an equivalent class in C++ should be helpful.

What do you say about this approach? Also, can you guide me to some resources on using C++ in Cython?

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:8

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

kliem commented 2 years ago
comment:9

Replying to @adarsh-kishore786:

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

sage -b.

For python changes with --enable-editable, even restarting will be fine.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:10

Replying to @kliem:

Replying to @adarsh-kishore786:

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

sage -b.

For python changes with --enable-editable, even restarting will be fine.

u mean ./sage -b in SAGE_ROOT?

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:11

And if I only want to build a specific file, like spanning_tree.pyx and not the whole Sage?

kliem commented 2 years ago
comment:12

Replying to @adarsh-kishore786:

Replying to @kliem:

Replying to @adarsh-kishore786:

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

sage -b.

For python changes with --enable-editable, even restarting will be fine.

u mean ./sage -b in SAGE_ROOT?

Yes, if you have different sage version, then this is how you have to do it. Of course, you can create an appropriate symlink to your sage to simplify things.

This will only build what changed during the last build. So if you only modify spanning_tree.pyx, it builds this and everything that depends on it.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:13

Replying to @kliem:

Replying to @adarsh-kishore786:

Replying to @kliem:

Replying to @adarsh-kishore786:

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

sage -b.

For python changes with --enable-editable, even restarting will be fine.

u mean ./sage -b in SAGE_ROOT?

Yes, if you have different sage version, then this is how you have to do it. Of course, you can create an appropriate symlink to your sage to simplify things.

This will only build what changed during the last build. So if you only modify spanning_tree.pyx, it builds this and everything that depends on it.

In my case, it is building everything it seems.

[sagelib-9.6.beta4] Discovering Python/Cython source code....
[sagelib-9.6.beta4] distributions = ['']
[sagelib-9.6.beta4] Discovered Python/Cython sources, time: 14.45 seconds.
[sagelib-9.6.beta4] running build
[sagelib-9.6.beta4] Generating auto-generated sources
[sagelib-9.6.beta4] Building interpreters for fast_callable
[sagelib-9.6.beta4] running build_cython
[sagelib-9.6.beta4] Enabling Cython debugging support
[sagelib-9.6.beta4] Compiling sage/schemes/toric/divisor_class.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/mod_sym_num.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/descent_two_isogeny.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/period_lattice_region.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/hyperelliptic_curves/hypellfrob.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/permutation_cython.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/expnums.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/combinat_cython.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/degree_sequences.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/debruijn_sequence.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/root_system/reflection_group_c.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/posets/hasse_cython.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/matrices/dancing_links.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/integer_lists/base.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/integer_lists/invlex.pyx because it depends on ./sage/combinat/integer_lists/base.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/evenly_distributed_sets.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/designs_pyx.pyx because it depends on ./sage/data_structures/sparse_bitset.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/orthogonal_arrays_find_recursive.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/gen_quadrangles_with_spread.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/rigged_configurations/rigged_partition.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/letters.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/tensor_product_element.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/pbw_datum.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/words/word_datatypes.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/words/word_char.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/probability/probability_distribution.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/coerce_maps.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/category_object.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/parent_base.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/list_clone.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/parent_gens.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/element.pyx because it changed.
...

I ran ./sage -b

kliem commented 2 years ago
comment:14

Replying to @adarsh-kishore786:

For starters, I will try to remove all Python objects from the section that I want to Cythonize. For example, for dict I can use map from C++, for list I can use a vector, again from C++, or a numpy array.

DisjointSet_of_hashtables might require more thought, but I think implementing an equivalent class in C++ should be helpful.

What do you say about this approach? Also, can you guide me to some resources on using C++ in Cython?

It might be best to think about some reasonable benchmarks first and then do changes. If you are going to use random graphs, you can reproduce them with the help of graph6_string.

A little starter for C++:

sage: cython('''
....: # distutils: language=c++
....: from libcpp.vector cimport vector
....: cdef vector[int] foo
....: ''')

If we are going to do it parallel, I would really recommend rethinking the data structures. What is merge going to do. E.g. the whole business of caching seems to be to complicated during the algorithm. All we need to have is a map between the vertices and range(n). Then our vertices have index size_t and we could do something like:

sage: cython('''
....: # distutils: language=c++
....: from libcpp.vector cimport vector
....: cdef struct edge:
....:     size_t vertex1
....:     size_t vertex2
....:     size_t weight
....: cdef vector[edge] edges = vector[edge]()
....: ''')
kliem commented 2 years ago
comment:15

Replying to @adarsh-kishore786:

Replying to @kliem:

Replying to @adarsh-kishore786:

Replying to @kliem:

Replying to @adarsh-kishore786:

Also, one minor thing. How do you recompile Sage code after making a change in Sage source code?

sage -b.

For python changes with --enable-editable, even restarting will be fine.

u mean ./sage -b in SAGE_ROOT?

Yes, if you have different sage version, then this is how you have to do it. Of course, you can create an appropriate symlink to your sage to simplify things.

This will only build what changed during the last build. So if you only modify spanning_tree.pyx, it builds this and everything that depends on it.

In my case, it is building everything it seems.

[sagelib-9.6.beta4] Discovering Python/Cython source code....
[sagelib-9.6.beta4] distributions = ['']
[sagelib-9.6.beta4] Discovered Python/Cython sources, time: 14.45 seconds.
[sagelib-9.6.beta4] running build
[sagelib-9.6.beta4] Generating auto-generated sources
[sagelib-9.6.beta4] Building interpreters for fast_callable
[sagelib-9.6.beta4] running build_cython
[sagelib-9.6.beta4] Enabling Cython debugging support
[sagelib-9.6.beta4] Compiling sage/schemes/toric/divisor_class.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/mod_sym_num.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/descent_two_isogeny.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/elliptic_curves/period_lattice_region.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/schemes/hyperelliptic_curves/hypellfrob.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/permutation_cython.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/expnums.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/combinat_cython.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/degree_sequences.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/debruijn_sequence.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/root_system/reflection_group_c.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/posets/hasse_cython.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/matrices/dancing_links.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/integer_lists/base.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/integer_lists/invlex.pyx because it depends on ./sage/combinat/integer_lists/base.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/evenly_distributed_sets.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/designs_pyx.pyx because it depends on ./sage/data_structures/sparse_bitset.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/orthogonal_arrays_find_recursive.pyx because it depends on ./sage/rings/integer.pxd.
[sagelib-9.6.beta4] Compiling sage/combinat/designs/gen_quadrangles_with_spread.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/rigged_configurations/rigged_partition.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/letters.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/tensor_product_element.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/crystals/pbw_datum.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/words/word_datatypes.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/combinat/words/word_char.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/probability/probability_distribution.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/coerce_maps.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/category_object.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/parent_base.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/list_clone.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/parent_gens.pyx because it changed.
[sagelib-9.6.beta4] Compiling sage/structure/element.pyx because it changed.
...

I ran ./sage -b?replyto=7#comment

That all it takes, if you only change sage/graphs/spanning_tree.pyx:

[sagelib-9.6.rc0] [1/1] Cythonizing sage/graphs/spanning_tree.pyx
[sagelib-9.6.rc0] Executing 1 command (using 1 thread)
[sagelib-9.6.rc0] [1/1] build/cythonized/sage/graphs/spanning_tree.c:24647:20: warning: ‘__pyx_mdef_4sage_9structure_7element_3have_same_parent’ defined but not used [-Wunused-variable]
[sagelib-9.6.rc0] 24647 | static PyMethodDef __pyx_mdef_4sage_9structure_7element_3have_same_parent = {"have_same_parent", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_4sage_9structure_7element_3have_same_parent, METH_VARARGS|METH_KEYWORDS, __pyx_doc_4sage_9structure_7element_2have_same_parent};
[sagelib-9.6.rc0]       |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[sagelib-9.6.rc0] build/cythonized/sage/graphs/spanning_tree.c:24301:20: warning: ‘__pyx_mdef_4sage_9structure_7element_1parent’ defined but not used [-Wunused-variable]
[sagelib-9.6.rc0] 24301 | static PyMethodDef __pyx_mdef_4sage_9structure_7element_1parent = {"parent", (PyCFunction)__pyx_pw_4sage_9structure_7element_1parent, METH_O, __pyx_doc_4sage_9structure_7element_parent};
[sagelib-9.6.rc0]       |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[sagelib-9.6.rc0] build/cythonized/sage/graphs/spanning_tree.c:17125:20: warning: ‘__pyx_mdef_4sage_7cpython_6string_3str_to_bytes’ defined but not used [-Wunused-variable]
[sagelib-9.6.rc0] 17125 | static PyMethodDef __pyx_mdef_4sage_7cpython_6string_3str_to_bytes = {"str_to_bytes", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_4sage_7cpython_6string_3str_to_bytes, METH_VARARGS|METH_KEYWORDS, __pyx_doc_4sage_7cpython_6string_2str_to_bytes};
[sagelib-9.6.rc0]       |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[sagelib-9.6.rc0] build/cythonized/sage/graphs/spanning_tree.c:16919:20: warning: ‘__pyx_mdef_4sage_7cpython_6string_1bytes_to_str’ defined but not used [-Wunused-variable]
[sagelib-9.6.rc0] 16919 | static PyMethodDef __pyx_mdef_4sage_7cpython_6string_1bytes_to_str = {"bytes_to_str", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_4sage_7cpython_6string_1bytes_to_str, METH_VARARGS|METH_KEYWORDS, __pyx_doc_4sage_7cpython_6string_bytes_to_str};
[sagelib-9.6.rc0]       |                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[sagelib-9.6.rc0] In file included from build/cythonized/sage/graphs/spanning_tree.c:4374:
[sagelib-9.6.rc0] sage/groups/perm_gps/partn_ref2/refinement_generic.h:19:12: warning: ‘my_comp_func’ defined but not used [-Wunused-function]
[sagelib-9.6.rc0]    19 | static int my_comp_func(const void *a, const void *b)
[sagelib-9.6.rc0]       |            ^~~~~~~~~~~~
[sagelib-9.6.rc0] Time to execute 1 command: 11.96 seconds.
[sagelib-9.6.rc0] Total time spent compiling C/C++ extensions: 12.01 seconds.
[sagelib-9.6.rc0] warning: no files found matching '*.hh' anywhere in distribution
[sagelib-9.6.rc0] warning: no files found matching '*.inc' anywhere in distribution
[sagelib-9.6.rc0] no previously-included directories found matching '.tox'
[sagelib-9.6.rc0] warning: no directories found matching 'sage/libs/gap/test'
[sagelib-9.6.rc0] no previously-included directories found matching 'sage_setup'
[sagelib-9.6.rc0] Cleaning up stale file: /home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/ext_data/nbconvert/__pycache__/postprocess.cpython-38.pyc
[sagelib-9.6.rc0] 
[sagelib-9.6.rc0] real  0m25,827s
[sagelib-9.6.rc0] user  0m22,311s
[sagelib-9.6.rc0] sys   0m2,156s

real    0m25,919s
user    0m22,400s
sys 0m2,161s
Sage build/upgrade complete!

However, if you change branches, then more files might be touched. An initial build always takes time, but once you only change that one file, it won't take that long.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:16

Replying to @kliem:

Replying to @adarsh-kishore786:

For starters, I will try to remove all Python objects from the section that I want to Cythonize. For example, for dict I can use map from C++, for list I can use a vector, again from C++, or a numpy array.

DisjointSet_of_hashtables might require more thought, but I think implementing an equivalent class in C++ should be helpful.

What do you say about this approach? Also, can you guide me to some resources on using C++ in Cython?

It might be best to think about some reasonable benchmarks first and then do changes. If you are going to use random graphs, you can reproduce them with the help of graph6_string.

A little starter for C++:

sage: cython('''
....: # distutils: language=c++
....: from libcpp.vector cimport vector
....: cdef vector[int] foo
....: ''')

If we are going to do it parallel, I would really recommend rethinking the data structures. What is merge going to do. E.g. the whole business of caching seems to be to complicated during the algorithm. All we need to have is a map between the vertices and range(n). Then our vertices have index size_t and we could do something like:

sage: cython('''
....: # distutils: language=c++
....: from libcpp.vector cimport vector
....: cdef struct edge:
....:     size_t vertex1
....:     size_t vertex2
....:     size_t weight
....: cdef vector[edge] edges = vector[edge]()
....: ''')

Thanks a lot, I'll follow this advice

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:17

So just as an example, I wrote the DisjointSet data structure in C++. https://github.com/adarsh-kishore786/Programming/tree/main/Cython/DisjointSets

I plan to Cythonize it to see if it at least works, and then I can do an equivalent thing in Sage's codebase.

What do you think of it?

kliem commented 2 years ago
comment:18

Can we please use as many standard implementations as possible. There is already std::set. So unless there is a good reason for it, I would recommend using that.

Also, can you please provide some examples on what kind of timings you want to improve or some interesting problems. As David Coudert pointed out (https://groups.google.com/g/sage-devel/c/flB1dxXDmnc/m/oOvJoPZ6BAAJ), we already have a large number of spanning tree algorithms. So I would be curious, if you can give me a graph in sage, for which obtaining a minimal spanning tree is a challenge. If there is no such thing, then I'm not sure why we are optimizing Boruvka's algorithm.

kliem commented 2 years ago
comment:19

Also, before you start implementing a data structure, I would be curious on what we need:

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:20

I am planning to

I hope this makes sense, otherwise I would be happy to clarify.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:21

Replying to @kliem:

Can we please use as many standard implementations as possible. There is already std::set. So unless there is a good reason for it, I would recommend using that.

Also, can you please provide some examples on what kind of timings you want to improve or some interesting problems. As David Coudert pointed out (https://groups.google.com/g/sage-devel/c/flB1dxXDmnc/m/oOvJoPZ6BAAJ), we already have a large number of spanning tree algorithms. So I would be curious, if you can give me a graph in sage, for which obtaining a minimal spanning tree is a challenge. If there is no such thing, then I'm not sure why we are optimizing Boruvka's algorithm.

I am not sure how std::set can be used as a DisjointSet. Can you explain?

kliem commented 2 years ago
comment:22

What do you mean by DisjointSet. What is this? What does this class do.

Is the purpose of DisjointSet to map each vertex to the current adjacency list?

There is no need to implement a C++ class in cython. We can just import it using cdef extern from "myclass.cpp": Then it will just compile the corrsponding part.

I think I almost got it. Before we proceed, I'm asking you to provide examples of graphs. Otherwise this whole thing is pointless. If the current algorithms work fine for all graphs, then we shouldn't worry about it.

kliem commented 2 years ago
comment:23

There is no need to implement a parallel algorithm in sage for educational purpose, I believe. Everything in sage has to be maintained and without use cases, this would be a burden.

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:24

Replying to @kliem:

What do you mean by DisjointSet. What is this? What does this class do.

Is the purpose of DisjointSet to map each vertex to the current adjacency list?

There is no need to implement a C++ class in cython. We can just import it using cdef extern from "myclass.cpp": Then it will just compile the corrsponding part.

I think I almost got it. Before we proceed, I'm asking you to provide examples of graphs. Otherwise this whole thing is pointless. If the current algorithms work fine for all graphs, then we shouldn't worry about it.

A DisjointSet is as described in https://en.wikipedia.org/wiki/Disjoint-set_data_structure. It will support operations

a5cff67d-07f8-46a5-a0b6-93601583e2f7 commented 2 years ago
comment:25

Replying to @kliem:

There is no need to implement a parallel algorithm in sage for educational purpose, I believe. Everything in sage has to be maintained and without use cases, this would be a burden.

I understand your point. I will try to come up with a convincing example graph to demonstrate that we indeed need this, or as discussed in https://groups.google.com/g/sage-devel/c/flB1dxXDmnc/m/oOvJoPZ6BAAJ,we can remove this line from the TODO list in https://github.com/sagemath/sage-prod/issues/33703

kliem commented 2 years ago
comment:26

Don't understand me wrong. I'm a big fan of parallelization and very curious, whether this can make a difference here. But I also think parallelization should be a last resort.