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 and Robert Miller.

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 benchmarking our findings.

Existing Graph Theory software

Software included with SAGE

GAP

Maxima

NetworkX

Software optional in SAGE

GRAPE

Nauty

Software interfaced in SAGE

Magma

Maple

Mathematica

Extensions of interfaced software in SAGE

Maple: 'laplacian.mpl'

  1. 'laplacian.mpl'; 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

      • (laplacian matrix), effective resistance between vertices, discrete and continuous canonical measure an unrelated explanation? and tau (also, taushorten "Investigates the behavior of tau as an edge is shortened"), discrete dx measure

  2. GraphTheory and Part II of the paper (haven't yet found the actual package...)

Mathematica: Combinatorica

  1. Combinatorica - for a list of functions, see help.pdf, page 13-14, 18, 21, 23, 25 - for a book

  2. For a comparison of functionality in Combinatorica and SAGE, see the CombinatoricaCompare page.

Other (useful) software

Python Libraries

pygraphlib

Pygraphviz, pydot, YAPGVB

GraphViz

Gato

C/C++

CHomP

Boost C++ Libraries

Very_nauty

plantri/fullgen

GraphThing

EWS

  1. (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

igraph

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

graph_survey (last edited 2008-11-14 13:41:50 by anonymous)