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.
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
|
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
|
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
|
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
|
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".
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}.