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.

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é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.

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 = (71, 82, 81, 92, 94, 98, 96, 97, 98, 97, 96, 96, 100, 98, 98, 96, 97,
     ------------------------------------------------------------------------
     98, 99, 99, 100, 99, 100, 98, 98, 98, 98, 99, 99)

o9 : Sequence
i10 : apply(2..30, n -> #filterGraphs(generateRandomGraphs(n, 100, (prob n)/2), connected))

o10 = (19, 7, 4, 7, 5, 5, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 0, 1, 0, 0, 1,
      -----------------------------------------------------------------------
      0, 0, 1, 1, 0, 0)

o10 : Sequence

See also