blib/lib/Graph/Traverse.pm

filter: Statementstmt 97.4% 77 / 79 Branchbran 90.7% 49 / 54 Conditioncond 87.8% 36 / 41 MC/DCmcdc 62.5% 15 / 24 Subroutinesub 100% 6 / 6 Podpod 100% 1 / 1 totaltotal 89.7% 184 / 205 CC 47 SCAR 37.6
CC
47
Cov
93%
traverse
47.6
BEGIN
1.0
BEGIN
1.0
CRAP 43.1
↑ Summary
1 2 package Graph::Traverse 0.04 {
2  
3 2 ▶ use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 2 ▶ use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 2 ▶ use parent 'Graph';
Subroutine BEGIN: called CC=1 SCAR=0.0
7 2 ▶ use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
8  
9 17 ▶ sub traverse {
Subroutine traverse: called CC=47 SCAR=38.6
Pod documented
10 # Use as: $graph->search( START_VERTEX, [OPTS])
11 #
12 # Traverses edges from the start vertex (or verticess) [either
13 # a scalar with a single vertex's name, or an array of vertex
14 # names, may be passed], finding adjacent vertices using the
15 # 'next' function (by default, 'successors'), until either a
16 # maximum accumulated edge weight ('max' option, if given) is
17 # exceeded (by default using the 'weight' attribute, or
18 # specify an 'attribute'), or until a callback function ('cb')
19 # returns a nonzero value. Default is to return the list of
20 # vertices encountered in the search; use option 'weights' to
21 # return a list of vertex=>weight_value.
22 #
23 # Use option 'hash=>1' to return a hash where keys are vertex
24 # names, and values are a hash containing the 'path' to that
25 # vertex from the starting vertex, the 'weight' at that
26 # vertex, and 'terminal' the value of the callback function
27 # returned for that vertex (if nonzero, further nodes on that
28 # branch are not searched). Note that as we traverse the
29 # graph, we may encounter the same vertex several times, but
30 # only the shortest path (lowest weight) will be retained in
31 # the final hash.
32
33 17 my ($self, $vertex, $opts) = @_;
34 17 ▶ carp "Must pass starting vertex" unless defined $vertex;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $vertex 0 17 17
35  
36 17 ▶ my $cb_check = $opts->{cb} if defined $opts;
Branch: 1 branch
BranchTrueFalseTotal
if defined $opts 16 1 17
37  
38 17 ▶ my $return_weights = (defined $opts && $opts->{weights});
Condition66%2/3
defined $opts && $opts->{'weights'}
!ll&&!rl&&r
1160
MC/DC0%0/2
defined $opts && $opts->{'weights'}
defined $opts $opts->{'weights'}
Truth table66%2/3
A && B
A= defined $optsB= $opts->{'weights'}
ABresult
0X0
100
111
39 17 ▶ my $return_hash = (defined $opts && $opts->{hash});
Condition66%2/3
defined $opts && $opts->{'hash'}
!ll&&!rl&&r
1016
MC/DC50%1/2
defined $opts && $opts->{'hash'}
defined $opts $opts->{'hash'}
Truth table66%2/3
A && B
A= defined $optsB= $opts->{'hash'}
ABresult
0X0
100
111
40 17 ▶ my $save_paths = ($return_hash) ? [] : undef;
Branch: 1 branch
BranchTrueFalseTotal
$return_hash ? : 16 1 17
41 # Save all nodes (default), or only the callback-flagged terminal nodes?
42 17 ▶ my $save_all = (defined $opts && ($opts->{all} // 1));
Condition100%5/5
defined $opts && ($opts->{'all'} // 1)
!ll&&!rl&&r
1313
$opts->{"all"} // 1
l!l
313
MC/DC100%2/2
defined $opts && ($opts->{'all'} // 1)
defined $opts $opts->{"all"}
Truth table100%3/3
A && B
A= defined $optsB= $opts->{"all"}
ABresult
0X0
100
111
43  
44 # If option 'attribute' is defined, we accumulate weights from each edge.
45 # Define 'max' to terminate when a maximum weight is achieved.
46 # Define 'vertex' to accumulate vertex weights rather than edge weights.
47 # Define 'incr' to change the default weight value from 1.
48 17 ▶ my $attr = (defined $opts) ? ($opts->{attribute} // 'weight') : 'weight';
Branch: 1 branch
BranchTrueFalseTotal
defined $opts ? : 16 1 17
Condition100%2/2
$opts->{"attribute"} // "weight"
l!l
214
MC/DC100%1/1
$opts->{"attribute"} // "weight"
$opts->{"attribute"}
Truth table100%2/2
A
A= $opts->{"attribute"}
Aresult
11
00
49 17 ▶ my $max_weight = $opts->{max} if defined $opts;
Branch: 1 branch
BranchTrueFalseTotal
if defined $opts 16 1 17
50 17 ▶ my $add_vertex = $opts->{vertex} if defined $opts;
Branch: 1 branch
BranchTrueFalseTotal
if defined $opts 16 1 17
51 17 ▶ my $incr = (defined $opts) ? ($opts->{default} // 1) : 1; # default weight for each edge
Branch: 1 branch
BranchTrueFalseTotal
defined $opts ? : 16 1 17
Condition100%2/2
$opts->{"default"} // 1
l!l
412
MC/DC100%1/1
$opts->{"default"} // 1
$opts->{"default"}
Truth table100%2/2
A
A= $opts->{"default"}
Aresult
11
00
52  
53 # Use a method that will return a list of adjacent vertices.
54 # Other useful values are 'predecessors' and 'neighbors'.
55 17 ▶ my $next = (defined $opts ? ($opts->{next}) : undef) // 'successors';
Branch: 1 branch
BranchTrueFalseTotal
defined $opts ? : 16 1 17
Condition100%2/2
(defined $opts ? $opts->{"next"} : undef) // "successors"
l!l
215
MC/DC100%1/1
(defined $opts ? $opts->{"next"} : undef) // "successors"
(defined $opts ? $opts->{"next"} : undef)
Truth table100%2/2
A
A= (defined $opts ? $opts->{"next"} : undef)
Aresult
11
00
56  
57 17 my (%todo, %path, %weight);
58 17 ▶ foreach my $s (@{ref $vertex ? $vertex : [$vertex]}) {
Branch: 1 branch
BranchTrueFalseTotal
ref $vertex ? : 14 3 17
59 19 $todo{$s} = $s;
60 19 $path{$s} = [$s];
61 19 $weight{$s} = 0;
62 }
63 17 my %terminal;
64 my %seen;
65 17 my %init = %todo;
66 17 ▶ while (keys %todo) {
Branch: 1 branch
BranchTrueFalseTotal
if (keys %todo) 86 17 103
67 86 my @todo = values %todo;
68 86 for my $t (@todo) {
69 163 $seen{$t} = delete $todo{$t};
70 163 for my $s ($self->$next($t)) {
71 173 ▶ next unless $self->has_vertex($s);
Branch: 1 branch
BranchTrueFalseTotal
unless $self->has_vertex($s) 0 173 173
72 173 my $newvalue;
73 173 ▶ if (defined $attr) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $attr) { } 173 0 173
74 173 ▶ if ($add_vertex) { # Add vertex attribute value
Branch: 1 branch
BranchTrueFalseTotal
if ($add_vertex) { } 20 153 173
75 20 ▶ $newvalue = $weight{$t} + ($self->get_vertex_attribute($s, $attr) // $incr);
Condition66%2/3
$self->get_vertex_attribute($s, $attr) // $incr
l!l&&r!l&&!r
1370
MC/DC0%0/2
$self->get_vertex_attribute($s, $attr) // $incr
$self->get_vertex_attribute($s, $attr) $incr
Truth table66%2/3
A // B
A= $self->get_vertex_attribute($s, $attr)B= $incr
ABresult
1X1
011
000
76 } else { # Add edge attribute value (default 'weight', default value 1)
77 # Note, if our search function is 'predecessors' or 'neighbors' we
78 # may find nodes in reverse direction, but we want the edge attributes
79 # in either case
80 153 ▶ $newvalue = $weight{$t} + ($self->get_edge_attribute($t, $s, $attr) //
Condition83%5/6
($self->get_edge_attribute($t, $s, $attr) // $self->get_edge_attribute($s, $t, $attr)) // $incr
l!l&&r!l&&!r
181350
$self->get_edge_attribute($t, $s, $attr) // $self->get_edge_attribute($s, $t, $attr)
l!l&&r!l&&!r
144135
MC/DC0%0/3
($self->get_edge_attribute($t, $s, $attr) // $self->get_edge_attribute($s, $t, $attr)) // $incr
$self->get_edge_attribute($t, $s, $attr) $self->get_edge_attribute($s, $t, $attr) $incr
Truth table75%3/4
A // B // C
A= $self->get_edge_attribute($t, $s, $attr)B= $self->get_edge_attribute($s, $t, $attr)C= $incr
ABCresult
1XX1
01X1
0011
0000
81 $self->get_edge_attribute($s, $t, $attr) //
82 $incr);
83 }
84 } else {
85 0 $newvalue = $weight{$t} + $incr;
86 }
87 # If callback function returns nonzero, do not traverse beyond this node.
88 173 ▶ if (defined $cb_check) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $cb_check) 64 109 173
89 64 ▶ if ($terminal{$s} = &$cb_check($self, $s, $newvalue, $opts)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($terminal{$s} = &$cb_check($self, $s, $newvalue, $opts)) 6 58 64
90 6 $seen{$s} = $s;
91 }
92 }
93 # Do not save vertices beyond a defined maximum weight
94 173 ▶ next if (defined $max_weight) && ($newvalue > $max_weight);
Branch: 1 branch
BranchTrueFalseTotal
if defined $max_weight and $newvalue > $max_weight 3 170 173
Condition100%3/3
defined $max_weight and $newvalue > $max_weight
!ll&&!rl&&r
153173
MC/DC100%2/2
defined $max_weight and $newvalue > $max_weight
defined $max_weight $newvalue > $max_weight
Truth table100%3/3
A and B
A= defined $max_weightB= $newvalue > $max_weight
ABresult
0X0
100
111
95 # Always save the found vertices. As we traverse,
96 # we may later encounter shortcuts which we must
97 # discard before the final return (see below).
98 170 ▶ if (defined $save_paths) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $save_paths) 167 3 170
99 my $this_node = { vertex => $s,
100 167 path => [@{$path{$t}}, $s],
101 weight => $newvalue };
102 167 ▶ $this_node->{terminal} = $terminal{$s} if exists $terminal{$s};
Branch: 1 branch
BranchTrueFalseTotal
if exists $terminal{$s} 64 103 167
103 167 ▶ push @{$save_paths}, $this_node if ($save_all || $terminal{$s});
Branch: 1 branch
BranchTrueFalseTotal
if $save_all or $terminal{$s} 109 58 167
Condition100%3/3
$save_all or $terminal{$s}
l!l&&r!l&&!r
103658
MC/DC100%2/2
$save_all or $terminal{$s}
$save_all $terminal{$s}
Truth table100%3/3
A or B
A= $save_allB= $terminal{$s}
ABresult
1X1
011
000
104 }
105 # Only save new paths, and shorter-than-previously-found paths.
106 170 ▶ if ((!defined $path{$s}) || ($newvalue < $weight{$s} )) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $path{$s} or $newvalue < $weight{$s}) 152 18 170
Condition100%3/3
not defined $path{$s} or $newvalue < $weight{$s}
l!l&&r!l&&!r
1351718
MC/DC100%2/2
not defined $path{$s} or $newvalue < $weight{$s}
not defined $path{$s} $newvalue < $weight{$s}
Truth table100%3/3
not(A) or B
A= not defined $path{$s}B= $newvalue < $weight{$s}
ABresult
1X1
011
000
107 # If new path is shorter than we previously
108 # found, then retrace all paths from this
109 # vertex onward.
110 152 ▶ delete $seen{$s} if (defined $weight{$s} && $newvalue < $weight{$s});
Branch: 1 branch
BranchTrueFalseTotal
if defined $weight{$s} and $newvalue < $weight{$s} 17 135 152
Condition66%2/3
defined $weight{$s} and $newvalue < $weight{$s}
!ll&&!rl&&r
135017
MC/DC50%1/2
defined $weight{$s} and $newvalue < $weight{$s}
defined $weight{$s} $newvalue < $weight{$s}
Truth table66%2/3
A and B
A= defined $weight{$s}B= $newvalue < $weight{$s}
ABresult
0X0
100
111
111 152 $weight{$s} = $newvalue;
112 152 $path{$s} = [@{$path{$t}}, $s];
113 }
114 # If callback function returns nonzero, do not
115 # traverse beyond this node. NOTE: In the case of
116 # multiple paths to the following node, the above
117 # does track the shortest path to the node, but
118 # the caller will not receive every combination of
119 # paths *through* the node.
120 170 ▶ next if ($terminal{$s});
Branch: 1 branch
BranchTrueFalseTotal
if $terminal{$s} 6 164 170
121 164 ▶ $todo{$s} = $s unless exists $seen{$s};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $seen{$s} 153 11 164
122 }
123 }
124 }
125 17 for my $v (keys %init) {
126 19 delete $seen{$v};
127 19 delete $weight{$v};
128 }
129 # return $save_paths if defined $return_all;
130 17 ▶ if ($return_hash) {
Branch: 1 branch
BranchTrueFalseTotal
if ($return_hash) 16 1 17
131 # Scan list of found vertices, overwriting higher-valued
132 # (longer) paths with lower (shorter) ones which were
133 # found later.
134 16 my $ret = {};
135 16 foreach my $v (@{$save_paths}) {
136 109 ▶ $ret->{$v->{vertex}} = $v if (!defined $ret->{$v->{vertex}} || ($ret->{$v->{vertex}}->{weight} > $v->{weight}));
Branch: 1 branch
BranchTrueFalseTotal
if not defined $$ret{$v->{"vertex"}} or $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"} 96 13 109
Condition100%3/3
not defined $$ret{$v->{"vertex"}} or $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"}
l!l&&r!l&&!r
791713
MC/DC100%2/2
not defined $$ret{$v->{"vertex"}} or $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"}
not defined $$ret{$v->{"vertex"}} $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"}
Truth table100%3/3
not(A) or B
A= not defined $$ret{$v->{"vertex"}}B= $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"}
ABresult
1X1
011
000
137 }
138 16 return $ret;
139 }
140 1 ▶ return $return_weights ? (%weight) : (values %seen);
Branch: 1 branch
BranchTrueFalseTotal
$return_weights ? : 0 1 1
141 }
142  
143 2 ▶ if (Graph->can('traverse')) {
Branch: 1 branch
BranchTrueFalseTotal
if ('Graph'->can('traverse')) { } 0 2 2
144 0 carp ('Graph already has a traverse method.');
145 } else {
146 2 ▶ no warnings 'redefine', 'once'; ## no critic
Subroutine BEGIN: called CC=1 SCAR=0.0
147 2 *Graph::traverse = \&traverse;
148 }
149  
150 };
151  
152 2 1;
153  
154 __END__
↑ Summary