Differences between revisions 1 and 127 (spanning 126 versions)
⇤ ← Revision 1 as of 2006-10-03 15:09:12 →
Size: 6625
Editor: wstein
Comment:
← Revision 127 as of 2008-11-14 13:41:59 → ⇥
Size: 3798
Editor: anonymous
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
The SAGE Graph Theory Project aims to implement Graph objects and algorithms in [SAGE] <<TableOfContents>>
Line 3: Line 3:
The following is a survey of existing Graph Theory software. The SAGE Graph Theory Project

== Introduction ==
 . We are implementing graph objects and algorithms in [[SAGE]]. The main people working on this project are Emily Kirkman and Robert Miller.

== Current Status ==
 * NetworkX base classes have been interfaced, and all functions are soon to follow.
 * Jason Grout's (Brigham Young) SQL lite graph database is almost finished, and when it is done, it will be interfaced by Emily.
 * Jim Morrow (UW) has expressed interest in using SAGE for his [[http://www.math.washington.edu/~morrow/reu07/reu.html|summer REU]] on graphs. Robert is working on implementing electrical networks, which includes implementing edge weights and graphs with boundary.
 * Chris Godsil (Waterloo) has expressed interest in helping design a more general discrete math package in SAGE.
 * Brendan !McKay's isomorphism algorithm has been replicated for the open source community (it is called "nice", as opposed to "nauty").
 * Graph plotting has been implemented in two dimensions:
Line 5: Line 17:
  <ul>
    <li>Software included with SAGE</li>
      <ol>
        <li>GAP</li>
        <li>Maxima</li>
        <li>Singular</li>
        <li>PARI, MWRANK, NTL</li>
        <li>Matplotlib</li>
        <li>GSL, Numeric</li>
      </ol>
    <li>Software SAGE interfaces with (but does not include)</li>
      <ol>
        <li>Gnuplot</li>
        <li>KASH</li>
        <li><a href="http://magma.maths.usyd.edu.au/magma/htmlhelp/text1452.htm">Magma</a></li>
          <ul>
            <li><b>Representation</b></li>Sparse support; function computes memory requirement for graph with n verts and m edges; consists of graph itself, vertex set, and edge set
            <li><b>Storage/Pipes</b></li>one function opens either file or stream, files stored in <a href="http://cs.anu.edu.au/~bdm/data/formats.html">Graph6 and Sparse6 format</a>
            <li><b>Construction</b></li>From matrix; from edge tuples; from vertex neighbors; from edges of other graphs; subgraphs; quotient graphs; incremental construction; complement; contraction; breaking edges; line graph; switch nbrs for non-nbrs of a vertex; disjoint unions, edge unions; complete unions; cartesian, lexicographic and tensor products; n-th power (same vert set, incident iff dist <= n); graph <-> digraph; Cayley graph constructor; Schreier graph constructor; Orbital graph constructor; Closure graph constructor (given G, add edges to make G invariant under a given permutation group); Paley graphs and tournaments; graphs from incidence structures; converse(reverse digraph); n-th odd graph; n-th triangular graph; n-th square lattice graph; Clebsch, Shrikhande, Gewirtz and Chang graphs;
            <li><b>Decorations (Coloring, Weight, Flow, etc.)</b></li>Vertices have labels only; Edges have labels, capacity(non-negative integers, loops=0) and weights(totally ordered ring);
            <li><b>Invariants</b></li>#verts, #edges; characteristic polynomial; spectrum
            <li><b>Predicates</b></li>2 verts incident, 2 edges incident, 1 vertex and 1 edge incident, subgraph, bipartite, complete, Eulerian, tree, forest, empty, null, path, polygon, regular
            <li><b>Subgraphs and Subsets</b></li>has k-clique, clique number, all cliques, maximum clique (<a href="http://magma.maths.usyd.edu.au/magma/htmlhelp/text1473.htm">"When comparing both algorithms in the situation where the problem is to find a maximum clique one observes that in general BranchAndBound does better. However Dynamic outperforms BranchAndBound when the graphs under consideration are large (more then 400 vertices) random graphs with high density (larger than 0.5%). So far, it can only be said that the comparative behaviour of both algorithms is highly dependent on the structure of the graphs."</a>), independent sets and number,
            <li><b>Adjacency, etc.</b></li>(in- & out-) degree, degree vector, valence (if regular), vertex nbrs, edge nbrs, bipartition, dominating sets
            <li><b>Connectivity</b></li>(strongly) connected, components, separable, 2-connected, 2-components, triconnectivity (<a href="http://magma.maths.usyd.edu.au/magma/htmlhelp/text1466.htm">"The linear-time triconnectivity algorithm by Hopcroft and Tarjan [HT73] has been implemented with corrections of our own and from C. Gutwenger and P. Mutzel [GM01]. This algorithm requires that the graph has a sparse representation."</a>), k-vertex connectivity, vertex separator, k-edge connectivity, edge separator
            <li><b>Paths, etc.</b></li>distance and geodesic, diameter and corr. path, ball and sphere, distance partition, equitable partition, girth and corr. cycle
            <li><b>Trees, etc.</b></li>spanning tree, breadth first and depth first searches, rooted, root, parent, vertex paths
            <li><b>Colorings</b>(see also Decorations)</li>chromatic number and index, optimal vertex and edge colorings, chromatic polynomial
            <li><b>Optimization</b></li>Max flow min cut (2 algorithms: <a href="http://magma.maths.usyd.edu.au/magma/htmlhelp/text1499.htm#15274">Dinic & push-relabel</a>), maximum matching for bipartite,
            <li><b>Embedding</b> (Planar graphs, etc.)</li>planarity, Kuratowski subgraphs, faces of a planar graph, embedding info as orientation of edges from a vertex
            <li><b>Algebra</b></li>adjacency matrix, distance matrix, incidence matrix, intersection matrix
            <li><b>Morphisms/Group Actions</b></li>interfaces <i>nauty</i>
            <li><b>Symmetry</b></li>vertex, edge and distance transitivity; orbit partitions; primitivity; symmetric; distance regularity and intersection array
            <li><b>Geometry</b></li>Go back and forth between incidence and coset geometries and their graphs; finite planes;
            <li><b>Generation/Random Graphs</b></li>interfaces <i>nauty</i>
            <li><b>Database</b></li>database interface, strongly regular graph DB, random graph from DB, slick implementation of for loops ("for G in D do ... end for;")
          </ul>
        <li>Maple</li>
        <li>Mathematica</li>
        <li>mwrank</li>
        <li>Octave</li>
        <li>Tachyon Ray Tracer</li>
      </ol>
    <li>Software that SAGE can now include as is</li>
    <li>Software that SAGE should include (or maybe interface with), pending stuff (e.g. licensing)</li>
    <li>Software that is incompatible with SAGE but still useful</li>
  </ul>		 C = graphs.CubeGraph(9)
color = {}
for v in C.vertices():
    b = v.count('1')/9
    g = 1 - b
    if color.has_key((0, g, b)): color[(0, g, b)].append(v)
    else: color[(0, g, b)] = [v]
C.show(vertex_labels=False, node_size=60, graph_border=True, color_dict=color, figsize=[9,8])
}}}
Line 53: Line 27:
  <p>Functionality categories:
          <ol>
            <li><b>Representation</b></li>
            <li><b>Storage/Pipes</b></li>
            <li><b>Construction</b></li>
            <li><b>Decorations (Coloring, Weight, Flow, etc.)</b></li>
            <li><b>Invariants</b></li>
            <li><b>Predicates</b></li>
            <li><b>Subgraphs and Subsets</b></li>
            <li><b>Adjacency, etc.</b></li>
            <li><b>Connectivity</b></li>
            <li><b>Paths, etc.</b></li>
            <li><b>Trees, etc.</b></li>
            <li><b>Colorings</b>
            <li><b>Optimization</b></li>
            <li><b>Embedding</b> (Planar graphs, etc.)</li>
            <li><b>Algebra</b></li>
            <li><b>Morphisms/Group Actions</b></li>
            <li><b>Geometry</b></li>
            <li><b>Topology</b></li> Homology groups
            <li><b>Generation/Random Graphs</b></li>
            <li><b>Database</b></li>
            <li><b>Visualization</b></li>
          </ol>		 {{attachment:9_cube.png}}
Line 78: Line 29:
== Talks ==
 * On Oct. 20, 2006, Robert gave a [[http://sage.math.washington.edu/home/rlmill/talk_2001-10-20/2006-10-20SAGE.pdf|talk]] about the state of affairs for existing software which shared a few benchmarks and discussed some implementation ideas.
 * On Feb. 15, 2007, Robert and Emily gave an Informal Introduction to the Graph Theory Package. This talk was essentially a review of newly available features.
 * On Feb. 17, 2007, Robert gave a [[http://www.robertlmiller.com/talks/graph_intro.pdf|talk]] at Sage Days 3.
 * On Mar. 2, 2007, Robert gave a talk entitled "Opening Graph Automorphisms".
 * On Mar. 29, 2007, he followed up with a [[http://www.robertlmiller.com/talks/nauty.pdf|part two]] of this talk, after implementing "nice".
 * On Apr. 21, 2007, Emily presented a [[http://sage.math.washington.edu/home/ekirkman/talks/ECCAD.ppt|poster (ppt)]] introducing the SAGE graph theory package at East Coast Computer Algebra Day.
 * On Apr. 27, 2007, Emily gave a [[http://sage.math.washington.edu/home/ekirkman/talks/2007_04_27.html|talk]] introducing the (almost complete) sqlite database.

== Other wiki pages ==
 * Surveys
  . [[http://wiki.sagemath.org/graph_survey|Existing Software]]: We are always seeking additions and comments.
  . [[http://wiki.sagemath.org/graph_db_survey|Existing Databases]]: Includes comments by Jason Grout.

 * [[http://wiki.sagemath.org/graph_benchmark|Benchmarks]]
  . Initial Benchmarks indicated that NetworkX was the appropriate package for inclusion in SAGE. They were designed to compare the constructions and very basic functionality found in our survey of existing software.

 * [[http://wiki.sagemath.org/graph_plotting|Plotting]]
  * 2D plotting is implemented using matplotlib.
  * 3D plotting via Tachyon is coming soon.
  * 3D interactive viewing is on its way, via Java applets (pending some serious implementation issues).

 * [[http://wiki.sagemath.org/graph_generators|Graph Generators]]
  * So far: Basic graph structures with intuitive graphics.
  * Extensive educational docstrings and many graph constructors.
  * Native positionings allow standard layouts and quicker plotting

 * [[http://wiki.sagemath.org/graph_database|Database]]
  . Emily has provided a provisional database of graphs on up to seven vertices:

{{{
graphs_query.show_graphs(with_properties=True, nodes=7, diameter=5)
Line 79: Line 62:
{{attachment:database.png}}

Contents

  1. Introduction
  2. Current Status
  3. Talks
  4. Other wiki pages

The SAGE Graph Theory Project

Introduction

  • We are implementing graph objects and algorithms in SAGE. The main people working on this project are Emily Kirkman and Robert Miller.

Current Status

  • NetworkX base classes have been interfaced, and all functions are soon to follow.
  • Jason Grout's (Brigham Young) SQL lite graph database is almost finished, and when it is done, it will be interfaced by Emily.

  • Jim Morrow (UW) has expressed interest in using SAGE for his summer REU on graphs. Robert is working on implementing electrical networks, which includes implementing edge weights and graphs with boundary.

  • Chris Godsil (Waterloo) has expressed interest in helping design a more general discrete math package in SAGE.

  • Brendan McKay's isomorphism algorithm has been replicated for the open source community (it is called "nice", as opposed to "nauty").

  • Graph plotting has been implemented in two dimensions: 

C = graphs.CubeGraph(9)
color = {}
for v in C.vertices():
    b = v.count('1')/9
    g = 1 - b
    if color.has_key((0, g, b)): color[(0, g, b)].append(v)
    else: color[(0, g, b)] = [v]
C.show(vertex_labels=False, node_size=60, graph_border=True, color_dict=color, figsize=[9,8])

9_cube.png

Talks

  • On Oct. 20, 2006, Robert gave a talk about the state of affairs for existing software which shared a few benchmarks and discussed some implementation ideas.

  • On Feb. 15, 2007, Robert and Emily gave an Informal Introduction to the Graph Theory Package. This talk was essentially a review of newly available features.

  • On Feb. 17, 2007, Robert gave a talk at Sage Days 3.

  • On Mar. 2, 2007, Robert gave a talk entitled "Opening Graph Automorphisms".

  • On Mar. 29, 2007, he followed up with a part two of this talk, after implementing "nice".

  • On Apr. 21, 2007, Emily presented a poster (ppt) introducing the SAGE graph theory package at East Coast Computer Algebra Day.

  • On Apr. 27, 2007, Emily gave a talk introducing the (almost complete) sqlite database.

Other wiki pages

  • Surveys

  • Benchmarks

    • Initial Benchmarks indicated that NetworkX was the appropriate package for inclusion in SAGE. They were designed to compare the constructions and very basic functionality found in our survey of existing software.

  • Plotting

    • 2D plotting is implemented using matplotlib.
    • 3D plotting via Tachyon is coming soon.
    • 3D interactive viewing is on its way, via Java applets (pending some serious implementation issues).

  • Graph Generators

    • So far: Basic graph structures with intuitive graphics.
    • Extensive educational docstrings and many graph constructors.
    • Native positionings allow standard layouts and quicker plotting

  • Database

    • Emily has provided a provisional database of graphs on up to seven vertices: 

graphs_query.show_graphs(with_properties=True, nodes=7, diameter=5)

database.png

graph (last edited 2009-11-29 06:48:46 by newacct)