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 = (72, 86, 86, 89, 96, 96, 94, 96, 96, 95, 97, 95, 98, 96, 99, 98, 98, 99,
     ------------------------------------------------------------------------
     98, 98, 99, 98, 94, 95, 100, 97, 99, 100, 99)

o9 : Sequence

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

o10 = (28, 14, 8, 5, 3, 2, 0, 2, 2, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0,
      -----------------------------------------------------------------------
      1, 0, 0, 0, 1, 0)

o10 : Sequence

Example: Generating and filtering graphs

See also