12
$\begingroup$

Since version 10, much of the original functionality in the Combinatorica package has been subsumed (consumed?) by new graph primitive functions. However, as per similar posts, at times there are conflicts.

As I am interested in better understanding graph encoding, I wish to investigate properties of different potential encodings. One simple/direct encoding is via Prüfer sequences. The Combinatorica package had two functions (one the inverse of the other) LabeledTreeToCode[] and CodeToLabeledTree[] to encode/decode the bijection between Prüfer codes and their graphs. However, simply using the following for a simple graph fail to instantiate, generating a general error that Combinatorica and permutation functions may be conflicting (which presumably they are).

 totalOrder = Graph[{1 <-> 2, 2 <-> 3}]

 Needs[Combinatorica`]  

 LabeledTreeToCode[totalOrder]

 CodeToLabeledTree[totalOrder]

If I create the graph after calling Combinatorica` I get a series of errors (Table, Join, General) finally suppressing output.

How can I obtain the original functionality of these two functions from within Vers. 11.1.1? Or, is there a way within Vers. 11.1.1 to obtain this functionality without calling the old Combinatorica code?

$\endgroup$
  • 6
    $\begingroup$ Use Block[{$ContextPath}, Needs["Combinatorica`"]] to load, then when you want a conbinatorica function, preface function name with Combinatorica'. In general, internal representations are not interchangeable, that is, a MMA graph object won't work with Combinatorica and vice-versa. $\endgroup$ – ciao Apr 29 '17 at 23:58
12
$\begingroup$

The problem is that you defined the Graph using M syntax and not Combinatorica syntax. For your example you should do:

g = Combinatorica`Graph[{{{1,2}},{{2,3}}}, {1,2,3}]

Combinatorica`Graph[{{{1, 2}}, {{2, 3}}}, {1, 2, 3}]

Then, you can use the Combinatorica functions:

code = Combinatorica`LabeledTreeToCode[g]
Combinatorica`CodeToLabeledTree[code]

{2}

Combinatorica`Graph[{{{1, 2}}, {{2, 3}}}, {{{-0.4999999999999998, 0.8660254037844387}}, {{-0.5000000000000004, -0.8660254037844384}}, {{ 1., 0}}}]

$\endgroup$
  • $\begingroup$ I think that should be FromUnorderedPairs[{{1,2}, {2,3}}]. Graph[{{{1,2}},{{2,3}}}, {1,2,3}] creates an invalid graph in Combinatorica. The second argument should be a list of vertex coordinates associated with options, e.g. {{{0,0}}, {{1,0}}, {{2,0}}}. I think Graph is not meant to be used as a constructor in Combinatorica. $\endgroup$ – Szabolcs Feb 11 '18 at 8:06
7
$\begingroup$

Apparently, they killed it off without making an equivalent, so you'd have to re-implement an algorithm.

documentation link is here: Upgrading from: Combinatorica

In some cases, parameterized variants have not yet been implemented in the Wolfram System, but a subset can be found in GraphData.

...

So you'll have to make your own.

This should work as the tree-to-code to produce a Prüfer sequence:

TreeToCode[g_Graph?(TreeGraphQ@# &)] := Block[{tempTree = g, res = {}},
  While[VertexCount@tempTree > 2,
    With[
      {leastLeaf = Sort[{VertexDegree[tempTree,#],#}&/@VertexList@tempTree][[1,2]]},
      AppendTo[res, AdjacencyList[tempTree,leastLeaf][[1]]];
      tempTree = VertexDelete[tempTree,leastLeaf];
  ]];
  Return[res]];

totalOrder = Graph[{4<->1, 4<->2, 4<->3, 4<->5, 5<->6}];
sample = Graph[{1<->2, 1<->3, 4<->1, 2<->6, 3<->5, 3<->7, 5<->8}];
TreeToCode[totalOrder]
TreeToCode[sample]
TreeToCode[Graph[{1<->2, 2<->3}]]

Out:

{4, 4, 4, 5}
{1, 2, 1, 3, 3, 5}
{2}

Code-to-Tree shouldn't be too difficult to recreate as well. This Wikipedia article has a procedural implementation, but there's a functional way to get it done in MMA.

Sorry that I don't have better news for you.

$\endgroup$
2
$\begingroup$

IGraph/M already has replacements for most graph-related Combinatorica functions that are not yet covered by built-in functionality.

Since IGraph/M 0.3.98, you can use IGFromPrufer to convert a Prüfer sequence to a tree. The reverse operation is planned for a future version. Until it is added, you can use Gregory Klopper's implementation.

IGFromPrufer[{4, 4, 4, 5}, VertexLabels -> Automatic]

enter image description here

To convert it back, use

IGToPrufer[%]
(* {4, 4, 4, 5} *)

IGToPrufer is available since v0.3.109.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.