# Example: Generating and filtering graphs

The method generateGraphs can generate all graphs with a given property. For example, we can verify the number of graphs on a given number of vertices. Compare these results to the Online Encyclopedia of Integer Sequences (http://oeis.org/), where the sequence name is also its OEIS identifier.

 i1 : A000088 = apply(1..9, n -> #generateGraphs n) o1 = (1, 2, 4, 11, 34, 156, 1044, 12346, 274668) o1 : Sequence i2 : B = apply(1..12, n -> generateGraphs(n, OnlyBipartite => true));

Further, we can use filterGraphs to refine the set of generate graphs for deeper properties.

Here we filter for forests, then for trees only,

 i3 : forestsOnly = buildGraphFilter {"NumCycles" => 0}; i4 : A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly)) o4 = (1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601) o4 : Sequence i5 : treesOnly = buildGraphFilter {"NumCycles" => 0, "Connectivity" => 0, "NegateConnectivity" => true}; i6 : A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly)) o6 = (1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551) o6 : Sequence

Moreover, we can generate random graphs using the generateRandomGraphs method. Here we verify a result of Erdos and R\'enyi (see http://www.ams.org/mathscinet-getitem?mr=120167), which says that a random graph on $n$ vertices with edge probability $(1+\epsilon)$log$(n)/n$ is almost always connected while a graph with edge probability $(1-\epsilon)$log$(n)/n$ is almost never connected, at least as $n$ tends to infinity.

 i7 : connected = buildGraphFilter {"Connectivity" => 0, "NegateConnectivity" => true}; i8 : prob = n -> log(n)/n; i9 : apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n)), connected)) o9 = (64, 84, 93, 92, 94, 95, 96, 98, 97, 99, 96, 97, 97, 98, 99, 96, 100, ------------------------------------------------------------------------ 99, 99, 97, 98, 100, 100, 97, 95, 99, 99, 96, 99) o9 : Sequence i10 : apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected)) o10 = (15, 13, 4, 3, 3, 1, 2, 2, 1, 2, 2, 1, 0, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, ----------------------------------------------------------------------- 0, 0, 0, 0, 0, 0) o10 : Sequence

• buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
• filterGraphs -- filters (i.e., selects) graphs in a list for given properties
• generateGraphs -- generates the graphs on a given number of vertices
• generateRandomGraphs -- generates random graphs on a given number of vertices