Services & ResourcesWolfram ForumsMathGroup Archive

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

Prufer Code/ LabeledTreeToCode Bug?

• To: mathgroup at smc.vnet.net
• Subject: [mg104530] Prufer Code/ LabeledTreeToCode Bug?
• From: Thomas Dowling <thomasgdowling at gmail.com>
• Date: Tue, 3 Nov 2009 02:54:22 -0500 (EST)

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

• Follow-Ups:
  • Re: Prufer Code/ LabeledTreeToCode Bug?
    • From: Thomas Dowling <thomasgdowling@gmail.com>