next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
NautyGraphs :: Example: Generating and filtering graphs

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.
A000088 = apply(1..9, n -> #generateGraphs n)
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,
forestsOnly = buildGraphFilter {"NumCycles" => 0};
A005195 = apply(B, graphs -> #filterGraphs(graphs, forestsOnly))
treesOnly = buildGraphFilter {"NumCycles" => 0, "Connectivity" => 0, "NegateConnectivity" => true};
A000055 = apply(B, graphs -> #filterGraphs(graphs, treesOnly))
Moreover, we can generate random graphs using the generateRandomGraphs method. Here we verify a result of Erdos and Rényi (see http://www.ams.org/mathscinet-getitem?mr=120167), which says that a random graph on n vertices with edge probability (1+ε)log(n)/n is almost always connected while a graph with edge probability (1-ε)log(n)/n is almost never connected, at least as n tends to infinity.
connected = buildGraphFilter {"Connectivity" => 0, "NegateConnectivity" => true};
prob = n -> log(n)/n;
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, 2*(prob n)), connected))
apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected))

See also