Opened 3 years ago
Last modified 19 months ago
#27532 new enhancement
Enumeration of Spanning trees in increasing order of weights
Reported by: | gh-rajat1433 | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | graph theory | Keywords: | enumeration, spanning trees |
Cc: | dcoudert | Merged in: | |
Authors: | Rajat Mittal | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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.
Change History (9)
comment:1 Changed 3 years ago by
- Keywords enumeration spanning trees added
- Owner changed from (none) to gh-rajat1433
comment:2 Changed 3 years ago by
Good idea.
comment:3 Changed 2 years ago by
- Owner changed from gh-rajat1433 to (none)
comment:4 Changed 2 years ago by
- Milestone sage-8.8 deleted
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 follow-up: ↓ 6 Changed 19 months ago by
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 in reply to: ↑ 5 Changed 19 months ago by
Replying to gh-Bhatt21:
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?
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. I have linked some papers citing optimized algorithms to achieve the same at the beginning comment of this tkt.
comment:7 Changed 19 months ago by
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 Changed 19 months ago by
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 Changed 19 months ago by
Got the problem thanks!
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
http://www.hariharan-ramesh.com/papers/spantree1.pdf