WOLFRAM LANGUAGE COMPATIBILITY INFORMATION

Upgrading from:

Combinatorica`

As of Version 8, much of the functionality covered by Combinatorica has been implemented in the Wolfram System.

Combinatorica provided a large amount of functionality in fields such as graph theory and permutations. In Version 8, a native Wolfram System implementation of much of this functionality has been created. While there is some overlap in naming, the native implementation is fundamentally different in many ways.

For example, the Graph object in Combinatorica was a regular Mathematica expression that could be directly pulled apart via expression manipulation functions such as Part. The Wolfram System implementation is instead an atomic object, which is modified only via accessor functions. This allows the Wolfram System to transparently attach rendering hints and other information supporting interactive graph manipulation.

Because of these basic differences, loading Combinatorica overrides the new functionality and provides compatibility with the old Graph expressions. It silently shadows the new functions, so that old code may be run. In most cases, the new implementation should not be mixed with use of Combinatorica. If necessary, the two versions can be used simultaneously by the use of full context names, as in or .

See the Graphs & Networks guide for an overview of the Wolfram System functionality.

Graph Representation and Manipulation

Graphs are now input by a list of directed or undirected edges. A display function is not required; like Graphics objects, they render directly in the front end.

Version 7.0 << Combinatorica`
ShowGraph[Graph[{{{1, 2}}, {{2, 3}}}, {{{0, 0}}, {{1, 1}}, {{2, 0}}}]]
In[7]:=
Click for copyable input
Out[7]=

Vertex locations are optional.

In[2]:=
Click for copyable input
Out[2]=

Directed edges are specified in the edge list.

Version 7.0 << Combinatorica`
ShowGraph[
 Graph[{{{1, 2}}, {{2, 3}}}, {{{0, 0}}, {{1, 1}}, {{2, 0}}}, 
  Directed -> True]]
In[3]:=
Click for copyable input
Out[3]=

A graph can be rendered with modified styles to highlight parts. The syntax is not identical, but can be adapted in a straightforward fashion.

Version 7.0 << Combinatorica`
ShowGraph[
 Highlight[CompleteGraph[5], {{1, 2, 3, {1, 2}, {2, 3}}, {{1, 3}}},
  HighlightedEdgeColors -> {Red, Orange}]]
In[15]:=
Click for copyable input
Out[15]=

Graphs can be input as adjacency matrices.

Version 7.0 << Combinatorica`
ShowGraph[
 FromAdjacencyMatrix[{{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1,
     0, 0}}]]
In[8]:=
Click for copyable input
Out[8]=

The adjacency matrix is a sparse array.

Version 7.0 << Combinatorica`
ToAdjacencyMatrix[Wheel[5]]
In[5]:=
Click for copyable input
Out[5]=
In[6]:=
Click for copyable input
Out[6]//MatrixForm=

At the current time, multigraphs (more than one edge between vertices) are not supported except for the special case of directed graphs, where a single edge in each direction can be specified. A non-symmetric matrix will automatically be understood to be directed; otherwise, use the option DirectedEdges.

Version 7.0 << Combinatorica`
ShowGraph[
 FromAdjacencyMatrix[{{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0,
     1, 0}}, Type -> Directed]]
In[7]:=
Click for copyable input
Out[7]=

For a weighted adjacency matrix, use WeightedAdjacencyGraph. An absent edge is specified by a weight of infinity, not zero.

Version 7.0 << Combinatorica`
GetEdgeWeights[
 SetEdgeWeights[
  FromAdjacencyMatrix[{{0, 1, 1}, {1, 0, 1}, {1, 1, 0}}], {2, 1, 2}]]
In[8]:=
Click for copyable input
Out[8]=

CombinatoricaVersion 8
AddEdge[g, e]EdgeAdd[g,e]
AddEdges[g,{e1,e2,}]EdgeAdd[g, {e1,e2,}]
AddVertex[g,v]VertexAdd[g,v]
AddVertices[g, {v1,v2,}]VertexAdd[g,{v1,v2,}]
DeleteEdge[g,e]EdgeDelete[g,e]
DeleteEdges[g,{e1,e2,}]EdgeDelete[g,{e1,e2,}]
DeleteVertex[g,v]VertexDelete[g,v]
DeleteVertices[g,{v1,v2,}]VertexDelete[g,{v1,v2,}]
InduceSubgraph[g,{v1,v2,}]Subgraph[g,{v1,v2,}]
MakeDirected[g]DirectedGraph[g]
MakeSimple[g]UndirectedGraph[SimpleGraph[g]]
MakeUndirected[g]UndirectedGraph[g]
ReverseEdges[g]ReverseGraph[g]

Note that in the Wolfram System, graph functionality generally refers to the names of vertices, while in Combinatorica, it is the indices or coordinates of the vertices that are used.

Version 7.0 << Combinatorica`
ShowGraph[AddEdges[AddVertex[Wheel[5]], {{2, 6}, {3, 6}}]]
In[9]:=
Click for copyable input
Out[9]=

Combinatorica's MakeSimple makes the graph undirected; this is a separate operation in the Wolfram System.

CombinatoricaVersion 8
GraphComplement[g]GraphComplement[g]
GraphDifference[g1,g2]GraphDifference[g1,g2]
GraphIntersection[g1,g2,]GraphIntersection[g1,g2,]
MakeSimple[GraphPower[g,n]]GraphPower[g,n]
MakeSimple[GraphSum[g1,g2,]]GraphUnion[g1,g2,]
GraphUnion[g1,g2,]GraphDisjointUnion[g1,g2,]
LineGraph[g]LineGraph[g]

Most of the operations to combine graphs are implemented. For some of these, the Wolfram System produces the equivalent simple graph of the corresponding Combinatorica operation. Note particularly that union and sum are defined differently in the Wolfram System. The requirement that the graphs start with the same number of vertices has been removed.

Version 7.0 << Combinatorica`
ShowGraph[MakeSimple[GraphSum[Cycle[6], AddVertex[Cycle[5]]]]]
In[10]:=
Click for copyable input
Out[10]=

Graph Properties

CombinatoricaVersion 8
AcyclicQ[g]AcyclicGraphQ[g]
BipartiteQ[g]BipartiteGraphQ[g]
CompleteQ[g]CompleteGraphQ[g]
ConnectedQ[g]ConnectedGraphQ[g]
EmptyQ[g]EmptyGraphQ[g]
EulerianQ[g]EulerianGraphQ[g]
HamiltonianQ[g]HamiltonianGraphQ[g]
IndependentSetQ[g,{v1,v2,}]IndependentVertexSetQ[g,{v1,v2,}]
IsomorphicQ[g]IsomorphicGraphQ[g]
SelfLoopsQ[g]!LoopFreeGraphQ[g]
SimpleQ[g]SimpleGraphQ[g]
TreeQ[g]TreeGraphQ[g]
UndirectedQ[g]UndirectedGraphQ[g]
UnweightedQ[g]!WeightedGraphQ[g]
VertexCoverQ[g,{v1,v2,}]VertexCoverQ[g,{v1,v2,}]

Many of the graph predicates are currently supported via different names, though some use the opposite sense of the predicate, such as WeightedGraphQ.

Version 7.0 << Combinatorica`
EulerianQ[CompleteGraph[5]]
In[11]:=
Click for copyable input
Out[11]=

CombinatoricaVersion 8
ConnectedComponents[g]ConnectedComponents[g]
Degrees[g]VertexDegree[g]
DegreeSequence[g]Reverse[Sort[VertexDegree[g]]]
Diameter[g]GraphDiameter[g]
Eccentricity[g]VertexEccentricity[g]
GraphCenter[g]GraphCenter[g]
InDegree[g,v]InDegree[g,v]
M[g]EdgeCount[g]
OutDegree[g,v]OutDegree[g,v]
Radius[g]GraphRadius[g]
V[g]VertexCount[g]

Version 7.0 << Combinatorica`
Diameter[ButterflyGraph[5]]
In[12]:=
Click for copyable input
Out[12]=

Graph Algorithms

CombinatoricaVersion 8
EulerianCycle[g]FindEulerianCycle[g]
HamiltonianCycle[g]FindHamiltonianCycle[g]
MaximumClique[g]FindClique[g]
MaximumIndependentSet[g]FindIndependentVertexSet[g]
ShortestPath[g,s,e]FindShortestPath[g,s,e]
MinimumVertexCover[g]FindVertexCover[g]

The Wolfram System also implements functionality for traveling salesman problems, but the syntax is not oriented towards the graph representation; see FindShortestTour.

See also the guide for Paths and Cycles.

The output may also have a different form. For example, FindEulerianCycle returns an edge list, compared to the vertex list returned by EulerianCycle.

Standard Graphs

CombinatoricaVersion 8
ButterflyGraph[n]ButterflyGraph[n]
CirculantGraph[n,j]CirculantGraph[n,j]
CompleteBinaryTree[n]KaryTree[n]
CompleteGraph[n]CompleteGraph[n]
CompleteKPartiteGraph[n1,n2,]CompleteGraph[{n1,n2,}]
CompleteKaryTree[n,k]KaryTree[n,k]
Cycle[n]CycleGraph[n]
DeBruijnGraph[n, m]DeBruijnGraph[n, m]
EmptyGraph[n]Graph[Range[n],{}]
ExactRandomGraph[n,m]RandomGraph[{n,m}]
FunctionalGraph[f,v]Graph[(#f[#])&/@v]
GeneralizedPetersenGraph[n,k]PetersenGraph[n,k]
GridGraph[n,m]GridGraph[{n,m}]
Harary[k,n]HararyGraph[k,n]
Hypercube[n]HypercubeGraph[n]
KnightsTourGraph[n,m]KnightTourGraph[n,m]
Path[n]PathGraph[Range[n]]
RandomGraph[n,p]RandomGraph[BernoulliGraphDistribution[n,p]]
RealizeDegreeSequence[s]RandomGraph[DegreeGraphDistribution[s]]
RegularGraph[k,n]RandomGraph[DegreeGraphDistribution[Table[k,{n}]]]
Star[n]StarGraph[n]
Turan[n,p]TuranGraph[n,p-1]
Wheel[n]WheelGraph[n]

There are a variety of standard named graphs that are parameterized by values. Most of these from Combinatorica have an equivalent in the Wolfram System. Note that names and syntax may be slightly different. Indexing of the vertices may also vary.

Version 7.0 << Combinatorica`
ShowGraph[Turan[5, 3]]
In[13]:=
Click for copyable input
Out[13]=

CombinatoricaVersion 8
CageGraph[k,r]GraphData[{"Cage",{k,r}}]
ChvatalGraphGraphData["ChvatalGraph"]
CoxeterGraphGraphData["CoxeterGraph"]
CubicalGraphGraphData["CubicalGraph"]
CubeConnectedCycle[n]GraphData[{"CubeConnectedCycle", n}]
DodecahedralGraphGraphData["DodecahedralGraph"]
FolkmanGraphGraphData["FolkmanGraph"]
FranklinGraphGraphData["FranklinGraph"]
FruchtGraphGraphData["FruchtGraph"]
GroetzschGraphGraphData["GroetzschGraph"]
HeawoodGraphGraphData["HeawoodGraph"]
HerschelGraphGraphData["HerschelGraph"]
IcosahedralGraphGraphData["IcosahedralGraph"]
LeviGraphGraphData["LeviGraph"]
McGeeGraphGraphData["McGeeGraph"]
MeredithGraphGraphData["MeredithGraph"]
MycielskiGraph[n]GraphData[{"Mycielski",n}]
NoPerfectMatchingGraphGraphData["NoPerfectMatchingGraph"]
NonLineGraphsGraphData["Beineke"]
OctahedralGraphGraphData["OctahedralGraph"]
OddGraph[n]GraphData[{"Odd",n}]
PetersenGraphGraphData["PetersenGraph"]
RobertsonGraphGraphData["RobertsonGraph"]
SmallestCyclicGroupGraphGraphData["SmallestCyclicGroupGraph"]
TetrahedralGraphGraphData["TetrahedralGraph"]
ThomassenGraphGraphData["ThomassenGraph"]
TutteGraphGraphData["TutteGraph"]
Uniquely3ColorableGraphGraphData["UniquelyThreeColorableGraph"]
UnitransitiveGraphGraphData["DesarguesGraph"]
WaltherGraphGraphData["WaltherGraph"]

A number of other standard graphs do not take parameters (or in the case of CageGraph, take only a limited range of parameters). These can generally be found in the GraphData database in Version 8.

Version 7.0 << Combinatorica`
ShowGraph[FruchtGraph]
In[14]:=
Click for copyable input
Out[14]=

In some cases, parameterized variants have not yet been implemented in the Wolfram System, but a subset can be found in GraphData. For example, CubeConnectedCycle is defined in GraphData for values 4 through 8; the MycielskiGraph can be found for values 5 through 11.

Version 7.0 << Combinatorica`
ShowGraph[MycielskiGraph[5]]
In[15]:=
Click for copyable input
Out[15]=

The Combinatorica function FiniteGraphs returns a list of the non-parameterized named graphs. GraphData[] could be considered something of an equivalent, as it returns the list of names that GraphData knows. However, this is a significantly longer list than FiniteGraphs!

BooleanAlgebra
CodeToLabeledTree
HasseDiagram
IntervalGraph
LabeledTreeToCode
ListGraphs
MakeGraph
PermutationGraph
RandomTree
ShuffleExchangeGraph
VertexConnectivityGraph

A small set of the named graphs do not yet have a direct equivalent in the Wolfram System. (See the documentation for TreeGraph for examples of generating random trees; it is still possible, just not yet with the method Combinatorica uses.)