Upgrading from:

Combinatorica`

As of Version 10, 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 10, 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 System`Graph or Combinatorica`Graph.

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

Vertex locations are optional.

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

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

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

The adjacency matrix is a sparse array.

Version 7.0 << Combinatorica` ToAdjacencyMatrix[Wheel[5]]

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

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

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

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

CombinatoricaVersion 10
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]]]]]

Graph Properties

CombinatoricaVersion 10
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]]

CombinatoricaVersion 10
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]VertexInDegree[g,v]
M[g]EdgeCount[g]
OutDegree[g,v]VertexOutDegree[g,v]
Radius[g]GraphRadius[g]
V[g]VertexCount[g]

Version 7.0 << Combinatorica` Diameter[ButterflyGraph[5]]

Graph Algorithms

CombinatoricaVersion 10
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 10
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]]

CombinatoricaVersion 10
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","Graph"]
OctahedralGraphGraphData["OctahedralGraph"]
OddGraph[n]GraphData[{"Odd",n}]
PetersenGraphGraphData["PetersenGraph"]
RobertsonGraphGraphData["RobertsonGraph"]
SmallestCyclicGroupGraphGraphData["SmallestCyclicGroupGraph"]
TetrahedralGraphGraphData["TetrahedralGraph"]
ThomassenGraphGraphData["ThomassenGraph34"]
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 10.

Version 7.0 << Combinatorica` ShowGraph[FruchtGraph]

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

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.)