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, which describes the properties desired in filtering
- l, a list, which describes the properties desired in filtering
Outputs:
- s, a string, 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 $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 : L = {graph {{1,2}}, graph {{1,2},{2,3}}, graph {{1,2},{2,3},{3,4}}, graph {{1,2},{2,3},{3,4},{4,5}}};

i2 : s = buildGraphFilter {"NumEdges" => 3};

i3 : filterGraphs(L, s)

o3 = {Graph{1 => {2}   }}
            2 => {1, 3}
            3 => {2, 4}
            4 => {3}

o3 : List

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

i4 : s = buildGraphFilter {"NumEdges" => (2,3)};

i5 : filterGraphs(L, s)

o5 = {Graph{1 => {2}   }, Graph{1 => {2}   }}
            2 => {1, 3}         2 => {1, 3}
            3 => {2}            3 => {2, 4}
                                4 => {3}

o5 : List

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

i6 : s = buildGraphFilter {"NumEdges" => (,3)};

i7 : filterGraphs(L, s)

o7 = {Graph{1 => {2}}, Graph{1 => {2}   }, Graph{1 => {2}   }}
            2 => {1}         2 => {1, 3}         2 => {1, 3}
                             3 => {2}            3 => {2, 4}
                                                 4 => {3}

o7 : List

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

i8 : s = buildGraphFilter {"NumEdges" => (2,)};

i9 : filterGraphs(L, s)

o9 = {Graph{1 => {2}   }, Graph{1 => {2}   }, Graph{1 => {2}   }}
            2 => {1, 3}         2 => {1, 3}         2 => {1, 3}
            3 => {2}            3 => {2, 4}         3 => {2, 4}
                                4 => {3}            4 => {3, 5}
                                                    5 => {4}

o9 : List

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

i10 : s = buildGraphFilter {"NumEdges" => (2,), "NegateNumEdges" => true};

i11 : filterGraphs(L, s)

o11 = {Graph{1 => {2}}}
             2 => {1}

o11 : 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$.

Ways to use buildGraphFilter:

buildGraphFilter(HashTable)
buildGraphFilter(List)

For the programmer

The object buildGraphFilter is a method function.