New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Enumeration of Spanning trees in increasing order of weights #27532
Comments
Changed keywords from none to enumeration, spanning trees |
comment:1
Following paper cover algorithms for enumerating the spanning trees in undirected weighted graphs. http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004 |
comment:2
Good idea. |
comment:4
As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9). |
comment:5
As of now the method spanning_trees is using Read-Tarjan backtracking algorithm and returns list of spanning trees, why can't we simply apply weight function to these trees and sort the result based on the weight to solve this? |
comment:6
Replying to @Bhatt21:
We wish to get an iterator over the spanning trees in increasing order of weights. Also the multiple edges must be taken into account and their different weights. This can't be done just by sorting the results based on weight. |
comment:7
Thanks for the reply!but I still have doubt about this. Can u give some trivial example where sorting the total weight of a spanning tree would give wrong result? with multiple edges |
comment:8
Sorting spanning trees by weight will not give wrong results. The problem is that the number of spanning trees can be too huge to be stored. See https://en.wikipedia.org/wiki/Spanning_tree. So an iterator is much better. |
comment:9
Got the problem thanks! |
comment:10
Relevant algorithms are:
Not sure if [2] is also for weighted graphs. |
comment:11
I just finished reading paper [1]. I'll attempt to implement the relevant algorithm (provided in Section 3) |
Commit: |
comment:13
Pertaining to my last commit: I just wanted to share my progress so far. The implementation is not right yet, and doesn't produce correct results. I think I understand how the algorithm is supposed to work, but still trying to wrap my head around how to properly implement it, especially when it comes to using data structures like circular doubly linked list and indexed priority queues. New commits:
|
comment:14
A few quick remarks:
|
comment:15
Gotcha, dcoudert
If we let T be a graph, it might cause issues with the priority queue. I recall trying to do this, but with I'll try and see how it goes! |
comment:16
any progress ? |
comment:17
No significant progress yet. I intend to start afresh, so it'll take some time before I can submit new code. |
Currently we have spanning_trees function to list all the spanning trees of undirected graph. But does not take the weight of edges into account. This ticket aims at implementing such algorithms to output all spanning trees of an undirected weighted graph in increasing order of weights. This can be of potential use for applications requiring additional constraints other than least weights.
CC: @dcoudert
Component: graph theory
Keywords: enumeration, spanning trees
Author: Rajat Mittal
Branch/Commit: u/gh-enjeck/enumeration_of_spanning_trees_in_increasing_order_of_weights @
c30de1c
Issue created by migration from https://trac.sagemath.org/ticket/27532
The text was updated successfully, but these errors were encountered: