Message Boards Message Boards

Incorrect Spanning trees with FindSpanningTree

I apologise for my previous post on the subject. Although in the post preview window looked fine, my post did not appear with the graphics I wanted to include. I am having a lot of troubles with the function FindSpanningTree. To better illustrate the issue consider an example provided in the documentation:

g = Graph[{1 <-> 3, 1 <-> 5, 2 <-> 3, 3 <-> 2, 3 <-> 5, 4 <-> 1, 
   4 <-> 2, 4 <-> 8, 5 <-> 1, 6 <-> 3, 7 <-> 3, 7 <-> 6, 8 <-> 1}, 
  VertexLabels -> "Name"]

enter image description here

Applying FindSpanningTree does not produce a Tree

 FindSpanningTree[g, Method -> "MinimumCostAborescence"]]

enter image description here

Because of the presence uf a cycle, this is not a Tree!! Even in the documentation FindSpanningTree>Options>Method>"MinimumCostAborescence" the given example does not result in a tree.

Hopefully someone from Wolfram could help.

is this a bug?

Best regards

Jesus Rico-Melgoza

5 Replies

I wrote the discussion notebook for that meeting. That graph was made by converting to Graphics then post-processing to get the desired edge labels as you suspected.


In one of the recent Twitch videos by Stephen Wolfram, I noticed a graph that had two different labels for parallel edges. Does this mean that there's hope that this will be solved in v12.0? If yes, I am really curious about what solution was chosen while maintaining backwards compatibility.

Or was that graph created with one of the usual tricks where either the Graph is converted to Graphics and then post-processed (ugly and not GraphQ) or the EdgeShapeFunction iterates through a list of labels (also ugly and requires the label list to be kept in memory)?

enter image description here

POSTED BY: Szabolcs Horvát

Are there any plans to resolve the problem of indistinguishability of parallel edges?

This means that whenever some data needs to be associated with edges, we cannot use Mathematica to work with multigraphs.

POSTED BY: Szabolcs Horvát

Jaebum Jung



Posted 10 years ago

Indeed, FindSpanningTree returns tree:

FindSpanningTree[g, Method -> "MinimumCostAborescence", 
 VertexLabels -> "Name"]

enter image description here

The thing is HighlightGraph couldn't distinguish multi edges, i.e., when it come to 2<->3, HighlightGraph will highlight both 2<->3.

POSTED BY: Jaebum Jung
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract