TableOfContents

Introduction

The SAGE [http://sage.math.washington.edu:9001/graph 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.

Existing Graph Theory software

Software included with SAGE

GAP

Software optional in SAGE

NetworkX

GRAPE

Nauty

Software interfaced in SAGE

Magma

Maple

Mathematica

Extensions of interfaced software in SAGE

Maple: 'laplacian.mpl'

  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: Combinatorica

  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]

Other (useful) software

Python Libraries

pygraphlib

Pygraphviz, pydot, YAPGVB

GraphViz

Gato

C/C++

CHomP

Boost C++ Libraries

Very_nauty

plantri/fullgen

GraphThing

EWS

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

    1. Free, but not open source
    2. C++ libraries
    3. Doc's are PS, which upsets my computer very much!!! (ie - I can't read them so I don't actually know that much about LINK)

ABACUS (A Branch-And-!CUt System)

GOBLIN

JAVA

CAIDA's Walrus

The Graph Visualization Framework

JGraphT

GINY

JUNG

JDigraph

WilmaScope

nv2d

JGraphEd

JIGGLE

RoxGT

And more

These need to be organized...

DISCRETA

GTL

GeoSteiner

GUESS

GRIN

DSATUR

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

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

      • Module graph and subgraph isomorphisms
    3. Needs a Functionality Category

      1. Curved Geometry: Polygons with Circular Arcs
      2. Module Compression
      3. Module Cryptography
      4. Static Graphs

GDToolkit

StOCNET

TouchGraph

Vancouver Network Analysis Team

yFiles

prefuse

LGL (Large Graph Layout)

Otter

Gravisto

INGRID

METIS

Algolib

ACE

Scalable Libraries for Graph Partitioning

Netvis Module

Cyram Netminer

Algorithm Repositories

Stony Brook

InterTools

Graph Partitioners

GraphBase

Groups & Graphs

Dr. Epstein

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