Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Prufer Code/ LabeledTreeToCode Bug?

• To: mathgroup at smc.vnet.net
• Subject: [mg104623] Re: [mg104530] Prufer Code/ LabeledTreeToCode Bug?
• From: Thomas Dowling <thomasgdowling at gmail.com>
• Date: Thu, 5 Nov 2009 03:49:24 -0500 (EST)
• References: <200911030754.CAA01430@smc.vnet.net>

Hello,

To update my own question,

the correct Prufer code may be obtained using a combination of EdgeList,
FromUnorderedPairs (to convert to a Combinatorica graph) and
LabeledTreeToCode,
as follows;

Needs["GraphUtilities`"]
Needs["Combinatorica`"]

grnew={2->4,4->3,3->1};

In[122]= LabeledTreeToCode@FromUnorderedPairs@EdgeList[grnew]
Out[122]= {3,4}

This gives a plot of the graph

GraphPlot[grnew, VertexLabeling-> True, Method-> "CircularEmbedding"]

I have no idea why the previous approach did not work (or should not work),
but it seems to me that something strange is going on.

Tom Dowling


On Tue, Nov 3, 2009 at 7:54 AM, Thomas Dowling <thomasgdowling at gmail.com>wrote:

> Hello,
>
> 1.   I am interested in generating the Prufer code for the following simple
> graph which I generate as follows:
>
> Needs["Combinatorica`"]
> Needs["GraphUtilities`"]
>
>
> In[137]= gr1 = MakeSimple[
>   ToCombinatoricaGraph[{2 -> 4, 4 -> 3, 3 -> 1},
>    Method -> "CircularEmbedding"]];
>
> 2.  I can visualize the graph as follows, and all is well (it is as I
> expect, with no edge between vertices 1 and 2):
>
>
> In[140]= ShowGraph[gr1, EdgeColor -> Orange, VertexColor -> LightYellow,
>  VertexLabelPosition -> Center, VertexStyle -> Disk[Large]]
>
> 3.  However, if I now generate the Prufer code for gr1,  I get a strange
> result.
>
> In[141]= LabeledTreeToCode@gr1
>
> Out[141]= {2, 3}
>
> 4. Firstly, the above Prufer code is clearly wrong:  it surely should be
> {3,4}?
>
> Secondly, if I use EdgeList, I also get an apparently wrong answer:
>
> In[143]= EdgeList[gr1]
>
> {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}}
>
> Why the edge between vertices 1 and 2?
>
> 5.  If I 'work backwards' I do not get back the original graph:
>
> In[144]= pcgr1 = CodeToLabeledTree[{2, 3}];
>
> ShowGraph[pcgr1, VertexLabel -> True, EdgeColor -> Orange,
>  VertexColor -> LightYellow, VertexLabelPosition -> Center,
>  VertexStyle -> Disk[Large]]
>
>
> In[145]= EdgeList[pcgr1]
>
> Out[145]= {{1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}}
>
>
> The  EdgeList is correct for pcgr1, but pcgr1 is not identical with gr1!
>
>
> 6.  Finally, if I work with the expected Prufer code, I get a graph and
> EdgeList consistent
> with what I expected for gr1 but did not get:
>
>
> In[148]= gr3 = CodeToLabeledTree[{3, 4}];
>
> In[149]= ShowGraph[gr3, EdgeColor -> Orange, VertexLabel -> True,
>  VertexColor -> LightYellow, VertexLabelPosition -> Center,
>  VertexStyle -> Disk[Large]]
>
> In[150]= EdgeList[gr3]
>
> Out[150]=  {{1, 3}, {2, 4}, {3, 1}, {3, 4}, {4, 2}, {4, 3}}
>
>
> 7.  I am working with Mathematica 7.0.0 on a Mac Powerbook G4 (non-Intel)
> with OS X  v 10.5.8.
>
> Have I missed something or is this a bug?
>
> I am also wondering if others can reproduce
> this behaviour on other systems, in particular with Mathematica 7.0.1.
>
> Any help / workaround will be greatly appreciated.
>
> Thanks,
>
>
> Tom Dowling
>
>
>

• References:
  • Prufer Code/ LabeledTreeToCode Bug?
    • From: Thomas Dowling <thomasgdowling@gmail.com>