igraph

How to get maximum spanning tree

Asked by Raj Kumar Pan

Is there a way to get the maximum spanning tree(tree whose links have maximum edge weights) instead of minimum spanning tree. I guess if the weights are positive one can use 1/weights, whereas in case non-negative weights exist things are not so straight forward?

Question information

Language:
English Edit question
Status:
Solved
For:
igraph Edit question
Assignee:
Tamás Nepusz Edit question
Solved by:
Tamás Nepusz
Solved:
Last query:
Last reply:
Revision history for this message
Tamás Nepusz (ntamas) said : 		#1

If the weights are all positive, you can negate the weights and the algorithm would still work. If you are worried about the presence of negative weights, you can add a constant weight to all of them to make them all positive - it makes no difference because the number of edges in the spanning tree is fixed (|V|-c, where |V| is the number of vertices and c is the number of connected components) so any constant that you add to the weights would offset the total weight of the tree with a constant amount.

If some weights are negative and some are positive, you can first negate the weights and then offset the weights again with a constant to make all of them positive.

Revision history for this message
Raj Kumar Pan (rajkrpan) said : 		#2

Did you think that for all the cases (only positive, only negative, and positive as well as negative) one can just negate the weights?

Revision history for this message
Best Tamás Nepusz (ntamas) said : 		#3

I think yes, because the algorithm will simply order the edges in increasing order of their weights and then start adding them one by one from the beginning of the list, skipping edges that would create a cycle.

Revision history for this message
Raj Kumar Pan (rajkrpan) said : 		#4

Thanks Tamás Nepusz, that solved my question.