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

HighlightGraph[g, 
 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
POSTED BY: J Jesus Rico-Melgoza
5 Replies
Sort By:

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.
POSTED BY: Ian Ford

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
POSTED BY: Szabolcs Horvát

Jaebum Jung

Thanks!

Jesús
POSTED BY: J Jesus Rico-Melgoza
Jaebum Jung
Jaebum Jung, Wolfram
Posted 11 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.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract