Differences between revisions 11 and 12
 ⇤ ← Revision 11 as of 2006-10-14 23:56:00 → Size: 1400 Editor: D-128-208-62-108 Comment: ← Revision 12 as of 2006-10-14 23:56:19 → ⇥ Size: 1388 Editor: D-128-208-62-108 Comment: Deletions are marked like this. Additions are marked like this. Line 26: Line 26: . From a given database of graphs (sparse and dense, undirected), we will compute . From a given database of graphs (sparse and dense), we will compute

## 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 will post results here as we get them. And as always, we love feedback!

## Initial Benchmarks

• Our initial tests are designed to compare the constructions and very basic functionality found in our [http://sage.math.washington.edu:9001/graph_survey survey of existing software]. At this stage in the game, we are testing to find the best way to construct graph objects in ["SAGE"]. For the first round of benchmarking we will only consider simple undirected graphs, and we will be comparing MAGMA, Mathematica (with Combinatorica), Maple, NetworkX, GRAPE, and nauty.

### Generic Constructor

• Create a graph with n nodes and no edges (sparse and dense, if supported)

### Edge Storage

• Fill in and then delete all edges one by one (sparse and dense, if supported)

### Specific Constructors

• Create a complete graph on n nodes
• Create a complete bipartite graph on n nodes
• Create a cycle on n nodes

### Basic Algorithms

• From a given database of graphs (sparse and dense), we will compute
• Connectivity
• Diameter
• Girth
• Chromatic number

graph_benchmark (last edited 2008-11-14 13:41:59 by localhost)