[Jprogramming] graphs

['Michael Day' via Programming]

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