|
Size: 1197
Comment:
|
Size: 1388
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| The SAGE Graph Theory Project aims to implement Graph objects and algorithms in ["SAGE"]. | The SAGE [http://sage.math.washington.edu:9001/graph Graph Theory Project] aims to implement Graph objects and algorithms in ["SAGE"]. |
| Line 8: | Line 8: |
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. |
|
| Line 14: | Line 12: |
| . 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. | |
| Line 16: | Line 15: |
| * Create a graph with n nodes and no edges | * Create a graph with n nodes and no edges (sparse and dense, if supported) |
| Line 19: | Line 18: |
| * Fill in and then delete all edges one by one | * Fill in and then delete all edges one by one (sparse and dense, if supported) |
| Line 22: | Line 21: |
| ==== Complete ==== ==== Complete bipartite ==== ==== Cycle ==== === Basic Storage Speed === * Compute the number of edges |
* Create a complete graph on n nodes * Create a complete bipartite graph on n nodes * Create a cycle on n nodes |
| Line 30: | Line 26: |
| ==== Connectivity ==== ==== Diameter ==== ==== Girth ==== ==== Chromatic number ==== |
. From a given database of graphs (sparse and dense), we will compute * Connectivity * Diameter * Girth * Chromatic number |
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