Generating non-isomorphic graphs with 6-8 nodes of specified degrees

2 次查看（过去 30 天）

Maxwell Day 2021-4-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/808955-generating-non-isomorphic-graphs-with-6-8-nodes-of-specified-degrees

generateGraphsMultiNestedLoops.m

I would like to increase the efficiency (reduce execution time) of my existing code (attached) for 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.

My Problem:

The attached code works great for graphs with 1-5 nodes as the memory requirements (number of permutations required) is significantly less and the code will finish and produce all non-isomorphic graphs within a couple mins to about 8 hours. However, when generating graphs with 6-8 nodes and setting k to an appropriate number the code takes an impratically large amount of time (weeks, even months) to finish, certain degree combinations have yet to complete as I suspect they may require years to complete based on how the current code is working.

Is there anyway to increase the efficiency (reduce the execution time) of this code by spliting the number of edges to iterate over into more than two parts? Upon completion of each of these parts, could the results (valid non-isomorphic graphs) be saved to file to reduce memory consumption?

If the code cannot be improved is there any other way to improve execution time? Run on a computer with more RAM/ faster processor, dual processors etc.?

The following is an example in which the code has yet to complete despite letting it run for over a month!

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

e.g. four nodes of degree 2 and four nodes of degree 3 is entered into the attached code as follows;

degList = [2 2 2 2 3 3 3 3]

Here, the number of edges (e) = 20 as (3x4) + (2x4) = 20

Then k must be set to less than e (the number of edges), since we are splitting up the number of edges into k edges, and then e-k other edges.

I know this is a very difficult problem and I greatly appreciate any time anyone is willling to put in to help! Thanks.

-Maxwell.