Generating all non-isomorphic graphs for a given number of nodes with specified degrees

I would like to generate the set of all possible, non-isomorphic graphs for a given number of nodes (n) with specified degrees. Such graphs are relatively small, they may have n = 1-8 where the degree of nodes may range from 1-4.

Generated graphs must be allowed to contain loops and multi-edges. Here, multi-edges have a max value of 2, that is any two nodes may be connected to eachother by a maximum of 2 edges, they may also be connected by 1 edge or 0 edges.

E.G. Generate all possible graphs (thay are allowed to contain loops and multi-edges) with 4 nodes (n = 4) where 2 of the nodes have the degree 2 (2-connected) and two of the nodes have the degree 3 (3-connected).

I have worked this out on paper, there should be 11 different graphs.

Is there an efficient way to generate all possible graphs (with restrictions listed above) with n nodes where the degree of each node is specified ?

Thanks!

-Maxwell Day

Answer 1

[Christine Tobler]

I've attached a script that computes the graphs in your example, here's the plot of all graphs it found:

[Maxwell Day]

Great! So far results match my calculations exactly, thank you very much.

[Maxwell Day]

@Christine Tobler

Is there anyway to revise the code to allow for execution of generategraphsMulti.m code where n = 6-8?. When attempting to generate graphs with 6-8 nodes the array size limit is exceeded or an enormous amount of time is required.

The following error message is recieved when attempting to generate graphs with 6-8 nodes:

Error using zeros

Requested 445891810x9 (29.9GB) array exceeds maximum array size preference. Creation of arrays greater

than this limit may take a long time and cause MATLAB to become unresponsive. See array size limit or

preference panel for more information.

Error in nchoosek>combs (line 164)

P = zeros(total, k, 'like', v);

Error in nchoosek (line 123)

c = combs(v,k);

Let me know if this is possible, thanks.

-Maxwell Day

[Christine Tobler]

Hi Maxwell,

Finding all combinations is kind of inherently likely to run out of memory - the memory requirements grow very quickly w.r.t. how many possible edges there are and how many edges we want to place here.

Here 29.9GB memory is likely to exceed memory depending on the machine, but it's not a complete fantasy number. Is this for 6 nodes or for 8 nodes? Every extra node is likely to be a considerable factor more expensive, the cost here is growing exponential with the number of possible edges, which itself grows like the number of nodes squared.

One thing to do here is that you can separate out choosing the first edge from choosing all other edges: make a for-loop over all possible edges, and then just compute all possible ways of choosing the remaining edges:

for firstEdge=1:size(ed, 1)
    setsOfAdditionalRows = nchoosek([1:firstEdge-1 firstEdge+1:size(ed, 1)], e);
    setsOfRows = [firstEdge setsOfAdditionalRows];
end

This reduces the size of setsOfRows - but note that when memory requirements go out of bounds, it's likely that the computational time will also be very slow. So this may prevent out-of-memory, but not necessarily be something you can actually finish in a sensible time anyway.

If taking out computing the first edge isn't enough, take out choosing the first few edges as separate for-loops. You could even call nchoosek to choose 3 edges (for example), then iterate through each choice of such 3 edges and find all ways to choose the remaining e-3 edges.

[Maxwell Day]

Hi Christine,

thank you for the quick response, 29.9GB was required for 6 nodes of degree 3, for 8 (as high as I have to go) of degree 3 well over 1 million GB is required. I had a feeling computation involving more than 5-6 nodes (depening on their degree) would require an iterative approach as this is nessacary for the manual calculations too, which take an enormous amount of time (the reason for using MatLab).

It appears that seperating out choosing the first edge, as you provided code for, isn't enough. How would I go about coding " call nchoosek to choose 3 edges (for example), then iterate through each choice of such 3 edges and find all ways to choose the remaining e-3 edges" and intergarting this into the existing code?

Unfortunately I am still quite novice when I comes to writing in MatLab.

Thanks again

-Maxwell

[Christine Tobler]

I've attached a version of the previous script which is using an additional outer for-loop (still for the case n=4 you had described). I haven't tested this for higher degrees, there things will depend a lot on the degrees of the nodes you're looking for, too.

Try passing in the problem you're trying to solve for 6 nodes, and then increase the variable k as much as is needed to prevent an out-of-memory error. Keep in mind that the number of graphs to check out for your problem grows explosively, so even if you can solve the 6 nodes case, a 7 nodes case I would guess can take about 50 times longer to get through all combinations (again, hard to tell because the degree distribution has a lot to say about this, too).

[Maxwell Day]

Hi Christine,

Thanks again, I am in the process of testing the new code, code seems to execute faster however the final figure produced contains no graphs, it is simply a blank figure. I am not sure why this is happening.

-Maxwell

[Maxwell Day]

Hi @Christine Tobler,

I have tested the new multinestedloops code for a number of cases with 6 nodes, seems to execute in a very reasonable amount of time. However, the Figure generated after the code has executed contains no graphs, I've compared the last half of the code to the original code (which doesn't have this problem) but I can't seem to fine the reason the figures are not appearing after the run is complete.

Is there something that needs to be added to the revised code to rectify this problem?

Thanks

[Christine Tobler]

Thanks for pointing this out, Maxwell. I made some last-minute modification that broke the code and didn't realize before. I've updated the file linked above, it should work now.

[Maxwell Day]

Thanks @Christine Tobler,

Now it appears the code is generating the Figure for each graph set properly!

I am attempting to run the degList = [2 2 2 2 3 3] with k = 8 and the following error shows up;

Error using nchoosek (line 29)

The second input has to be a non-negative integer.

Error in generateGraphsMultiNestedLoops (line 43)

lastSetsOfRows = nchoosek(firstSet(end)+1:size(ed, 1), e-k);

From your last comment, it sounds like increasing k should only decrease the memory required to a maximum value where k = e/2, where e = # of edges given by "degList", is this true? If so, should k always be set equal to e/2?

[Christine Tobler]

k must also be less than e, since we are splitting up the number of edges into k edges, and then e-k other edges. The error is because e-k becomes negative.