TableOfContents

Introduction

The SAGE Graph Theory Project aims to implement Graph objects and algorithms in ["SAGE"].

The main people working on this project are Emily Kirkman, Robert Miller and Bobby Moretti.

We have attempted to make a complete list of existing graph theory software. We posted functionality lists and some algorithm/construction summaries. We are very interested in feedback or last-minute additions, as we are ready to begin [http://sage.math.washington.edu:9001/graph_benchmark benchmarking] our findings.

Survey of existing Graph Theory software

Software included with SAGE

GAP

Maxima

Singular

PARI, MWRANK, NTL

Matplotlib

GSL, Numeric

Software included with SAGE as optional

GRAPE

Nauty

Software SAGE interfaces with (but does not include)

Magma

Maple

Mathematica

Extensions of software that SAGE interfaces with

Magma

Maple

  1. [http://www.math.uga.edu/~mbaker/REU/maple/laplacian-guide.html 'laplacian.mpl']; [http://www.fmf.uni-lj.si/~mohar/Papers/Spec.pdf here] is a paper on the Laplacian Spectrum

    1. Storage/Pipes

      • creation of certain spreadsheets, such as known eigenvalues and eigenvalues of increasing subdivisions of the graph
    2. Construction

      • banana graphs, star graphs, bouquets and flowers, hypercubes, supercirc (see docs), subdivide edges into n edges, contract, assign directions (apparently in a random way)
    3. Decorations (Coloring, Weight, Flow, etc.)

      • normalilze (so sum of weights = 1)
    4. Algebra

      • discrete laplacian matrix (this function may fight with the built-in laplacian in 'linalg'), compute its eigenvalues given a measure,
    5. Topology

  2. [http://www.cecm.sfu.ca/CAG/papers/GTpaper.pdf GraphTheory] and [http://www.cecm.sfu.ca/CAG/papers/GT2006.pdf Part II] of the paper (haven't yet found the actual package...)

Mathematica

  1. [http://www.combinatorica.com/ Combinatorica] - for a list of functions, see [http://www.cs.sunysb.edu/~skiena/combinatorica/help.pdf help.pdf], page 13-14, 18, 21, 23, 25 - for a [http://www.amazon.com/exec/obidos/ASIN/0521806860/ref=nosim/thealgorithmrepo/ book]

Software that SAGE can now include as is (not as an optional package...)

Gato

NetworkX

CHomP

Software that SAGE can now include as optional

GeoSteiner

http://www.diku.dk/geosteiner/LICENSE

Very_nauty

GraphViz

plantri/fullgen

Software that is incompatible with SAGE but still useful

GUESS

CAIDA's Walrus

GraphThing

GRIN

DSATUR

LEDA

  1. [http://www.alogorithmic-solutions.com Link]

    1. Commercial, but supposedly fast
    2. Morphisms / Group Actions

      • Module graph and subgraph isomorphisms

  1. [http://dimacs.rutgers.edu/~berryj/LINK.html (hyper)link]

    1. Free, but not open source
    2. C++ libraries

ABACUS (A Branch-And-!CUt System)

Apparently useless / and/or misc. / and/or etc.

Vancouver Network Analysis Team

!yFiles

prefuse

LGL (Large Graph Layout)

nv2d

Otter

Gravisto

JIGGLE

RoxGT

INGRID

METIS

Algolib

ACE

GOBLIN

JGraphEd

Scalable Libraries for Graph Partitioning

Netvis Module

Cyram Netminer

Algorithm Repositories

Stony Brook

InterTools

GraphBase

Groups & Graphs

Functionality categories

  1. Representation

  2. Storage/Pipes

  3. Construction

  4. Decorations (Coloring, Weight, Flow, etc.)

  5. Invariants

  6. Predicates

  7. Subgraphs and Subsets

  8. Adjacency, etc.

  9. Connectivity

  10. Paths, etc.

  11. Trees, etc.

  12. Colorings

  13. Optimization

  14. Embedding (Planar graphs, etc.)

  15. Algebra

  16. Morphisms/Group Actions

  17. Symmetry

  18. Geometry

  19. Topology

  20. Generation/Random Graphs

  21. Database

  22. Visualization

Miscellaneous Flora and Fauna