Hopefully we wont have this HTML problem with the new Maple Primes!

Hi!

Yes, what Alec suggests above definitely works. But there is indeed also a *select* option to the *NonIsomorphicGraphs* command, and it has a potential efficiency advantage, so here's a way to use it. I'll first demonstrate a way to use it that's actually less efficient than what Alec suggests, but it's a useful step in the explanation:

myFilter := g -> evalb(min(GraphTheory:-DegreeSequence(g)) > 0);
[GraphTheory:-NonIsomorphicGraphs(8, output = graphs, outputform = graph,
select = myFilter, selectform = graph)];

The procedure myFilter expects to find its argument as a GraphTheory-understandable graph structure; that's why we need the *selectform* = *graph* option. However, constructing all of these graph structures takes time: the internal algorithm doesn't use these structures at every step. A more efficient alternative is *selectform* = *adjacency*. This gives the graph as an adjacency matrix with *datatype* = *integer*[1]. We can use that as follows:

myMatrixFilter := proc(m)
local i, n;
n := LinearAlgebra:-RowDimension(m);
for i to n do
if rtable_num_elems(m[i], 'NonZero') = 0 then
return false;
end if;
end do;
return true;
end proc;
[GraphTheory:-NonIsomorphicGraphs(8, output = graphs, outputform = graph,
select = myMatrixFilter, selectform = adjacency)];

This is already slightly faster than Alec's version; however, since almost all matrices satisfy the property we are interested in, almost all graph structures still need to be constructed in the end. If, however, we are content with the adjacency graphs (or indeed with the number of graphs), then this is substantially faster:

[GraphTheory:-NonIsomorphicGraphs(8, output = graphs, outputform = adjacency,
select = myMatrixFilter, selectform = adjacency)];

My timings:

5.800 for Alec's original code (for 8 nodes instead of 5),

9.900 for the version with myFilter,

5.640 for the version with myMatrixFilter,

2.140 for the version with outputform = adjacency.

(Alec's approach can of course also be sped up if you only need the adjacency matrices; I got 2.230 seconds for that.)

As I said earlier, a large fraction of all graphs has this property; for 8 vertices, the number is 11302 out of 12346. You can expect a greater advantage to using the *select* option instead of the *select* command if the fraction of graphs that satisfies the criterion is small. For example, if you would be interested in the set of graphs that have at least one vertex of maximal degree, *n* - 1, then you will find only 1044 out of 12346 graphs; you can write a similar procedure to *myMatrixFilter* and get a speedup from 2.300 to 0.750 seconds for 8 vertices.

Hope this helps,

Erik Postma

Maplesoft.

P.S.: It looks like the formatting is lost for now - I'll see what I can do to get it working again. In the mean time, here is an unformatted copy: http://pastebin.com/7uQ8hq0H