blib/lib/Graph/Weighted.pm

filter: Statementstmt 80.5% 95 / 118 Branchbran 83.3% 30 / 36 Conditioncond 76.0% 19 / 25 MC/DCmcdc 66.6% 10 / 15 Subroutinesub 85.7% 12 / 14 Podpod 100% 7 / 7 totaltotal 80.4% 173 / 215 CC 45 SCAR 23.1
CC
45
Cov
80%
dump
30.0
populate
14.1
edge_span
10.0
CRAP 10.1
↑ Summary
1 package Graph::Weighted;
2 3 our $AUTHORITY = 'cpan:GENE';
3  
4 # ABSTRACT: A weighted graph implementation
5  
6 3 our $VERSION = '0.9101';
7  
8 3 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
9 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
10  
11 3 ▶use parent qw( Graph );
Subroutine BEGIN: called CC=1 SCAR=0.0
12  
13 3 ▶use Carp qw( croak );
Subroutine BEGIN: called CC=1 SCAR=0.0
14  
15 3 ▶use constant WEIGHT => 'weight';
Subroutine BEGIN: called CC=1 SCAR=0.0
16  
17  
18 8 ▶sub populate {
Subroutine populate: called CC=11 SCAR=26.4
Pod documented
19 8 my ($self, $data, $attr) = @_;
20  
21 # Set the default attribute.
22 8 ▶ $attr ||= WEIGHT;
Condition50%1/2
$attr ||= "weight"
l!l
08
MC/DC0%0/1
$attr ||= "weight"
$attr
Truth table50%1/2
A
A= $attr
Aresult
11
00
23  
24 # What type of data are we given?
25 8 my $data_ref = ref $data;
26  
27 8 ▶ if ($data_ref eq 'ARRAY' || $data_ref eq 'Math::Matrix') {
Branch: 3 branches
BranchTrueFalseTotal
if ($data_ref eq 'ARRAY' or $data_ref eq 'Math::Matrix') { } 6 2 8
elsif ($data_ref eq 'Math::MatrixReal') { } 0 2 2
elsif ($data_ref eq 'HASH') { } 2 0 2
Condition66%2/3
$data_ref eq "ARRAY" or $data_ref eq "Math::Matrix"
l!l&&r!l&&!r
602
MC/DC50%1/2
$data_ref eq "ARRAY" or $data_ref eq "Math::Matrix"
$data_ref eq "ARRAY" $data_ref eq "Math::Matrix"
Truth table66%2/3
A or B
A= $data_ref eq "ARRAY"B= $data_ref eq "Math::Matrix"
ABresult
1X1
011
000
28 6 my $vertex = 0; # Initial vertex id.
29 6 for my $neighbors (@$data) {
30 14 $self->_from_array($vertex, $neighbors, $attr);
31 14 $vertex++; # Move on to the next vertex...
32 }
33 }
34 elsif ($data_ref eq 'Math::MatrixReal') {
35 0 my $vertex = 0;
36 0 for my $neighbors (@{ $data->[0] }) {
37 0 $self->_from_array($vertex, $neighbors, $attr);
38 0 $vertex++;
39 }
40 }
41 elsif ($data_ref eq 'HASH') {
42 2 for my $vertex (keys %$data) {
43 5 for my $entry ( keys %{ $data->{$vertex} } ) {
44 11 ▶ if ( $entry eq 'label' ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry eq "label") 1 10 11
45 1 my $label = delete $data->{$vertex}{$entry};
46 1 $self->set_vertex_attribute($vertex, $entry, $label);
47 }
48 }
49 5 $self->_from_hash( $vertex, $data->{$vertex}, $attr );
50 }
51 }
52 else {
53 0 croak "Unknown data type: $data\n";
54 }
55 }
56  
57 14 ▶sub _from_array {
Subroutine _from_array: called CC=3 SCAR=11.0
58 14 my ($self, $vertex, $neighbors, $attr) = @_;
59  
60 # Initial vertex weight
61 14 my $vertex_weight = 0;
62  
63 # Make nodes and edges.
64 14 for my $n (0 .. @$neighbors - 1) {
65 55 my $w = $neighbors->[$n]; # Weight of the edge to the neighbor.
66 55 ▶ next unless $w; # Skip zero weight nodes
Branch: 1 branch
BranchTrueFalseTotal
unless $w 39 16 55
67  
68 # Add a node-node edge to the graph.
69 16 $self->add_edge($vertex, $n);
70  
71 16 $self->set_edge_attribute($vertex, $n, $attr, $w);
72  
73 # Tally the weight of the vertex.
74 16 $vertex_weight += $w;
75 }
76  
77 # Set the weight of the graph node.
78 14 $self->set_vertex_attribute($vertex, $attr, $vertex_weight);
79 }
80  
81 5 ▶sub _from_hash {
Subroutine _from_hash: called CC=3 SCAR=11.1
82 5 my ($self, $vertex, $neighbors, $attr) = @_;
83  
84 # Initial vertex weight
85 5 my $vertex_weight = 0;
86  
87 # Handle terminal nodes.
88 5 ▶ if (ref $neighbors) {
Branch: 1 branch
BranchTrueFalseTotal
if (ref $neighbors) { } 5 0 5
89 # Make nodes and edges.
90 5 for my $n (keys %$neighbors) {
91 10 my $w = $neighbors->{$n}; # Weight of the edge to the neighbor.
92  
93 # Add a node-node edge to the graph.
94 10 $self->add_edge($vertex, $n);
95  
96 10 $self->set_edge_attribute($vertex, $n, $attr, $w);
97  
98 # Tally the weight of the vertex.
99 10 $vertex_weight += $w;
100 }
101 }
102 else {
103 0 $vertex_weight = $neighbors;
104 }
105  
106 # Set the weight of the graph node.
107 5 $self->set_vertex_attribute($vertex, $attr, $vertex_weight);
108 }
109  
110  
111 36 ▶sub get_cost {
Subroutine get_cost: called CC=6 SCAR=18.1
Pod documented
112 36 my ($self, $v, $attr) = @_;
113 36 ▶ croak 'ERROR: No vertex given to get_cost()' unless defined $v;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $v 0 36 36
114  
115 # Default to weight.
116 36 ▶ $attr ||= WEIGHT;
Condition100%2/2
$attr ||= "weight"
l!l
927
MC/DC100%1/1
$attr ||= "weight"
$attr
Truth table100%2/2
A
A= $attr
Aresult
11
00
117  
118 # Return the edge attribute if given a list.
119 36 ▶ return $self->get_edge_attribute(@$v, $attr) || 0 if ref $v eq 'ARRAY';
Branch: 1 branch
BranchTrueFalseTotal
if ref $v eq "ARRAY" 22 14 36
Condition50%1/2
$self->get_edge_attribute(@$v, $attr) || 0
l!l
220
MC/DC0%0/1
$self->get_edge_attribute(@$v, $attr) || 0
$self->get_edge_attribute(@$v, $attr)
Truth table50%1/2
A
A= $self->get_edge_attribute(@$v, $attr)
Aresult
11
00
120  
121 # Return the vertex attribute if given a scalar.
122 14 ▶ return $self->get_vertex_attribute($v, $attr) || 0;
Condition100%2/2
$self->get_vertex_attribute($v, $attr) || 0
l!l
104
MC/DC100%1/1
$self->get_vertex_attribute($v, $attr) || 0
$self->get_vertex_attribute($v, $attr)
Truth table100%2/2
A
A= $self->get_vertex_attribute($v, $attr)
Aresult
11
00
123 }
124  
125  
126 1 ▶sub vertex_span {
Subroutine vertex_span: called CC=10 SCAR=23.0
Pod documented
127 1 my ($self, $attr) = @_;
128  
129 # Get the cost of each vertex
130 1 my $mass = {};
131 1 for my $vertex ( $self->vertices ) {
132 5 $mass->{$vertex} = $self->get_cost($vertex, $attr);
133 }
134  
135 # Find the smallest & biggest costs
136 1 my ($smallest, $biggest);
137 1 for my $vertex ( keys %$mass ) {
138 5 my $current = $mass->{$vertex};
139 5 ▶ if ( !defined $smallest || $smallest > $current ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $smallest or $smallest > $current) 2 3 5
Condition100%3/3
not defined $smallest or $smallest > $current
l!l&&r!l&&!r
113
MC/DC100%2/2
not defined $smallest or $smallest > $current
not defined $smallest $smallest > $current
Truth table100%3/3
not(A) or B
A= not defined $smallestB= $smallest > $current
ABresult
1X1
011
000
140 2 $smallest = $current;
141 }
142 5 ▶ if ( !defined $biggest || $biggest < $current ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $biggest or $biggest < $current) 2 3 5
Condition100%3/3
not defined $biggest or $biggest < $current
l!l&&r!l&&!r
113
MC/DC100%2/2
not defined $biggest or $biggest < $current
not defined $biggest $biggest < $current
Truth table100%3/3
not(A) or B
A= not defined $biggestB= $biggest < $current
ABresult
1X1
011
000
143 2 $biggest = $current;
144 }
145 }
146  
147 # Collect the lightest & heaviest vertices
148 1 my ($lightest, $heaviest) = ([], []);
149 1 for my $vertex ( keys %$mass ) {
150 5 ▶ push @$lightest, $vertex if $mass->{$vertex} == $smallest;
Branch: 1 branch
BranchTrueFalseTotal
if $mass->{$vertex} == $smallest 1 4 5
151 5 ▶ push @$heaviest, $vertex if $mass->{$vertex} == $biggest;
Branch: 1 branch
BranchTrueFalseTotal
if $mass->{$vertex} == $biggest 1 4 5
152 }
153  
154 1 return $lightest, $heaviest;
155 }
156  
157  
158 1 ▶sub edge_span {
Subroutine edge_span: called CC=10 SCAR=23.0
Pod documented
159 1 my ($self, $attr) = @_;
160  
161 # Get the cost of each edge
162 1 my $mass = {};
163 1 for my $edge ( $self->edges ) {
164 7 $mass->{ $edge->[0] . '_' . $edge->[1] } = $self->get_cost($edge, $attr);
165 }
166  
167 # Find the smallest & biggest costs
168 1 my ($smallest, $biggest);
169 1 for my $edge ( keys %$mass ) {
170 7 my $current = $mass->{$edge};
171 7 ▶ if ( !defined $smallest || $smallest > $current ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $smallest or $smallest > $current) 1 6 7
Condition66%2/3
not defined $smallest or $smallest > $current
l!l&&r!l&&!r
106
MC/DC50%1/2
not defined $smallest or $smallest > $current
not defined $smallest $smallest > $current
Truth table66%2/3
not(A) or B
A= not defined $smallestB= $smallest > $current
ABresult
1X1
011
000
172 1 $smallest = $current;
173 }
174 7 ▶ if ( !defined $biggest || $biggest < $current ) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $biggest or $biggest < $current) 3 4 7
Condition100%3/3
not defined $biggest or $biggest < $current
l!l&&r!l&&!r
124
MC/DC100%2/2
not defined $biggest or $biggest < $current
not defined $biggest $biggest < $current
Truth table100%3/3
not(A) or B
A= not defined $biggestB= $biggest < $current
ABresult
1X1
011
000
175 3 $biggest = $current;
176 }
177 }
178  
179 # Collect the lightest & heaviest edges
180 1 my ($lightest, $heaviest) = ([], []);
181 1 for my $edge ( sort keys %$mass ) {
182 7 my $arrayref = [ split /_/, $edge ];
183 7 ▶ push @$lightest, $arrayref if $mass->{$edge} == $smallest;
Branch: 1 branch
BranchTrueFalseTotal
if $mass->{$edge} == $smallest 3 4 7
184 7 ▶ push @$heaviest, $arrayref if $mass->{$edge} == $biggest;
Branch: 1 branch
BranchTrueFalseTotal
if $mass->{$edge} == $biggest 2 5 7
185 }
186  
187 1 return $lightest, $heaviest;
188 }
189  
190  
191  
192 4 ▶sub path_cost {
Subroutine path_cost: called CC=3 SCAR=11.0
Pod documented
193 4 my ($self, $path, $attr) = @_;
194  
195 4 ▶ return undef unless $self->has_path( @$path );
Branch: 1 branch
BranchTrueFalseTotal
unless $self->has_path(@$path) 1 3 4
196  
197 3 my $path_cost = 0;
198  
199 3 for my $i ( 0 .. @$path - 2 ) {
200 6 $path_cost += $self->get_cost( [ $path->[$i], $path->[ $i + 1 ] ], $attr );
201 }
202  
203 3 return $path_cost;
204 }
205  
206  
207 0 ▶sub MST_edge_sum {
Subroutine MST_edge_sum: not called CC=2 SCAR=17.9
Pod documented
208 0 my ($self, $tree) = @_;
209  
210 0 my $sum = 0;
211  
212 0 my @edges = split /,/, $tree;
213  
214 0 for my $edge (@edges) {
215 0 my @edge = split /=/, $edge;
216 0 $sum += $self->get_cost(\@edge);
217 }
218  
219 0 return $sum;
220 }
221  
222  
223 0 ▶sub dump {
Subroutine dump: not called CC=5 SCAR=34.0
Pod documented
224 0 my $self = shift;
225 0 ▶ my $attr = shift || WEIGHT;
Condition0%0/2
shift() || 'weight'
l!l
00
MC/DC0%0/1
shift() || 'weight'
shift()
Truth table0%0/2
A
A= shift()
Aresult
11
00
226  
227 0 for my $vertex ( sort { $a <=> $b } $self->vertices ) {
228 0 my $label = $self->get_vertex_attribute($vertex, 'label');
229 0 ▶ printf "%svertex: %s %s=%.2f\n",
Branch: 1 branch
BranchTrueFalseTotal
$label ? : 0 0 0
230 ( $label ? "$label " : '' ),
231 $vertex,
232 $attr,
233 $self->get_cost( $vertex, $attr );
234 0 for my $successor ( sort { $a <=> $b } $self->successors($vertex) ) {
235 0 printf "\tedge to: %s %s=%.2f\n",
236 $successor,
237 $attr,
238 $self->get_cost( [ $vertex, $successor ], $attr );
239 }
240 }
241 }
242  
243 3 1;
244  
245 __END__
↑ Summary