next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Nauty :: buildGraphFilter

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

Synopsis

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 h or the List 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 or in ZZ. Boolean 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 (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 (,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 (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

Ways to use buildGraphFilter :