Graph-Maker-Other
view release on metacpan or search on metacpan
lib/Graph/Maker/BinomialBoth.pm view on Meta::CPAN
return $graph;
}
Graph::Maker->add_factory_type('binomial_both' => __PACKAGE__);
1;
__END__
=for stopwords Ryde undirected Apery OEIS Wnew
=head1 NAME
Graph::Maker::BinomialBoth - create binomial both graph
=for test_synopsis my ($graph)
=head1 SYNOPSIS
use Graph::Maker::BinomialBoth;
$graph = Graph::Maker->new ('binomial_both', order => 3,
direction_type => 'bigger');
=head1 DESCRIPTION
C<Graph::Maker::BinomialBoth> creates a C<Graph.pm> graph of a "binomial
both" of order k. This is a binomial tree both upwards and downwards.
Vertices are numbered from 0 up to max = 2^k-1 where k is the "order".
0----
| \ \
1 2 4 order => 3
\ | | \ vertices 0 to 7
3 5 6
\ \ |
----7
Each vertex v is taken as k many bits, including high 0s as necessary. Each
edge is
from to
---- -----------------------
v clear lowest 1-bit of v \ edges
v set lowest 0-bit of v /
Clear-lowest-1 is the parent of v in the binomial tree
(L<Graph::Maker::BinomialTree>). Set-lowest-0 is the same applied towards
the maximum vertex 2^k-1, as if that was the root by everywhere bit flip
0E<lt>-E<gt>1.
Both rules apply at the least significant bit, which is the low bit flipped
0 E<lt>-E<gt> 1. Just one edge is added for this, by not applying the
set-lowest-0 rule at the low bit. Consequently there are 2^k-1 edges of
clear-lowest-1 and 2^(k-1)-1 edges of set-lowest-0 for total
num_edges(k) = / 0 if k = 0
\ 3 * 2^(k-1) - 2 if k >= 1
= 0, 1, 4, 10, 22, 46, 94, 190, ... (A296953)
=cut
# GP-DEFINE num_edges_formula(k) = 3*2^(k-1) - 2;
# GP-DEFINE num_edges(k) = if(k==0,0, num_edges_formula(k));
# GP-Test num_edges_formula(0) == -1/2
# GP-Test vector(8,k,k--; num_edges(k)) == [0, 1, 4, 10, 22, 46, 94, 190]
=pod
Each edge changes just one bit so binomial both is a sub-graph of hypercube
k (L<Graph::Maker::Hypercube>).
A top-down definition is to make order k from two copies of k-1. The max of
the first connects down to the max of the second, and the min of the first
connects down to the min of the second.
min
first |.| \
|.| min
max |.| second
\ |.|
max
=head2 Direction Type
The default is a directed graph with edges both ways between vertices (like
most C<Graph::Maker> directed graphs). This is parameter C<direction_type
=E<gt> 'both'>.
Optional C<direction_type =E<gt> 'bigger'> gives edges directed to the
bigger vertex number, so from smaller to bigger. The result is a graded
lattice (the algebra type of lattice, partially ordered set) with edges its
cover relations. (The name "binomial lattice" is normally given to the grid
type lattice formed by random share price movements, so here "binomial both"
instead.)
The lattice is graded by d = number of 1-bits in the vertex number, which is
the binomial tree depth. Like the binomial tree, the number of vertices at
depth d is binomial coefficient binomial(k,d).
Option C<direction_type =E<gt> 'smaller'> gives edges directed to the
smaller vertex number, so from bigger to smaller. This is the same as
C<$graph-E<gt>transpose()> reversing edges.
=head2 Coordinates
There's a secret undocumented coordinates option the same as the binomial
tree L<Graph::Maker::BinomialTree/Coordinates>. Don't rely on this yet as
it might change or be removed.
=head1 FUNCTIONS
=over
=item C<$graph = Graph::Maker-E<gt>new('binomial_both', key =E<gt> value, ...)>
The key/value parameters are
order => integer >=0
direction_type => string, "both" (default)
"bigger"
"smaller"
graph_maker => subr(key=>value) constructor,
default Graph->new
lib/Graph/Maker/BinomialBoth.pm view on Meta::CPAN
=cut
# GP-DEFINE num_max_chains(k) = if(k==0,1, 2^(k-1));
# GP-Test vector(6,k,k--; num_max_chains(k)) == [1, 1, 2, 4, 8, 16]
=pod
In the top-down definition above, a path can go through the first half or
second half, and then the same recursively in quarters etc until k=1 is 2
vertices and just one path.
=head2 Intervals
An interval in a lattice is a pair of vertices u,v which are comparable. In
the graph with direction type "bigger", this means one vertex is reachable
from the other by some directed path. u=v is an interval too.
num_intervals(k) = k*2^k + 1 Cullen numbers
= 1, 3, 9, 25, 65, 161, 385, ... (A002064)
In the top-down definition, order k formed from two k-1 gives new intervals
from first half min to each second half vertex, and from each of the other
first half vertices to the second half max. So the following recurrence,
and from which the Cullen numbers,
num_intervals(k) = 2*num_intervals(k-1) + 2^(k-1) + 2^(k-1) - 1
=cut
# GP-DEFINE num_intervals(k) = k*2^k + 1;
# GP-Test vector(8,k,k--; num_intervals(k)) == \
# GP-Test [1, 3, 9, 25, 65, 161, 385, 897]
# GP-Test vector(10,k, num_intervals(k)) == \
# GP-Test vector(10,k, 2*num_intervals(k-1) + 2^(k-1) + 2^(k-1) - 1)
=pod
=head2 Complementary Pairs
A complementary pair in a lattice is two vertices u,v where their meet and
join are the global min and global max. In the graph with direction type
"bigger", this means C<$u-E<gt>all_predecessors()> and
C<$v-E<gt>all_predecessors()> have only the global minimum (0) in common,
and also C<all_successors()> only the global maximum in common (2^k-1).
num_complementary(k) = / 1 if k=0
\ (2^(k-1) - 1)^2 + 1 if k>=1
= 0, 1, 2, 10, 50, 226, ... (2*A092440)
This count follows from the top-down definition. Pairs within a half have
the half min and max in common, only one of those is the global min/max, so
no complementary pairs. The first half min has all of the second half as
descendants, so only first half min as global smallest and second max as
global biggest are a pair. Then the other 2^(k-1)-1 vertices of the first
half are complementary to the 2^(k-1)-1 vertices of the second half except
the second max which is the global maximum. For k=0, the single vertex is a
complementary pair 0,0.
=cut
# GP-DEFINE num_complementary_formula(k) = (2^(k-1) - 1)^2 + 1;
# GP-DEFINE num_complementary(k) = if(k==0,1, num_complementary_formula(k));
# GP-Test vector(6,k,k--; num_complementary(k)) == [1, 1, 2, 10, 50, 226]
=pod
=head2 Wiener Index
The top-down definition means the Wiener index of order k+1 is twice k plus
paths from the first k to the second k. Those paths go by the top edge or
the bottom edge between the halves, whichever is the shorter way. So a sum
over depth u in the first, depth v in the second, with respective numbers of
vertices at those depths,
k k
Wnew(k) = sum sum binomial(k,u) * binomial(k,v)
u=0 v=0 * min(u+v+1, (k-u)+(k-v)+1)
= 1, 6, 36, 196, 1000, 4884, 23128, ...
W(k+1) = 2*W(k) + Wnew(k) Wiener index
starting W(k)=0
W(k) = 0, 1, 8, 52, 300, 1600, 8084, 39296, ...
=cut
# GP-DEFINE Wnew_by_min(k) = {
# GP-DEFINE k>=0 || error();
# GP-DEFINE sum(u=0,k, sum(v=0,k,
# GP-DEFINE binomial(k,u) * binomial(k,v) * min(u+v+1,(k-u)+(k-v)+1)));
# GP-DEFINE }
# GP-Test vector(7,k,k--; Wnew_by_min(k)) == \
# GP-Test [1, 6, 36, 196, 1000, 4884, 23128]
# vector(10,k,k--; Wnew_by_min(k))
# not in OEIS: 1, 6, 36, 196, 1000, 4884, 23128, 107048, 486864, 2183860
#
# GP-DEFINE W_by_min(k) = {
# GP-DEFINE k>=0 || error();
# GP-DEFINE if(k==0,0, 2*W_by_min(k-1) + Wnew_by_min(k-1));
# GP-DEFINE }
# GP-DEFINE W_by_min=memoize(W_by_min);
# GP-Test vector(9,k,k--; W_by_min(k)) == \
# GP-Test [0,1,8,52,300,1600,8084,39296,185640]
# vector(10,k, W_by_min(k))
# not in OEIS: 1, 8, 52, 300, 1600, 8084, 39296, 185640, 858144, 3900148
=pod
For comparison, the Wiener index of the binomial tree is this sum but always
u+v+1 instead of min().
=cut
# GP-DEFINE TreeW(k) = ( (k-1)*4^k + 2^k ) /2;
# vector(9,k,k--; TreeW(k+1) - 2*TreeW(k)) == \
# vector(9,k,k--; (k+1)*4^k)
# GP-DEFINE gTreeW(x) = x/(1-2*x) * 1/(1 - 4*x)^2;
# GP-Test sum(k=0,20, x^k*TreeW(k) ) == gTreeW(x + O(x^20))
#
# GP-Test vector(9,k,k--; TreeW(k+1)) == \
# GP-Test vector(9,k,k--; 2*TreeW(k) \
( run in 0.641 second using v1.01-cache-2.11-cpan-39bf76dae61 )