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".
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$.
The object buildGraphFilter is a method function.