Combinatorica Comparison

This page compares the functionality in SAGE 2.8.10 (November 2007) with that of the Combinatorica package in Mathematica. We compare to Mathematica version 6 and Combinatorica version 2.1.0. Feel free to update this page.

Sage functions

This table lists the functions available in SAGE and the equivalent Combinatorica functions. It also has some notes about the implementation and suggestions on how to make SAGE better.

SAGE Class

SAGE function

Combinatorica

Combinatorica Notes

SAGE notes

GenericGraph

add_vertex

AddVertex

Can specify coordinates for new vertices

add_vertices

AddVertices

Can specify coordinates and graphical info for new vertices

am

ToAdjacencyMatrix

Can return edge weight matrix and matrix counting loops/multiple edges as well

antisymmetric

AntiSymmetricQ

associate

Can we add this functionality to the add_vertex functions?

breadth_first_search

BreadthFirstTraversal

Returns list of vertices, edges, the tree, or just the levels of traversal

cartesian_product

GraphProduct

How are vertex properties transferred? How are loops/multiple edges handled?

center

GraphCenter

clear

Is this more efficient than just setting the graph to the empty graph?

clique_number

cliques

MaximumClique

Can find a k-clique, not just a maximum clique

cliques_containing_vertex

cliques_get_clique_bipartite

cliques_get_max_clique_graph

cliques_vertex_clique_number

cliques_number_of

cluster_transitivity

TransitiveQ

I think these two functions are/can be made equivalent

cluster_triangles

clustering_average

clustering_coeff

complement

GraphComplement

Pick a convention to deal with loops and make an option to switch conventions. We can also make an option for a max number of edges to set a convention for multiple edges

cores

delete_vertex

DeleteVertex

delete_vertices

DeleteVertices

density

depth_first_search

DepthFirstTraversal

Returns list of vertices, edges, or the traversal tree

diameter

Diameter

max( {} ) isn't right in the latex version

disjoint_union

GraphUnion

not restricted to two graphs, and can easily make copies of the same graph

disjunctive_product

distance

Distances

Returns list of distances to every other vertex

eccentricity

Eccentricity

Much more complete

get_boundary

The boundary functions let you make a set of vertices special. You can then get or set the boundary of a graph.

has_vertex

is_clique

CliqueQ and CompleteQ

is_clique(directed_clique=True) is equivalent to CompleteQ

is_independent_set

IndependetSetQ and EmptyQ

lexicographic_product

line_graph

LineGraph

loop_vertices

loops

SelfLoopsQ

name

neighbors

Neighborhood

can return neighbors distance k or less, not just immediate neighbors

networkx_graph

networkx_info

obj

order

V

periphery

plot

ShowGraph

Plotting differences should be looked at more carefully.

radius

Radius

random_subgraph

relabel

PermuteSubgraph

can relabel a subgraph, not just entire graph

set_boundary

shortest_path

ShortestPath

Also uses BellmanFord algorithm? Automatically switches between this and Dijkstra depending on whether the graph has negative weights and the density of the graph

shortest_path_all_pairs

shortest_path_length

what is the difference between this and distance?

shortest_path_lengths

shortest_paths

show

ShowGraph

what is the difference between this and the plot function?

size

M

strong_product

tensor_product

to_simple

MakeSimple

transitive_closure

TransitiveClosure

union

What does “common vertices will be renamed” mean in the docs?

vertex_boundary

vertex_iterator

vertices

Range[V[#]]&

Since vertices are always numerically numbered, the range gives the list of vertices

cmp

IdenticalQ

IdenticalQ isn't quite the same, I don't think it cares about loops/multiple edge settings, just the actual edge list.

contains

extend this to handle edges?

_matrix_

This is the adjacency matrix.

Graph

add_cycle

add_edge

AddEdge

add_edges

AddEdges

add_path

adjacency_matrix

ToAdjacencyMatrix

all_paths

automorphism_group

Automorphisms

bipartite_color, bipartite_sets

TwoColor

canonical_label

centrality_betweenness

centrality_closeness

centrality_degree

connected_component_containing_vertex

connected_components

ConnectedComponents

connected_components_number

connected_components_subgraphs

copy

degree

DegreeSequence, Degrees

can return only some degrees.

degree_histogram

degree_iterator

delete_edge

DeleteEdge

nondestructive; “All” Option to delete all multiple edges

delete_edges

DeleteEdges

nondestructive; “All” Option to delete all multiple edges

delete_multiedge

DeleteEdge

can we make this an option in delete_edge and delete_edges?

edge_boundary

edge_iterator

edge_label

edge_labels

GetEdgeLabels

edges

Edges

edges_incident

eulerian_circuit

EulerianCycle

genus

graph6_string

extend this to handle bigger graphs

has_edge

incidence_matrix

IncidenceMatrix

example shows a 0,1,-1 matrix. Should this be 0,1 matrix?

interior_paths

is_bipartite

BipartiteQ

is_circular_planar

write an outer_planar function using this.

is_connected

ConnectedQ

is_directed

Not[UndirectedQ[#]]&

is_eulerian

EulerianQ

is_isomorphic

IsomorphicQ

examine the differences between Combinatorica and SAGE later

kirchhoff_matrix

loop_edges

min_spanning_tree

MinimumSpanningTree

Implements Kruskal's algorithm

has three algorithms implemented (Kruskal's and two variants of Prim's)

multiple_edges

MultipleEdgesQ

neighbor_iterator

number_of_loops

plot3d

remove_loops

RemoveSelfLoops

can remove loops from selected vertices

remove_multiple_edges

RemoveMultipleEdges

extend to just remove multiple edges between sets of vertices

set_edge_label

SetEdgeLabels

How does this handle multiedges?

show3d

sparse6_string

extend this to handle bigger graphs

spectrum

Spectrum

subgraph

InduceSubgraph

to_directed

MakeDirected

“All” option to transfer edge attributes to both directed edges

to_undirected

MakeUndirected

weighted_adjacency_matrix

make an option in “adjacency_matrix”

write_to_eps

DiGraph

add_edge

AddEdge

add_edges

AddEdges

adjacency_matrix

ToAdjacencyMatrix

edge_boundary

edge_iterator

edge_label

edge_labels

GetEdgeLabels

edges

Edges

automorphism_group

Automorphisms

canonical_label

connected_component_containing_vertex

connected_components

ConnectedComponents

connected_components_number

connected_components_subgraphs

copy

degree

degree_iterator

delete_edge

DeleteEdge

nondestructive; “All” Option to delete all multiple edges

delete_edges

DeleteEdges

nondestructive; “All” Option to delete all multiple edges

delete_multiedge

DeleteEdge

can we make this an option in delete_edge and delete_edges?

dig6_string

has_edge

in_degree

InDegree

in_degree_iterator

incidence_matrix

IncidenceMatrix

Convention for sign is opposite (1 means outgoing in Combinatorica)

incoming_edge_iterator

incoming_edges

is_connected

ConnectedQ

Options for strong or weakly connected

is_directed

is_directed_acyclic

DirectedQ and AcyclicQ

Can do acyclic test for undirected graphs too

is_eulerian

EulerianQ

is_isomorphic

IsomorphicQ

loop_edges

multiple_edges

MultipleEdgesQ

neighbor_iterator

make option for “out” edges or “in” edges

number_of_loops

out_degree

OutDegree

out_degree_iterator

outgoing_edge_iterator

outgoing_edges

plot3d

predecessor_iterator

make this an option for neighbor_iterator and neighbors

predecessors

make this an option for neighbor_iterator and neighbors

remove_loops

RemoveSelfLoops

remove_multiple_edges

RemoveMultipleEdges

reverse

ReverseEdges

set_edge_label

SetEdgeLabels

show3d

subgraph

InduceSubgraph

successor_iterator

make this an option for neighbor_iterator and neighbors

successors

make this an option for neighbor_iterator and neighbors

to_directed

MakeDirected

to_undirected

MakeUndirected

topological_sort

TopologicalSort

topological_sort_generator

graphs

BalancedTree

CompleteKaryTree

can specify the total number of vertices

can specify the height

BarbellGraph

BullGraph

ChvatalGraph

ChvatalGraph

put “smallest triangle-free, 4-regular, 4-chromatic graph.” in docs?

CircularLadderGraph

CirculantGraph

CirculantGraph

ClawGraph

CompleteBipartiteGraph

CompleteKPartiteGraph

can create complete multipartite graph

CompleteGraph

CompleteGraph

CubeGraph

Hypercube

CycleGraph

Cycle

DegreeSequence

RealizeDegreeSequence

should “random” be “semirandom”, like in the Combinatorica documentation?

DegreeSequenceConfigurationModel

Can this be an option in DegreeSequence?

DegreeSequenceExpected

Can this be an option in DegreeSequence?

DegreeSequenceTree

Can this be an option in DegreeSequence?

DesarguesGraph

DiamondGraph

DodecahedralGraph

DodecahedralGraph

DorogovtsevGoltsevMendesGraph

EmptyGraph

EmptyGraph[0]

can give a number of vertices to include (empty means no edges)

FlowerSnark

FruchtGraph

FruchtGraph

Grid2dGraph

GridGraph

GridGraph

GridGraph

Only does up to 3 dimensions

HeawoodGraph

HeawoodGraph

smallest (6, 3)-cage

HexahedralGraph

HouseGraph

HouseXGraph

IcosahedralGraph

IcosahedralGraph

KrackhardtKiteGraph

LadderGraph

LCFGraph

LollipopGraph

MoebiusKantorGraph

OctahedralGraph

OctahedralGraph

PappusGraph

PathGraph

Path

PetersenGraph

PetersenGraph

RandomBarabasiAlbert

RandomDirectedGN

RandomDirectedGNC

RandomDirectedGNR

RandomGNM

RandomGNP

RandomGraph?

RandomHolmeKim

RandomLobster

RandomNewmanWattsStrogatz

RandomRegular

RandomShell

RandomTreePowerlaw

StarGraph

Star

TetrahedralGraph

TetrahedralGraph

ThomsenGraph

WheelGraph

Wheel

Combinatorica functions not in SAGE

These functions are implemented in Combinatorica, but not in SAGE. Feel free to implement them!

Note that this is outdated, and many of the features listed here are already implemented.

Combinatorica functions implemented, but not included yet

CombinatoricaCompare (last edited 2011-01-03 06:04:24 by Eviatar)