view release on metacpan or  search on metacpan

lib/Graph/Maker/GosperIsland.pm  view on Meta::CPAN

      *       *             /     \     /     \
       \     /             *       *---*       *
        *---*               \     /     \     /
                             *---*       *---*
      level => 0            /     \     /     \
                           *       *---*       *
                            \     /     \     /
                             *---*       *---*
                                  \     /
                                   *---*

C<level =E<gt> $k> is the grid expansion level.  Each level is 7 copies of
the previous, arranged with common sides in the surround pattern of level 1.
The effect is slowly curling spiralling boundaries (the shape of the
terdragon curve unfolded to 120 degrees).

                    * *
           * *   * *   * *
        * *   * *   * *   *          level => 2
       *   * *   * *   * *
        * *   * *   * *   * *
       *   * *   * *   * *   * *
        * *   * *   * *   * *   *
     * *   * *   * *   * *   * *
    *   * *   * *   * *   * *   *
     * *   * *   * *   * *   * *
    *   * *   * *   * *   * *
     * *   * *   * *   * *   *
        * *   * *   * *   * *
           * *   * *   * *   *
          *   * *   * *   * *
           * *   * *   * *
              * *

level=1 is a 6-cycle like L<Graph::Maker::Cycle>.

level=2 is a 2x2x2 hex grid like L<Graph::Maker::HexGrid> can give.

The graph size grows rapidly with the level,

    num hexagons = 7^k
                 = 1, 7, 49, 343, 2401, ...    (A000420)
    num vertices = 2*7^k + 3^(k+1) + 1
                 = 6, 24, 126, 768, 5046, ...
    num edges    = 3*7^k + 3^(k+1)
                 = 6, 30, 174, 1110, 7446, ...

=cut

# GP-DEFINE  H(k) = 7^k;
# GP-DEFINE  V(k) = 2*7^k + 3^(k+1) + 1;
# GP-DEFINE  E(k) = 3*7^k + 3^(k+1);
# GP-Test  vector(5,k,k--; H(k)) == [1, 7, 49, 343, 2401]
# GP-Test  vector(5,k,k--; V(k)) == [6, 24, 126, 768, 5046]
# GP-Test  vector(5,k,k--; E(k)) == [6, 30, 174, 1110, 7446]
# not in OEIS: 6, 24, 126, 768, 5046
# not in OEIS: 6, 30, 174, 1110, 7446

=pod

These formulas follow from a bottom-up construction.  Each existing edge
becomes 3 edges and inside each hexagon is a new hexagon and edges to the
outside there to make the level 1 base figure.

=cut

# GP-Test  vector(100,k,k--; V(k)+H(k)) == vector(100,k,k--; E(k)+1)
# GP-Test  vector(100,k,k--; E(k+1)) == vector(100,k,k--; 3*E(k) + 12*H(k))
# GP-Test  vector(100,k,k--; V(k+1)) == vector(100,k,k--; V(k)+2*E(k)+6*H(k))

=pod

Vertex names are currently x,y coordinates used in the construction, but
don't rely on that.

=head1 FUNCTIONS

=over

=item C<$graph = Graph::Maker-E<gt>new('Gosper_island', key =E<gt> value, ...)>

The key/value parameters are

    level       => integer>=0, island expansion
    graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either C<graph_maker> or
C<Graph-E<gt>new()>.

If the graph is directed (the default) then edges are added both ways
between vertices (like L<Graph::Maker::Grid> does).  Option C<undirected
=E<gt> 1> creates an undirected graph and for it there is a single edge
between vertices.

=back

=head1 HOUSE OF GRAPHS

House of Graphs entries for graphs here include

=over

=item level=0 L<https://hog.grinvin.org/ViewGraphInfo.action?id=670>, 6-cycle

=item level=1 L<https://hog.grinvin.org/ViewGraphInfo.action?id=28529>, hex grid 2,2,2

=item level=2 L<https://hog.grinvin.org/ViewGraphInfo.action?id=28531>

=back

=head1 SEE ALSO

L<Graph::Maker>,
L<Graph::Maker::Cycle>,
L<Graph::Maker::Grid>,
L<Graph::Maker::HexGrid>

=head1 HOME PAGE

L<http://user42.tuxfamily.org/graph-maker-other/index.html>