output = count, countbyedges, graphs, or iterator

For output=count, the number of unique isomorphic graphs matching all criteria is output.

For output=countbyedges, a sequence of the form e1=c1, e2=c2, ... is returned, where ei is the number of edges, and ci is the graph count for those edges.

For output=graphs, a sequence of representations for all graphs is returned.

For output=iterator a module is returned. When called as a procedure, it outputs the next graph in the sequence. The iterator output is similar to the graphs output, but the complete sequence of graphs is never actually formed, which makes this most useful when dealing with a large number of graphs.

The iterator will start with the first graph that would be output for the graphs output form, then the next in the sequence with each call, and after the last graph has been output, the return will be FAIL, which indicates that the procedure has already returned all graphs. Calling the procedure with the optional argument reset will restart the iteration from the beginning, as demonstrated in the examples.

outputform = graph, adjacency, or bits

The outputform option specifies the form used to represent output graphs. This option is only valid for output = graphs or output = iterator. When outputform=bits (the default) the graph is output as an integer such that the adjacency matrix for the graph can be constructed by the bits set in the output integer. Specifically the integer is the one formed by examining the upper triangular portion of the symmetric adjacency Matrix, excluding the diagonal, and building up, from least to most significant bit order, the entries, moving left to right, then down, by using a 1 digit if the edge is present, and a 0 digit otherwise. There is an example that constructs the adjacency matrix from the bits representation in the examples section below. When outputform=adjacency, the adjacency Matrix of the graph is constructed as a v x v integer[1] Matrix. When outputform=graph, Graph structures are constructed.

restrictto = none (default), connected, regular, regular[n]

The restrictto option specifies that the graphs either returned or iterated over should satisfy the specified criteria, otherwise they should be skipped. Specifically, when restrictto=connected is used, only connected graphs are counted or returned, when restrictto=regular, only regular graphs are counted or returned, and when restrictto=regular[n], only n-regular graphs are counted or returned.

select=procedure

This allows specification of a procedure to control whether a graph should be included in the output. This provides similar functionality as restrictto but allows for implementation of more complex criteria. Note that this option can be used in combination with restrictto, and only the graphs that satisfy the restrictto criteria will be passed to the select procedure.

selectform = graph, adjacency, or bits

This specifies the form used for a graph when it is being passed to the select procedure. The forms are identical to those for outputform, but note that adjacency and bits are the most efficient forms, while graph is only reasonable for a relatively small number of comparison operations (1000 or less), as it needs to form a Graph for every comparison. Note also that when selectform=adjacency the same read-only Matrix is internally used to pass the data for every call to reduce overhead. This is not possible with a Graph structure.

The NonIsomorphicGraphs command allows for operations to be performed for one member of each isomorphic class of undirected, unweighted graphs for a fixed number of vertices having a specified number of edges or range of edges.  Use the options to return a count on the number of isomorphic classes or a representative graph from each class.

As quick examples, one can obtain a count of the number of isomorphic classes of 4-vertex graphs:

with(GraphTheory):

NonIsomorphicGraphs(4,output=count);

$11$

[NonIsomorphicGraphs(4,output=countbyedges)];

$\left[0=1\,1=1\,2=2\,3=3\,4=2\,5=1\,6=1\right]$

[NonIsomorphicGraphs(4,2..4,output=countbyedges)];

$\left[2=2\,3=3\,4=2\right]$

NonIsomorphicGraphs(4,3,output=count);

$3$

One can obtain representations for a member of each distinct isomorphic class of graphs, restricting based on built-in criteria and/or procedure-defined criteria, with output either as a (possibly very large) sequence of graph representations, or an iterator that can be used to output the sequence one graph at a time.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\left[\mathrm{NonIsomorphicGraphs}\left(8\right)\,\mathrm{NonIsomorphicGraphs}\left(8\,\mathrm{restrictto}=\mathrm{connected}\right)\right]$

$\left[12346\,11117\right]$

$\left[\mathrm{NonIsomorphicGraphs}\left(8\,\mathrm{output}=\mathrm{graphs}\,\mathrm{restrictto}=\mathrm{regular}\left[2\right]\right)\right]$

$\left[210256131\,213917955\,210501763\right]$

$\mathrm{bit}≔\mathrm{Vector}\left[\mathrm{row}\right]\left(\mathrm{Bits}:-\mathrm{Split}\left(210256131\,\mathrm{bits}=\frac{8\left(8-1\right)}{2}\right)\right)\:$

$M≔\mathrm{Matrix}\left(8\,8\,\mathrm{shape}=\mathrm{symmetric}\,\mathrm{datatype}=\mathrm{integer}\left[1\right]\right)\:$

$M\left[1,2..8\right]≔\mathrm{bit}\left[1..7\right]\:$$M\left[2,3..8\right]≔\mathrm{bit}\left[8..13\right]\:$$M\left[3,4..8\right]≔\mathrm{bit}\left[14..18\right]\:$

$M\left[4,5..8\right]≔\mathrm{bit}\left[19..22\right]\:$$M\left[5,6..8\right]≔\mathrm{bit}\left[23..25\right]\:$$M\left[6,7..8\right]≔\mathrm{bit}\left[26..27\right]\:$

$M\left[7,8..8\right]≔\mathrm{bit}\left[28..28\right]\:$

$M$

$\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right]$

$\mathrm{NonIsomorphicGraphs}\left(8\,\mathrm{output}=\mathrm{graphs}\,\mathrm{outputform}=\mathrm{adjacency}\,\mathrm{restrictto}=\mathrm{regular}\left[2\right]\right)$

$\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right],\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right],\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right]$

$\mathrm{prc}≔\mathrm{NonIsomorphicGraphs}\left(8\,\mathrm{output}=\mathrm{iterator}\,\mathrm{outputform}=\mathrm{adjacency}\,\mathrm{restrictto}=\mathrm{regular}\left[2\right]\right)$

$\mathrm{prc}≔\mathbf{module}\left(\right)\mathbf{local}\mathrm{cdata}\,\mathrm{atend}\,\mathrm{ModuleApply}\;\mathbf{end\; module}$

$\mathrm{prc}\left(\right),\mathrm{prc}\left(\right),\mathrm{prc}\left(\right)$

$\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right],\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right],\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right]$

$\mathrm{prc}\left(\right)$

$\mathrm{FAIL}$

$\mathrm{prc}\left(\mathrm{reset}\right)$

$\mathrm{prc}\left(\right)$

$\left[\begin{array}{cccccccc}0& 1& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right]$