Diff for "graph_benchmark"

Differences between revisions 6 and 7

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.

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

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

Initial Benchmarks

For the first round of benchmarking, 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 (directed and undirected, sparse and dense)

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, we will compute
Connectivity
Diameter
Girth
Chromatic number

-  ⇤ ← Revision 6 as of 2006-10-14 17:01:48 → 
  Size: 1178
  Editor: anonymous
  Comment:
+   ← Revision 7 as of 2006-10-14 17:05:01 → ⇥
  Size: 1331
  Editor: anonymous
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 17:
- * Create a graph with n nodes and no edges
+ * Create a graph with n nodes and no edges (sparse and dense, if supported)
 Line 20:
- * Fill in and then delete all edges one by one
+ * Fill in and then delete all edges one by one (directed and undirected, sparse and dense)
 Line 23:
-==== Complete ====
==== Complete bipartite ====
==== Cycle ====
+ * Create a complete graph on n nodes
 * Create a complete bipartite graph on n nodes
 * Create a cycle on n nodes
 Line 28:
-==== Connectivity ====
==== Diameter ====
==== Girth ====
==== Chromatic number ====
+ . From a given database of graphs, we will compute
 * Connectivity
 * Diameter
 * Girth
 * Chromatic number