blib/lib/Algorithm/CriticalPath.pm

filter: Statementstmt 100% 70 / 70 Branchbran 100% 6 / 6 Conditioncond 90.4% 19 / 21 MC/DCmcdc 77.7% 7 / 9 Subroutinesub 100% 6 / 6 Podpod 100% 1 / 1 totaltotal 96.4% 109 / 113 CC 18 SCAR 26.6
CC
18
Cov
98%
BUILD
18.0
BEGIN
1.0
BEGIN
1.0
CRAP 14.3
↑ Summary
1 package Algorithm::CriticalPath;
2
3 1 ▶use 5.010;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 1 ▶use Mouse;
Subroutine BEGIN: called CC=1 SCAR=0.0
5
6
7
8 =head1 NAME
9
10 Algorithm::CriticalPath - Perform a critical path analysis over a Graph Object, by Ded MedVed
11
12 =head1 VERSION
13
14 Version 0.07
15
16 =cut
17
18 1 our $VERSION = '0.07';
19
20
21 1 ▶use Graph;
Subroutine BEGIN: called CC=1 SCAR=0.0
22 1 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
23 1 ▶use Data::Dumper;
Subroutine BEGIN: called CC=1 SCAR=0.0
24
25 1 has 'graph' => (
26 is => 'ro'
27 , isa => 'Graph'
28 , required => 1
29 );
30
31 1 has 'vertices' => (
32 is => 'rw'
33 , isa => 'ArrayRef[Str]'
34 );
35 1 has 'cost' => (
36 is => 'rw'
37 , isa => 'Num'
38 );
39
40
41 10 ▶sub BUILD {
Subroutine BUILD: called CC=18 SCAR=28.9
Pod documented
42
43 10 my ($self) = @_;
44
45 10 ▶ if ( ! defined $self->graph()
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed or $self->graph->is_undirected or $self->graph->is_multiedged or $self->graph->is_multivertexed) 5 5 10
Condition88%16/18
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed or $self->graph->is_undirected or $self->graph->is_multiedged or $self->graph->is_multivertexed
l!l&&r!l&&!r
415
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed or $self->graph->is_undirected or $self->graph->is_multiedged
l!l&&r!l&&!r
316
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed or $self->graph->is_undirected
l!l&&r!l&&!r
217
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed
l!l&&r!l&&!r
118
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph
l!l&&r!l&&!r
109
not defined $self->graph or $self->graph->has_a_cycle
l!l&&r!l&&!r
019
MC/DC71%5/7
not defined $self->graph or $self->graph->has_a_cycle or $self->graph->is_pseudo_graph or $self->graph->is_refvertexed or $self->graph->is_undirected or $self->graph->is_multiedged or $self->graph->is_multivertexed
not defined $self->graph $self->graph->has_a_cycle $self->graph->is_pseudo_graph $self->graph->is_refvertexed $self->graph->is_undirected $self->graph->is_multiedged $self->graph->is_multivertexed
Truth table75%6/8
not(A) or B or C or D or E or F or G
A= not defined $self->graphB= $self->graph->has_a_cycleC= $self->graph->is_pseudo_graphD= $self->graph->is_refvertexedE= $self->graph->is_undirectedF= $self->graph->is_multiedgedG= $self->graph->is_multivertexed
ABCDEFGresult
1XXXXXX1
01XXXXX1
001XXXX1
0001XXX1
00001XX1
000001X1
00000011
00000000
46 || $self->graph()->has_a_cycle()
47 || $self->graph()->is_pseudo_graph()
48 || $self->graph()->is_refvertexed()
49 || $self->graph()->is_undirected()
50 || $self->graph()->is_multiedged()
51 || $self->graph()->is_multivertexed()
52 )
53 {
54 5 croak 'Invalid graph type for critical path analysis' ;
55 } ;
56
57 # this is ropey - should use guaranteed unique names
58 5 my $start = 'GCP::dummyStart';
59 5 my $end = 'GCP::dummyEnd';
60
61
62 # this is ropey, should use a BFS search method to return the depth-ordered rankings of vertices.
63 5 my $g = $self->graph()->deep_copy();
64 5 my @rank;
65 5 my $i = 0 ;
66 5 ▶ while ( $g->vertices() > 0 ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->vertices > 0) 8 5 13
67
68 8 @{$rank[$i]} = $g->source_vertices();
69 8 push @{$rank[$i]}, $g->isolated_vertices();
70
71 8 for my $s (@{$rank[$i]}) {
72 10 $g->delete_vertex($s);
73 }
74 8 $i++;
75 }
76
77 # $copy adds in the dummy start and end nodes, so we don't destroy the original.
78 5 my $copy = $self->graph()->deep_copy();
79 5 $copy->add_weighted_vertex($start,0);
80 5 $copy->add_weighted_vertex($end,0);
81
82 5 for my $n ($copy->source_vertices()) {
83 3 $copy->add_edge($start, $n);
84 }
85 5 for my $n ($copy->sink_vertices()) {
86 4 $copy->add_edge($n,$end);
87 }
88
89 5 for my $n ($copy->isolated_vertices()) {
90 5 $copy->add_edge($start, $n);
91 5 $copy->add_edge($n,$end);
92 }
93
94 5 unshift @rank, [$start];
95 5 push @rank, [$end];
96
97 5 my %costToHere = map { $_ => 0 } $copy->vertices();
98
99 5 my %criticalPathToHere;
100 5 $criticalPathToHere{$start} = [$start];
101
102 5 for my $row ( @rank ) {
103 18 for my $node ( @$row ) {
104 20 for my $s ( $copy->successors($node) ) {
105 22 ▶ if ( $costToHere{$node} + $copy->get_vertex_weight($s) > $costToHere{$s} ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($costToHere{$node} + $copy->get_vertex_weight($s) > $costToHere{$s}) 14 8 22
106 14 $costToHere{$s} = $costToHere{$node} + $copy->get_vertex_weight($s);
107 14 @{$criticalPathToHere{$s}} = @{$criticalPathToHere{$node}};
108 14 push @{$criticalPathToHere{$s}}, $s;
109 }
110 }
111 }
112 }
113
114 # we don't want to see the dummy nodes on the returned critical path.
115 5 ▶ @{$criticalPathToHere{$end}} = grep { $_ ne ${start} && $_ ne ${end} } @{$criticalPathToHere{$end}} ;
Condition100%3/3
$_ ne $start && $_ ne $end
!ll&&!rl&&r
448
MC/DC100%2/2
$_ ne $start && $_ ne $end
$_ ne $start $_ ne $end
Truth table100%3/3
A && B
A= $_ ne $startB= $_ ne $end
ABresult
0X0
100
111
116
117 5 $self->vertices(\@{$criticalPathToHere{$end}});
118 5 $self->cost($costToHere{$end});
119
120
121 } ;
122
123 1 __PACKAGE__->meta->make_immutable();
124
125
126 1 1;
127 __DATA__
↑ Summary