Kruskal's Algorithm using Priority Queues

[Adarsh Kishore]

Hi everyone,

I was going through Sage's codebase, and I came across the file

```

SAGE_ROOT/src/sage/graphs/spanning_tree.pyx

```

In the TODO section, it is mentioned that 

```

    - Rewrite: func:`kruskal` to use priority queues.

```

I looked it up on Google and StackOverFlow, but I didn't come across any such implementation. The standard implementations all prefer to use the DisjointSet data structure. I would like to contribute to Sage and if someone can point me to a good resource which discusses this concept, preferably with a better time complexity than by using Disjoint Sets, that would be really great

[David Coudert]

This query has been added in https://trac.sagemath.org/ticket/10433.

I don't think that priority queue can be of any help to speed up the current code.

[Adarsh Kishore]

Okay, then I think that line should be removed right? It can be misleading to potential contributors

[Adarsh Kishore]

I can open a ticket to correct this if you want

[David Coudert]

Sure, feel free to open a ticket to correct this.

[Adarsh Kishore]

https://trac.sagemath.org/ticket/33688
I have done the change

[Enjeck Cleopatra]

Just wondering if the third TODO (Randomized spanning tree construction) should be removed as well, since I see a function called "random_spanning_tree" exists already.

[David Coudert]

You are right, this can be removed too.

And I'm not sure a parallel version of Boruvka's algorithm is needed. We already have a large number of spanning tree algorithms.

[Adarsh Kishore]

Can I make these changes in https://trac.sagemath.org/ticket/33688 as discussed? The ticket has not been closed yet

[Adarsh Kishore]

By the way, I opened https://trac.sagemath.org/ticket/33703 after a discussion on https://groups.google.com/g/sage-devel/c/R3r3G_Qrllo.

If I am successful, we will test it to see if there are any performance improvements over the sequential version, else we can remove that line.

Is that fine?

[davida...@gmail.com]

Yes, you just need to change it back to "need review" so that it can be reviewed.