In case of interest - some improved timings, incorporating some tests
inspired by
Erdos & Gallai conditions, and Barnes & Savage, 1997, "Efficient
generation of graphical partitions":
(".;1&ts) '#graphsmdg 7'
+---+----------------+
|342|0.0077907 137088|
+---+----------------+
(".;1&ts) '#graphsmdg 7'
+---+----------------+
|342|0.0078118 141184|
+---+----------------+
(".;1&ts) '#graphsmdg 8'
+----+--------------+
|1213|0.02722 852864|
+----+--------------+
(".;1&ts) '#graphsmdg 10'
+-----+------------------+
|16016|0.356398 1.25327e7|
+-----+------------------+
(".;1&ts) '#graphsmdg 11'
+-----+-----------------+
|59348|1.39803 4.68659e7|
+-----+-----------------+
(".;1&ts) '#graphsmdg 12'
+------+----------------+
|222117|8.14412 3.1122e8|
+------+----------------+
Mike
On 21/06/2020 20:03, 'Michael Day' via Programming wrote:
OK, Raul - I've spent some time on this - but still managed a covid-19
walk with Liz, so could be worse.
I'd already spotted that it would somehow be useful to generate the
partitions that you're siftinf.
Luckily, I've got a script for partitions that I've built up over the
years, including k-partitions of n
with maximum element <: m. I've modified what I'd called, none too
helpfully, mmaxmpartz; it
looks for partitions of size k or less of n, max <: m. The new
function is m Gpart n
which produces degree sequences, or Graphic partitions, ie partitions
which satisfy the Erdos Gallai
requirement, as stated, eg in
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r11/pdf
It turns out to be quite easy to generate typical graphs from
partitions, using the Havel-Hakimi algorithm.
See eg http://szhorvat.net/pelican/hh-connected-graphs.html
I'd spotted earlier that you only need to go halfway in your loop on
n. Take any graph with m arcs and
remove them from the pairs array, size Nx2, to produce an appropriate
graph with N-m arcs. This saves
building excessively large partitions. This roughly halves the
running time, unsurprisingly.
I've built a cover function, graphsmdg to tie it all together. It
gets past the killer size of 8 quite nicely,
but still suffers time and probably space problems around, perhaps 12
or 13 , so no great gains!!!
You're welcome to the code, but, for now, I'll just show some time
and space observations.
(".; 1&ts) '#graphs 7' NB. Raul's original
+---+-----------------+
|342|1.62947 1.67847e8|
+---+-----------------+
(".; 1&ts) '#graphsmdg 7' NB. My version
+---+----------------+
|342|0.0061999 190208|
+---+----------------+
(".; 1&ts) '#graphsmdg 8'
+----+-------------------+
|1213|0.0307665 1.25306e6|
+----+-------------------+
(".; 1&ts) '#graphsmdg 10'
+-----+----------------+
|16016|1.1692 2.26577e7|
+-----+----------------+
(".; 1&ts) '#graphsmdg 11' NB. Haven't tried any bigger
+-----+-----------------+
|59348|15.3455 9.89311e7|
+-----+-----------------+
My application of the Erdos-Gallai property is deferred in the
partition generation;
it should be possible to anticipate some of its requirements in the
main construction
loop, to cut down on the size of intermediate partial partitions.
Cheers,
Mike
On 20/06/2020 19:00, Raul Miller wrote:
I want the outputs, though as the \:~@(#/.~)@,"2 idiom expresses, I am
primarily concerned with the structure of the underlying graph. (Any
of the nodes with the same \:~@(#/.~)@,"2 signature here represent the
same graph. And, I personally do not have reason to prefer one over
another)
Thanks,
--
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
