Incorrect Spanning trees with FindSpanningTree

Questions
, ,
1

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

test1.gif
test1.gif360Ă—203 5.21 KB

Applying FindSpanningTree does not produce a Tree

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

test2.gif
test2.gif360Ă—203 5.25 KB

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

2

Indeed, FindSpanningTree returns tree:

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

ScreenShot2014-08-28at9.24.46PM.png
ScreenShot2014-08-28at9.24.46PM.png265Ă—368 3.88 KB

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

3

Jaebum Jung

Thanks!

JesĂşs

4

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.

5

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


Screenshot2018-05-0714.43.54.jpg

6

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.