Graph::Maker::BulgarianSolitaire - create Bulgarian solitaire trees and graphs
use Graph::Maker::BulgarianSolitaire; $graph = Graph::Maker->new ('Bulgarian_solitaire', N => 6);
Graph::Maker::BulgarianSolitaire creates Graph.pm graphs of Bulgarian solitaire steps.
Graph::Maker::BulgarianSolitaire
Graph.pm
+-+ v | (self loop) 1,2,3 ^ | 2,4 N => 6 ^ ^ has 11 vertices / \ 1,1,1,3 1,5 / / \ 2,2,2 6 1,1,1,1,2 | | 3,3 1,1,1,1,1,1 | 1,1,4 | 1,1,2,2
Each vertex is a partition of the integer N, meaning a set of integers which sum to N. Vertex names are the terms in ascending order separated by commas. For example vertex 1,3,3,5 in N=12.
num vertices = 1, 1, 2, 3, 5, 7, 11, 15, ... (A000041) num edges = num vertices (one out each)
Bulgarian solitaire steps a partition by subtracting 1 from each element, summing the subtractions as a new term, and discarding any zeros. For example 1,3,3,5 steps to 2,2,4,5. Graph edges are from a partition to its successor by this rule.
N=0 is a single empty partition. N=1 is a single 1 partition.
If N is a triangular number N = t*(t+1)/2 = 1,3,6,10,... then partition 1,2,3,...,t steps to itself, so is a "fixed point". Per various authors, all partitions in triangular N eventually reach this fixed point (because the diagonal extent eventually decreases). The default is to include a self-loop at this partition so all vertices have out-degree 1. Optional parameter no_self_loop can omit,
no_self_loop
$graph = Graph::Maker->new ('Bulgarian_solitaire', N => 10, no_self_loop => 1);
no_self_loop is intended for making such N a tree, rather than tree and loop.
Non-triangular N gives one or more components, each with a cycle at the top. The number of components ($graph->connected_components()), is determined, for all N, in
$graph->connected_components()
Ethan Akin and Morton Davis, "Bulgarian Solitaire", American Mathematical Monthly, volume 92, number 4, April 1985, pages 237-250. http://www.jstor.org/stable/2323643
num components = num compositions of t,r up to cyclic shifts, for N = triangular(t-1) + r = 1,1,1,1,1,1,1,2,1,1,1,2,2,1,1,1,3,4,3 ... (A037306)
Some cycles are between 2 vertices. In an undirected simple graph, they become a single edge between the two. A multiedged=>1 or countedged=>1 has two edges between them.
multiedged=>1
countedged=>1
Some vertices have no predecessors, ie. in-degree 0 ($graph->predecessorless_vertices()). These are called "Garden of Eden" partitions after some terminology of Edward Moore in cellular automata. They are characterized and counted in
$graph->predecessorless_vertices()
Brian Hopkins and James A. Sellers, "Exact Enumeration of Garden of Eden Partitions", INTEGERS: Electronic Journal of Combinatorial Number Theory, volume 7 number 2, 2007, #A19.
num predecessorless = 0,0,0,1,1,2,3,5,7,10,14, ... (A123975) = sum(j=1,up, (-1)^(j+1) * NumPartions(n - 3*j*(j+1)/2)) num with predecessors = 1,1,2,2,4,5,8,10,15,20,28,... (A260894)
Predecessorless are all partitions with rank <= -2, where rank = LargestTerm - NumTerms (per Dyson). For example largest term 3 and having 5 or more terms is Garden of Eden.
Option compositions => $type applies the solitaire rule to compositions of N (partitions with ordered terms). Griggs and Ho call this "Carolina solitaire". $type can be "append" to append the new term or "prepend" to prepend. Append and prepend give the same structure, just with terms in each composition reversed.
compositions => $type
$type
1,2,1 ---> 1,3 ----> 2,2 <--- 3,1 <-- 4 <-- 1,1,1,1 ^ ^ / / \ v N => 4 2,1,1 1,1,2 compositions => 'append'
The number of compositions is
num vertices = 2^(N-1), or 1 if N=0 = 1,1,2,4,8,16,... (A011782) num edges = num vertices (one out each)
Hopkins and Jones show the number of Garden of Eden compositions is 2^(N-1) - Fibonacci(N+1).
Brian Hopkins, Michael A. Jones, "Shift-Induced Dynamical Systems on Partitions and Compositions", The Electronic Journal of Combinatorics 13 (2006), #R80.
$graph = Graph::Maker->new('Bulgarian_solitaire', key => value, ...)
The key/value parameters are
N => integer, to partition compositions => string "0", "append", "prepend" default "0" no_self_loop => boolean, default false graph_maker => subr(key=>value) constructor, default Graph->new
compositions defaults to "0" meaning not compositions, but partitions. no_self_loop omits the self-loop at the fixed point of triangular N.
compositions
Other parameters are passed to the constructor, either graph_maker coderef or Graph->new().
graph_maker
Graph->new()
If the graph is directed (the default) then edges are added just in the successor direction. Option undirected => 1 creates an undirected graph. Some steps can be a 2-cycle A->B and back B->A. In an undirected multigraph they are two edges.
undirected => 1
House of Graphs entries for graphs here include the following. House of Graphs is undirected simple graphs, so for example N=2 is a directed 2-cycle which as simple undirected is a 2-path. N=8 includes such a 2-cycle collapsing too.
https://hog.grinvin.org/ViewGraphInfo.action?id=1310 etc
1310 N=1, singleton 19655 N=2, path-2 32234 N=3, path-3 330 N=4 820 N=5 32254 N=6 32380 N=7 32256 N=8 32382 N=9 32258 N=10 32384 N=11 32386 N=12 32388 N=13 32390 N=14 32260 N=15 32392 N=16
Compositions are the same as partitions for N<=2, and then
594 N=3, path-4
Entries in Sloane's Online Encyclopedia of Integer Sequences related to these graphs include
http://oeis.org/A000041 (etc)
A000041 num vertices = num partitions = num edges too A260894 num with predecessors A123975 num predecessorless, Garden of Eden A037306 num connected components A054531 smallest cycle length = girth, for N>=1 A277227 same, for N>=0 A183110 longest cycle length A201144 longest path length (non-repeating)
For N=triangular (so a tree),
A066655 num vertices = num partitions of triangular = num edges too A002378 tree height (pronic numbers)
Compositions,
A011782 num vertices = 2^(N-1) or 1 when N=0 A000045 num with predecessors = Fibonacci(N+1) A008466 num predecessorless, Garden of Eden = 2^(N-1) - Fibonacci(N+1)
Graph::Maker
http://user42.tuxfamily.org/graph-maker-other/index.html
Copyright 2018, 2019, 2020, 2021 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.
To install Graph::Maker::Other, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Graph::Maker::Other
CPAN shell
perl -MCPAN -e shell install Graph::Maker::Other
For more information on module installation, please visit the detailed CPAN module installation guide.