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:
Jaebum Jung
Jaebum Jung, Wolfram
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

Jaebum Jung

Thanks!

Jesús
POSTED BY: J Jesus Rico-Melgoza

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

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

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