blib/lib/Graph/Geometric.pm

filter: Statementstmt 78.9% 473 / 599 Branchbran 73.9% 102 / 138 Conditioncond 33.3% 15 / 45 MC/DCmcdc 37.0% 10 / 27 Subroutinesub 76.5% 49 / 64 Podpod 92.5% 37 / 40 totaltotal 75.1% 686 / 913 CC 138 SCAR 30.5
CC
138
Cov
75%
elongate
91.7
delete_face
42.0
tetrahedron
20.0
CRAP 21.1
↑ Summary
1 package Graph::Geometric;
2  
3 10 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 10 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 10 ▶use feature qw(current_sub); # Perl v5.16 or later
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 =head1 NAME
8  
9 Graph::Geometric - create and work with geometric graphs
10  
11 =cut
12  
13 # ABSTRACT: Create and work with geometric graphs
14 10 our $VERSION = '0.2.0'; # VERSION
15  
16 10 ▶use Exporter;
Subroutine BEGIN: called CC=1 SCAR=0.0
17 10 ▶use Graph 0.9713;
Subroutine BEGIN: called CC=1 SCAR=0.0
18 10 ▶use Graph::Undirected;
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 10 ▶use parent Graph::Undirected::, Exporter::;
Subroutine BEGIN: called CC=1 SCAR=0.0
21  
22 10 our @polygon_names = (
23 '', 'mono', 'di', 'tri', 'tetra', 'penta', 'hexa', 'hepta', 'octa', 'nona', 'deca',
24 'undeca', 'dodeca', 'trideca', 'tetradeca', 'pentadeca', 'hexadeca', 'heptadeca', 'octadeca', 'nonadeca',
25 'icosa', 'henicosa', 'docosa', 'tricosa', 'tetracosa', 'pentacosa', 'hexacosa', 'heptacosa', 'octacosa', 'nonacosa',
26 'triaconta', 'hentriaconta', 'dotriaconta', 'tritriaconta', 'tetratriaconta', 'pentatriaconta', 'hexatriaconta', 'heptatriaconta',
27 'octatriaconta', 'nonatriaconta', 'tetraconta',
28 );
29 10 my @subs = qw(
30 antiprism
31 bifrustum
32 bipyramid
33 cucurbituril
34 cupola
35 dodecahedron
36 gyrobicupola
37 icosahedron
38 icosidodecahedron
39 octahedron
40 orthobicupola
41 prism
42 pyramid
43 rectified
44 rhombic_dodecahedron
45 rotunda
46 stellated
47 trapezohedron
48 truncated
49 );
50 10 push @subs, map { $_ . 'gonal' } @polygon_names[1..$#polygon_names];
51 10 push @subs, 'triangular', 'square';
52  
53 10 our @EXPORT = @subs;
54  
55 10 ▶use List::Util qw( all any max sum uniq );
Subroutine BEGIN: called CC=1 SCAR=0.0
56 10 ▶use Set::Scalar;
Subroutine BEGIN: called CC=1 SCAR=0.0
57  
58 384 ▶sub AUTOLOAD {
Subroutine AUTOLOAD: called CC=6 SCAR=18.7
59 384 our $AUTOLOAD;
60 384 my $call = $AUTOLOAD;
61 384 $call =~ s/.*:://;
62 384 ▶ return if $call eq 'DESTROY';
Branch: 1 branch
BranchTrueFalseTotal
if $call eq "DESTROY" 363 21 384
63 21 ▶ if( $call =~ /gonal$/ ) {
Branch: 3 branches
BranchTrueFalseTotal
if ($call =~ /gonal$/) { } 20 1 21
elsif ($call eq 'triangular') { } 0 1 1
elsif ($call eq 'square') { } 1 0 1
64 20 my $N = _polygon_name_to_number( $call );
65 20 ▶ return unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 0 20 20
66 20 $_[0]->($N);
67 } elsif( $call eq 'triangular' ) {
68 0 $_[0]->(3);
69 } elsif( $call eq 'square' ) {
70 1 $_[0]->(4);
71 } else {
72 0 return;
73 }
74 }
75  
76 =head1 SYNOPSIS
77  
78 use Graph::Geometric;
79  
80 # Generate a truncated regular icosahedron
81 my $g = icosahedron->truncated;
82  
83 # Count the faces
84 print scalar $g->faces;
85  
86 =head1 DESCRIPTION
87  
88 C<Graph::Geometric> is an extension of L<Graph> to support working with geometric (topologic) graphs.
89 In addition to vertices and edges, C<Graph::Geometric> has a concept of faces to ease handling of geometric graphs.
90 C<Graph::Geometric> does not provide coordinates for vertices as it is supposed to be used for topology analysis of geometric shapes.
91  
92 As of now, C<Graph::Geometric> does not allow for arbitrary graph construction.
93 Geometric graphs have to be built from simple polyhedra (constructors listed below) or derived from them by using modifiers such as stellation or truncation.
94 Removal of vertices and faces is also supported.
95  
96 =head2 ON THE STABILITY OF API
97  
98 As C<Graph::Geometric> is in its early stages of development, not much of API stability can be promised.
99 In particular, method names are likely to be changed for the sake of homogeneity.
100 Names of generated vertices and order of faces returned by C<faces()> as well are likely to change.
101 Some syntax sugar may also appear.
102  
103 =head1 CONSTRUCTORS
104  
105 =head2 C<antiprism( $N )>
106  
107 Given N, creates an N-gonal antiprism.
108 If N is not given, returns a code reference to itself.
109  
110 =cut
111  
112 sub antiprism
113 0 ▶{
Subroutine antiprism: not called CC=3 SCAR=24.8
Pod documented
114 0 my( $N ) = @_;
115 0 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 0 0 0
116  
117 0 my @vertices = _names( $N * 2 );
118  
119 # Cap faces
120 0 my @F1 = map { $vertices[$_] } grep { !($_ % 2) } 0..($N*2-1);
121 0 my @F2 = map { $vertices[$_] } grep { $_ % 2 } 0..($N*2-1);
122  
123 0 my $self = Graph::Undirected->new;
124 0 $self->add_vertices( @vertices );
125  
126 0 $self->add_cycle( @F1 );
127 0 $self->add_cycle( @F2 );
128 0 $self->add_cycle( @vertices );
129  
130 0 my @faces = ( Set::Scalar->new( @F1 ), Set::Scalar->new( @F2 ) );
131 0 for my $i (0..($N-1)) {
132 0 push @faces, Set::Scalar->new( map { $vertices[($i*2+$_) % ($N*2)] } 0..2 );
133 0 push @faces, Set::Scalar->new( map { $vertices[($i*2+$_) % ($N*2)] } 1..3 );
134 }
135  
136 0 $self->set_graph_attribute( 'constructor', 'antiprism' );
137 0 $self->set_graph_attribute( 'faces', \@faces );
138 0 return bless $self;
139 }
140  
141 =head2 C<bifrustum( $N )>
142  
143 Given N, creates an N-gonal bifrustum.
144 If N is not given, returns a code reference to itself.
145 Since C<Graph::Geometric> does not provide coordinates, bifrustum is simply a prism with side faces cut in half.
146  
147 =cut
148  
149 sub bifrustum
150 6 ▶{
Subroutine bifrustum: called CC=9 SCAR=22.0
Pod documented
151 6 my( $N ) = @_;
152 6 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 2 4 6
153  
154 4 my $prism = prism( $N );
155  
156 # Find top and bottom faces by the number of vertices in them
157 # FIXME: The following is unstable in cubes
158 4 my( $F1, $F2 ) = grep { scalar( @$_ ) == $N } $prism->faces;
159  
160 # Select size edges, Graph::subgraph() does not work somewhy
161 4 my @side_edges;
162 4 for ($prism->edges) {
163 93 my $in_F1 = (Set::Scalar->new( @$F1 ) * Set::Scalar->new( @$_ ))->size;
164 93 my $in_F2 = (Set::Scalar->new( @$F2 ) * Set::Scalar->new( @$_ ))->size;
165 93 ▶ push @side_edges, $_ if $in_F1 && $in_F2;
Branch: 1 branch
BranchTrueFalseTotal
if $in_F1 and $in_F2 31 62 93
Condition100%3/3
$in_F1 and $in_F2
!ll&&!rl&&r
313131
MC/DC100%2/2
$in_F1 and $in_F2
$in_F1 $in_F2
Truth table100%3/3
A and B
A= $in_F1B= $in_F2
ABresult
0X0
100
111
166 }
167  
168 # Carve side edges
169 4 for( @side_edges ) {
170 31 $prism->carve_edge( @$_ );
171 }
172  
173 # Align vertices in both faces
174 4 my @F1 = $prism->_cycle_in_order( @$F1 );
175 4 my @F2;
176 4 for my $vertex (@F1) {
177 31 ▶ my( $edge ) = grep { $_->[0] eq $vertex || $_->[1] eq $vertex } @side_edges;
Condition100%3/3
$_->[0] eq $vertex || $_->[1] eq $vertex
l!l&&r!l&&!r
1318230
MC/DC100%2/2
$_->[0] eq $vertex || $_->[1] eq $vertex
$_->[0] eq $vertex $_->[1] eq $vertex
Truth table100%3/3
A || B
A= $_->[0] eq $vertexB= $_->[1] eq $vertex
ABresult
1X1
011
000
178 31 push @F2, grep { $_ ne $vertex } @$edge;
179 }
180  
181 # Carve all side faces
182 4 for (0..($N-1)) {
183 31 $prism->carve_face( join( '', sort ( $F1[$_], $F2[$_] ) ),
184 join( '', sort ( $F1[($_+1) % $N], $F2[($_+1) % $N] ) ) );
185 }
186  
187 4 $prism->set_graph_attribute( 'constructor', 'bifrustum' );
188  
189 4 return $prism;
190 }
191  
192 =head2 C<bipyramid( $N )>
193  
194 Given N, creates an N-gonal bipyramid.
195 If N is not given, returns a code reference to itself.
196  
197 =cut
198  
199 sub bipyramid
200 4 ▶{
Subroutine bipyramid: called CC=2 SCAR=6.9
Pod documented
201 4 my( $N ) = @_;
202 4 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 3 4
203  
204 3 my $pyramid = pyramid( $N );
205 3 my( $base ) = $pyramid->faces;
206 3 $pyramid->stellate( $base );
207 3 $pyramid->set_graph_attribute( 'constructor', 'bipyramid' );
208 3 return $pyramid;
209 }
210  
211 =head2 C<cucurbituril( $N )>
212  
213 Given N, creates a geometric graph representing chemical structure of cucurbit[N]uril.
214 Cucurbiturils do not exacly fit the definition of polyhedra, but have nevertheless interesting structures.
215 If N is not given, returns a cucurbit[5]uril, the smallest naturally occurring cucurbituril.
216  
217 =cut
218  
219 sub cucurbituril
220 0 ▶{
Subroutine cucurbituril: not called CC=3 SCAR=24.8
Pod documented
221 0 my( $N ) = @_;
222 0 ▶ $N = 5 unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 0 0 0
223  
224 0 my @vertices = _names( $N * 10 );
225  
226 0 my $self = Graph::Undirected->new;
227 0 $self->add_vertices( @vertices );
228  
229 # Cap faces
230 0 my( @CAP1, @CAP2 );
231  
232 0 my @faces;
233  
234 # For each of the clycouril units
235 0 for (0..($N-1)) {
236 0 my @F51 = ( @vertices[($_*10) .. ($_*10+4)] );
237 0 my @F52 = ( @vertices[($_*10+4) .. ($_*10+7)], $vertices[$_*10] );
238 0 my @F8 = ( @vertices[($_*10+3) .. ($_*10+5)],
239 $vertices[$_*10+9],
240 $vertices[(($_+1)*10+7) % ($N * 10)],
241 $vertices[(($_+1)*10) % ($N * 10)],
242 $vertices[(($_+1)*10+1) % ($N * 10)],
243 $vertices[$_*10+8] );
244 0 $self->add_cycle( @F51 );
245 0 $self->add_cycle( @F52 );
246 0 $self->add_cycle( @F8 );
247 0 push @faces, Set::Scalar->new( @F51 ),
248 Set::Scalar->new( @F52 ),
249 Set::Scalar->new( @F8 );
250  
251 0 push @CAP1, @vertices[($_*10+1)..($_*10+3)], $vertices[$_*10+8];
252 0 push @CAP2, $vertices[$_*10+9], @vertices[($_*10+5)..($_*10+7)];
253 }
254  
255 0 @faces = ( Set::Scalar->new( @CAP1 ),
256 Set::Scalar->new( @CAP2 ),
257 @faces );
258  
259 0 $self->set_graph_attribute( 'constructor', 'cucurbituril' );
260 0 $self->set_graph_attribute( 'faces', \@faces );
261  
262 0 return bless $self;
263 }
264  
265 =head2 C<cupola( $N )>
266  
267 Given N, creates an N-gonal cupola.
268 If N is not given, returns a code reference to itself.
269  
270 =cut
271  
272 sub cupola
273 3 ▶{
Subroutine cupola: called CC=3 SCAR=11.0
Pod documented
274 3 my( $N ) = @_;
275 3 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 2 3
276  
277 2 my $prism = prism( $N*2 );
278 2 my( $face ) = grep { scalar( @$_ ) == $N*2 } $prism->faces;
279 2 my @face = $prism->_cycle_in_order( @$face );
280 2 ▶ while( @face ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@face) 10 2 12
281 10 $prism->delete_edge( shift @face, shift @face );
282 }
283 2 $prism->set_graph_attribute( 'constructor', 'cupola' );
284 2 return $prism;
285 }
286  
287 =head2 C<dodecahedron()>
288  
289 Creates a regular dodecahedron.
290  
291 =cut
292  
293 sub dodecahedron()
294 1 ▶{
Subroutine dodecahedron: called CC=1 SCAR=0.0
Pod documented
295 1 my $pt = trapezohedron( 5 );
296 1 $pt->truncate( 'A', 'B' );
297 1 $pt->set_graph_attribute( 'constructor', 'dodecahedron' );
298 1 return $pt;
299 }
300  
301 =head2 C<gyrobicupola( $N )>
302  
303 Given N, creates an N-gonal gyrobicupola.
304 If N is not given, returns a code reference to itself.
305 Implementation detail: gyrobicupola is constructed by creating a bifrustum and removing every second edge on top and bottom faces.
306  
307 =cut
308  
309 sub gyrobicupola
310 2 ▶{
Subroutine gyrobicupola: called CC=6 SCAR=17.9
Pod documented
311 2 my( $N ) = @_;
312 2 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 1 2
313  
314 1 my $bifrustum = bifrustum( $N*2 );
315  
316 # All side vertices, and only them, have degree of 4
317 my @side_vertices =
318 1 $bifrustum->_cycle_in_order( grep { $bifrustum->degree( $_ ) == 4 }
319 $bifrustum->vertices );
320  
321 # Top and bottom faces consist only of vertices of degree 3
322 1 ▶ my( $F1, $F2 ) = grep { all { $bifrustum->degree( $_ ) == 3 } @$_ }
Subroutine __ANON__: called CC=1 SCAR=0.0
323 $bifrustum->faces;
324  
325 # Collect face vertices in the same order
326 1 my( @F1, @F2 );
327 1 for my $vertex (@side_vertices) {
328 10 my( $v1, $v2 ) = grep { $bifrustum->degree( $_ ) == 3 }
329 $bifrustum->neighbours( $vertex );
330 10 ▶ ( $v1, $v2 ) = ( $v2, $v1 ) if grep { $_ eq $v2 } @$F1;
Branch: 1 branch
BranchTrueFalseTotal
if grep {$_ eq $v2;} @$F1 5 5 10
331 10 push @F1, $v1;
332 10 push @F2, $v2;
333 }
334  
335 1 push @F2, shift @F2;
336 1 ▶ while( @F1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@F1) 5 1 6
337 5 $bifrustum->delete_edge( shift @F1, shift @F1 );
338 }
339 1 ▶ while( @F2 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@F2) 5 1 6
340 5 $bifrustum->delete_edge( shift @F2, shift @F2 );
341 }
342  
343 1 $bifrustum->set_graph_attribute( 'constructor', 'gyrobicupola' );
344  
345 1 return $bifrustum;
346 }
347  
348 =head2 C<icosahedron()>
349  
350 Creates a regular icosahedron.
351  
352 =cut
353  
354 sub icosahedron()
355 1 ▶{
Subroutine icosahedron: called CC=1 SCAR=0.0
Pod documented
356 1 return dodecahedron->dual;
357 }
358  
359 =head2 C<icosidodecahedron()>
360  
361 Creates an icosidodecahedron.
362  
363 =cut
364  
365 sub icosidodecahedron()
366 0 ▶{
Subroutine icosidodecahedron: not called CC=1 SCAR=6.9
Pod documented
367 0 return dodecahedron->rectify;
368 }
369  
370 =head2 C<octahedron()>
371  
372 Creates a regular octahedron.
373  
374 =cut
375  
376 sub octahedron()
377 2 ▶{
Subroutine octahedron: called CC=1 SCAR=0.0
Pod documented
378 2 return bipyramid( 4 );
379 }
380  
381 =head2 C<orthobicupola( $N )>
382  
383 Given N, creates an N-gonal orthobicupola.
384 If N is not given, returns a code reference to itself.
385 Implementation detail: orthobicupola is constructed by creating a bifrustum and removing every second edge on top and bottom faces.
386  
387 =cut
388  
389 sub orthobicupola
390 2 ▶{
Subroutine orthobicupola: called CC=6 SCAR=17.9
Pod documented
391 2 my( $N ) = @_;
392 2 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 1 2
393  
394 1 my $bifrustum = bifrustum( $N*2 );
395  
396 # All side vertices, and only them, have degree of 4
397 my @side_vertices =
398 1 $bifrustum->_cycle_in_order( grep { $bifrustum->degree( $_ ) == 4 }
399 $bifrustum->vertices );
400  
401 # Top and bottom faces consist only of vertices of degree 3
402 1 ▶ my( $F1, $F2 ) = grep { all { $bifrustum->degree( $_ ) == 3 } @$_ }
Subroutine __ANON__: called CC=1 SCAR=0.0
403 $bifrustum->faces;
404  
405 # Collect face vertices in the same order
406 1 my( @F1, @F2 );
407 1 for my $vertex (@side_vertices) {
408 10 my( $v1, $v2 ) = grep { $bifrustum->degree( $_ ) == 3 }
409 $bifrustum->neighbours( $vertex );
410 10 ▶ ( $v1, $v2 ) = ( $v2, $v1 ) if grep { $_ eq $v2 } @$F1;
Branch: 1 branch
BranchTrueFalseTotal
if grep {$_ eq $v2;} @$F1 6 4 10
411 10 push @F1, $v1;
412 10 push @F2, $v2;
413 }
414  
415 1 ▶ while( @F1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@F1) 5 1 6
416 5 $bifrustum->delete_edge( shift @F1, shift @F1 );
417 }
418 1 ▶ while( @F2 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@F2) 5 1 6
419 5 $bifrustum->delete_edge( shift @F2, shift @F2 );
420 }
421  
422 1 $bifrustum->set_graph_attribute( 'constructor', 'orthobicupola' );
423 1 return $bifrustum;
424 }
425  
426 =head2 C<prism( $N )>
427  
428 Given N, creates an N-gonal prism.
429 If N is not given, returns a code reference to itself.
430  
431 =cut
432  
433 sub prism
434 30 ▶{
Subroutine prism: called CC=3 SCAR=11.0
Pod documented
435 30 my( $N ) = @_;
436 30 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 12 18 30
437  
438 18 my @vertices = _names( $N * 2 );
439 18 my @F1 = @vertices[0..($N-1)];
440 18 my @F2 = @vertices[$N..$#vertices];
441  
442 18 my $self = Graph::Undirected->new;
443 18 my @faces;
444 18 $self->add_cycle( @F1 );
445 18 $self->add_cycle( @F2 );
446 18 push @faces, Set::Scalar->new( @F1 ), Set::Scalar->new( @F2 );
447  
448 18 for (0..($N-1)) {
449 126 $self->add_edge( $F1[$_], $F2[$_] );
450 126 push @faces, Set::Scalar->new( $F1[$_], $F2[$_],
451 $F1[($_+1) % $N],
452 $F2[($_+1) % $N] );
453 }
454  
455 18 $self->set_graph_attribute( 'constructor', 'prism' );
456 18 $self->set_graph_attribute( 'faces', \@faces );
457  
458 18 return bless $self;
459 }
460  
461 =head2 C<pyramid( $N )>
462  
463 Given N, creates an N-gonal pyramid.
464 If N is not given, returns a code reference to itself.
465  
466 =cut
467  
468 sub pyramid
469 5 ▶{
Subroutine pyramid: called CC=3 SCAR=11.0
Pod documented
470 5 my( $N ) = @_;
471 5 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 4 5
472  
473 4 my @vertices = _names( $N + 1 );
474 4 my( $apex, @base ) = @vertices;
475  
476 4 my $self = Graph::Undirected->new;
477 4 my @faces;
478 4 $self->add_vertices( @vertices );
479 4 $self->add_cycle( @base );
480 4 push @faces, Set::Scalar->new( @base );
481  
482 4 for (0..($N-1)) {
483 23 $self->add_edge( $apex, $base[$_] );
484 23 push @faces, Set::Scalar->new( $apex,
485 $base[$_],
486 $base[($_+1) % $N] );
487 }
488  
489 4 $self->set_graph_attribute( 'constructor', 'pyramid' );
490 4 $self->set_graph_attribute( 'faces', \@faces );
491  
492 4 return bless $self;
493 }
494  
495 =head2 C<rhombic_dodecahedron()>
496  
497 Creates a rhombic dodecahedron.
498  
499 =cut
500  
501 sub rhombic_dodecahedron()
502 1 ▶{
Subroutine rhombic_dodecahedron: called CC=1 SCAR=0.0
Pod documented
503 1 return octahedron->rectify->dual;
504 }
505  
506 =head2 C<rotunda( $N )>
507  
508 Given N, creates an N-gonal rotunda.
509 If N is not given, returns a code reference to itself.
510  
511 =cut
512  
513 sub rotunda
514 2 ▶{
Subroutine rotunda: called CC=5 SCAR=16.2
Pod documented
515 2 my( $N ) = @_;
516 2 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 1 2
517  
518 1 my $cupola = cupola( $N );
519 1 my $face;
520 1 for ($cupola->faces) {
521 1 ▶ next unless scalar( @$_ ) == $N;
Branch: 1 branch
BranchTrueFalseTotal
unless scalar @$_ == $N 0 1 1
522 1 ▶ next unless sum( map { $cupola->degree($_) } @$_ ) == $N*4;
Branch: 1 branch
BranchTrueFalseTotal
unless &sum(map({$cupola->degree($_);} @$_)) == $N * 4 0 1 1
523 1 $face = $_;
524 1 last;
525 }
526 1 $cupola->face_dualify( @$face );
527 1 $cupola->set_graph_attribute( 'constructor', 'rotunda' );
528  
529 1 return $cupola;
530 }
531  
532 =head2 C<tetrahedron()>
533  
534 Creates a regular tetrahedron.
535  
536 =cut
537  
538 sub tetrahedron()
539 0 ▶{
Subroutine tetrahedron: not called CC=4 SCAR=30.0
Pod documented
540 0 my @vertices = 'A'..'D';
541  
542 0 my $self = Graph::Undirected->new;
543 0 $self->add_vertices( @vertices );
544  
545 0 my @faces;
546 0 for my $v1 (@vertices) {
547 0 for my $v2 (@vertices) {
548 0 ▶ next if $v1 eq $v2;
Branch: 1 branch
BranchTrueFalseTotal
if $v1 eq $v2 0 0 0
549 0 $self->add_edge( $v1, $v2 );
550 }
551  
552 0 push @faces, Set::Scalar->new( grep { $_ ne $v1 } @vertices );
553 }
554  
555 0 $self->set_graph_attribute( 'constructor', 'pyramid' );
556 0 $self->set_graph_attribute( 'faces', \@faces );
557  
558 0 return bless $self; # TODO: Bless with class?
559 }
560  
561 =head2 C<trapezohedron( $N )>
562  
563 Creates an N-gonal trapezohedron.
564 If N is not given, returns a code reference to itself.
565  
566 =cut
567  
568 sub trapezohedron
569 3 ▶{
Subroutine trapezohedron: called CC=5 SCAR=16.1
Pod documented
570 3 my( $N ) = @_;
571 3 ▶ return __SUB__ unless defined $N;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $N 1 2 3
572  
573 2 my @vertices = _names( $N * 2 + 2 );
574  
575 2 my $self = Graph::Undirected->new;
576 2 $self->add_vertices( @vertices );
577 2 my( $apex1, $apex2, @equator ) = @vertices;
578 2 $self->add_cycle( @equator );
579  
580 2 for (0..$#equator) {
581 20 ▶ $self->add_edge( $equator[$_],
Branch: 1 branch
BranchTrueFalseTotal
($_ + 1) % 2 ? : 10 10 20
582 (($_+1) % 2 ? $apex1 : $apex2) );
583 }
584  
585 2 my @faces;
586 2 for my $i (0..$N-1) {
587 push @faces, Set::Scalar->new( $apex1,
588 10 map { $equator[($i*2+$_) % ($N*2)] } 0..2 );
589 push @faces, Set::Scalar->new( $apex2,
590 10 map { $equator[($i*2+$_) % ($N*2)] } 1..3 );
591 }
592  
593 2 $self->set_graph_attribute( 'constructor', 'trapezohedron' );
594 2 $self->set_graph_attribute( 'faces', \@faces );
595 2 return bless $self; # TODO: Bless with class?
596 }
597  
598 =head1 ACCESSORS
599  
600 =head2 C<faces( @vertices )>
601  
602 Returns an array of arrays listing vertices in each of polyhedron's faces.
603 Vertex lists are returned sorted, they do not maintain the order of vertices in faces.
604 Experimental: given a list of vertices, select only faces containing all of them.
605  
606 =cut
607  
608 sub faces
609 111 ▶{
Subroutine faces: called CC=4 SCAR=13.9
Pod documented
610 111 my( $self, @vertices ) = @_;
611  
612 111 my @faces = @{$self->get_graph_attribute( 'faces' )};
613 111 ▶ if( @vertices ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@vertices) 28 83 111
614 # Set::Scalar::is_subset() fails as of 1.29 for unknown reasons
615 28 my @faces_now;
616 28 for my $face (@faces) {
617 278 ▶ push @faces_now, $face if all { $face->has( $_ ) } @vertices;
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
BranchTrueFalseTotal
if &all(sub { $face->has($_); } , @vertices) 96 182 278
618 }
619 28 @faces = @faces_now;
620 }
621  
622 111 return map { [ sort $_->members ] } @faces;
623 }
624  
625 =head1 GRAPH METHODS
626  
627 =head2 C<deep_copy()>
628  
629 Creates a deep copy of a Graph::Geometric object.
630  
631 =cut
632  
633 sub deep_copy
634 4 ▶{
Subroutine deep_copy: called CC=1 SCAR=0.0
Pod documented
635 4 my( $self ) = @_;
636 4 my $copy = $self->SUPER::deep_copy;
637 4 return bless $copy; # FIXME: Bless with the same class
638 }
639  
640 =head2 C<delete_edge( $u, $v )>
641  
642 Deletes an edge by merging its vertices.
643 Given edge is assumed to exist, a check will be implemented later.
644 Modifies and returns the original object.
645  
646 =cut
647  
648 sub delete_edge
649 30 ▶{
Subroutine delete_edge: called CC=9 SCAR=22.0
Pod documented
650 30 my( $self, $vertex1, $vertex2 ) = @_;
651 30 ▶ return $self unless $self->has_edge( $vertex1, $vertex2 );
Branch: 1 branch
BranchTrueFalseTotal
unless $self->has_edge($vertex1, $vertex2) 0 30 30
652  
653 30 my @neighbours = ( $self->neighbours( $vertex1 ),
654 $self->neighbours( $vertex2 ) );
655 30 $self->SUPER::delete_vertex( $vertex1 ); # delete_vertices() does not work
656 30 $self->SUPER::delete_vertex( $vertex2 );
657  
658 30 my $vertex = join '', sort ( $vertex1, $vertex2 );
659 30 $self->_ensure_vertices_do_not_exist( $vertex );
660  
661 30 for (@neighbours) {
662 180 ▶ next if $_ eq $vertex1;
Branch: 1 branch
BranchTrueFalseTotal
if $_ eq $vertex1 30 150 180
663 150 ▶ next if $_ eq $vertex2;
Branch: 1 branch
BranchTrueFalseTotal
if $_ eq $vertex2 30 120 150
664 120 $self->add_edge( $vertex, $_ );
665 }
666  
667 30 my @faces;
668 30 for (@{$self->get_graph_attribute( 'faces' )}) {
669 560 ▶ if( $_->has( $vertex1 ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($_->has($vertex1)) 90 470 560
670 90 $_->delete( $vertex1 );
671 90 $_->insert( $vertex );
672 }
673 560 ▶ if( $_->has( $vertex2 ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($_->has($vertex2)) 90 470 560
674 90 $_->delete( $vertex2 );
675 90 $_->insert( $vertex );
676 }
677 560 ▶ push @faces, $_ if $_->size > 2; # Exclude collapsed faces
Branch: 1 branch
BranchTrueFalseTotal
if $_->size > 2 560 0 560
678 }
679  
680 30 $self->delete_graph_attribute( 'constructor' );
681 30 $self->set_graph_attribute( 'faces', \@faces );
682  
683 30 return $self;
684 }
685  
686 =head2 C<delete_face( $face )>
687  
688 Deletes a given face from polyhedra.
689 A face is defined by an unordered list of vertices.
690 Does nothing if a given face does not exist.
691 Modifies and returns the original object.
692  
693 =cut
694  
695 sub delete_face
696 0 ▶{
Subroutine delete_face: not called CC=6 SCAR=37.4
Pod documented
697 0 my( $self, $face ) = @_;
698 0 ▶ return $self unless $self->has_face( $face );
Branch: 1 branch
BranchTrueFalseTotal
unless $self->has_face($face) 0 0 0
699  
700 0 my $vertex = join '', sort @$face;
701 0 $self->_ensure_vertices_do_not_exist( $vertex );
702 0 $self->add_vertex( $vertex );
703  
704 0 for my $member (@$face) {
705 0 for my $neighbour ($self->neighbours( $member )) {
706 0 $self->add_edge( $neighbour, $vertex );
707 }
708 }
709  
710 0 $self->SUPER::delete_vertices( @$face );
711  
712 0 my $face_set = Set::Scalar( @$face );
713 0 my @faces = grep { !$face_set->is_equal( $_ ) }
714 0 @{$self->get_graph_attribute( 'faces' )};
715 0 for (@faces) {
716 0 ▶ next if $face_set->is_disjoint( $_ );
Branch: 1 branch
BranchTrueFalseTotal
if $face_set->is_disjoint($_) 0 0 0
717 0 $_->delete( @$face );
718 0 $_->insert( $vertex );
719 }
720  
721 0 $self->delete_graph_attribute( 'constructor' );
722 0 $self->set_graph_attribute( 'faces', \@faces );
723  
724 0 return $self;
725 }
726  
727 =head2 C<delete_vertex( $v )>
728  
729 Handles vertex deletion by merging neighbouring faces.
730 Modifies and returns the original object.
731  
732 =cut
733  
734 sub delete_vertex
735 28 ▶{
Subroutine delete_vertex: called CC=2 SCAR=6.9
Pod documented
736 28 my( $self, $vertex ) = @_;
737 28 $self->SUPER::delete_vertex( $vertex );
738  
739 374 my @containing_faces = grep { $_->has( $vertex ) }
740 28 @{$self->get_graph_attribute( 'faces' )};
741 374 my @other_faces = grep { !$_->has( $vertex ) }
742 28 @{$self->get_graph_attribute( 'faces' )};
743  
744 28 ▶ return $self unless @containing_faces;
Branch: 1 branch
BranchTrueFalseTotal
unless @containing_faces 0 28 28
745  
746 28 my $new_face = sum( @containing_faces );
747 28 $new_face->delete( $vertex );
748  
749 28 $self->delete_graph_attribute( 'constructor' );
750 28 $self->set_graph_attribute( 'faces', [ @other_faces, $new_face ] );
751  
752 28 return $self;
753 }
754  
755 =head2 C<has_face( $face )>
756  
757 Returns true if a given face exists, false otherwise.
758  
759 =cut
760  
761 sub has_face
762 3 ▶{
Subroutine has_face: called CC=1 SCAR=0.0
Pod documented
763 3 my( $self, $face ) = @_;
764 3 $face = join ',', sort @$face;
765 25 ▶ return any { join( ',', sort @$_ ) eq $face }
Subroutine __ANON__: called CC=1 SCAR=0.0
766 3 @{$self->get_graph_attribute( 'faces' )};
767 }
768  
769 =head1 GEOMETRIC METHODS
770  
771 =cut
772  
773 sub carve_edge
774 87 ▶{
Subroutine carve_edge: called CC=4 SCAR=13.9
Pod undocumented
775 87 my( $self, @edge ) = @_;
776  
777 87 $self->SUPER::delete_edge( @edge );
778 87 my $vertex = join '', sort @edge;
779 87 $self->_ensure_vertices_do_not_exist( $vertex );
780  
781 # Add new vertex in between the given ones
782 87 $self->add_path( $edge[0], $vertex, $edge[1] );
783  
784 # Update all faces containing the edge to also have the new vertex
785 87 for (@{$self->get_graph_attribute( 'faces' )}) {
786 737 ▶ next unless $_->has( $edge[0] ) && $_->has( $edge[1] );
Branch: 1 branch
BranchTrueFalseTotal
unless $_->has($edge[0]) and $_->has($edge[1]) 563 174 737
Condition100%3/3
$_->has($edge[0]) and $_->has($edge[1])
!ll&&!rl&&r
447116174
MC/DC100%2/2
$_->has($edge[0]) and $_->has($edge[1])
$_->has($edge[0]) $_->has($edge[1])
Truth table100%3/3
A and B
A= $_->has($edge[0])B= $_->has($edge[1])
ABresult
0X0
100
111
787 174 $_->insert( $vertex );
788 }
789  
790 87 $self->delete_graph_attribute( 'constructor' );
791  
792 87 return $self;
793 }
794 =head2 C<carve_face( $u, $v )>
795  
796 Given a graph and a pair of vertices lying on the same face, add a new edge splitting the face in two.
797 Subroutine dies if there is no face containing both vertices.
798  
799 =cut
800  
801 sub carve_face
802 134 ▶{
Subroutine carve_face: called CC=8 SCAR=20.8
Pod undocumented
803 134 my( $self, @edge ) = @_;
804 134 ▶ return $self if $self->has_edge( @edge ); # has edge already
Branch: 1 branch
BranchTrueFalseTotal
if $self->has_edge(@edge) 1 133 134
805  
806 # Find a face containing both vertices, filter it out from face list
807 133 my @faces;
808 my $face;
809 133 for (@{$self->get_graph_attribute( 'faces' )}) {
810 1558 ▶ if( $_->has( $edge[0] ) && $_->has( $edge[1] ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($_->has($edge[0]) and $_->has($edge[1])) { } 133 1425 1558
Condition100%3/3
$_->has($edge[0]) and $_->has($edge[1])
!ll&&!rl&&r
1150275133
MC/DC100%2/2
$_->has($edge[0]) and $_->has($edge[1])
$_->has($edge[0]) $_->has($edge[1])
Truth table100%3/3
A and B
A= $_->has($edge[0])B= $_->has($edge[1])
ABresult
0X0
100
111
811 133 $face = $_;
812 } else {
813 1425 push @faces, $_;
814 }
815 }
816 133 ▶ if( !$face ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($face) 0 133 133
817 0 local $" = ' and ';
818 0 die "there is no face having both @edge vertices\n";
819 }
820 133 my @face = $self->_cycle_in_order( $face->members );
821  
822 133 $self->add_edge( @edge );
823  
824 # "Rewind" the vertices in cycle to start with the first joined vertex
825 133 ▶ while( $face[0] ne $edge[0] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($face[0] ne $edge[0]) 174 133 307
826 174 push @face, shift @face;
827 }
828 # Store all vertices in @F1 until the second joined vertex is reached
829 133 my @F1;
830 133 ▶ while( $face[0] ne $edge[1] ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($face[0] ne $edge[1]) 436 133 569
831 436 push @F1, shift @face;
832 }
833 133 push @F1, $edge[1];
834 133 my @F2 = ( @face, $edge[0] );
835  
836 133 push @faces, Set::Scalar->new( @F1 ), Set::Scalar->new( @F2 );
837 133 $self->set_graph_attribute( 'faces', \@faces );
838  
839 133 $self->delete_graph_attribute( 'constructor' );
840  
841 133 return $self;
842 }
843  
844 =head2 C<elongate( $cycle )>
845  
846 Elongate the given polyhedron.
847 If given a face, elongates the polyhedron by extruding it.
848 If given a non-face cycle, elongates the polyhedron by cutting accross the given cycle and inserting a prism in between.
849 If not given anything, attempts to elongate according to the type of given polyhedron.
850 I.e., pyramids are elongated by extruding their faces and so on.
851 Subroutine dies if it encounters a polyhedron of a type unknown to it.
852  
853 =cut
854  
855 sub elongate
856 4 ▶{
Subroutine elongate: called CC=33 SCAR=45.2
Pod documented
857 4 my( $self, $cycle ) = @_;
858  
859 4 ▶ if( $cycle && $self->has_face( $cycle ) ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($cycle and $self->has_face($cycle)) { } 1 3 4
elsif ($cycle) { } 2 1 3
Condition100%3/3
$cycle and $self->has_face($cycle)
!ll&&!rl&&r
121
MC/DC100%2/2
$cycle and $self->has_face($cycle)
$cycle $self->has_face($cycle)
Truth table100%3/3
A and B
A= $cycleB= $self->has_face($cycle)
ABresult
0X0
100
111
860 # Elongate along the given face
861 1 my @face = $self->_cycle_in_order( @$cycle );
862 1 my @vertices = map { $_ . 'e' } @face;
863 1 $self->_ensure_vertices_do_not_exist( @vertices );
864 1 $self->add_cycle( @vertices );
865  
866 1 my @faces;
867 1 for my $face (@{$self->get_graph_attribute( 'faces' )}) {
868 7 ▶ next if join( '', sort $face->members ) eq join( '', sort @face );
Branch: 1 branch
BranchTrueFalseTotal
if join("", sort($face->members)) eq join("", sort(@face)) 1 6 7
869 6 push @faces, $face;
870 }
871  
872 1 for my $i (0..$#face) {
873 5 $self->add_edge( $face[$i], $face[$i] . 'e' );
874 5 push @faces, Set::Scalar->new( $face[$i],
875 $face[$i] . 'e',
876 $face[($i+1) % @face],
877 $face[($i+1) % @face] . 'e' );
878 }
879 1 push @faces, Set::Scalar->new( @vertices );
880  
881 1 $self->set_graph_attribute( 'faces', \@faces );
882 } elsif( $cycle ) {
883 # Elongate along the given cut
884 2 ▶ if( !$self->has_cycle( @$cycle ) ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->has_cycle(@$cycle)) 0 2 2
885 0 die "cannot elongate nonexisting cycle\n";
886 }
887  
888 2 my @cycle = $self->_cycle_in_order( @$cycle );
889 2 my $copy = $self->copy;
890 2 for (@cycle) { $copy->SUPER::delete_vertex( $_ ) } # delete_vertices() does not work
891 2 my( $C1, $C2 ) = $copy->connected_components; # FIXME: Establish deterministic order
892  
893 2 my @vertices1 = map { $_ . '1' } @cycle;
894 2 my @vertices2 = map { $_ . '2' } @cycle; # FIXME: Check new vertices
895  
896 2 $self->add_cycle( @vertices1 );
897 2 $self->add_cycle( @vertices2 );
898  
899 2 my $cycle_set = Set::Scalar->new( @cycle );
900 2 for my $face (@{$self->get_graph_attribute( 'faces' )}) {
901 24 my @vertices = ($face * $cycle_set)->elements;
902 24 ▶ next unless @vertices;
Branch: 1 branch
BranchTrueFalseTotal
unless @vertices 2 22 24
903  
904 # The remaining vertices in a face will belong either to $C1 or $C2
905 22 my( $vertex ) = ($face - $cycle_set)->elements;
906 22 ▶ if( any { $_ eq $vertex } @$C1 ) {
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 1 branch
BranchTrueFalseTotal
if (&any(sub { $_ eq $vertex; } , @$C1)) { } 11 11 22
907 11 $face->invert( @vertices, map { $_ . '1' } @vertices );
908 } else {
909 11 $face->invert( @vertices, map { $_ . '2' } @vertices );
910 }
911 }
912  
913 2 my @new_faces;
914 2 for (0..$#cycle) {
915 11 $self->add_edge( $vertices1[$_], $vertices2[$_] );
916 11 push @new_faces, Set::Scalar->new( $vertices1[$_],
917 $vertices2[$_],
918 $vertices1[($_+1) % @cycle],
919 $vertices2[($_+1) % @cycle] );
920 }
921  
922 2 for my $cycle_vertex (@cycle) {
923 11 for my $neighbour ($self->neighbours( $cycle_vertex )) {
924 44 ▶ if( any { $_ eq $neighbour } @$C1 ) {
Subroutine __ANON__: called CC=1 SCAR=0.0
Branch: 2 branches
BranchTrueFalseTotal
if (&any(sub { $_ eq $neighbour; } , @$C1)) { } 11 33 44
elsif (&any(sub { $_ eq $neighbour; } , @$C2)) { } 11 22 33
925 11 $self->add_edge( $neighbour, $cycle_vertex . '1' );
926 108 ▶ } elsif( any { $_ eq $neighbour } @$C2 ) {
Subroutine __ANON__: called CC=1 SCAR=0.0
927 11 $self->add_edge( $neighbour, $cycle_vertex . '2' );
928 }
929 }
930 }
931  
932 2 for (@cycle) { $self->SUPER::delete_vertex( $_ ) } # delete_vertices() does not work
933 2 $self->set_graph_attribute( 'faces', [ @{$self->get_graph_attribute( 'faces' )},
934 @new_faces ] );
935 } else {
936 # Elongate according to the type of geometric figure
937 1 ▶ if( !$self->has_graph_attribute( 'constructor' ) ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->has_graph_attribute("constructor")) 0 1 1
938 0 die "unknown geometric type for elongation\n";
939 }
940  
941 1 my $constructor = $self->get_graph_attribute( 'constructor' );
942  
943 1 ▶ if( $constructor eq 'bipyramid' ) {
Branch: 4 branches
BranchTrueFalseTotal
if ($constructor eq 'bipyramid') { } 1 0 1
elsif ($constructor eq 'cupola' or $constructor eq 'pyramid' or $constructor eq 'rotunda') { } 0 0 0
elsif ($constructor eq 'gyrobicupola' or $constructor eq 'orthobicupola') { } 0 0 0
elsif ($constructor eq 'gyrobirotunda' or $constructor eq 'orthobirotunda') { } 0 0 0
944 # FIXME: May be nondeterministic for square bipyramids
945 1 my @cycle = grep { $self->degree( $_ ) == 4 } $self->vertices;
946 1 $self->elongate( \@cycle );
947 ▶ } elsif( $constructor eq 'cupola' ||
Condition0%0/6
$constructor eq "cupola" or $constructor eq "pyramid" or $constructor eq "rotunda"
l!l&&r!l&&!r
000
$constructor eq "cupola" or $constructor eq "pyramid"
l!l&&r!l&&!r
000
MC/DC0%0/3
$constructor eq "cupola" or $constructor eq "pyramid" or $constructor eq "rotunda"
$constructor eq "cupola" $constructor eq "pyramid" $constructor eq "rotunda"
Truth table0%0/4
A or B or C
A= $constructor eq "cupola"B= $constructor eq "pyramid"C= $constructor eq "rotunda"
ABCresult
1XX1
01X1
0011
0000
948 $constructor eq 'pyramid' ||
949 $constructor eq 'rotunda' ) {
950 # Elongate (extrude) the largest face
951 0 my( $face ) = sort { scalar( @$b ) <=> scalar( @$a ) } $self->faces;
952 0 $self->elongate( $face );
953 ▶ } elsif( $constructor eq 'gyrobicupola' ||
Condition0%0/3
$constructor eq "gyrobicupola" or $constructor eq "orthobicupola"
l!l&&r!l&&!r
000
MC/DC0%0/2
$constructor eq "gyrobicupola" or $constructor eq "orthobicupola"
$constructor eq "gyrobicupola" $constructor eq "orthobicupola"
Truth table0%0/3
A or B
A= $constructor eq "gyrobicupola"B= $constructor eq "orthobicupola"
ABresult
1X1
011
000
954 $constructor eq 'orthobicupola' ) {
955 # Bicupolae are elongated along cycle where every vertex belongs to two triangular faces
956 0 my %triangular_faces;
957 0 for my $face ($self->faces) {
958 0 ▶ next unless scalar( @$face ) == 3;
Branch: 1 branch
BranchTrueFalseTotal
unless scalar @$face == 3 0 0 0
959 0 for (@$face) {
960 0 ▶ $triangular_faces{$_} = 0 unless $triangular_faces{$_};
Branch: 1 branch
BranchTrueFalseTotal
unless $triangular_faces{$_} 0 0 0
961 0 $triangular_faces{$_}++;
962 }
963 }
964  
965 0 my @cycle = grep { $triangular_faces{$_} == 2 } keys %triangular_faces;
966 0 $self->elongate( \@cycle );
967 ▶ } elsif( $constructor eq 'gyrobirotunda' ||
Condition0%0/3
$constructor eq "gyrobirotunda" or $constructor eq "orthobirotunda"
l!l&&r!l&&!r
000
MC/DC0%0/2
$constructor eq "gyrobirotunda" or $constructor eq "orthobirotunda"
$constructor eq "gyrobirotunda" $constructor eq "orthobirotunda"
Truth table0%0/3
A or B
A= $constructor eq "gyrobirotunda"B= $constructor eq "orthobirotunda"
ABresult
1X1
011
000
968 $constructor eq 'orthobirotunda' ) {
969 # Birotundas should have two faces that are neither triangles nor pentagons.
970 # FIXME: Will fail with trigonal and pentagonal birotundas.
971 0 ▶ my @bases = grep { scalar( @$_ ) != 3 && scalar( @$_ ) != 5 }
Condition0%0/3
scalar @$_ != 3 && scalar @$_ != 5
!ll&&!rl&&r
000
MC/DC0%0/2
scalar @$_ != 3 && scalar @$_ != 5
scalar @$_ != 3 scalar @$_ != 5
Truth table0%0/3
A && B
A= scalar @$_ != 3B= scalar @$_ != 5
ABresult
0X0
100
111
972 $self->faces;
973 0 my @removed = uniq @bases, map { $self->neighbours( $_ ) } @bases;
974 0 my $copy = $self->copy;
975 0 for (@removed) { $copy->SUPER::delete_vertex( $_ ) }
976 0 $self->elongate( [ $copy->vertices ] );
977 } else {
978 0 die "do not know how to elongate $constructor\n";
979 }
980 }
981  
982 4 $self->delete_graph_attribute( 'constructor' );
983 4 return $self;
984 }
985  
986 sub face_dualify
987 1 ▶{
Subroutine face_dualify: called CC=4 SCAR=13.9
Pod undocumented
988 1 my( $self, @face ) = @_;
989  
990 # Remove the to-be-dualified face
991 1 my @faces;
992 1 for my $face (@{$self->get_graph_attribute( 'faces' )}) {
993 12 ▶ next if join( '', sort $face->members ) eq join( '', sort @face );
Branch: 1 branch
BranchTrueFalseTotal
if join("", sort($face->members)) eq join("", sort(@face)) 1 11 12
994 11 push @faces, $face;
995 }
996  
997 1 @face = $self->_cycle_in_order( @face );
998 1 my @new_vertices;
999 1 for (0..$#face) {
1000 5 my @edge = sort ( $face[$_], $face[($_+1) % scalar @face] );
1001 5 $self->carve_edge( @edge );
1002 5 my $vertex = join '', @edge;
1003 5 push @new_vertices, join '', @edge;
1004 5 push @faces, Set::Scalar->new( $vertex, @edge );
1005 }
1006 1 $self->add_cycle( @new_vertices );
1007 1 push @faces, Set::Scalar->new( @new_vertices );
1008  
1009 1 $self->set_graph_attribute( 'faces', \@faces );
1010 1 $self->delete_graph_attribute( 'constructor' );
1011  
1012 1 return $self;
1013 }
1014  
1015 =head2 C<rectify()>
1016  
1017 Given a polyhedron, performs its rectification.
1018 Modifies and returns the original object.
1019  
1020 =cut
1021  
1022 sub rectify
1023 4 ▶{
Subroutine rectify: called CC=4 SCAR=13.9
Pod documented
1024 4 my( $self ) = @_;
1025  
1026 # Preserve the original list of vertices
1027 4 my @vertices = $self->vertices;
1028  
1029 # Carve all the edges
1030 4 for ($self->edges) {
1031 48 $self->carve_edge( @$_ );
1032 }
1033  
1034 # Cut off the original vertices
1035 4 for my $vertex (@vertices) {
1036 # Carve all adjacent faces
1037 28 for my $face ($self->faces( $vertex )) {
1038 96 my( $A, $B ) = grep { $self->has_edge( $vertex, $_ ) } @$face;
1039 96 $self->carve_face( $A, $B );
1040 }
1041  
1042 # Delete the vertex and merge adjacent faces
1043 28 $self->delete_vertex( $vertex );
1044 }
1045  
1046 4 $self->delete_graph_attribute( 'constructor' );
1047  
1048 4 return $self;
1049 }
1050  
1051 =head2 C<stellate( @faces )>
1052  
1053 Given a polyhedron and a list of faces, performs stellation of specified faces.
1054 If no faces are given, all faces are stellated.
1055 Modifies and returns the original object.
1056  
1057 =cut
1058  
1059 sub stellate
1060 3 ▶{
Subroutine stellate: called CC=6 SCAR=17.9
Pod documented
1061 3 my( $self, @faces ) = @_;
1062 3 ▶ @faces = $self->faces unless @faces;
Branch: 1 branch
BranchTrueFalseTotal
unless @faces 0 3 3
1063  
1064 3 my @faces_now;
1065 3 for my $face ($self->faces) {
1066 16 ▶ if( grep { join( '', sort @$face ) eq join( '', sort @$_ ) } @faces ) {
Branch: 1 branch
BranchTrueFalseTotal
if (grep {join('', sort(@$face)) eq join('', sort(@$_));} @faces) { } 3 13 16
1067 # This face has been requested to be stellated
1068 3 my $center = join '', @$face;
1069 3 $self->_ensure_vertices_do_not_exist( $center );
1070 3 $self->add_vertex( $center );
1071 3 for my $vertex (@$face) {
1072 13 $self->add_edge( $center, $vertex );
1073 }
1074  
1075 3 for my $edge ($self->subgraph( $face )->edges) {
1076 13 push @faces_now, Set::Scalar->new( $center, @$edge );
1077 }
1078 } else {
1079 # This face has not been requested to be stellated
1080 13 push @faces_now, Set::Scalar->new( @$face );
1081 }
1082 }
1083  
1084 3 $self->delete_graph_attribute( 'constructor' );
1085 3 $self->set_graph_attribute( 'faces', \@faces_now );
1086  
1087 3 return $self;
1088 }
1089  
1090 =head2 C<truncate( @vertices )>
1091  
1092 Given a polyhedron and a list of vertices, performs truncation of specified vertices.
1093 If no vertices are given, all vertices are stellated.
1094 Modifies and returns the original object.
1095  
1096 =cut
1097  
1098 sub truncate
1099 2 ▶{
Subroutine truncate: called CC=6 SCAR=17.9
Pod documented
1100 2 my( $self, @vertices ) = @_;
1101 2 ▶ @vertices = $self->vertices unless @vertices;
Branch: 1 branch
BranchTrueFalseTotal
unless @vertices 1 1 2
1102  
1103 2 for my $vertex (@vertices) {
1104 # Cut all the edges
1105 14 for my $neighbour ($self->neighbours( $vertex )) {
1106 70 $self->_ensure_vertices_do_not_exist( $vertex . $neighbour );
1107 70 $self->add_edge( $neighbour, $vertex . $neighbour );
1108 }
1109  
1110 # Trim all the faces
1111 14 for my $face_id (0..scalar( $self->faces ) - 1) {
1112 327 my $face = $self->get_graph_attribute( 'faces' )->[$face_id];
1113 327 ▶ next unless $face->has( $vertex );
Branch: 1 branch
BranchTrueFalseTotal
unless $face->has($vertex) 257 70 327
1114  
1115 # Find the two neighbours of $vertex in the face
1116 70 my( $v1, $v2 ) = grep { $face->has( $_ ) } $self->neighbours( $vertex );
1117  
1118 # Connect the new vertices corresponding to edges with these neighbours
1119 70 $self->add_edge( $vertex . $v1, $vertex . $v2 );
1120  
1121 # Adjust the face
1122 70 $face->invert( $vertex, $vertex . $v1, $vertex . $v2 );
1123 }
1124  
1125 # Add new face created by trimming this one
1126 14 push @{$self->get_graph_attribute( 'faces' )},
1127 14 Set::Scalar->new( map { $vertex . $_ } $self->neighbours( $vertex ) );
1128  
1129 # Remove the vertex
1130 14 $self->SUPER::delete_vertex( $vertex );
1131 }
1132  
1133 2 $self->delete_graph_attribute( 'constructor' );
1134  
1135 2 return $self;
1136 }
1137  
1138 =head2 C<dual()>
1139  
1140 Given a polyhedron, returns its dual as a new object.
1141 The original object is not modified.
1142  
1143 =cut
1144  
1145 sub dual
1146 2 ▶{
Subroutine dual: called CC=7 SCAR=19.5
Pod documented
1147 2 my( $self ) = @_;
1148  
1149 2 my $dual = Graph::Undirected->new;
1150  
1151 # All faces become vertices
1152 2 $dual->add_vertices( map { join '', @$_ } $self->faces );
1153  
1154 2 for my $face1_id (0..scalar( $self->faces ) - 1) {
1155 26 my $face1 = $self->get_graph_attribute( 'faces' )->[$face1_id];
1156  
1157 26 my $edges = {};
1158 26 for ($self->subgraph( [$face1->members] )->edges) {
1159 108 my @edges = sort @$_;
1160 108 $edges->{$edges[0]}{$edges[1]} = 1;
1161 }
1162  
1163 26 for my $face2_id ($face1_id+1..scalar( $self->faces ) - 1) {
1164 157 my $face2 = $self->get_graph_attribute( 'faces' )->[$face2_id];
1165  
1166 # If faces share an edge, they are connected in the dual
1167 157 for ($self->subgraph( [$face2->members] )->edges) {
1168 547 my @edges = sort @$_;
1169 547 ▶ next unless $edges->{$edges[0]}{$edges[1]};
Branch: 1 branch
BranchTrueFalseTotal
unless $$edges{$edges[0]}{$edges[1]} 493 54 547
1170  
1171 54 $dual->add_edge( join( '', sort $face1->members ),
1172 join( '', sort $face2->members ) );
1173 54 last;
1174 }
1175 }
1176 }
1177  
1178 2 my @dual_faces;
1179 2 for my $vertex ($self->vertices) {
1180 408 my @faces = grep { $_->has( $vertex ) }
1181 32 @{$self->get_graph_attribute( 'faces' )};
1182 push @dual_faces,
1183 32 Set::Scalar->new( map { join '', sort $_->members } @faces );
1184 }
1185  
1186 2 $dual->set_graph_attribute( 'faces', \@dual_faces );
1187  
1188 2 return bless $dual; # TODO: Bless with a class
1189 }
1190  
1191 =head1 OPERATORS
1192  
1193 The following class methods take a single Graph::Geometric object, copy it, perform a certain operation and return the results.
1194 They allow for such syntactically sweet calls like:
1195  
1196 my $cuboctahedron1 = rectified tetragonal prism;
1197 my $cuboctahedron2 = rectified octahedron;
1198  
1199 my $truncated_icosahedron = truncated icosahedron;
1200  
1201 =head2 C<elongated()>
1202  
1203 Copies the given polyhedron, elongates it and returns the elongated polyhedron.
1204 This subroutine does not accept any parameters, thus if nonstandard elongation is wanted, other methods have to be used.
1205  
1206 =cut
1207  
1208 sub elongated($)
1209 0 ▶{
Subroutine elongated: not called CC=1 SCAR=6.9
Pod documented
1210 0 return $_[0]->deep_copy->elongate;
1211 }
1212  
1213 =head2 C<rectified()>
1214  
1215 Copies the given polyhedron, rectifies it and returns the rectified polyhedron.
1216  
1217 =cut
1218  
1219 sub rectified($)
1220 3 ▶{
Subroutine rectified: called CC=1 SCAR=0.0
Pod documented
1221 3 return $_[0]->deep_copy->rectify;
1222 }
1223  
1224 =head2 C<stellated()>
1225  
1226 Copies the given polyhedron, stellates all its faces and returns the stellated polyhedron.
1227  
1228 =cut
1229  
1230 sub stellated($)
1231 0 ▶{
Subroutine stellated: not called CC=1 SCAR=6.9
Pod documented
1232 0 return $_[0]->deep_copy->stellate;
1233 }
1234  
1235 =head2 C<truncated()>
1236  
1237 Copies the given polyhedron, truncates all its vertices and returns the truncated polyhedron.
1238  
1239 =cut
1240  
1241 sub truncated($)
1242 1 ▶{
Subroutine truncated: called CC=1 SCAR=0.0
Pod documented
1243 1 return $_[0]->deep_copy->truncate;
1244 }
1245  
1246 =head1 PROPERTIES
1247  
1248 =head2 C<is_isogonal()>
1249  
1250 Tests if a given polyhedron is isogonal (vertex-transitive) by checking whether all its vertices belong to the same symmetry orbit.
1251 Requires L<Graph::Nauty> to locate symmetry orbits of a graph.
1252  
1253 =cut
1254  
1255 sub is_isogonal
1256 0 ▶{
Subroutine is_isogonal: not called CC=1 SCAR=6.9
Pod documented
1257 0 my( $self ) = @_;
1258 0 require Graph::Nauty;
1259 0 ▶ return scalar( Graph::Nauty::orbits( $self, sub { return '' } ) ) == 1;
Subroutine __ANON__: not called CC=1 SCAR=6.9
1260 }
1261  
1262 =head2 C<is_isotoxal()>
1263  
1264 Tests if a given polyhedron is isotoxal (edge-transitive) by checking whether all its edges belong to the same symmetry orbit.
1265 Requires L<Graph::Nauty> to locate symmetry orbits of a graph.
1266 Implementation detail: figure is rectified and tested for being isogonal.
1267  
1268 =cut
1269  
1270 sub is_isotoxal
1271 0 ▶{
Subroutine is_isotoxal: not called CC=1 SCAR=6.9
Pod documented
1272 0 my( $self ) = @_;
1273 0 return $self->rectified->is_isogonal;
1274 }
1275  
1276 =head2 C<is_isohedral()>
1277  
1278 Tests if a given polyhedron is isohedral (face-transitive) by checking whether all its faces belong to the same symmetry orbit.
1279 Requires L<Graph::Nauty> to locate symmetry orbits of a graph.
1280 Implementation detail: dual of a figure is tested for being isogonal.
1281  
1282 =cut
1283  
1284 sub is_isohedral
1285 0 ▶{
Subroutine is_isohedral: not called CC=1 SCAR=6.9
Pod documented
1286 0 my( $self ) = @_;
1287 0 return $self->dual->is_isogonal;
1288 }
1289  
1290 =head2 C<is_regular()>
1291  
1292 Tests if given polyhedron is regular.
1293 A regular polyhedron is vertex-transitive, edge-transitive and face-transitive.
1294 Requires L<Graph::Nauty> to locate symmetry orbits of a graph.
1295  
1296 =cut
1297  
1298 sub is_regular
1299 0 ▶{
Subroutine is_regular: not called CC=3 SCAR=24.8
Pod documented
1300 0 my( $self ) = @_;
1301 0 ▶ return $self->is_isogonal && $self->is_isotoxal && $self->is_isohedral;
Condition0%0/6
$self->is_isogonal && $self->is_isotoxal && $self->is_isohedral
!ll&&!rl&&r
000
$self->is_isogonal and $self->is_isotoxal
!ll&&!rl&&r
000
MC/DC0%0/3
$self->is_isogonal && $self->is_isotoxal && $self->is_isohedral
$self->is_isogonal $self->is_isotoxal $self->is_isohedral
Truth table0%0/4
A and B && C
A= $self->is_isogonalB= $self->is_isotoxalC= $self->is_isohedral
ABCresult
0XX0
10X0
1100
1111
1302 }
1303  
1304 =head2 C<is_quasiregular()>
1305  
1306 Tests if given quasiregular is regular.
1307 A quasiregular polyhedron is vertex-transitive and edge-transitive, has two kinds of faces.
1308 Requires L<Graph::Nauty> to locate symmetry orbits of a graph.
1309  
1310 =cut
1311  
1312 sub is_quasiregular
1313 0 ▶{
Subroutine is_quasiregular: not called CC=3 SCAR=24.8
Pod documented
1314 0 my( $self ) = @_;
1315 return $self->is_isogonal && $self->is_isotoxal &&
1316 0 ▶ scalar( Graph::Nauty::orbits( $self->dual, sub { return '' } ) ) == 2;
Subroutine __ANON__: not called CC=1 SCAR=6.9
Condition0%0/6
$self->is_isogonal && $self->is_isotoxal && scalar Graph::Nauty::orbits($self->dual, sub { return ''; } ) == 2
!ll&&!rl&&r
000
$self->is_isogonal and $self->is_isotoxal
!ll&&!rl&&r
000
MC/DC0%0/3
$self->is_isogonal && $self->is_isotoxal && scalar Graph::Nauty::orbits($self->dual, sub { return ''; } ) == 2
$self->is_isogonal $self->is_isotoxal scalar Graph::Nauty::orbits($self->dual, sub { return ''; } ) == 2
Truth table0%0/4
A and B && C
A= $self->is_isogonalB= $self->is_isotoxalC= scalar Graph::Nauty::orbits($self->dual, sub { return ''; } ) == 2
ABCresult
0XX0
10X0
1100
1111
1317 }
1318  
1319 sub _cycle_in_order
1320 145 ▶{
Subroutine _cycle_in_order: called CC=2 SCAR=6.9
1321 145 my( $graph, @face ) = @_;
1322 145 my $subgraph = $graph->subgraph( \@face );
1323 145 my @order;
1324 145 my( $current ) = sort $subgraph->vertices;
1325 145 ▶ while( $subgraph->vertices ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($subgraph->vertices) 860 145 1005
1326 860 my( $next ) = sort $subgraph->neighbours( $current );
1327 860 push @order, $current;
1328 860 $subgraph->SUPER::delete_vertex( $current );
1329 860 $current = $next;
1330 }
1331 145 return @order;
1332 }
1333  
1334 sub _ensure_vertices_do_not_exist
1335 191 ▶{
Subroutine _ensure_vertices_do_not_exist: called CC=3 SCAR=11.2
1336 191 my( $graph, @vertices ) = @_;
1337 191 for (@vertices) {
1338 195 ▶ die "vertex $_ already exists\n" if $graph->has_vertex( $_ );
Branch: 1 branch
BranchTrueFalseTotal
if $graph->has_vertex($_) 0 195 195
1339 }
1340 }
1341  
1342 sub _largest_face
1343 0 ▶{
Subroutine _largest_face: not called CC=4 SCAR=30.0
1344 0 my( $self ) = @_;
1345 0 my $max;
1346 0 for ($self->faces) {
1347 0 ▶ next if defined $max && scalar( @$_ ) <= scalar( @$max );
Branch: 1 branch
BranchTrueFalseTotal
if defined $max and scalar @$_ <= scalar @$max 0 0 0
Condition0%0/3
defined $max and scalar @$_ <= scalar @$max
!ll&&!rl&&r
000
MC/DC0%0/2
defined $max and scalar @$_ <= scalar @$max
defined $max scalar @$_ <= scalar @$max
Truth table0%0/3
A and B
A= defined $maxB= scalar @$_ <= scalar @$max
ABresult
0X0
100
111
1348 0 $max = $_;
1349 }
1350 0 return @$max;
1351 }
1352  
1353 sub _names
1354 24 ▶{
Subroutine _names: called CC=2 SCAR=6.9
1355 24 my( $N ) = @_;
1356  
1357 24 my $n_letters = int( log( $N ) / log( 27 ) ) + 1;
1358 24 my $name = 'A' x $n_letters;
1359 24 my @names;
1360 24 for (1..$N) {
1361 303 push @names, $name;
1362 303 $name++;
1363 }
1364  
1365 24 return @names;
1366 }
1367  
1368 # TODO: Implement according to https://en.wikipedia.org/wiki/Polygon#Naming
1369 # Not all synonyms are supported yet.
1370 sub _polygon_name_to_number
1371 20 ▶{
Subroutine _polygon_name_to_number: called CC=1 SCAR=0.0
1372 20 my( $name ) = @_;
1373 20 $name =~ s/gon(al)?$//;
1374 20 my( $number ) = grep { $name eq $polygon_names[$_] } 0..$#polygon_names;
1375 20 return $number;
1376 }
1377  
1378 =head1 AUTHORS
1379  
1380 Andrius Merkys, E<lt>merkys@cpan.orgE<gt>
1381  
1382 =cut
1383  
1384 10 1;
↑ Summary