Combinatorica Functionality in Vers. 11.1.1

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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]

To convert it back, use

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

IGToPrufer is available since v0.3.109.