TableOfContents

In Process of Updating... Check back 11/23/06

Introduction

The SAGE Graph Theory Project aims to implement Graph objects and algorithms in ["SAGE"].

The goal of the Graph Database is to implement constructors for many common graphs, as well as thorough docstrings that can be used for educational purposes. Please check below for updates and note the section set aside for suggestions at the bottom of the page.

Emily Kirkman is working on this project.

Class Docstrings

A collection of constructors of common graphs.

USES:
    A list of all graphs and graph structures in this database is available via tab completion.
    Type "graphs." and then hit tab to see which graphs are available.

    The docstrings include educational information about each named graph with the hopes that this
    database can be used as a reference.

PLOTTING:
    All graphs (i.e., networks) have an associated SAGE graphics object, which you can display:
        
        sage: G = WheelGraph(15)
        sage: p = G.plot()
        sage: is_Graphics(p)
        True

    When creating a graph in SAGE, the default positioning of nodes is determined using the spring-layout
    algorithm.  Often, it is more efficient to pre-set the positions in a dictionary.  Additionally, we can use
    this position dictionary to display the graph in an intuitive manner, whereas the spring-layout would 
    fail if the graph is not very symmetric.  For example, consider the Petersen graph with default node
    positioning vs. the Petersen graph constructed by this database:

        sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9],\
                5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]})
        sage.: petersen_spring.show()
        sage: petersen_database = graphs.PetersenGraph()
        sage.: petersen_database.show()
    
    For all the constructors in this database (except the random and empty graphs), the position dictionary
    is filled, instead of using the spring-layout algorithm.

ORGANIZATION:
    The constructors available in this database are organized as follows:
        Basic Structures:
            - EmptyGraph
            - CycleGraph
            - StarGraph
            - WheelGraph
        Named Graphs:
            - PetersenGraph
        Families of Graphs:
            - CompleteGraph
            - CompleteBipartiteGraph
            - RandomGNP
            - RandomGNPFast

AUTHORS:
    -- Robert Miller (2006-11-05): initial version - empty, random, petersen
    -- Emily Kirkman (2006-11-12): basic structures, node positioning for all constructors
    -- Emily Kirkman (2006-11-19): docstrings, examples
    
TODO:
    [] more named graphs
    [] thorough docstrings and examples

Basic Structures

We've begun to implement some basic graph constructors with (hopefully) intuitive graphics. Please browse below and for more information on graph plotting, look at Rober Miller's [http://sage.math.washington.edu:9001/graph_plotting wiki].

Empty Graphs

Info

Plotting

Examples

 # Add one vertex to an empty graph and then show:
 sage: empty1 = graphs.EmptyGraph()
 sage: empty1.add_vertex()
 sage.: empty1.show()

 # Use for loops to build a graph from an empty graph:
 sage: empty2 = graphs.EmptyGraph()
 sage: for i in range(5):
 ...    empty2.add_vertex() # add 5 nodes, labeled 0-4
 ...
 sage: for i in range(3):
 ...    empty2.add_edge(i,i+1) # add edges {[0:1],[1:2],[2:3]}
 ...
 sage: for i in range(4)[1:]:
 ...    empty2.add_edge(4,i) # add edges {[1:4],[2:4],[3:4]}
 ...
 sage.: empty2.show()

Cycle Graphs

Info

Plotting

Examples

attachment:cycle_10.png

attachment:cycle_array.png

Star Graphs

Info

Plotting

Examples

attachment:star_33.png

attachment:star_array.png

Wheel Graphs

Info

Plotting

Examples

attachment:wheel_32.png

attachment:wheel_array.png

Named Graphs

Petersen

Info

Plotting

Examples

attachment:petersen_pos.png

attachment:petersen_spring.png

Graph Families

Complete Graphs

Info

Plotting

Examples

C = graphs.CompleteGraph(16)
C.show()

attachment:complete_16.png

attachment:complete_array.png

Complete Bipartite Graphs

Info

Plotting

Examples

attachment:complete_bipartite_9_6.png

attachment:complete_bipartite_array.png

Graphs I Plan to Add

Suggestions