| 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
| |||||||||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||||||||
| 36 | 17 | ▶ | my $cb_check = $opts->{cb} if defined $opts; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||||||||
| 38 | 17 | ▶ | my $return_weights = (defined $opts && $opts->{weights}); | ||||||||||||||||||||||||||||||||
|
Condition66%2/3
defined $opts && $opts->{'weights'}
MC/DC0%0/2
defined $opts && $opts->{'weights'}
defined $opts
$opts->{'weights'}
Truth table66%2/3
A && B
A= defined $optsB= $opts->{'weights'}
| |||||||||||||||||||||||||||||||||||
| 39 | 17 | ▶ | my $return_hash = (defined $opts && $opts->{hash}); | ||||||||||||||||||||||||||||||||
|
Condition66%2/3
defined $opts && $opts->{'hash'}
MC/DC50%1/2
defined $opts && $opts->{'hash'}
defined $opts
$opts->{'hash'}
Truth table66%2/3
A && B
A= defined $optsB= $opts->{'hash'}
| |||||||||||||||||||||||||||||||||||
| 40 | 17 | ▶ | my $save_paths = ($return_hash) ? [] : undef; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 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)
$opts->{"all"} // 1
MC/DC100%2/2
defined $opts && ($opts->{'all'} // 1)
defined $opts
$opts->{"all"}
Truth table100%3/3
A && B
A= defined $optsB= $opts->{"all"}
| |||||||||||||||||||||||||||||||||||
| 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
Condition100%2/2
$opts->{"attribute"} // "weight"
MC/DC100%1/1
$opts->{"attribute"} // "weight"
$opts->{"attribute"}
Truth table100%2/2
A
A= $opts->{"attribute"}
| |||||||||||||||||||||||||||||||||||
| 49 | 17 | ▶ | my $max_weight = $opts->{max} if defined $opts; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 50 | 17 | ▶ | my $add_vertex = $opts->{vertex} if defined $opts; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 51 | 17 | ▶ | my $incr = (defined $opts) ? ($opts->{default} // 1) : 1; # default weight for each edge | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%2/2
$opts->{"default"} // 1
MC/DC100%1/1
$opts->{"default"} // 1
$opts->{"default"}
Truth table100%2/2
A
A= $opts->{"default"}
| |||||||||||||||||||||||||||||||||||
| 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
Condition100%2/2
(defined $opts ? $opts->{"next"} : undef) // "successors"
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)
| |||||||||||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||||||||
| 57 | 17 | my (%todo, %path, %weight); | |||||||||||||||||||||||||||||||||
| 58 | 17 | ▶ | foreach my $s (@{ref $vertex ? $vertex : [$vertex]}) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 72 | 173 | my $newvalue; | |||||||||||||||||||||||||||||||||
| 73 | 173 | ▶ | if (defined $attr) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 74 | 173 | ▶ | if ($add_vertex) { # Add vertex attribute value | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 75 | 20 | ▶ | $newvalue = $weight{$t} + ($self->get_vertex_attribute($s, $attr) // $incr); | ||||||||||||||||||||||||||||||||
|
Condition66%2/3
$self->get_vertex_attribute($s, $attr) // $incr
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
| |||||||||||||||||||||||||||||||||||
| 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
$self->get_edge_attribute($t, $s, $attr) // $self->get_edge_attribute($s, $t, $attr)
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
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 89 | 64 | ▶ | if ($terminal{$s} = &$cb_check($self, $s, $newvalue, $opts)) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
defined $max_weight and $newvalue > $max_weight
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
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 103 | 167 | ▶ | push @{$save_paths}, $this_node if ($save_all || $terminal{$s}); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$save_all or $terminal{$s}
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}
| |||||||||||||||||||||||||||||||||||
| 104 | } | ||||||||||||||||||||||||||||||||||
| 105 | # Only save new paths, and shorter-than-previously-found paths. | ||||||||||||||||||||||||||||||||||
| 106 | 170 | ▶ | if ((!defined $path{$s}) || ($newvalue < $weight{$s} )) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
not defined $path{$s} or $newvalue < $weight{$s}
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}
| |||||||||||||||||||||||||||||||||||
| 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
Condition66%2/3
defined $weight{$s} and $newvalue < $weight{$s}
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}
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 121 | 164 | ▶ | $todo{$s} = $s unless exists $seen{$s}; | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||||||||
| 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
Condition100%3/3
not defined $$ret{$v->{"vertex"}} or $$ret{$v->{"vertex"}}{"weight"} > $v->{"weight"}
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"}
| |||||||||||||||||||||||||||||||||||
| 137 | } | ||||||||||||||||||||||||||||||||||
| 138 | 16 | return $ret; | |||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||
| 140 | 1 | ▶ | return $return_weights ? (%weight) : (values %seen); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 141 | } | ||||||||||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||||||||
| 143 | 2 | ▶ | if (Graph->can('traverse')) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 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__ | ||||||||||||||||||||||||||||||||||