This is Nauty.info, produced by Macaulay2, version 1.21

Nauty -- Interface to nauty
***************************

Description
===========

This package provides an interface from Macaulay2 to many of the functions
provided in the software nauty by Brendan D. McKay, available at
http://cs.anu.edu.au/~bdm/nauty/. The nauty package provides very efficient
methods for determining whether given graphs are isomorphic, generating all
graphs with particular properties, generating random graphs, and more.

Most methods can handle graphs in either the Macaulay2 Graph (EdgeIdeals),
type as provided by the EdgeIdeals,
package or as Graph6 and Sparse6 strings as used by nauty. The purpose of this
is that graphs stored as strings are greatly more efficient than graphs stored
as instances of the class Graph (EdgeIdeals). (See
Comparison of Graph6 and Sparse6 formats.)

It is recommended to work with graphs represented as strings while using
nauty-provided methods and then converting the graphs to instances of the class
Graph (EdgeIdeals), for further work (e.g., computing the chromatic
number).

The theoretical underpinnings of nauty are in the paper: B. D. McKay,
"Practical graph isomorphism," Congr. Numer. 30 (1981), 45–87.

See also
========

  * Comparison of Graph6 and Sparse6 formats
  * Example_colon_ Checking for isomorphic graphs
  * Example_colon_ Generating and filtering graphs

Author
======

  * David Cook II (see http://ux1.eiu.edu/~dwcook/ ) <dwcook@eiu.edu>

Certification a gold star
=========================

Version 1.4.1 of this package was accepted for publication in volume 3 (see
http://j-sag.org/Volume3/ ) of The Journal of Software for Algebra and
Geometry: Macaulay2 (see http://j-sag.org/ ) on 2011-04-20, in the article
Nauty in Macaulay2 (see http://j-sag.org/Volume3/jsag-1-2011.pdf ). That
version can be obtained from the journal (see http://j-sag.org/Volume3/Nauty.m2
) or from the Macaulay2 source code repository (see
https://github.com/Macaulay2/M2/blob/ea719b4fd3b65bb35ebd0f10f356c7d53ba73b7d/
M2/Macaulay2/packages/Nauty.m2 ).

Version
=======

This documentation describes version 1.4.3.1 of Nauty.

Source code
===========

The source code from which this documentation is derived is in the file
Nauty.m2 (see common/share/Macaulay2/Nauty.m2 ).

Exports
=======

  * Functions and commands
      * addEdges -- creates a list of graphs obtained by
        adding one new edge to the given graph in all possible ways
      * areIsomorphic -- determines whether two graphs
        are isomorphic
      * buildGraphFilter -- creates the appropriate
        filter string for use with filterGraphs and countGraphs
      * countGraphs -- counts the number of graphs in the
        list with given properties
      * filterGraphs -- filters (i.e., selects) graphs in
        a list for given properties
      * generateBipartiteGraphs -- generates
        the bipartite graphs with a given bipartition
      * generateGraphs -- generates the graphs on a
        given number of vertices
      * generateRandomGraphs -- generates random
        graphs on a given number of vertices
      * generateRandomRegularGraphs, --
        generates random regular graphs on a given number of vertices
      * graph6ToSparse6 -- converts a Graph6 string to
        a Sparse6 string
      * graphComplement -- computes the complement of a
        graph
      * graphToString -- converts a graph to a string in
        the Graph6 format
      * isPlanar -- determines if a given graph is planar
      * neighborhoodComplements -- complements
        the neighborhood for each vertex, individually
      * newEdges -- replaces disjoint pairs of edges by
        disjoint pairs of two-chains
      * onlyPlanar -- removes non-planar graphs from a list
      * relabelBipartite -- relabels a bipartite graph
        so all vertices of a given class are contiguous
      * relabelGraph -- applies a vertex invariant based
        refinement to a graph
      * removeEdges -- creates a list of graphs obtained by
        removing one edge from the given graph in all possible ways
      * removeIsomorphs -- removes all isomorphs from a
        list of graphs
      * sparse6ToGraph6 -- converts a Sparse6 string to
        a Graph6 string
      * stringToEdgeIdeal -- converts a Sparse6 or
        Graph6 String to an edge ideal in the given polynomial ring
      * stringToGraph -- converts a Sparse6 or Graph6
        String to a Graph in the given polynomial ring
  * Methods
      * "addEdges(Graph)" -- see addEdges, -- creates a list of
        graphs obtained by adding one new edge to the given graph in all
        possible ways
      * "addEdges(List)" -- see addEdges, -- creates a list of
        graphs obtained by adding one new edge to the given graph in all
        possible ways
      * "addEdges(String)" -- see addEdges, -- creates a list
        of graphs obtained by adding one new edge to the given graph in all
        possible ways
      * "areIsomorphic(Graph,Graph)" -- see areIsomorphic,
        -- determines whether two graphs are isomorphic
      * "areIsomorphic(Graph,String)" -- see areIsomorphic,
        -- determines whether two graphs are isomorphic
      * "areIsomorphic(String,Graph)" -- see areIsomorphic,
        -- determines whether two graphs are isomorphic
      * "areIsomorphic(String,String)" -- see areIsomorphic,
        -- determines whether two graphs are isomorphic
      * "Graph == Graph" -- see areIsomorphic, --
        determines whether two graphs are isomorphic
      * "Graph == String" -- see areIsomorphic, --
        determines whether two graphs are isomorphic
      * "String == Graph" -- see areIsomorphic, --
        determines whether two graphs are isomorphic
      * "buildGraphFilter(HashTable)" -- see buildGraphFilter,
        -- creates the appropriate filter string for use with
        filterGraphs and countGraphs
      * "buildGraphFilter(List)" -- see buildGraphFilter,
        -- creates the appropriate filter string for use with
        filterGraphs and countGraphs
      * "countGraphs(List,HashTable)" -- see countGraphs, --
        counts the number of graphs in the list with given properties
      * "countGraphs(List,List)" -- see countGraphs, --
        counts the number of graphs in the list with given properties
      * "countGraphs(List,String)" -- see countGraphs, --
        counts the number of graphs in the list with given properties
      * "filterGraphs(List,HashTable)" -- see filterGraphs,
        -- filters (i.e., selects) graphs in a list for given properties
      * "filterGraphs(List,List)" -- see filterGraphs, --
        filters (i.e., selects) graphs in a list for given properties
      * "filterGraphs(List,String)" -- see filterGraphs, --
        filters (i.e., selects) graphs in a list for given properties
      * "generateBipartiteGraphs(PolynomialRing)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateBipartiteGraphs(PolynomialRing,ZZ)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ,ZZ)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateBipartiteGraphs(ZZ)" -- see generateBipartiteGraphs,
        -- generates the bipartite graphs with a given
        bipartition
      * "generateBipartiteGraphs(ZZ,ZZ)" -- see generateBipartiteGraphs,
        -- generates the bipartite graphs with a given
        bipartition
      * "generateBipartiteGraphs(ZZ,ZZ,ZZ)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateBipartiteGraphs(ZZ,ZZ,ZZ,ZZ)" -- see
        generateBipartiteGraphs, -- generates the
        bipartite graphs with a given bipartition
      * "generateGraphs(PolynomialRing)" -- see generateGraphs,
        -- generates the graphs on a given number of vertices
      * "generateGraphs(PolynomialRing,ZZ)" -- see generateGraphs,
        -- generates the graphs on a given number of vertices
      * "generateGraphs(PolynomialRing,ZZ,ZZ)" -- see generateGraphs,
        -- generates the graphs on a given number of vertices
      * "generateGraphs(ZZ)" -- see generateGraphs, --
        generates the graphs on a given number of vertices
      * "generateGraphs(ZZ,ZZ)" -- see generateGraphs, --
        generates the graphs on a given number of vertices
      * "generateGraphs(ZZ,ZZ,ZZ)" -- see generateGraphs,
        -- generates the graphs on a given number of vertices
      * "generateRandomGraphs(PolynomialRing,ZZ)" -- see
        generateRandomGraphs, -- generates random graphs
        on a given number of vertices
      * "generateRandomGraphs(PolynomialRing,ZZ,QQ)" -- see
        generateRandomGraphs, -- generates random graphs
        on a given number of vertices
      * "generateRandomGraphs(PolynomialRing,ZZ,RR)" -- see
        generateRandomGraphs, -- generates random graphs
        on a given number of vertices
      * "generateRandomGraphs(PolynomialRing,ZZ,ZZ)" -- see
        generateRandomGraphs, -- generates random graphs
        on a given number of vertices
      * "generateRandomGraphs(ZZ,ZZ)" -- see generateRandomGraphs,
        -- generates random graphs on a given number of
        vertices
      * "generateRandomGraphs(ZZ,ZZ,QQ)" -- see generateRandomGraphs,
        -- generates random graphs on a given number of
        vertices
      * "generateRandomGraphs(ZZ,ZZ,RR)" -- see generateRandomGraphs,
        -- generates random graphs on a given number of
        vertices
      * "generateRandomGraphs(ZZ,ZZ,ZZ)" -- see generateRandomGraphs,
        -- generates random graphs on a given number of
        vertices
      * "generateRandomRegularGraphs(PolynomialRing,ZZ,ZZ)" -- see
        generateRandomRegularGraphs, -- generates
        random regular graphs on a given number of vertices
      * "generateRandomRegularGraphs(ZZ,ZZ,ZZ)" -- see
        generateRandomRegularGraphs, -- generates
        random regular graphs on a given number of vertices
      * "graph6ToSparse6(String)" -- see graph6ToSparse6,
        -- converts a Graph6 string to a Sparse6 string
      * "graphComplement(Graph)" -- see graphComplement,
        -- computes the complement of a graph
      * "graphComplement(List)" -- see graphComplement,
        -- computes the complement of a graph
      * "graphComplement(String)" -- see graphComplement,
        -- computes the complement of a graph
      * "graphToString(Graph)" -- see graphToString, --
        converts a graph to a string in the Graph6 format
      * "graphToString(Ideal)" -- see graphToString, --
        converts a graph to a string in the Graph6 format
      * "graphToString(List,ZZ)" -- see graphToString, --
        converts a graph to a string in the Graph6 format
      * "graphToString(MonomialIdeal)" -- see graphToString,
        -- converts a graph to a string in the Graph6 format
      * "graphToString(String)" -- see graphToString, --
        converts a graph to a string in the Graph6 format
      * "isPlanar(Graph)" -- see isPlanar, -- determines if a
        given graph is planar
      * "isPlanar(String)" -- see isPlanar, -- determines if a
        given graph is planar
      * "neighborhoodComplements(Graph)" -- see neighborhoodComplements,
        -- complements the neighborhood for each
        vertex, individually
      * "neighborhoodComplements(List)" -- see neighborhoodComplements,
        -- complements the neighborhood for each
        vertex, individually
      * "neighborhoodComplements(String)" -- see neighborhoodComplements,
        -- complements the neighborhood for each
        vertex, individually
      * "newEdges(Graph,PolynomialRing)" -- see newEdges, --
        replaces disjoint pairs of edges by disjoint pairs of two-chains
      * "newEdges(List)" -- see newEdges, -- replaces disjoint
        pairs of edges by disjoint pairs of two-chains
      * "newEdges(String)" -- see newEdges, -- replaces
        disjoint pairs of edges by disjoint pairs of two-chains
      * "onlyPlanar(List)" -- see onlyPlanar, -- removes
        non-planar graphs from a list
      * "onlyPlanar(List,Boolean)" -- see onlyPlanar, --
        removes non-planar graphs from a list
      * "relabelBipartite(Graph)" -- see relabelBipartite,
        -- relabels a bipartite graph so all vertices of a
        given class are contiguous
      * "relabelBipartite(List)" -- see relabelBipartite,
        -- relabels a bipartite graph so all vertices of a
        given class are contiguous
      * "relabelBipartite(String)" -- see relabelBipartite,
        -- relabels a bipartite graph so all vertices of a
        given class are contiguous
      * "relabelGraph(Graph)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(Graph,ZZ)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(Graph,ZZ,ZZ)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(List)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(List,ZZ)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(List,ZZ,ZZ)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(String)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(String,ZZ)" -- see relabelGraph, --
        applies a vertex invariant based refinement to a graph
      * "relabelGraph(String,ZZ,ZZ)" -- see relabelGraph,
        -- applies a vertex invariant based refinement to a graph
      * "removeEdges(Graph)" -- see removeEdges, -- creates
        a list of graphs obtained by removing one edge from the given graph in
        all possible ways
      * "removeEdges(List)" -- see removeEdges, -- creates a
        list of graphs obtained by removing one edge from the given graph in
        all possible ways
      * "removeEdges(String)" -- see removeEdges, -- creates
        a list of graphs obtained by removing one edge from the given graph in
        all possible ways
      * "removeIsomorphs(List)" -- see removeIsomorphs,
        -- removes all isomorphs from a list of graphs
      * "sparse6ToGraph6(String)" -- see sparse6ToGraph6,
        -- converts a Sparse6 string to a Graph6 string
      * "stringToEdgeIdeal(String,PolynomialRing)" -- see
        stringToEdgeIdeal, -- converts a Sparse6 or Graph6
        String to an edge ideal in the given polynomial ring
      * "stringToGraph(String,PolynomialRing)" -- see stringToGraph,
        -- converts a Sparse6 or Graph6 String to a Graph in the
        given polynomial ring
  * Symbols

For the programmer
==================

The object Nauty, is a package (Macaulay2Doc).

addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
************************************************************************************************************

Synopsis
========

  * Usage:
        Ll = addEdges L
        Lg = addEdges G
        Ls = addEdges S
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * S, a string (Macaulay2Doc), which describes a graph in
        Graph6 or Sparse6 format
      * G, a graph (EdgeIdeals),
  * Optional inputs (Macaulay2Doc),:
      * MaxDegree => an integer (Macaulay2Doc), default value null,
        the maximum degree allowable for any vertex in the output graphs
      * NoNew3Cycles => a Boolean value (Macaulay2Doc), default
        value false, whether graphs with new 3-cycles are allowed
      * NoNew4Cycles => a Boolean value (Macaulay2Doc), default
        value false, whether graphs with new 4-cycles are allowed
      * NoNew5Cycles => a Boolean value (Macaulay2Doc), default
        value false, whether graphs with new 5-cycles are allowed
      * NoNewOddCycles => a Boolean value (Macaulay2Doc),
        default value false, whether graphs with new odd-cycles are allowed
      * NoNewSmallCycles => an integer (Macaulay2Doc), default value
        null, an upper bound on cycles which are not allowed
  * Outputs:
      * Ll, a list (Macaulay2Doc), the list of graphs obtained from
        the graphs in $L$ in Graph6 format
      * Lg, a list (Macaulay2Doc), the list of graphs obtained from
        $G$
      * Ls, a list (Macaulay2Doc), the list of strings (in Graph6
        format) obtained from $S$

Description
===========

Simply creates a list, in the same format as the input, of all possible graphs
obtained by adding one new edge to the input graph.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : addEdges cycle R                                                        |
|                                                                             |
|o2 = {Graph{edges => {{a, b}, {a, c}, {b, c}, {c, d}, {a, e}, {d, e}}},      |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e}                                      |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {a, d}, {c, d}, {a, e}, {d, e}}},       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {b, d}, {c, d}, {a, e}, {d, e}}},       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}, {b, e}, {d, e}}},       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}, {c, e}, {d, e}}}}       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

If the List input format is used, then one should use care as the list may
contain isomorphic pairs.

See also
========

  * removeEdges -- creates a list of graphs obtained by
    removing one edge from the given graph in all possible ways

Ways to use addEdges :
======================

  * "addEdges(Graph)"
  * "addEdges(List)"
  * "addEdges(String)"

For the programmer
==================

The object addEdges, is a method function with options (Macaulay2Doc).

areIsomorphic -- determines whether two graphs are isomorphic
*************************************************************

Synopsis
========

  * Usage:
        b = areIsomorphic(G, H)
        G == H
        b = areIsomorphic(S, T)
        b = areIsomorphic(S, H)
        S == H
        b = areIsomorphic(G, T)
        G == T
  * Inputs:
      * G, a graph (EdgeIdeals),
      * H, a graph (EdgeIdeals),
      * S, a string (Macaulay2Doc),
      * T, a string (Macaulay2Doc),
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), whether the two
        graphs are isomorphic

Description
===========

A very efficient method for determining whether two graphs (of the same format)
are isomorphic.

+------------------------------------------------------------+
|i1 : R = QQ[a..e];                                          |
+------------------------------------------------------------+
|i2 : areIsomorphic(cycle R, graph {a*c, c*e, e*b, b*d, d*a})|
|                                                            |
|o2 = true                                                   |
+------------------------------------------------------------+
|i3 : areIsomorphic(cycle R, completeGraph R)                |
|                                                            |
|o3 = false                                                  |
+------------------------------------------------------------+
|i4 : cycle R == "Dhc"                                       |
|                                                            |
|o4 = true                                                   |
+------------------------------------------------------------+

See also
========

  * Example_colon_ Checking for isomorphic graphs
  * removeIsomorphs -- removes all isomorphs from a
    list of graphs

Ways to use areIsomorphic :
===========================

  * "areIsomorphic(Graph,Graph)"
  * "areIsomorphic(Graph,String)"
  * "areIsomorphic(String,Graph)"
  * "areIsomorphic(String,String)"

For the programmer
==================

The object areIsomorphic, is a method function (Macaulay2Doc).

buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
***************************************************************************************************

Synopsis
========

  * Usage:
        s = buildGraphFilter h
        s = buildGraphFilter l
  * Inputs:
      * h, a hash table (Macaulay2Doc), which describes the
        properties desired in filtering
      * l, a list (Macaulay2Doc), which describes the properties
        desired in filtering
  * Outputs:
      * s, a string (Macaulay2Doc), which can be used with
        filterGraphs, and countGraphs,

Description
===========

The filterGraphs, and countGraphs,
methods both can use a tremendous number of constraints which are described by
a rather tersely encoded string.  This method builds that string given
information in the HashTable (Macaulay2Doc), $h$ or the
List (Macaulay2Doc), $l$.  Any keys which do not exist are simply ignored
and any values which are not valid (e.g., exactly $-3$ vertices) are also
ignored.

The values can either be Boolean (Macaulay2Doc), or in ZZ (Macaulay2Doc).
See Boolean (Macaulay2Doc), values are treated
exactly as expected.  Numerical values are more complicated; we use an example
to illustrate how numerical values can be used, but note that this usage works
for all numerically valued keys.

The key NumEdges restricts to a specific number of edges in the graph.  If the
value is the integer $n$, then only graphs with exactly $n$ edges are returned.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : L = {graph {a*b}, graph {a*b, b*c}, graph {a*b, b*c, c*d}, graph {a*b,  |
|-----------------------------------------------------------------------------|
|b*c, c*d, d*e}};                                                             |
+-----------------------------------------------------------------------------+
|i3 : s = buildGraphFilter {"NumEdges" => 3};                                 |
+-----------------------------------------------------------------------------+
|i4 : filterGraphs(L, s)                                                      |
|                                                                             |
|o4 = {Graph{edges => {{a, b}, {b, c}, {c, d}}}}                              |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e, f}                                   |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+

If the value is the Sequence (Macaulay2Doc), $(m,n)$, then all
graphs with at least $m$ and at most $n$ edges are returned.

+-----------------------------------------------------------------------------+
|i5 : s = buildGraphFilter {"NumEdges" => (2,3)};                             |
+-----------------------------------------------------------------------------+
|i6 : filterGraphs(L, s)                                                      |
|                                                                             |
|o6 = {Graph{edges => {{a, b}, {b, c}}     }, Graph{edges => {{a, b}, {b,     |
|            ring => R                              ring => R                 |
|            vertices => {a, b, c, d, e, f}         vertices => {a, b, c,     |
|     ------------------------------------------------------------------------|
|     c}, {c, d}}}}                                                           |
|                                                                             |
|     d, e, f}                                                                |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+

If the value is the Sequence (Macaulay2Doc), $(,n)$, then all
graphs with at most $n$ edges are returned.

+-----------------------------------------------------------------------------+
|i7 : s = buildGraphFilter {"NumEdges" => (,3)};                              |
+-----------------------------------------------------------------------------+
|i8 : filterGraphs(L, s)                                                      |
|                                                                             |
|o8 = {Graph{edges => {{a, b}}             }, Graph{edges => {{a, b}, {b,     |
|            ring => R                              ring => R                 |
|            vertices => {a, b, c, d, e, f}         vertices => {a, b, c,     |
|     ------------------------------------------------------------------------|
|     c}}     }, Graph{edges => {{a, b}, {b, c}, {c, d}}}}                    |
|                      ring => R                                              |
|     d, e, f}         vertices => {a, b, c, d, e, f}                         |
|                                                                             |
|o8 : List                                                                    |
+-----------------------------------------------------------------------------+

If the value is the Sequence (Macaulay2Doc), $(m,)$, then all
graphs with at least $m$ edges are returned.

+-----------------------------------------------------------------------------+
|i9 : s = buildGraphFilter {"NumEdges" => (2,)};                              |
+-----------------------------------------------------------------------------+
|i10 : filterGraphs(L, s)                                                     |
|                                                                             |
|o10 = {Graph{edges => {{a, b}, {b, c}}     }, Graph{edges => {{a, b}, {b,    |
|             ring => R                              ring => R                |
|             vertices => {a, b, c, d, e, f}         vertices => {a, b, c,    |
|      -----------------------------------------------------------------------|
|      c}, {c, d}}}, Graph{edges => {{a, b}, {b, c}, {c, d}, {d, e}}}}        |
|                          ring => R                                          |
|      d, e, f}            vertices => {a, b, c, d, e, f}                     |
|                                                                             |
|o10 : List                                                                   |
+-----------------------------------------------------------------------------+

Moreover, the associated key NegateNumEdges, if true, causes the opposite to
occur.

+--------------------------------------------------------------------------+
|i11 : s = buildGraphFilter {"NumEdges" => (2,), "NegateNumEdges" => true};|
+--------------------------------------------------------------------------+
|i12 : filterGraphs(L, s)                                                  |
|                                                                          |
|o12 = {Graph{edges => {{a, b}}             }}                             |
|             ring => R                                                    |
|             vertices => {a, b, c, d, e, f}                               |
|                                                                          |
|o12 : List                                                                |
+--------------------------------------------------------------------------+

The following are the boolean options: "Regular", "Bipartite", "Eulerian",
"VertexTransitive".

The following are the numerical options (recall all have the associate "Negate"
option): "NumVertices", "NumEdges", "MinDegree", "MaxDegree", "Radius",
"Diameter", "Girth", "NumCycles", "NumTriangles", "GroupSize", "Orbits",
"FixedPoints", "Connectivity", "MinCommonNbrsAdj", "MaxCommonNbrsAdj",
"MinCommonNbrsNonAdj", "MaxCommonNbrsNonAdj".

Caveat
======

Connectivity only works for the values $0, 1, 2$ and uses the following
definition of $k$-connectivity. A graph is $k$-connected if $k$ is the minimum
size of a set of vertices whose complement is not connected.

Thus, in order to filter for connected graphs, one must use {"Connectivity" =>
0, "NegateConnectivity" => true}.

NumCycles can only be used with graphs on at most $n$ vertices, where $n$ is
the number of bits for which nauty was compiled, typically $32$ or $64$.

See also
========

  * countGraphs -- counts the number of graphs in the list
    with given properties
  * Example_colon_ Generating and filtering graphs
  * filterGraphs -- filters (i.e., selects) graphs in a
    list for given properties

Ways to use buildGraphFilter :
==============================

  * "buildGraphFilter(HashTable)"
  * "buildGraphFilter(List)"

For the programmer
==================

The object buildGraphFilter, is a method function (Macaulay2Doc).

Comparison of Graph6 and Sparse6 formats
****************************************

The program nauty uses two string-based formats for storing graphs:  Graph6 and
Sparse6 format. Each format has benefits and drawbacks.

In particular, the length of a Graph6 string representation of a graph depends
only on the number of vertices. However, this also means that graphs with few
edges take as much space as graphs with many edges. On the other hand, Sparse6
is a variable length format which can use dramatically less space for sparse
graphs but can have a much larger storage size for dense graphs.

Consider the 26-cycle, a rather sparse graph.  Notice how Sparse6 format takes
half the space of the Graph6 format.

+------------------------------------+
|i1 : R = QQ[a..z];                  |
+------------------------------------+
|i2 : g6 = graphToString cycle R; #g6|
|                                    |
|o3 = 56                             |
+------------------------------------+
|i4 : s6 = graph6ToSparse6 g6; #s6   |
|                                    |
|o5 = 28                             |
+------------------------------------+

However, the complete graph, which is as dense as possible, on 26 vertices is
the opposite: the Sparse6 format takes nearly six times the space of the Graph6
format.

+--------------------------------------------+
|i6 : g6 = graphToString completeGraph R; #g6|
|                                            |
|o7 = 56                                     |
+--------------------------------------------+
|i8 : s6 = graph6ToSparse6 g6; #s6           |
|                                            |
|o9 = 327                                    |
+--------------------------------------------+

See also
========

  * graph6ToSparse6 -- converts a Graph6 string to a
    Sparse6 string
  * graphToString -- converts a graph to a string in the
    Graph6 format
  * sparse6ToGraph6 -- converts a Sparse6 string to a
    Graph6 string
  * stringToGraph -- converts a Sparse6 or Graph6 String
    to a Graph in the given polynomial ring

countGraphs -- counts the number of graphs in the list with given properties
****************************************************************************

Synopsis
========

  * Usage:
        n = countGraphs(L, s)
        n = countGraphs(L, h)
        n = countGraphs(L, l)
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs (mixed formats
        are allowed)
      * s, a string (Macaulay2Doc), a filter, as generated by
        buildGraphFilter,
      * h, a hash table (Macaulay2Doc), a filter, as used by
        buildGraphFilter,
      * l, a list (Macaulay2Doc), a filter, as used by
        buildGraphFilter,
  * Outputs:
      * n, an integer (Macaulay2Doc), the number of graphs in $L$
        satisfying the filter

Description
===========

Counts the number of graphs in a list that satisfy certain restraints as given
in the filter (see buildGraphFilter).  Notice that the
input list can be graphs represented as instances of the class Graph (EdgeIdeals),
or in a nauty-based String (Macaulay2Doc),
format.

For example, we can count the number of connected graphs on five vertices.

+------------------------------------------------------------------------+
|i1 : L = generateGraphs 5;                                              |
+------------------------------------------------------------------------+
|i2 : countGraphs(L, {"Connectivity" => 0, "NegateConnectivity" => true})|
|                                                                        |
|o2 = 21                                                                 |
+------------------------------------------------------------------------+

See also
========

  * buildGraphFilter -- creates the appropriate filter
    string for use with filterGraphs and countGraphs
  * filterGraphs -- filters (i.e., selects) graphs in a
    list for given properties

Ways to use countGraphs :
=========================

  * "countGraphs(List,HashTable)"
  * "countGraphs(List,List)"
  * "countGraphs(List,String)"

For the programmer
==================

The object countGraphs, is a method function (Macaulay2Doc).

Example: Checking for isomorphic graphs
***************************************

The main use of nauty is to determine if two graphs are isomorphic.  We can
demonstrate it for two given graphs with the method areIsomorphic.

+--------------------------------------------------------+
|i1 : R = QQ[a..e];                                      |
+--------------------------------------------------------+
|i2 : G = graph {{a, c}, {c, e}, {e, b}, {b, d}, {d, a}};|
+--------------------------------------------------------+
|i3 : areIsomorphic(cycle R, G)                          |
|                                                        |
|o3 = true                                               |
+--------------------------------------------------------+

Further, a list of graphs can be reduced to only graphs that are non-isomorphic
with the method removeIsomorphs.  Here we create a list
of 120 different labellings of the 5-cycle and use nauty to verify they are
indeed all the same.

+-----------------------------------------------------------------------------+
|i4 : L = apply(permutations gens R, P -> graphToString graph apply(5, i->    |
|-----------------------------------------------------------------------------|
|{P_i, P_((i+1)%5)}));                                                        |
+-----------------------------------------------------------------------------+
|i5 : N = removeIsomorphs L                                                   |
|                                                                             |
|o5 = {Dhc}                                                                   |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+
|i6 : stringToGraph(first N, R)                                               |
|                                                                             |
|o6 = Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}                |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|                                                                             |
|o6 : Graph                                                                   |
+-----------------------------------------------------------------------------+

See also
========

  * areIsomorphic -- determines whether two graphs are
    isomorphic
  * removeIsomorphs -- removes all isomorphs from a
    list of graphs

Example: Generating and filtering graphs
****************************************

The method generateGraphs, can generate all graphs with a
given property. For example, we can verify the number of graphs on a given
number of vertices. Compare these results to the Online Encyclopedia of Integer
Sequences (http://oeis.org/), where the sequence name is also its OEIS
identifier.

+---------------------------------------------------------------------+
|i1 : A000088 = apply(1..9, n -> #generateGraphs n)                   |
|                                                                     |
|o1 = (1, 2, 4, 11, 34, 156, 1044, 12346, 274668)                     |
|                                                                     |
|o1 : Sequence                                                        |
+---------------------------------------------------------------------+
|i2 : B = apply(1..12, n -> generateGraphs(n, OnlyBipartite => true));|
+---------------------------------------------------------------------+

Further, we can use filterGraphs, to refine the set of
generate graphs for deeper properties.

Here we filter for forests, then for trees only,

+-----------------------------------------------------------------------------+
|i3 : forestsOnly = buildGraphFilter {"NumCycles" => 0};                      |
+-----------------------------------------------------------------------------+
|i4 : A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly))        |
|                                                                             |
|o4 = (1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601)                       |
|                                                                             |
|o4 : Sequence                                                                |
+-----------------------------------------------------------------------------+
|i5 : treesOnly = buildGraphFilter {"NumCycles" => 0, "Connectivity" => 0,    |
|-----------------------------------------------------------------------------|
|"NegateConnectivity" => true};                                               |
+-----------------------------------------------------------------------------+
|i6 : A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly))          |
|                                                                             |
|o6 = (1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551)                           |
|                                                                             |
|o6 : Sequence                                                                |
+-----------------------------------------------------------------------------+

Moreover, we can generate random graphs using the generateRandomGraphs,
method.  Here we verify a result of Erdos and R\'enyi
(see http://www.ams.org/mathscinet-getitem?mr=120167), which says that a random
graph on $n$ vertices with edge probability $(1+\epsilon)$log$(n)/n$ is almost
always connected while a graph with edge probability $(1-\epsilon)$log$(n)/n$
is almost never connected, at least as $n$ tends to infinity.

+-----------------------------------------------------------------------------+
|i7 : connected = buildGraphFilter {"Connectivity" => 0, "NegateConnectivity" |
|-----------------------------------------------------------------------------|
|=> true};                                                                    |
+-----------------------------------------------------------------------------+
|i8 : prob = n -> log(n)/n;                                                   |
+-----------------------------------------------------------------------------+
|i9 : apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n))|
|                                                                             |
|o9 = (75, 87, 92, 94, 91, 96, 92, 94, 95, 97, 95, 96, 96, 97, 98, 98, 100,   |
|     ------------------------------------------------------------------------|
|     100, 97, 100, 98, 99, 98, 98, 98, 98, 100, 96, 97)                      |
|                                                                             |
|o9 : Sequence                                                                |
|-----------------------------------------------------------------------------|
|, connected))                                                                |
+-----------------------------------------------------------------------------+
|i10 : apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2|
|                                                                             |
|o10 = (21, 9, 5, 3, 4, 2, 0, 2, 2, 0, 1, 1, 0, 2, 1, 1, 2, 0, 1, 1, 1, 3, 0, |
|      -----------------------------------------------------------------------|
|      0, 2, 0, 0, 0, 0)                                                      |
|                                                                             |
|o10 : Sequence                                                               |
|-----------------------------------------------------------------------------|
|), connected))                                                               |
+-----------------------------------------------------------------------------+

See also
========

  * buildGraphFilter -- creates the appropriate filter
    string for use with filterGraphs and countGraphs
  * filterGraphs -- filters (i.e., selects) graphs in a
    list for given properties
  * generateGraphs -- generates the graphs on a given
    number of vertices
  * generateRandomGraphs -- generates random
    graphs on a given number of vertices

filterGraphs -- filters (i.e., selects) graphs in a list for given properties
*****************************************************************************

Synopsis
========

  * Usage:
        F = filterGraphs(L, s)
        F = filterGraphs(L, h)
        F = filterGraphs(L, l)
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs (mixed formats
        are allowed)
      * s, a string (Macaulay2Doc), a filter, as generated by
        buildGraphFilter,
      * h, a hash table (Macaulay2Doc), a filter, as used by
        buildGraphFilter,
      * l, a list (Macaulay2Doc), a filter, as used by
        buildGraphFilter,
  * Outputs:
      * F, a list (Macaulay2Doc), the graphs in $L$ satisfying the
        filter

Description
===========

Filters the graphs in a list which satisfy certain restraints as given in the
filter (see buildGraphFilter).  Notice that the input
list can be graphs represented as instances of the class Graph (EdgeIdeals),
or in a nauty-based String (Macaulay2Doc),
format.

For example, we can filter for the connected graphs on five vertices.

+-----------------------------------------------------------------------------+
|i1 : L = generateGraphs 5;                                                   |
+-----------------------------------------------------------------------------+
|i2 : filterGraphs(L, {"Connectivity" => 0, "NegateConnectivity" => true})    |
|                                                                             |
|o2 = {D?{, DCw, DC{, DEw, DEk, DE{, DFw, DF{, DQo, DQw, DQ{, DUW, DUw, DU{,  |
|     ------------------------------------------------------------------------|
|     DTw, DT{, DV{, D]w, D]{, D^{, D~{}                                      |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * buildGraphFilter -- creates the appropriate filter
    string for use with filterGraphs and countGraphs
  * countGraphs -- counts the number of graphs in the list
    with given properties
  * Example_colon_ Generating and filtering graphs

Ways to use filterGraphs :
==========================

  * "filterGraphs(List,HashTable)"
  * "filterGraphs(List,List)"
  * "filterGraphs(List,String)"

For the programmer
==================

The object filterGraphs, is a method function (Macaulay2Doc).

generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
**********************************************************************************

Synopsis
========

  * Usage:
        G = generateBipartiteGraphs n
        G = generateBipartiteGraphs(n, m)
        G = generateBipartiteGraphs(n, m, e)
        G = generateBipartiteGraphs(n, m, le, ue)
        G = generateBipartiteGraphs R
        G = generateBipartiteGraphs(R, m)
        G = generateBipartiteGraphs(R, m, e)
        G = generateBipartiteGraphs(R, m, le, ue)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), the ring in
        which the graphs will be created
      * n, an integer (Macaulay2Doc), the number of vertices of the
        graphs, must be positive (see caveat)
      * m, an integer (Macaulay2Doc), the number of vertices in the
        first class of the bipartition
      * e, an integer (Macaulay2Doc), the number of edges in the
        graphs
      * le, an integer (Macaulay2Doc), a lower bound on the number of
        edges in the graphs
      * ue, an integer (Macaulay2Doc), an upper bound on the number
        of edges in the graphs
  * Optional inputs (Macaulay2Doc),:
      * Class2Degree2 => a Boolean value (Macaulay2Doc), default
        value false, whether the vertices in the second class must have at
        least two neighbors of degree at least 2
      * Class2DistinctNeighborhoods => a Boolean value (Macaulay2Doc),
        default value false, whether all vertices in
        the second class must have distinct neighborhoods
      * Class2MaxCommonNeighbors => an integer (Macaulay2Doc),
        default value null, an upper bound on the number of common neighbors of
        vertices in the second class
      * MaxDegree => an integer (Macaulay2Doc), default value null,
        an upper bound on the degrees of the vertices
      * MinDegree => an integer (Macaulay2Doc), default value null, a
        lower bound on the degrees of the vertices
      * OnlyConnected => a Boolean value (Macaulay2Doc), default
        value false, whether to only allow connected graphs
  * Outputs:
      * G, a list (Macaulay2Doc), the bipartite graphs satisfying
        the input conditions

Description
===========

This method generates all bipartite graphs on $n$ vertices. The size of the
bipartition is specified by giving the size of one class; the other class is
determined automatically from the number of vertices.

If only one integer argument is given, then the method generates all bipartite
graphs on that number of vertices with first class of sizes $0$ to $n$.

If a PolynomialRing $R$ is supplied instead, then the number of vertices is the
number of generators.  Moreover, the strings are automatically converted to
graphs in $R$.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : generateBipartiteGraphs(R, 2)                                           |
|                                                                             |
|o2 = {Graph{edges => {}                }, Graph{edges => {{a, e}}          },|
|            ring => R                           ring => R                    |
|            vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}  |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, e}, {b, e}}  }, Graph{edges => {{a, d}, {a, e}}  }, |
|           ring => R                           ring => R                     |
|           vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}   |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, d}, {b, e}}  }, Graph{edges => {{a, d}, {a, e}, {b, |
|           ring => R                           ring => R                     |
|           vertices => {a, b, c, d, e}         vertices => {a, b, c, d, e}   |
|     ------------------------------------------------------------------------|
|     e}}}, Graph{edges => {{a, d}, {b, d}, {a, e}, {b, e}}},                 |
|                 ring => R                                                   |
|                 vertices => {a, b, c, d, e}                                 |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, c}, {a, d}, {a, e}}}, Graph{edges => {{a, c}, {a,   |
|           ring => R                                 ring => R               |
|           vertices => {a, b, c, d, e}               vertices => {a, b, c,   |
|     ------------------------------------------------------------------------|
|     d}, {a, e}, {b, e}}}, Graph{edges => {{a, c}, {b, d}, {a, e}}},         |
|                                 ring => R                                   |
|     d, e}                       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}, {a, d}, {b, d}, {a, e}, {b, e}}},               |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, c}, {b, c}, {a, d}, {b, d}, {a, e}, {b, 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
========

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

Ways to use generateBipartiteGraphs :
=====================================

  * "generateBipartiteGraphs(PolynomialRing)"
  * "generateBipartiteGraphs(PolynomialRing,ZZ)"
  * "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ)"
  * "generateBipartiteGraphs(PolynomialRing,ZZ,ZZ,ZZ)"
  * "generateBipartiteGraphs(ZZ)"
  * "generateBipartiteGraphs(ZZ,ZZ)"
  * "generateBipartiteGraphs(ZZ,ZZ,ZZ)"
  * "generateBipartiteGraphs(ZZ,ZZ,ZZ,ZZ)"

For the programmer
==================

The object generateBipartiteGraphs, is a
method function with options (Macaulay2Doc).

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

Synopsis
========

  * Usage:
        G = generateGraphs n
        G = generateGraphs(n, e)
        G = generateGraphs(n, le, ue)
        G = generateGraphs R
        G = generateGraphs(R, e)
        G = generateGraphs(R, le, ue)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), the ring in
        which the graphs will be created
      * n, an integer (Macaulay2Doc), the number of vertices of the
        graphs, must be positive (see caveat)
      * e, an integer (Macaulay2Doc), the number of edges in the
        graphs
      * le, an integer (Macaulay2Doc), a lower bound on the number of
        edges in the graphs
      * ue, an integer (Macaulay2Doc), an upper bound on the number
        of edges in the graphs
  * Optional inputs (Macaulay2Doc),:
      * MaxDegree => an integer (Macaulay2Doc), default value null,
        an upper bound on the degrees of the vertices
      * MinDegree => an integer (Macaulay2Doc), default value null, a
        lower bound on the degrees of the vertices
      * Only4CycleFree => a Boolean value (Macaulay2Doc),
        default value false, whether to only allow graphs without 4-cycles
      * OnlyBiconnected => a Boolean value (Macaulay2Doc),
        default value false, whether to only allow biconnected graphs
      * OnlyBipartite => a Boolean value (Macaulay2Doc), default
        value false, whether to only allow bipartite graphs
      * OnlyConnected => a Boolean value (Macaulay2Doc), default
        value false, whether to only allow connected graphs
      * OnlyTriangleFree => a Boolean value (Macaulay2Doc),
        default value false, whether to only allow graphs without triangles
        (3-cycles)
  * Outputs:
      * G, a list (Macaulay2Doc), the graphs satisfying the input
        conditions

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 (Macaulay2Doc), $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 (EdgeIdeals), 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
========

  * Example_colon_ Generating and filtering graphs
  * generateBipartiteGraphs -- generates the
    bipartite graphs with a given bipartition

Ways to use generateGraphs :
============================

  * "generateGraphs(PolynomialRing)"
  * "generateGraphs(PolynomialRing,ZZ)"
  * "generateGraphs(PolynomialRing,ZZ,ZZ)"
  * "generateGraphs(ZZ)"
  * "generateGraphs(ZZ,ZZ)"
  * "generateGraphs(ZZ,ZZ,ZZ)"

For the programmer
==================

The object generateGraphs, is a method function with options (Macaulay2Doc).

generateRandomGraphs -- generates random graphs on a given number of vertices
*****************************************************************************

Synopsis
========

  * Usage:
        G = generateRandomGraphs(n, num)
        G = generateRandomGraphs(n, num, pq)
        G = generateRandomGraphs(n, num, pz)
        G = generateRandomGraphs(R, num)
        G = generateRandomGraphs(R, num, pq)
        G = generateRandomGraphs(R, num, pz)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), the ring in
        which the graphs will be created
      * n, an integer (Macaulay2Doc), the number of vertices of the
        graphs, must be positive (see caveat)
      * num, an integer (Macaulay2Doc), the number of random graphs
        to generate
      * pq, a rational number (Macaulay2Doc), the edge probability
        (between 0 and 1)
      * pq, a real number (Macaulay2Doc), the edge probability
        (between 0 and 1)
      * pz, an integer (Macaulay2Doc), the reciprocal of the edge
        probability (positive)
  * Optional inputs (Macaulay2Doc),:
      * RandomSeed => an integer (Macaulay2Doc), default value null,
        the specified random seed is passed to nauty
  * Outputs:
      * G, a list (Macaulay2Doc), the randomly generated graphs

Description
===========

This method generates a specified number of random graphs with a given number
of vertices.  Note that some graphs may be isomorphic.

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

If the input $pq$ is included, then the edges are chosen to be included with
probability $pq$.  If the input $pz$ is included and is positive, then the
edges are chosen to be included with probability $1/pz$.

+-----------------------------------------------------+
|i1 : generateRandomGraphs(5, 5, RandomSeed => 314159)|
|                                                     |
|o1 = {DEK, DbO, D[O, DiO, DMg}                       |
|                                                     |
|o1 : List                                            |
+-----------------------------------------------------+
|i2 : generateRandomGraphs(5, 5)                      |
|                                                     |
|o2 = {DF{, DNo, DTw, DBk, DCS}                       |
|                                                     |
|o2 : List                                            |
+-----------------------------------------------------+
|i3 : generateRandomGraphs(5, 5, RandomSeed => 314159)|
|                                                     |
|o3 = {DEK, DbO, D[O, DiO, DMg}                       |
|                                                     |
|o3 : List                                            |
+-----------------------------------------------------+

Caveat
======

The number of vertices $n$ must be positive as nauty cannot handle graphs with
zero vertices.  Further, if the probability $pq$ is included, then it is
rounded to a precision of one-hundred millionth.

See also
========

  * Example_colon_ Generating and filtering graphs
  * generateRandomRegularGraphs, --
    generates random regular graphs on a given number of vertices

Ways to use generateRandomGraphs :
==================================

  * "generateRandomGraphs(PolynomialRing,ZZ)"
  * "generateRandomGraphs(PolynomialRing,ZZ,QQ)"
  * "generateRandomGraphs(PolynomialRing,ZZ,RR)"
  * "generateRandomGraphs(PolynomialRing,ZZ,ZZ)"
  * "generateRandomGraphs(ZZ,ZZ)"
  * "generateRandomGraphs(ZZ,ZZ,QQ)"
  * "generateRandomGraphs(ZZ,ZZ,RR)"
  * "generateRandomGraphs(ZZ,ZZ,ZZ)"

For the programmer
==================

The object generateRandomGraphs, is a method function with options (Macaulay2Doc).

generateRandomRegularGraphs -- generates random regular graphs on a given number of vertices
********************************************************************************************

Synopsis
========

  * Usage:
        G = generateRandomRegularGraphs(n, num, reg)
        G = generateRandomRegularGraphs(R, num, reg)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), the ring in
        which the graphs will be created
      * n, an integer (Macaulay2Doc), the number of vertices of the
        graphs, must be positive (see caveat)
      * num, an integer (Macaulay2Doc), the number of random graphs
        to generate
      * reg, an integer (Macaulay2Doc), the regularity of the
        generated graphs
  * Optional inputs (Macaulay2Doc),:
      * RandomSeed => an integer (Macaulay2Doc), default value null,
        the specified random seed is passed to nauty
  * Outputs:
      * G, a list (Macaulay2Doc), the randomly generated regular
        graphs

Description
===========

This method generates a specified number of random graphs on a given number of
vertices with a given regularity. Note that some graphs may be isomorphic.

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

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : generateRandomRegularGraphs(R, 3, 2)                                    |
|                                                                             |
|o2 = {Graph{edges => {{a, c}, {b, d}, {c, d}, {a, e}, {b, e}}},              |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e}                                      |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {a, d}, {c, e}, {d, e}}},               |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {a, c}, {c, d}, {b, e}, {d, 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
========

  * generateRandomGraphs -- generates random
    graphs on a given number of vertices

Ways to use generateRandomRegularGraphs :
=========================================

  * "generateRandomRegularGraphs(PolynomialRing,ZZ,ZZ)"
  * "generateRandomRegularGraphs(ZZ,ZZ,ZZ)"

For the programmer
==================

The object generateRandomRegularGraphs, is a
method function with options (Macaulay2Doc).

graph6ToSparse6 -- converts a Graph6 string to a Sparse6 string
***************************************************************

Synopsis
========

  * Usage:
        s6 = graph6ToSparse6 g6
  * Inputs:
      * g6, a string (Macaulay2Doc), a string in nauty's Graph6
        format
  * Outputs:
      * s6, a string (Macaulay2Doc), a string in nauty's Sparse6
        format

Description
===========

This method converts a graph stored in nauty's Graph6 format to a graph stored
in nauty's Sparse6 format.  For graphs with very few edges, the Sparse6 format
can use dramatically less space.  However, for graphs with many edges, the
Sparse6 format can increase the storage requirements.

+----------------------------------------+
|i1 : graph6ToSparse6 "Dhc"              |
|                                        |
|o1 = :DaY_~                             |
+----------------------------------------+
|i2 : graph6ToSparse6 "M????????????????"|
|                                        |
|o2 = :M                                 |
+----------------------------------------+

See also
========

  * Comparison of Graph6 and Sparse6 formats
  * graphToString -- converts a graph to a string in the
    Graph6 format
  * stringToEdgeIdeal -- converts a Sparse6 or Graph6
    String to an edge ideal in the given polynomial ring
  * stringToGraph -- converts a Sparse6 or Graph6 String
    to a Graph in the given polynomial ring
  * sparse6ToGraph6 -- converts a Sparse6 string to a
    Graph6 string

Ways to use graph6ToSparse6 :
=============================

  * "graph6ToSparse6(String)"

For the programmer
==================

The object graph6ToSparse6, is a method function (Macaulay2Doc).

graphComplement -- computes the complement of a graph
*****************************************************

Synopsis
========

  * Usage:
        L' = graphComplement L
        T = graphComplement S
        H = graphComplement G
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
  * Optional inputs (Macaulay2Doc),:
      * OnlyIfSmaller => a Boolean value (Macaulay2Doc), default
        value false, when true, then the smaller (fewer edges) of the graph and
        its complement are returned
  * Outputs:
      * L', a list (Macaulay2Doc), the graph complement of the
        elements of $L$ stored in Graph6 format
      * T, a string (Macaulay2Doc), the graph complement of $S$
        stored in the same format at $S$
      * H, a graph (EdgeIdeals), the graph complement of $G$

Description
===========

This method computes the graph complement of the input graph and returns the
result in the same format.

For graphs as defined in the EdgeIdeals, package, one
can use the complementGraph (EdgeIdeals), method to
achieve the same effect; however, this method provides the option of not taking
the complement if the complement has more edges than the graph itself.

+-------------------------------------------------------------+
|i1 : R = QQ[a..e];                                           |
+-------------------------------------------------------------+
|i2 : graphComplement cycle R                                 |
|                                                             |
|o2 = Graph{edges => {{a, c}, {a, d}, {b, d}, {b, e}, {c, e}}}|
|           ring => R                                         |
|           vertices => {a, b, c, d, e}                       |
|                                                             |
|o2 : Graph                                                   |
+-------------------------------------------------------------+
|i3 : graphComplement "Dhc"                                   |
|                                                             |
|o3 = DUW                                                     |
+-------------------------------------------------------------+

Batch calls can be performed considerably faster when using the List input
format.  However, care should be taken as the returned list is entirely in
Graph6 or Sparse6 format.

+-----------------------------------+
|i4 : G = generateBipartiteGraphs 7;|
+-----------------------------------+
|i5 : time graphComplement G;       |
|     -- used 0.000764588 seconds   |
+-----------------------------------+
|i6 : time (graphComplement \ G);   |
|     -- used 0.164114 seconds      |
+-----------------------------------+

See also
========

  * complementGraph (EdgeIdeals) -- returns the
    complement of a graph or hypergraph

Ways to use graphComplement :
=============================

  * "graphComplement(Graph)"
  * "graphComplement(List)"
  * "graphComplement(String)"

For the programmer
==================

The object graphComplement, is a method function with options (Macaulay2Doc).

graphToString -- converts a graph to a string in the Graph6 format
******************************************************************

Synopsis
========

  * Usage:
        S = graphToString(E, n)
        S = graphToString I
        S = graphToString G
        S = graphToString T
  * Inputs:
      * E, a list (Macaulay2Doc), a list of edge pairs
      * n, an integer (Macaulay2Doc), the number of vertices in the
        graph, must be positive (see caveat)
      * I, an ideal (Macaulay2Doc), the edge ideal of a graph
      * G, a graph (EdgeIdeals),
      * T, a string (Macaulay2Doc), a string containing a graph;
        the string automatically passes through untouched
  * Outputs:
      * S, a string (Macaulay2Doc), the graph converted to a
        Graph6 format string

Description
===========

This method converts various ways of representing a graph into nauty's Graph6
string format.  Note that if the Ideal (Macaulay2Doc), (or
MonomialIdeal (Macaulay2Doc)) passed to the method is not
squarefree and monomial, then the method may have unknown and possibly
undesired results.

In this example, all graphs are the 5-cycle.

+----------------------------------------------------------+
|i1 : graphToString({{0,1}, {1,2}, {2,3}, {3,4}, {0,4}}, 5)|
|                                                          |
|o1 = Dhc                                                  |
+----------------------------------------------------------+
|i2 : R = QQ[a..e];                                        |
+----------------------------------------------------------+
|i3 : graphToString monomialIdeal (a*c, a*d, b*d, b*e, c*e)|
|                                                          |
|o3 = DUW                                                  |
+----------------------------------------------------------+
|i4 : graphToString cycle R                                |
|                                                          |
|o4 = Dhc                                                  |
+----------------------------------------------------------+
|i5 : graphToString "Dhc"                                  |
|                                                          |
|o5 = Dhc                                                  |
+----------------------------------------------------------+

We note that if the input is a string, then the output is simply that string
returned, regardless of format or correctness.

Caveat
======

Notice that if using a List (Macaulay2Doc), and number of vertices
input to create the string, then the List (Macaulay2Doc), must have
vertices labeled $0$ to $n-1$.

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

See also
========

  * Comparison of Graph6 and Sparse6 formats
  * graph6ToSparse6 -- converts a Graph6 string to a
    Sparse6 string
  * sparse6ToGraph6 -- converts a Sparse6 string to a
    Graph6 string
  * stringToGraph -- converts a Sparse6 or Graph6 String
    to a Graph in the given polynomial ring

Ways to use graphToString :
===========================

  * "graphToString(Graph)"
  * "graphToString(Ideal)"
  * "graphToString(List,ZZ)"
  * "graphToString(MonomialIdeal)"
  * "graphToString(String)"

For the programmer
==================

The object graphToString, is a method function (Macaulay2Doc).

isPlanar -- determines if a given graph is planar
*************************************************

Synopsis
========

  * Usage:
        p = isPlanar G
        p = isPlanar S
  * Inputs:
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
  * Outputs:
      * p, a Boolean value (Macaulay2Doc), whether the given
        graph is planar

Description
===========

A graph is planar if the graph can be embedded in the plane, i.e., the vertices
can be arranged such that no edges cross except at vertices.

+-----------------------------+
|i1 : R = QQ[a..e];           |
+-----------------------------+
|i2 : isPlanar cycle R        |
|                             |
|o2 = true                    |
+-----------------------------+
|i3 : isPlanar completeGraph R|
|                             |
|o3 = false                   |
+-----------------------------+

This method uses the program planarg. The code was written by Paulette Lieby
for the Magma project and used with permission in the software nauty.

See also
========

  * onlyPlanar -- removes non-planar graphs from a list

Ways to use isPlanar :
======================

  * "isPlanar(Graph)"
  * "isPlanar(String)"

For the programmer
==================

The object isPlanar, is a method function (Macaulay2Doc).

neighborhoodComplements -- complements the neighborhood for each vertex, individually
*************************************************************************************

Synopsis
========

  * Usage:
        N' = neighborhoodComplements L
        N = neighborhoodComplements S
        N = neighborhoodComplements G
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
  * Outputs:
      * N', a list (Macaulay2Doc), containing graphs in either
        Graph6 or Sparse6 format, modified as described below
      * N, a list (Macaulay2Doc), containing graphs, in the same
        format as the input, modified as described below

Description
===========

The method creates a list of graphs, one for each vertex of the original graph
$G$.  The graph associated to a vertex $v$ of $G$ has the neighborhood of $v$
complemented.

The method does not remove isomorphs.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : neighborhoodComplements graph {a*b, a*c, b*c, c*d, d*e}                 |
|                                                                             |
|o2 = {Graph{edges => {{a, b}, {a, c}, {b, c}, {b, d}, {b, e}, {c, e}, {d,    |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e}                                      |
|     ------------------------------------------------------------------------|
|     e}}}, Graph{edges => {{a, b}, {a, c}, {b, c}, {a, d}, {a, e}, {c, e},   |
|                 ring => R                                                   |
|                 vertices => {a, b, c, d, e}                                 |
|     ------------------------------------------------------------------------|
|     {d, e}}}, Graph{edges => {{a, b}, {a, c}, {b, c}, {c, d}, {a, e}, {b,   |
|                     ring => R                                               |
|                     vertices => {a, b, c, d, e}                             |
|     ------------------------------------------------------------------------|
|     e}}}, Graph{edges => {{a, b}, {c, d}, {a, e}, {b, e}, {d, e}}},         |
|                 ring => R                                                   |
|                 vertices => {a, b, c, d, e}                                 |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {d, e}}}}       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * graphComplement -- computes the complement of a
    graph
  * neighbors (EdgeIdeals) -- returns the neighbors of a
    vertex or list of vertices

Ways to use neighborhoodComplements :
=====================================

  * "neighborhoodComplements(Graph)"
  * "neighborhoodComplements(List)"
  * "neighborhoodComplements(String)"

For the programmer
==================

The object neighborhoodComplements, is a
method function (Macaulay2Doc).

newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
****************************************************************************

Synopsis
========

  * Usage:
        N' = newEdges L
        N = newEdges S
        N = newEdges(G, R)
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
      * R, a polynomial ring (Macaulay2Doc), a ring with
        exactly two more variables than the ring of $G$
  * Outputs:
      * N', a list (Macaulay2Doc), containing graphs in either
        Graph6 or Sparse6 format, modified as described below
      * N, a list (Macaulay2Doc), a list of graphs, in the same
        format as the input, modified as described below

Description
===========

The list of "new edge" graphs are formed as follows: Let $ab$ and $cd$ be
disjoint edges of $G$.  Then the associated "new edge" graph $H$ is $G$ with
the edges $ab$ and $cd$ removed, the vertices $e$ and $f$ added, and the new
edges $ae, be, cf, df,$ and $ef$ added.

+---------------------------------------------------------------+
|i1 : R = QQ[a..d];                                             |
+---------------------------------------------------------------+
|i2 : G = graph {a*b, c*d};                                     |
+---------------------------------------------------------------+
|i3 : S = QQ[a..f];                                             |
+---------------------------------------------------------------+
|i4 : newEdges(G, S)                                            |
|                                                               |
|o4 = {Graph{edges => {{a, e}, {b, e}, {c, f}, {d, f}, {e, f}}}}|
|            ring => S                                          |
|            vertices => {a, b, c, d, e, f}                     |
|                                                               |
|o4 : List                                                      |
+---------------------------------------------------------------+

If the List input format is used, then one should use care as the list may
contain isomorphic pairs.

Ways to use newEdges :
======================

  * "newEdges(Graph,PolynomialRing)"
  * "newEdges(List)"
  * "newEdges(String)"

For the programmer
==================

The object newEdges, is a method function (Macaulay2Doc).

onlyPlanar -- removes non-planar graphs from a list
***************************************************

Synopsis
========

  * Usage:
        P = onlyPlanar L
        P = onlyPlanar(L, non)
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * non, a Boolean value (Macaulay2Doc), whether to return
        non-planar graphs
  * Outputs:
      * P, a list (Macaulay2Doc), containing the planar graphs of
        $L$ in Graph6 or Sparse6 format

Description
===========

A graph is planar if the graph can be embedded in the plane, i.e., the vertices
can be arranged such that no edges cross except at vertices.

The only non-planar graph on five vertices is the complete graph.

+-------------------------------------------+
|i1 : R = QQ[a..e];                         |
+-------------------------------------------+
|i2 : K5 = completeGraph R;                 |
+-------------------------------------------+
|i3 : P = onlyPlanar(generateGraphs 5, true)|
|                                           |
|o3 = {D~{}                                 |
|                                           |
|o3 : List                                  |
+-------------------------------------------+
|i4 : areIsomorphic(first P, K5)            |
|                                           |
|o4 = true                                  |
+-------------------------------------------+

This method uses the program planarg. The code was written by Paulette Lieby
for the Magma project and used with permission in the software nauty.

See also
========

  * isPlanar -- determines if a given graph is planar

Ways to use onlyPlanar :
========================

  * "onlyPlanar(List)"
  * "onlyPlanar(List,Boolean)"

For the programmer
==================

The object onlyPlanar, is a method function (Macaulay2Doc).

relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
**********************************************************************************************

Synopsis
========

  * Usage:
        L' = relabelBipartite L
        T = relabelBipartite S
        H = relabelBipartite G
  * Inputs:
      * L, a list (Macaulay2Doc), a list of bipartite graphs in
        various formats
      * S, a string (Macaulay2Doc), a bipartite graph encoded in
        either Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals), a bipartite graph
  * Outputs:
      * L', a list (Macaulay2Doc), a list of graphs isomorphic to
        $S$
      * T, a string (Macaulay2Doc), a graph isomorphic to $S$
        encoded in either Sparse6 or Graph6 format
      * H, a graph (EdgeIdeals), a graph isomorphic to $G$

Description
===========

A bipartite graph can be labeled so all vertices of a given class are
contiguous.  This method does precisely that to a bipartite graph.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = graph flatten apply({a,c,e}, v->v*{b,d,f})                          |
|                                                                             |
|o2 = Graph{edges => {{a, b}, {b, c}, {a, d}, {c, d}, {b, e}, {d, e}, {a, f}, |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e, f}                                    |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|{c, f}, {e, f}}}                                                             |
+-----------------------------------------------------------------------------+
|i3 : relabelBipartite G                                                      |
|                                                                             |
|o3 = Graph{edges => {{a, d}, {b, d}, {c, d}, {a, e}, {b, e}, {c, e}, {a, f}, |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e, f}                                    |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|{b, f}, {c, f}}}                                                             |
+-----------------------------------------------------------------------------+

If any of the inputs are not bipartite graphs, then the method throws an error.

See also
========

  * relabelGraph -- applies a vertex invariant based
    refinement to a graph

Ways to use relabelBipartite :
==============================

  * "relabelBipartite(Graph)"
  * "relabelBipartite(List)"
  * "relabelBipartite(String)"

For the programmer
==================

The object relabelBipartite, is a method function (Macaulay2Doc).

relabelGraph -- applies a vertex invariant based refinement to a graph
**********************************************************************

Synopsis
========

  * Usage:
        L' = relabelGraph(L, i, a)
        L' = relabelGraph(L, i)
        L' = relabelGraph L
        T = relabelGraph(S, i, a)
        T = relabelGraph(S, i)
        T = relabelGraph S
        H = relabelGraph(G, i, a)
        H = relabelGraph(G, i)
        H = relabelGraph G
  * Inputs:
      * L, a list (Macaulay2Doc), a list of graphs in various
        formats
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
      * i, an integer (Macaulay2Doc), a choice of invariant to order
        by ($0 \leq i \leq 15$, default is $0$)
      * a, an integer (Macaulay2Doc), a non-negative argument passed
        to nauty, (default is $3$)
  * Outputs:
      * L', a list (Macaulay2Doc), a list of graphs isomorphic to
        $S$
      * T, a string (Macaulay2Doc), a graph isomorphic to $S$
        encoded in either Sparse6 or Graph6 format
      * H, a graph (EdgeIdeals), a graph isomorphic to $G$

Description
===========

This method applies one of sixteen vertex invariant based refinements to a
graph.  See the nauty documentation for a more complete description of each and
how the argument $a$ is used.

The sixteen vertex invariants are: \break \ \ \ \ $i = 0$: none,\ \ \ \ $i =
1$: twopaths,\ \ \ \ $i = 2$: adjtriang(K),\ \ \ \ $i = 3$: triples,\ \ \ \ $i
= 4$: quadruples,\ \ \ \ $i = 5$: celltrips,\ \ \ \ $i = 6$: cellquads,\ \ \ \
$i = 7$: cellquins,\ \ \ \ $i = 8$: distances(K),\ \ \ \ $i = 9$: indsets(K),\
\ \ \ $i = 10$: cliques(K),\ \ \ \ $i = 11$: cellcliq(K),\ \ \ \ $i = 12$:
cellind(K),\ \ \ \ $i = 13$: adjacencies,\ \ \ \ $i = 14$: cellfano, and\ \ \ \
$i = 15$: cellfano2.

+-------------------------------------------------------------+
|i1 : R = QQ[a..e];                                           |
+-------------------------------------------------------------+
|i2 : G = graph {a*e, e*c, c*b, b*d, d*a};                    |
+-------------------------------------------------------------+
|i3 : relabelGraph G                                          |
|                                                             |
|o3 = Graph{edges => {{a, b}, {a, c}, {b, d}, {c, e}, {d, e}}}|
|           ring => R                                         |
|           vertices => {a, b, c, d, e}                       |
|                                                             |
|o3 : Graph                                                   |
+-------------------------------------------------------------+

Note that on most small graphs, all sixteen orderings produce the same result.

See also
========

  * relabelBipartite -- relabels a bipartite graph so
    all vertices of a given class are contiguous

Ways to use relabelGraph :
==========================

  * "relabelGraph(Graph)"
  * "relabelGraph(Graph,ZZ)"
  * "relabelGraph(Graph,ZZ,ZZ)"
  * "relabelGraph(List)"
  * "relabelGraph(List,ZZ)"
  * "relabelGraph(List,ZZ,ZZ)"
  * "relabelGraph(String)"
  * "relabelGraph(String,ZZ)"
  * "relabelGraph(String,ZZ,ZZ)"

For the programmer
==================

The object relabelGraph, is a method function (Macaulay2Doc).

removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
***************************************************************************************************************

Synopsis
========

  * Usage:
        R' = removeEdges L
        R = removeEdges S
        R = removeEdges G
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs in various
        formats
      * S, a string (Macaulay2Doc), a graph encoded in either
        Sparse6 or Graph6 format
      * G, a graph (EdgeIdeals),
  * Optional inputs (Macaulay2Doc),:
      * MinDegree => an integer (Macaulay2Doc), default value null,
        the minimum degree which a returned graph can have
  * Outputs:
      * R', a list (Macaulay2Doc), a list of all graphs obtained by
        removed one edge from the given graphs; it contains graphs in Graph6 or
        Sparse6 format
      * R, a list (Macaulay2Doc), a list of all graphs obtained by
        removed one edge from the given graph; it contains graphs in the same
        format as the input

Description
===========

This method creates a list of all possible graphs obtainable from the given
graph by removing one edge.  Notice that isomorphic graphs are allowed within
the list.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : removeEdges cycle R                                                     |
|                                                                             |
|o2 = {Graph{edges => {{b, c}, {c, d}, {a, e}, {d, e}}},                      |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e}                                      |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {c, d}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {c, d}, {a, e}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {a, e}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}}}}                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|                                                                             |
|o2 : List                                                                    |
+-----------------------------------------------------------------------------+
|i3 : removeEdges graph {a*b, a*c, b*c, c*d, d*e}                             |
|                                                                             |
|o3 = {Graph{edges => {{a, c}, {b, c}, {c, d}, {d, e}}},                      |
|            ring => R                                                        |
|            vertices => {a, b, c, d, e}                                      |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {b, c}, {c, d}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {a, c}, {c, d}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {a, c}, {b, c}, {d, e}}},                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|     ------------------------------------------------------------------------|
|     Graph{edges => {{a, b}, {a, c}, {b, c}, {c, d}}}}                       |
|           ring => R                                                         |
|           vertices => {a, b, c, d, e}                                       |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

If the List input format is used, then one should use care as the list may
contain isomorphic pairs.

See also
========

  * addEdges -- creates a list of graphs obtained by adding
    one new edge to the given graph in all possible ways

Ways to use removeEdges :
=========================

  * "removeEdges(Graph)"
  * "removeEdges(List)"
  * "removeEdges(String)"

For the programmer
==================

The object removeEdges, is a method function with options (Macaulay2Doc).

removeIsomorphs -- removes all isomorphs from a list of graphs
**************************************************************

Synopsis
========

  * Usage:
        M = removeIsomorphs L
  * Inputs:
      * L, a list (Macaulay2Doc), containing graphs (mixed formats
        allowed)
  * Outputs:
      * M, a list (Macaulay2Doc), containing the sub-list of
        non-isomorphic graphs of the input list, retaining format

Description
===========

This method returns the sublist of $L$ giving all non-isomorphic graphs with
selection based on which comes first in $L$.  The format of the graph is
retained.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = {"EhEG", cycle R, completeGraph R, graph {a*d, d*b, b*e, e*c, c*f,  |
|-----------------------------------------------------------------------------|
|f*a}};                                                                       |
+-----------------------------------------------------------------------------+
|i3 : removeIsomorphs G                                                       |
|                                                                             |
|o3 = {EhEG, Graph{edges => {{a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {b, c},  |
|                  ring => R                                                  |
|                  vertices => {a, b, c, d, e, f}                             |
|     ------------------------------------------------------------------------|
|     {b, d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}, {d, e}, {d, f}, {e,     |
|     ------------------------------------------------------------------------|
|     f}}}}                                                                   |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * areIsomorphic -- determines whether two graphs are
    isomorphic
  * Example_colon_ Checking for isomorphic graphs

Ways to use removeIsomorphs :
=============================

  * "removeIsomorphs(List)"

For the programmer
==================

The object removeIsomorphs, is a method function (Macaulay2Doc).

sparse6ToGraph6 -- converts a Sparse6 string to a Graph6 string
***************************************************************

Synopsis
========

  * Usage:
        g6 = sparse6ToGraph6 s6
  * Inputs:
      * s6, a string (Macaulay2Doc), a string in nauty's Sparse6
        format
  * Outputs:
      * g6, a string (Macaulay2Doc), a string in nauty's Graph6
        format

Description
===========

This method converts a graph stored in nauty's Sparse6 format to a graph stored
in nauty's Graph6 format.  The Graph6 format has the benefit of being a
constant length dependent only on the number of vertices.

+-----------------------------+
|i1 : sparse6ToGraph6 ":DaY_~"|
|                             |
|o1 = Dhc                     |
+-----------------------------+
|i2 : sparse6ToGraph6 ":M"    |
|                             |
|o2 = M????????????????       |
+-----------------------------+

See also
========

  * Comparison of Graph6 and Sparse6 formats
  * graph6ToSparse6 -- converts a Graph6 string to a
    Sparse6 string
  * graphToString -- converts a graph to a string in the
    Graph6 format
  * stringToEdgeIdeal -- converts a Sparse6 or Graph6
    String to an edge ideal in the given polynomial ring
  * stringToGraph -- converts a Sparse6 or Graph6 String
    to a Graph in the given polynomial ring

Ways to use sparse6ToGraph6 :
=============================

  * "sparse6ToGraph6(String)"

For the programmer
==================

The object sparse6ToGraph6, is a method function (Macaulay2Doc).

stringToEdgeIdeal -- converts a Sparse6 or Graph6 String to an edge ideal in the given polynomial ring
******************************************************************************************************

Synopsis
========

  * Usage:
        I = stringToEdgeIdeal(S, R)
  * Inputs:
      * S, a string (Macaulay2Doc), a string in nauty's Sparse6
        or Graph6 format
      * R, a polynomial ring (Macaulay2Doc), a polynomial
        ring
  * Outputs:
      * I, an ideal (Macaulay2Doc), an ideal in the given
        polynomial ring

Description
===========

This method converts a Sparse6 or Graph6 string $S$ to an edge ideal $I$ in the
given polynomial ring $R$.  That is, for each edge $(a,b)$ in the graph given
by $S$, the monomial $a*b$ is added as a generator to $I$.

Note, this method requires that the number of variables of $R$ be the same as
the number of vertices of $S$.

+--------------------------------------------+
|i1 : R = QQ[a..e];                          |
+--------------------------------------------+
|i2 : stringToEdgeIdeal("Dhc", R)            |
|                                            |
|o2 = monomialIdeal (a*b, b*c, c*d, a*e, d*e)|
|                                            |
|o2 : MonomialIdeal of R                     |
+--------------------------------------------+

This method is almost always faster than converting the string to a graph and
then to an edge ideal using the edgeIdeal (EdgeIdeals), method.

See also
========

  * graphToString -- converts a graph to a string in the
    Graph6 format
  * stringToGraph -- converts a Sparse6 or Graph6 String
    to a Graph in the given polynomial ring

Ways to use stringToEdgeIdeal :
===============================

  * "stringToEdgeIdeal(String,PolynomialRing)"

For the programmer
==================

The object stringToEdgeIdeal, is a method function (Macaulay2Doc).

stringToGraph -- converts a Sparse6 or Graph6 String to a Graph in the given polynomial ring
********************************************************************************************

Synopsis
========

  * Usage:
        G = stringToEdgeIdeal(S, R)
  * Inputs:
      * S, a string (Macaulay2Doc), a string in nauty's Sparse6
        or Graph6 format
      * R, a polynomial ring (Macaulay2Doc), a polynomial
        ring
  * Outputs:
      * G, a graph (EdgeIdeals), a graph in the given polynomial
        ring

Description
===========

This method converts a Sparse6 or Graph6 string $S$ to an instance of the class
Graph, stored in $G$, with the given polynomial ring $R$.

Note, this method requires that the number of variables of $R$ be the same as
the number of vertices of $S$.

+-------------------------------------------------------------+
|i1 : R = QQ[a..e];                                           |
+-------------------------------------------------------------+
|i2 : stringToGraph("Dhc", R)                                 |
|                                                             |
|o2 = Graph{edges => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}|
|           ring => R                                         |
|           vertices => {a, b, c, d, e}                       |
|                                                             |
|o2 : Graph                                                   |
+-------------------------------------------------------------+

See also
========

  * graphToString -- converts a graph to a string in the
    Graph6 format
  * stringToEdgeIdeal -- converts a Sparse6 or Graph6
    String to an edge ideal in the given polynomial ring

Ways to use stringToGraph :
===========================

  * "stringToGraph(String,PolynomialRing)"

For the programmer
==================

The object stringToGraph, is a method function (Macaulay2Doc).