Enumeration of Spanning trees in increasing order of weights

[2460b664-5ecd-43fc-9bbe-d0f333762988]

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

[2460b664-5ecd-43fc-9bbe-d0f333762988]

Changed keywords from none to enumeration, spanning trees

[2460b664-5ecd-43fc-9bbe-d0f333762988]

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

http://www.hariharan-ramesh.com/papers/spantree1.pdf

[dcoudert]

comment:2

Good idea.

[embray]

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).

[14c9a0b4-ba9d-4cea-af48-bc083383d474]

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?

[2460b664-5ecd-43fc-9bbe-d0f333762988]

comment:6

Replying to @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.

[14c9a0b4-ba9d-4cea-af48-bc083383d474]

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

[dcoudert]

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.

[14c9a0b4-ba9d-4cea-af48-bc083383d474]

comment:9

Got the problem thanks!

[dcoudert]

comment:10

Relevant algorithms are:

1. Sanjiv Kapoor, H. Ramesh: Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs. SIAM J. Comput. 24(2): 247-265 (1995) https://epubs.siam.org/doi/10.1137/S009753979225030X
2. Sanjiv Kapoor, H. Ramesh: An Algorithm for Enumerating All Spanning Trees of a Directed Graph. Algorithmica volume 27, pages 120–130 (2000) https://doi.org/10.1007/s004530010008

Not sure if [2] is also for weighted graphs.

[enjeck]

comment:11

1. Sanjiv Kapoor, H. Ramesh: Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs. SIAM J. Comput. 24(2): 247-265 (1995) ​https://epubs.siam.org/doi/10.1137/S009753979225030X

I just finished reading paper [1]. I'll attempt to implement the relevant algorithm (provided in Section 3)

[enjeck]

Branch: u/gh-enjeck/enumeration_of_spanning_trees_in_increasing_order_of_weights

[enjeck]

Commit: c30de1c

[enjeck]

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:

c30de1c

Initial naive implementation

[dcoudert]

comment:14

A few quick remarks:

• The cycle basis should be computed outside the while loop, so only once
• To simplify your tests, it might be interesting to create the graph of each cycle of the basis. Then you can search for the graph containing a given edge f
• Similarly, it might be easier to let T be a graph instead of a list of edges. The goal is first to get a valid implementation. Then you can search for a faster method

[enjeck]

comment:15

Gotcha, dcoudert

Similarly, it might be easier to let T be a graph instead of a list of edges. The goal is first to get a valid implementation. Then you can search for a faster method

If we let T be a graph, it might cause issues with the priority queue. I recall trying to do this, but with new_graph, and there was a comparison-related error. I guess that the current heap implementation can't compare graphs to see which is "less than" or "greater than" so as to push or pop from the heap.

I'll try and see how it goes!

[dcoudert]

comment:16

any progress ?

[enjeck]

comment:17

No significant progress yet. I intend to start afresh, so it'll take some time before I can submit new code.