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 be a rather tersely encoded string. This method builds that string given information in the HashTable h. 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 hashTable {"NumEdges" => 3}

o3 = -e3 
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 hashTable {"NumEdges" => (2,3)}

o5 = -e2: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 hashTable {"NumEdges" => (,3)}

o7 = -e: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 hashTable {"NumEdges" => (2,)}

o9 = -e2: 
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 hashTable {"NumEdges" => (2,), "NegateNumEdges" => true}

o11 = -~e2: 
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 is strict, that is, {"Connectivity" => 1} yields only those graphs with exactly 1-connectivity. In order to filter for connected graphs, one must use {"Connectivity" => 0, "NegateConnectivity" => true}.

See also

Ways to use buildGraphFilter :