Message Boards Message Boards

Work with Graph object of Combinatorica package?

GROUPS:

I am completely new to Mathematica and I am completely stuck on a seemingly simple problem. I have spent over an hour to try to calculate the chromatic number of a simple (two vertex) graph to no avail, and the Wolfram reference site for graphs did not help me much either. The following screenshot illustrates my problem - essentially the output is either a strange error message or the same as the input, whereas I expect a simple '2' as an answer. Thank you very much for your help!

Cannot get ChromaticNumber function to run, and strange error messages

POSTED BY: Adam Zsolt Wagner
Answer
2 years ago

I believe the Combinatorica package was originally written by Pemmaraju and Skiena outside of Wolfram Inc. They wrote "Computational Discrete Mathematics Combinatorics and Graph Theory with Mathematica(r)" and there are used copies of that available at bargain prices. I urge anyone thinking of using Combinatorica to buy a copy of that.

Later Wolfram Inc. incorporated the Combinatorica package into the Mathematica kernel. This has caused some confusion. The original package is still available if you pull that in.

In[1]:= Needs["Combinatorica`"];
g = CompleteGraph[2];
MinimumVertexColoring[g]

During evaluation of In[1]:= General::compat: Combinatorica Graph and Permutations functionality has been
superseded by preloaded functionality. The package now being loaded may conflict with this. Please see the
Compatibility Guide for details.

Out[3]= {1, 2}

In[4]:= ChromaticNumber[g]

Out[4]= 2
POSTED BY: Bill Simpson
Answer
2 years ago

Thank you for your thorough answer Bill - unfortunately this does not quite solve my issue. When I run your code I get the same output as you did. However when I try to define the graph g as Graph[{1<->2}] then the ChromaticNumber function does not work again. So everything works well for inbuilt graphs, but clearly I am doing something wrong when defining the graphs 'by hand'. This is a big issue for me, as in my research project I want to calculate the chromatic number of graphs that are certainly not built into Mathematica. (And if I am not mistaken the Combinatorica package is built into the Wolfram system as of version 10, hence there is no need to include them with the Needs[-] command.) -

Edit: I entered "Needs["Combinatorica`"]" and ran the same inputs as in the screenshot just to be safe, and got the exact same results.

POSTED BY: Adam Zsolt Wagner
Answer
2 years ago

When CompleteGraph[2] appears to work for you and Graph[{1<->2}] doesn't my first thought is to use FullForm on each of those and see how they differ. Perhaps that can provide you with the needed information to be able to construct your own graphs manually and see if they will work.

There seems to be some inconsistencies between the kernel and the package versions of the combinatorica functions. I suspect that is why both versions are supplied. I have not spent the time to see if there is documentation available explaining the fine details of the changes in combinatorica. Having that information would be very helpful.

I remember finding a perplexing problem in the past when I manually fabricated a graph instead of using the graph construction primitives to build it.

POSTED BY: Bill Simpson
Answer
2 years ago

Thank you for your answer Bill, this FullForm is truly a wonderful function! Turns out Graph[{1<->2}] and CompleteGraph[2] are two different animals. By imitating the syntax of the CompleteGraph function given to me by FullForm I managed to find a workaround that lets me define arbitrary graphs and calculate their chromatic number. I still have no clue why my initial approach using simply Graph[{1<->2}] did not work, and I am confident that there exists an easier solution than mine (but who cares, this works!). See the last input on the screenshot below for my solution (the number 5 at the very end is the number of vertices in the graph).

workaround for using Graph[] to define arbitrary graphs

POSTED BY: Adam Zsolt Wagner
Answer
2 years ago

Avoid using Combinatorica if you can. It is not supported any more and therefore not easy to use. It also shadows (= "conflicts with") several builtin functions.

There is indeed some functionality which is only available in Combinatorica. If you do need to use it, prefix your function/symbol names with the appropriate context to disambiguate whether you want the builtin one or the Combinatorica one. It's best if you always do this with symbol names that are coloured red.

It is also a good idea to get the Pemmaraju & Skiena book as there is no other documentation for Combinatorica.

The most important thing to keep in mind: System`Graph and CombinatoricaGraph`` are two distinct, unrelated and incompatible things. They cannot be mixed. Builtin functions work on builtin graphs only. Combinatorica functions work on Combinatorica graphs only.

You can convert between them using the GraphUtilities package.

Example:

<< Combinatorica`

<< GraphUtilities`

At this point, do not refer to Graph anymore without explicitly specifying which one you mean.

Writing Graph[{1<->2}] is no longer valid because Graph now refers to Combinatorica`Graph. So let's be explicit from now on.

g = System`Graph[{1 <-> 2}]

Combinatorica`MinimumVertexColoring[
 ToCombinatoricaGraph[g]
 ]

(* {1, 2} *)

If you work with graph, also take a look at my IGraph/M package which provides graph-related functionality not available with builtins. It is an interface to igraph.

POSTED BY: Szabolcs Horvát
Answer
2 years ago

Perfect answer, this explains everything very clearly. Thank you Szabolcs!

POSTED BY: Adam Zsolt Wagner
Answer
2 years ago

Maybe it's easier to work with Combinatorica this way:

First we load these package without adding them to the context path.

Block[{$ContextPath}, Needs["Combinatorica`"]; Needs["GraphUtilities`"]]

Now System` context symbols are not shadowed. But we must explicitly write the context to call any function from these packages.

I prefer this because it enforces a clear rule and it avoids shadowing altogether.

The function GraphUtilities`ToCombinatoricaGraph has a quirk: it evaluates Needs["Combinatorica"]` every time it's called, and this re-adds this package to the context path. To prevent this, we define our own special version:

toCombinatoricaGraph[g_?GraphQ] := 
 Block[{$ContextPath}, GraphUtilities`ToCombinatoricaGraph[g]]

We can now do this:

g = Graph[{1 <-> 2}];

Combinatorica`MinimumVertexColoring[toCombinatoricaGraph[g]]

We don't need to type System`Graph any more.


I suggested a few times to Wolfram Support to change ToCombinatoricaGraph so that it wouldn't add Combinatorica to the context path and make all this easier on users. But I guess no more changes will be done to unsupported packages.

POSTED BY: Szabolcs Horvát
Answer
2 years ago

IGraph/M now provides graph colouring functionality that is well integrated with the rest of Mathematica. You no longer need Combinatorica for this.

Demo:

Let's make a graph:

g = StarGraph[5, VertexSize -> Large];

Compute a minimum colouring and visualize it:

g // IGVertexMap[ColorData[112], VertexStyle -> IGMinimumVertexColoring]

Mathematica graphics

Transform it into a larger graph that needs one more colour:

g2 = IGMycielskian[g, VertexSize -> Large]

Mathematica graphics

Colour it:

g2 // IGVertexMap[ColorData[112], VertexStyle -> IGMinimumVertexColoring]

Mathematica graphics

Obtain the colouring as a list:

IGMinimumVertexColoring[g2]
(* {1, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1} *)

Direct and explicit verification that the same graph is not 2-colourable:

IGKVertexColoring[g2, 2]
(* {} *)

Run a fast colouring algorithm that does not guarantee minimum colouring.

IGVertexColoring[g2]
(* {1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1} *)

It gave us a different result, also with 3 colours.

Directly compute the chromatic number:

IGChromaticNumber[g2]
(* 3 *)
POSTED BY: Szabolcs Horvát
Answer
24 days ago

Group Abstract Group Abstract