next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Nauty :: generateGraphs

generateGraphs -- generates the graphs on a given number of vertices

Synopsis

Description

This method generates all graphs on $n$ vertices subject to the constraints on the number of edges. It uses numerous options to allow further constraining of the output.

If a PolynomialRing $R$ is supplied instead, then the number of vertices is the number of generators. Moreover, the nauty-derived strings are automatically converted to instances of the class Graph in $R$.

i1 : R = QQ[a..e];
i2 : generateGraphs(R, 4, 6, OnlyConnected => true)

o2 = {Graph{edges => {{a, e}, {b, e}, {c, e}, {d, e}}},
            ring => R                                  
            vertices => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {a, e}, {b, e}, {c, e}}},
           ring => R                                  
           vertices => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {b, d}, {a, e}, {b, e}, {c, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {b, d}, {a, e}, {c, e}, {d, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {b, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           ring => R                                                  
           vertices => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{edges => {{a, d}, {b, d}, {c, d}, {a, e}, {b, e}, {c, e}}},
           ring => R                                                  
           vertices => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {b, d}, {a, e}, {b, e}}},
           ring => R                                  
           vertices => {a, b, c, d, e}                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {b, d}, {a, e}, {b, e}, {c, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {b, d}, {a, e}, {b, e}, {c, e}, {d, e}}},
           ring => R                                                  
           vertices => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {a, d}, {b, d}, {b, e}, {c, e}}},
           ring => R                                          
           vertices => {a, b, c, d, e}                        
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {a, d}, {b, d}, {a, e}, {b, e}, {c, e}}},
           ring => R                                                  
           vertices => {a, b, c, d, e}                                
     ------------------------------------------------------------------------
     Graph{edges => {{a, c}, {a, d}, {c, d}, {a, e}, {b, e}, {c, e}}}}
           ring => R
           vertices => {a, b, c, d, e}

o2 : List

Caveat

The number of vertices $n$ must be positive as nauty cannot handle graphs with zero vertices.

See also

Ways to use generateGraphs :

For the programmer

The object generateGraphs is a method function with options.