Prev: DateListBarChart / Ticks in BarChart
Next: SelectionMove[] busted with InputField and DockedCells?
From: Thomas Dowling on 3 Nov 2009 02:55
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(a)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


From: Thomas Dowling on 5 Nov 2009 04:25
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(a)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(a)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(a)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
>
>
>

 | 
Pages: 1
Prev: DateListBarChart / Ticks in BarChart
Next: SelectionMove[] busted with InputField and DockedCells?