Incompatibilities with the package Combinatorica 
(Mathematica Version 8)

Boros, Benedek <bboros@math.bme.hu>

Introduction

Here we show that built in functions of Mathematica 8 to treat graphs behave differently from those of the package Combinatorica, and what is more they are invompatible. Before reading in the package the built in functions create or treat objects of the type Graph, whereas after reading it in these objects become System`Graph type objects, different form the Garph type what we have upon loading in the package. When the package is in, the built in funcions are no more capable of treating Graph type objects, only the System`Graph type objects, and vice versa, functions of the package are only capable to treat Graph type objects and unable to handle System`Graph type objects. In order to (temporarily) eliminate these incompatibilities functions (ToSystemGraph and ToCombinatoricaGraph) to convert into both directions are provided.

Built in functions working without Combinatorica 
These function were previously parts of the package Combinatorica, now, in Version 8 they became built in functions.

Creating graphs (Graph needs a list of edges, AdjacencyGraph needs an adjacency matrix,  IncidenceGraph needs an incidence matrix).
The sign of undirected edges can be typed in using Esc ue Esc, whereas the sign of directed edges can be typed in using Esc de Esc.

{G=Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4},VertexLabels->"Name"],
AdjacencyGraph[{{0,1,1,0},{1,0,1,1},{1,1,0,1},{0,1,1,0}}],
IncidenceGraph[{{1,1,0,0,0},{1,0,1,1,0},{0,1,1,0,1},{0,0,0,1,1}}]}

All the three functions create an object with the head Graph.

Head /@%

System`Graph works in the same way as Graph (i.e. it creates an object of the type Graph):

System`Graph[{1\[UndirectedEdge]2,ToAdjacency1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

Head[%]

GraphPlot plots the graph.

GraphPlot[G]

EdgeCount counts its edges

EdgeCount[G]

VertexCount counts its vertices.

VertexCount[G]

EdgeList gives the list of its edges.

EdgeList[G]

VertexList gives the list of its vertices.

VertexList[G]

EdgeDelete deletes the given edge or the given list of edges – this is new in Mathematica 8.

EdgeDelete[G,3\[UndirectedEdge]4]

VertexDelete deletes the given vertex or the given list of vertices – this is new in Mathematica 8, and keeps the labeling of the vertices.

VertexDelete[G,3]

EdgeAdd adds the given edge or the given list of edges – this is new in Mathematica 8.

EdgeAdd[G,4\[UndirectedEdge]5]

A VertexAdd adds the given vertex or the given list of vertices – this is new in Mathematica 8.

VertexAdd[G,5]

ConnectedComponents provides the list of connected components of the graph – this is new in Mathematica 8.

ConnectedComponents[%]

AdjacencyMatrix creates the adjacency matrix of the matrix as a SparseArray object.

AdjacencyMatrix[G]

MatrixForm[%]

IncidenceMatrix creates the incidence matrix of the matrix as a SparseArray object.

IncidenceMatrix[G]

MatrixForm[%]

CompleteGraph creates a complete graph.

CompleteGraph[5]

Lets read in the package Combinatorica (immediately a message arrives)

<<Combinatorica`

Upon reading in the package objects of the type Graph become System`Graph type objects.

Head[G]

By scrolling back we see that another effect of loading in the package is that some of the command became red, because they are shadowed by the package, therefore their Combinatorica version becomes valid/functioning, and the will not work with System`Graph type objects.

ConnectedComponents[G]

IncidenceMatrix[G]

Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

A remedy for this is to add the prefix  System`.

System`ConnectedComponents[G]

System`IncidenceMatrix[G]

System`Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

System`Graph creates System`Graph type objects now.

Head[%]

Unshadowed commands will continue to function (i.e. also for objects of the type System`Graph).

GraphPlot[G]

EdgeList[G]

VertexList[G]

EdgeCount[G]

VertexCount[G]

EdgeDelete[G,3\[UndirectedEdge]4]

VertexDelete[G,3]

EdgeAdd[G,4\[UndirectedEdge]5]

VertexAdd[G,5]

AdjacencyMatrix[G]

Functions of Combinatorica

Creating a graph using FromAdjacencyMatrix (the argument of which is an adjacency matrix, similarly to AdjacencyGraph).

H=FromAdjacencyMatrix[{{0,1,1,0},{1,0,1,1},{1,1,0,1},{0,1,1,0}}]

The result is an object of the type Graph.

Head[%]

After loading in the package graphs of the Graph type will no more plotted automatically, one has to use either GraphPlot or ShowGraph.

GraphPlot[H]

ShowGraph[H]

Shadowed commands work well for Graph type objects.

ConnectedComponents[H]

The result of IncidenceMatrix is now a matrix and not a SparseArray.

IncidenceMatrix[H]

The type of CompleteGraph is Graph.

CompleteGraph[5]

ShowGraph[%]

ToAdjacencyMatrix gives the adjacency matrix.

ToAdjacencyMatrix[H]

M counts the edges.

M[H]

V counts the vertices.

V[H]

Edges gives the list of edges (all the edges are rpresented as two element lists).

Edges[H]

Vertices gives the coordinates of vertices embedded in a plane as shown by ShowGraph.

Vertices[H]

DeleteEdge deletes the given edge (a single one given in the form of a list).

DeleteEdge[H,{3,4}]

ShowGraph[%]

DeleteEdges deletes the given edge or edges (given in the form of a list or of a list of lists).

DeleteEdges[H,{{1,3},{3,4}}]

ShowGraph[%]

DeleteVertex deletes the given vertex (a single one given in the form of a number), and as opposed to VertexDelete, it renumbers the labels of the verticces (more precisely the Graph type graphs after loading in the package will always be labeled with Range[n] differently from System`Graph type ones).

DeleteVertex[H,3]

ShowGraph[%]

GraphPlot[DeleteVertex[H,3],VertexLabeling->True]

DeleteVertices deletes the given vertex or vertices (given in the form of a number(s)).

DeleteVertices[H,{1,3}]

ShowGraph[%]

AddEdge adds the given edge (a single one given in the form of a list, and only edges between two existing points are accepted, differetnly from EdgeAdd).

AddEdge[H,{1,4}]

ShowGraph[%]

AddEdges adds the given edges (given in the form of a list, and only edges between two existing points are accepted).

AddEdges[H,{{1,3},{1,4}}]

ShowGraph[%]

AddVertex adds the given vertex (a single one given with its coordinates).

AddVertex[H,{1,1}]

ShowGraph[%]

AddVertices adds the given vertex or vertices (given with their coordinates).

AddVertices[H,{{1,1},{-1,1}}]

ShowGraph[%]

Cycle creates a cycle.

Cycle[5]

ShowGraph[%]

GraphJoin joins all the vertices of a graph with all the vertivces of another one.

GraphJoin[H,CompleteGraph[1]]

ShowGraph[%]

HamiltonianQ tests if it does contain a Hamiltonian cycle or not.

HamiltonianQ[H]

HamiltonianCycle provides one Hamiltonian cycle if there is any, and an empty list if there is none.

HamiltonianCycle[H]

HamiltonianPath provides one Hamiltonian path if there is any, and an empty list if there is none.

HamiltonianPath[H]

Adding and deleting edges and vertices

({{Function, Function of Combinatorica, Arguments, Built in function, Arguments}, {Deleting an edge, DeleteEdge, a graph,an edge(a list of length two), EdgeDelete, a graph,and edge or a list of edges(x<->y)}, {Deleting edges, DeleteEdges, a graph, a list of edges, , }, {Deleting a vertex, DeleteVertex, a graph, a vertex(a number as a label), VertexDelete, a graph,a vertex or a list of vertices(number(s))}, {Deleting vertices, DeleteVertices, a graph, a list of points, , }, {Adding an edge, AddEdge, a grap, an edge(a list of length two), EdgeAdd, a graph,and edge or a list of edges(x<->y)}, {Adding edges, AddEdges, a graph, list of edges, , }, {Adding a vertex, AddVertex, a graph, a vertex(its coordinates), VertexDelete, a graph,a vertex or a list of vertices(number(s))}, {Adding vertices, AddVertices, a graph, a list of vertices, , }})

Incompatibilities

Let us try to use built in functions (i.e. are not part of Combinatorica) on a graph of type Graph.
They are not capable handling graphs of the type Graph created after reading in Combinatorica.

EdgeCount[H]

VertexCount[H]

EdgeList[H]

VertexList[H]

EdgeDelete[H,3\[UndirectedEdge]4]

VertexDelete[H,3]

EdgeAdd[H,4\[UndirectedEdge]5]

VertexAdd[H,5]

AdjacencyMatrix[H]

Solution: The command AdjacencyGraph [ ToAdjacencyMatrix [ G ]] reforms the object of the type Graphs as an object of the type System`Graph.

ToSystemGraph[G_]:=AdjacencyGraph[ToAdjacencyMatrix[G]]

H2=ToSystemGraph[H]

Head[%]

This graph can be handled by built in functions (outside Combinatorica).

VertexCount[H2]

Upon trying the functions of the package Combinatorica it turns out that they are unable to handle graphs of the type System`Graph.

G=System`Graph[{1\[UndirectedEdge]2,1\[UndirectedEdge]3,2\[UndirectedEdge]3,2\[UndirectedEdge]4,3\[UndirectedEdge]4}]

ShowGraph[G]

ToAdjacencyMatrix[G]

M[G]

V[G]

Edges[G]

Vertices[G]

DeleteEdge[G,{3,4}]

DeleteVertex[G,3]

AddEdge[G,{1,4}]

AddVertex[G,{1,1}]

GraphJoin[G,System`CompleteGraph[1]]

HamiltonianQ[G]

HamiltonianCycle[G]

HamiltonianPath[G]

The simple solution FromAdjacencyMatrix[AdjacencyMatrix[G]] does not work, because FromAdjacencyMatrix cannot handle matrices in SparseArray form.

FromAdjacencyMatrix[AdjacencyMatrix[G]]

Solution: Insert Normal.

Normal[AdjacencyMatrix[G]]

Therefore FromAdjacencyMatrix[Normal[AdjacencyMatrix[G]]] converts an object of the type System`Graph into an object of the type Graph.

ToCombinatoricaGraph[G_]:=FromAdjacencyMatrix[Normal[AdjacencyMatrix[G]]]

G2=ToCombinatoricaGraph[G]

Head[%]

Now one can use the functions of Combinatorica.

V[G2]

Importing graphs from files

Suppose tha graphs are cotained in a file of the format graph6 and read them in using Import.

SetDirectory[NotebookDirectory[]];
graphs=Import["graph4c.g6"]

F=graphs[[5]]

These graphs are of the type System`Graph.

Head[%]

Thus, the functions of Combinatorica are useless.

V[F]

ToAdjacencyMatrix[F]

HamiltonianQ[F]

Solution: Use the appropriate option of Import to get adjacency matrix which can be trasformed into both types of graphs.

am=Import["graph4c.g6",{"AdjacencyMatrix",5}]

F1=AdjacencyGraph[am]

F2=FromAdjacencyMatrix[am]

GraphPlot[%]

This form is appropriate also for the functions of Combinatorica.

V[F2]

ToAdjacencyMatrix[F2]

HamiltonianQ[F2]

Remark: The list of functions abiove is by no means exhaustive, our only aim was to highlight incompatibilites hoping that they will be eliminated by the developers soon.