Differences between revisions 2 and 3
Revision 2 as of 2006-10-14 05:45:28
Size: 905
Editor: D-128-208-62-108
Comment:
Revision 3 as of 2006-10-14 05:54:32
Size: 1197
Editor: D-128-208-62-108
Comment:
Deletions are marked like this. Additions are marked like this.
Line 12: Line 12:
Line 15: Line 16:
 * Create a graph with n nodes and no edges
Line 16: Line 19:
 * Fill in and then delete all edges one by one
Line 17: Line 22:
==== Complete ====
==== Complete bipartite ====
==== Cycle ====
Line 18: Line 27:
 * Compute the number of edges
Line 19: Line 30:
==== Connectivity ====
==== Diameter ====
==== Girth ====
==== Chromatic number ====

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.

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 initial benchmarks listed below, we will be comparing MAGMA, Mathematica (with Combinatorica), Maple, NetworkX, GRAPE, and nauty.

We will post results here as we get them. And as always, we love feedback!

Initial Benchmarks

Generic Constructor

  • Create a graph with n nodes and no edges

Edge Storage

  • Fill in and then delete all edges one by one

Specific Constructors

Complete

Complete bipartite

Cycle

Basic Storage Speed

  • Compute the number of edges

Basic Algorithms

Connectivity

Diameter

Girth

Chromatic number

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