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:

Status badges

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 gh-rajat1433

  • Keywords enumeration spanning trees added
  • Owner changed from (none) to gh-rajat1433

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

Last edited 3 years ago by gh-rajat1433 (previous) (diff)

comment:2 Changed 3 years ago by dcoudert

Good idea.

comment:3 Changed 2 years ago by gh-rajat1433

  • Owner changed from gh-rajat1433 to (none)

comment:4 Changed 2 years ago by embray

  • 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: Changed 19 months ago by 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?

comment:6 in reply to: ↑ 5 Changed 19 months ago by gh-rajat1433

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 gh-Bhatt21

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 dcoudert

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 gh-Bhatt21

Got the problem thanks!

Note: See TracTickets for help on using tickets.