blib/lib/Graph/ModularDecomposition.pm

filter: Statementstmt 98.3% 303 / 308 Branchbran 93.4% 170 / 182 Conditioncond 85.1% 23 / 27 MC/DCmcdc 71.4% 10 / 14 Subroutinesub 100% 22 / 22 Podpod 100% 17 / 17 totaltotal 95.6% 545 / 570 CC 118 SCAR 26.7
CC
118
Cov
96%
modular_decomposition_EGMS
34.4
factor
13.0
G
12.0
CRAP 14.4
↑ Summary
1 package Graph::ModularDecomposition;
2  
3 19 ▶use 5.006;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 19 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 19 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 =head1 NAME
8  
9 Graph::ModularDecomposition - Modular decomposition of directed graphs
10  
11 =cut
12  
13 19 require Exporter;
14 19 our $VERSION = '0.15';
15  
16 19 ▶use Graph 0.20105;
Subroutine BEGIN: called CC=1 SCAR=0.0
17 19 require Graph::Directed;
18  
19 # NB! Exporter must come before Graph::Directed in @ISA
20 19 our @ISA = qw(Exporter Graph::Directed);
21  
22 # This allows declaration use Graph::ModularDecomposition ':all';
23 # may want tree_to_string, should move into own Tree::... module some day
24 # other exports are most likely for internal use only
25 # all other functions should be accessed as methods
26 19 our %EXPORT_TAGS = ( 'all' => [ qw(
27 setminus
28 setunion
29 pairstring_to_graph
30 partition_to_string
31 tree_to_string
32 ) ] );
33  
34 19 our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );
35  
36 19 our @EXPORT = qw(
37 );
38  
39 =head1 SYNOPSIS
40  
41 use Graph::ModularDecomposition qw(pairstring_to_graph tree_to_string);
42 my $g = new Graph::ModularDecomposition;
43  
44 my $h = $g->pairstring_to_graph( 'ab,ac,bc' );
45 print "yes\n" if check_transitive( $h );
46 print "yes\n" if $h->check_transitive; # same thing
47 my $m = $h->modular_decomposition_EGMS;
48 print tree_to_string( $m );
49  
50  
51 =head1 DESCRIPTION
52  
53 This module extends L<Graph::Directed|Graph::Directed> by providing
54 new methods related to modular decomposition.
55  
56 The most important new method is modular_decomposition_EGMS(), which
57 for a directed graph with n vertices finds the modular decomposition
58 tree of the graph in O(n^2) time. Method tree_to_string() may be
59 useful to represent the decomposition tree in a friendlier format;
60 this needs to be explicitly imported.
61  
62 If you need to decompose an undirected graph, represent it as a
63 directed graph by adding two directed edges for each undirected edge.
64  
65 The method classify() uses the modular decomposition tree to classify
66 a directed graph as non-transitive, or for transitive digraphs,
67 as series-parallel (linear or parallel modules only), decomposable
68 (not series-parallel, but with at least one non-primitive module),
69 indecomposable (primitive), decomposable but consisting of primitive
70 or series modules only (only applies to graphs of at least 7 vertices),
71 or unclassified (should never apply).
72  
73 =head2 RELATED WORK
74  
75 Several graph algorithms use the modular decomposition tree as a
76 building block. A simple example application of these routines is
77 to construct and search the modular decomposition tree of a directed
78 graph to determine if it is node-series-parallel.
79 Checking if a digraph is series-parallel can also be determined using
80 the O(m+n) Valdes-Tarjan-Lawler algorithm published in 1982, but this
81 only constructs a decomposition tree if the input is series-parallel:
82 other inputs are simply classified as non-series-parallel.
83  
84 The code here is based on algorithm 6.1 for modular decomposition of
85 two-structures, from
86  
87 A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, and S. J. Sullivan, "An
88 O(n^2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition
89 of Two-Structures and Modular Decomposition of Graphs", Journal of
90 Algorithms 16 (1994), pp. 283-294. doi:10.1006/jagm.1994.1013
91  
92 I am not aware of any other publicly available implementations.
93 Any errors and omissions are of course my fault. Better algorithms
94 are known: O(m+n) run-time can be achieved using sophisticated data
95 structures (where m is the number of edges in the graph), see
96  
97 R. M. McConnell and F. de Montgolfier, "Linear-time modular
98 decomposition of directed graphs", Discrete Applied Mathematics
99 145 (2005), pp. 198-209. doi:10.1016/j.dam.2004.02.017
100  
101  
102 =head2 EXPORT
103  
104 None by default. Methods tree_to_string() and partition_to_string()
105 can be imported. Methods setminus() and setunion() are for internal
106 use but can also be imported.
107  
108  
109 =head2 METHODS
110  
111 =over 4
112  
113 =item debug()
114  
115 my $g = new Graph::ModularDecomposition;
116 Graph::ModularDecomposition->debug(1); # turn on debugging
117 Graph::ModularDecomposition->debug(2); # extra debugging
118 $g->debug(2); # same thing
119 $g->debug(0); # off (default)
120  
121 Manipulates the debug level of this module. Debug output is sent
122 to STDERR. Object-level debugging is not yet supported.
123  
124 =cut
125  
126 19 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
127  
128 19 my $VSEP = '|'; # string used to separate vertices
129 19 my $WSEP = '\|'; # regexp used to separate vertices
130 19 my $PSEP = '\+'; # regexp used to separate elements of partition
131 19 my $QSEP = '+'; # string used to separate elements of partition
132  
133 19 my $MD_Debug = 0;
134  
135 25 ▶sub debug {
Subroutine debug: called CC=4 SCAR=13.9
Pod documented
136 25 my $class = shift;
137 25 ▶ if ( ref($class) ) { $class = ref($class) }
Branch: 1 branch
BranchTrueFalseTotal
if (ref $class) 13 12 25
138 25 $MD_Debug = shift;
139 25 ▶ carp 'Turning ', ($MD_Debug ? 'on' : 'off'), ' ',
Branch: 2 branches
BranchTrueFalseTotal
$MD_Debug ? : 13 12 25
$MD_Debug ? : 13 12 25
140 $class, ' debugging', ($MD_Debug ? ", level $MD_Debug" : '');
141 }
142  
143  
144 =item canonical_form()
145  
146 my $g = new Graph::ModularDecomposition;
147 Graph::ModularDecomposition->canonical_form(1); # on (default)
148 Graph::ModularDecomposition->canonical_form(0); # off
149 $g->canonical_form(1); # same thing
150 $g->canonical_form(0); # off
151 print "yes" if $g->canonical_form();
152  
153 Manipulates whether this module keeps modular decomposition trees in
154 "canonical" form, where lists of vertices are kept sorted. This allows
155 tree_to_string() on two isomorphic decomposition trees to produce the
156 same output (well, sometimes -- a more general solution requires an
157 isomorphism test). Canonical form forces sorting of vertices in several
158 places, which will slow down some of the algorithms. When called with
159 no arguments, returns the current state.
160  
161 =cut
162  
163 19 my $Canonical_form = 1;
164  
165 80 ▶sub canonical_form {
Subroutine canonical_form: called CC=3 SCAR=11.0
Pod documented
166 80 my $class = shift;
167 80 ▶ if ( ref($class) ) { $class = ref($class) }
Branch: 1 branch
BranchTrueFalseTotal
if (ref $class) 80 0 80
168 80 my $cf = shift;
169 80 ▶ return $Canonical_form unless defined $cf;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $cf 79 1 80
170 1 $Canonical_form = $cf;
171 }
172  
173  
174 =item new()
175  
176 my $g = new Graph::ModularDecomposition;
177 $g = Graph::ModularDecomposition->new; # same thing
178 my $h = $g->new;
179  
180 Constructor. The instance method style C<< $object->new >> is an extension
181 and was not present in L<Graph::Directed|Graph::Directed>.
182  
183 =cut
184  
185 217 ▶sub new {
Subroutine new: called CC=2 SCAR=6.9
Pod documented
186 217 my $self = shift;
187 217 ▶ my $class = ref($self) ? ref($self) : $self;
Branch: 1 branch
BranchTrueFalseTotal
ref $self ? : 148 69 217
188 217 return bless $class->SUPER::new(@_,directed=>1), $class;
189 }
190  
191  
192 =item pairstring_to_graph
193  
194 my $g = Graph::ModularDecomposition
195 ->pairstring_to_graph( 'ac, ad, bd' );
196 my $h = $g->pairstring_to_graph( 'a-c, a-d,b-d' ); # same thing
197 my $h = $g->pairstring_to_graph( 'a,b,c,d,a-c,a-d,b-d' ); # same thing
198  
199 use Graph::ModularDecomposition qw( pairstring_to_graph );
200 my $k = pairstring_to_graph( 'Graph::ModularDecomposition',
201 'ac,ad,bd' ); # same thing
202  
203 Convert string of pairs input to Graph::ModularDecomposition output.
204 Allows either 'a-b,b-c,d' or 'ab,bc,d' style notation but these should
205 not be mixed in one string. Vertex labels should not include the
206 '-' character. Use the '-' style if multi-character vertex labels
207 are in use. Single label "pairs" are interpreted as vertices to add.
208  
209 =cut
210  
211 19 ▶sub pairstring_to_graph {
Subroutine pairstring_to_graph: called CC=8 SCAR=20.9
Pod documented
212 19 my $class = shift;
213 0 ▶ if ( ref($class) ) { $class = ref($class) }
Branch: 1 branch
BranchTrueFalseTotal
if (ref $class) 0 19 19
214 19 my $pairs = shift;
215 19 my $g = new $class;
216 19 my ($p, $q);
217 19 ▶ my $s = ( ( index( $pairs, '-' ) >= 0 ) ? '\-' : '' );
Branch: 1 branch
BranchTrueFalseTotal
(index($pairs, '-') != -1) ? : 6 13 19
218 19 foreach my $r ( split /,\s*/, $pairs ) {
219 232 ( $p, $q ) = split $s, $r;
220 232 ▶ print "p=$p, q=$q\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 68 164 232
221 232 ▶ if ( $q ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($q) { } 230 2 232
222 230 ▶ $g = $g->add_edge( $p, $q ) unless $g->has_edge( $p, $q );
Branch: 1 branch
BranchTrueFalseTotal
unless $g->has_edge($p, $q) 229 1 230
223 } else {
224 2 ▶ $g = $g->add_vertex( $p ) unless $g->has_vertex( $p );
Branch: 1 branch
BranchTrueFalseTotal
unless $g->has_vertex($p) 0 2 2
225 }
226 }
227 19 return bless $g, $class;
228 }
229  
230  
231 =item check_transitive()
232  
233 my $g = new Graph::ModularDecomposition;
234 # add some edges...
235 print "transitive" if $g->check_transitive;
236  
237 Returns 1 if input digraph is transitive, '' otherwise. May break if
238 Graph::stringify lists vertices in unsorted order.
239  
240 =cut
241  
242 20 ▶sub check_transitive {
Subroutine check_transitive: called CC=4 SCAR=13.9
Pod documented
243 20 my $g = shift;
244 20 my $g2 = $g->copy;
245 20 my $h = $g->TransitiveClosure_Floyd_Warshall;
246 # get rid of loops
247 20 foreach ( $h->vertices ) { $h->delete_edge( $_, $_ ) }
248 20 foreach ( $g2->vertices ) { $g2->delete_edge( $_, $_ ) }
249 20 ▶ print STDERR "gdct: ", $g, ' vs. ', $h, "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 17 20
250 20 return $h eq $g2;
251 }
252  
253  
254 =item setminus()
255  
256 my @d = setminus( ['a','b','c'], ['b','d'] ); # ('a','c')
257  
258 Given two references to lists, returns the set difference of the two
259 lists as a list. Can be imported.
260  
261 =cut
262  
263 1100 ▶sub setminus {
Subroutine setminus: called CC=4 SCAR=13.9
Pod documented
264 1100 my $X = shift;
265 1100 my $Y = shift;
266 1100 my @X = @{$X};
267 1100 ▶ print STDERR 'setminus# ', @X, ' - ', @{$Y}, ' = ' if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 49 1051 1100
268 1100 foreach my $x ( @{$Y} ) {
269 1275 @X = grep $x ne $_, @X;
270 }
271 1100 ▶ print STDERR @X, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 49 1051 1100
272 1100 return @X;
273 }
274  
275  
276 =item setunion()
277  
278 my @u = setunion(['a','bc',42], [42,4,'a','c']);
279 # ('a','bc',42,4,'c')
280  
281 Given two references to lists, returns the set union of the two lists
282 as a list. Can be imported.
283  
284 =cut
285  
286 507 ▶sub setunion {
Subroutine setunion: called CC=5 SCAR=16.1
Pod documented
287 507 my $X = shift;
288 507 my $Y = shift;
289 507 my @X = @{$X};
290 507 ▶ print STDERR 'setunion# ', @X, ' U ', @{$Y}, ' = ' if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 23 484 507
291 507 foreach my $x ( @{$Y} ) {
292 380 ▶ push @X, $x unless grep $x eq $_, @X;
Branch: 1 branch
BranchTrueFalseTotal
unless grep(($x eq $_), @X) 376 4 380
293 }
294 507 ▶ print STDERR @X, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 23 484 507
295 507 return sort @X;
296 }
297  
298  
299 =item restriction()
300  
301 use Graph::ModularDecomposition;
302 my $G = new Graph::ModularDecomposition;
303 foreach ( 'ac', 'ad', 'bd' ) { $G->add_edge( split // ) }
304 restriction( $G, split(//, 'abdefgh') ); # a-d,b-d
305 $G->restriction( split(//, 'abdefgh') ); # same thing
306  
307 Compute G|X, the subgraph of G induced by X. X is represented as a
308 list of vertices.
309  
310 =cut
311  
312 42 ▶sub restriction {
Subroutine restriction: called CC=3 SCAR=11.0
Pod documented
313 42 my $G = shift;
314 42 ▶ if ( $MD_Debug > 2 ) { print STDERR 'restriction(', ref($G), ")\n" }
Branch: 1 branch
BranchTrueFalseTotal
if ($MD_Debug > 2) 1 41 42
315 42 my $h = ($G->copy)->delete_vertices( setminus( [$G->vertices], [@_] ) );
316 42 ▶ if ( $MD_Debug > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($MD_Debug > 1) 1 41 42
317 1 print STDERR 'restriction(', $G, '|', join($QSEP, @_), ') = ', $h, "\n"
318 }
319 42 return $h;
320 }
321  
322  
323 =item factor()
324  
325 $h = factor( $g, [['a','b'], ['c'], ['d','e','f']] );
326 $h = $g->factor( [[qw(a b)], ['c'], [qw(d e f)]] ); # same thing
327  
328 Compute G/P for partition P containing modules. Will fail in odd
329 ways if members of P are not modules.
330  
331 =cut
332  
333 22 ▶sub factor {
Subroutine factor: called CC=13 SCAR=25.7
Pod documented
334 22 my $G = shift;
335 22 my $P = shift;
336 22 my $GP = $G->copy;
337 22 my $p;
338 22 foreach my $X ( @{$P} ) {
339 67 ▶ print STDERR "factor# X = $X\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 3 64 67
340 67 ▶ print STDERR "factor# \@X = @$X\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 3 64 67
341 67 my $newnode = join $VSEP, @{$X}; # turn nodes a, b, c into new node abc
342 67 ▶ print STDERR "factor# newnode = $newnode\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 3 64 67
343 67 my $a = ${$X}[0];
344 67 ▶ print STDERR "factor# representative node $a\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 3 64 67
345 67 ▶ if ( $newnode ne $a ) { # do nothing if singleton
Branch: 1 branch
BranchTrueFalseTotal
if ($newnode ne $a) 15 52 67
346 15 $GP->add_vertex( $newnode );
347 15 foreach $p ( $GP->predecessors( $a ) ) {
348 12 ▶ print STDERR "factor# predecessor $p\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 3 9 12
349 12 ▶ $GP = $GP->add_edge( $p, $newnode )
Branch: 1 branch
BranchTrueFalseTotal
unless $GP->has_edge($p, $newnode) 12 0 12
350 unless $GP->has_edge( $p, $newnode );
351 }
352 15 foreach $p ( $GP->successors( $a ) ) {
353 28 ▶ print STDERR "factor# successor $p\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 8 20 28
354 28 ▶ $GP = $GP->add_edge( $newnode, $p )
Branch: 1 branch
BranchTrueFalseTotal
unless $GP->has_edge($newnode, $p) 28 0 28
355 unless $GP->has_edge( $newnode, $p );
356 }
357 15 $GP = $GP->delete_vertices( @{$X} );
358 }
359 }
360 22 return $GP;
361 }
362  
363  
364 =item partition_subsets()
365  
366 @part = partition_subsets( $G, ['a','b','c'], $w );
367 @part = $G->partition_subsets( ['a','b','c'], $w ); # same thing
368  
369 Partition set of vertices into maximal subsets not distinguished by w in G.
370  
371 =cut
372  
373 415 ▶sub partition_subsets {
Subroutine partition_subsets: called CC=11 SCAR=24.0
Pod documented
374 415 my $G = shift;
375 415 my $S = shift;
376 415 my $w = shift;
377  
378 415 ▶ print STDERR 'p..n_subsets# @S = ', @{$S}, ", w = $w \n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 19 396 415
379 415 my (@A, @B, @C, @D);
380 415 foreach my $x ( @{$S} ) {
381 697 ▶ print STDERR 'p..n_subsets# xw = ', $x, $w if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 33 664 697
382 697 ▶ if ( $G->has_edge( $w, $x ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($G->has_edge($w, $x)) { } 165 532 697
383 165 ▶ if ( $G->has_edge( $x, $w ) ) { # xw wx (not poset)
Branch: 1 branch
BranchTrueFalseTotal
if ($G->has_edge($x, $w)) { } 2 163 165
384 2 push @A, $x;
385 2 ▶ print STDERR ' A = ', @A, "\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 1 1 2
386 } else { # ~xw wx
387 163 push @B, $x;
388 163 ▶ print STDERR ' B = ', @B, "\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 6 157 163
389 }
390 } else {
391 532 ▶ if ( $G->has_edge( $x, $w ) ) { # xw ~wx
Branch: 1 branch
BranchTrueFalseTotal
if ($G->has_edge($x, $w)) { } 132 400 532
392 132 push @C, $x;
393 132 ▶ print STDERR ' C = ', @C, "\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 7 125 132
394 } else { # ~xw ~wx
395 400 push @D, $x;
396 400 ▶ print STDERR ' D = ', @D, "\n" if $MD_Debug > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 2 19 381 400
397 }
398 }
399 }
400 415 return grep @{$_}, (\@A, \@B, \@C, \@D);
401 }
402  
403  
404 =item partition()
405  
406 my $p = partition( $g, $v );
407 $p = $g->partition( $v ); # same thing
408  
409 For a graph, calculate maximal modules not including a given vertex.
410  
411 =cut
412  
413 47 ▶sub partition {
Subroutine partition: called CC=10 SCAR=23.0
Pod documented
414 47 my $G = shift;
415 47 my $v = shift;
416  
417 47 ▶ print STDERR 'partition# G = ', $G, ", v = $v\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 2 45 47
418 47 my (%L, @done, $tempset, $S, @ZS, $w);
419 47 $S = [ setminus( [ $G->vertices ], [ $v ] ) ];
420 47 ▶ print STDERR 'partition# @S = ', @{$S}, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 2 45 47
421 47 $L{$S} = [ $v ];
422 47 my @todo = ( $S );
423 47 ▶ print STDERR 'partition# L{S}[0] = ', $L{$S}[0], "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 2 45 47
424 47 ▶ while ( @todo ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@todo) 408 47 455
425 408 $S = shift @todo;
426 408 @ZS = @{$L{$S}};
427 408 $w = $ZS[0];
428 408 ▶ print STDERR 'partition# ZS = ', @ZS, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 19 389 408
429 408 delete $L{$S};
430 408 foreach my $W ( $G->partition_subsets( $S, $w ) ) {
431 505 ▶ print STDERR 'partition# W = ', @{$W}, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 23 482 505
432 505 $tempset = [ setunion( [ setminus( $S, $W ) ],
433 [ setminus( \@ZS, [ $w ] ) ] ) ];
434 505 ▶ if ( @{$tempset} ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@{$tempset;}) { } 361 144 505
435 361 ▶ print STDERR 'partition# tempset = ', @{$tempset}, "\n"
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 17 344 361
436 if $MD_Debug > 1;
437 361 $L{$W} = $tempset;
438 361 push @todo, $W;
439 } else {
440 144 push @done, $W;
441 }
442 }
443 }
444 47 return \@done;
445 }
446  
447  
448 =item distinguishes()
449  
450 print "yes" if distinguishes( $g, $x, $y, $z );
451 print "yes" if $g->distinguishes( $x, $y, $z ); # same thing
452  
453 True if vertex $x distinguishes vertices $y and $z in graph $g.
454  
455 =cut
456  
457 314 ▶sub distinguishes {
Subroutine distinguishes: called CC=7 SCAR=19.5
Pod documented
458 314 my ($g,$x,$y,$z) = @_;
459 314 ▶ print STDERR " $x$y?", $g->has_edge($x,$y) if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 10 304 314
460 314 ▶ print STDERR " $x$z?", $g->has_edge($x,$z) if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 10 304 314
461 314 ▶ print STDERR " $y$x?", $g->has_edge($y,$x) if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 10 304 314
462 314 ▶ print STDERR " $z$x?", $g->has_edge($z,$x) if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 10 304 314
463 314 ▶ my $ret = ( $g->has_edge($x,$y) != $g->has_edge($x,$z) )
Condition100%3/3
$g->has_edge($x, $y) != $g->has_edge($x, $z) || $g->has_edge($y, $x) != $g->has_edge($z, $x)
l!l&&r!l&&!r
9574145
MC/DC100%2/2
$g->has_edge($x, $y) != $g->has_edge($x, $z) || $g->has_edge($y, $x) != $g->has_edge($z, $x)
$g->has_edge($x, $y) != $g->has_edge($x, $z) $g->has_edge($y, $x) != $g->has_edge($z, $x)
Truth table100%3/3
A || B
A= $g->has_edge($x, $y) != $g->has_edge($x, $z)B= $g->has_edge($y, $x) != $g->has_edge($z, $x)
ABresult
1X1
011
000
464 || ( $g->has_edge($y,$x) != $g->has_edge($z,$x) );
465 314 ▶ print STDERR "=$ret\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 10 304 314
466 314 return $ret;
467 }
468  
469  
470 =item G()
471  
472 $G = G( $g, $v );
473 $G = $g->G( $v ); # same thing
474  
475 "Trivially" calculate G(g,v). dom(G(g,v)) = dom(g)\{v}, and (x,y) is
476 an edge of G(g,v) whenever x distinguishes y and v in g.
477  
478 =cut
479  
480 30 ▶sub G {
Subroutine G: called CC=12 SCAR=24.9
Pod documented
481 30 my $g = shift;
482 30 my $v = shift;
483 30 my $G = new ref($g);
484 30 ▶ print STDERR 'G([', $g, "], $v) =...\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 4 26 30
485 30 X: foreach my $x ( $g->vertices ) {
486 123 ▶ next X if ( $v eq $x );
Branch: 1 branch
BranchTrueFalseTotal
if $v eq $x 30 93 123
487 93 ▶ print STDERR 'X=', $x, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 3 90 93
488 93 $G = $G->add_vertex( $x );
489 93 Y: foreach my $y ( $g->vertices ) {
490 490 ▶ next Y if ( $v eq $y or $x eq $y );
Branch: 1 branch
BranchTrueFalseTotal
if $v eq $y or $x eq $y 186 304 490
Condition100%3/3
$v eq $y or $x eq $y
l!l&&r!l&&!r
9393304
MC/DC100%2/2
$v eq $y or $x eq $y
$v eq $y $x eq $y
Truth table100%3/3
A or B
A= $v eq $yB= $x eq $y
ABresult
1X1
011
000
491 304 ▶ print STDERR 'Y=', $y, "\n" if $MD_Debug > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug > 1 6 298 304
492 304 ▶ if ( $g->distinguishes( $x, $y, $v ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->distinguishes($x, $y, $v)) 164 140 304
493 164 ▶ $G = $G->add_edge( $x, $y ) unless $G->has_edge( $x, $y );
Branch: 1 branch
BranchTrueFalseTotal
unless $G->has_edge($x, $y) 164 0 164
494 }
495 }
496 }
497 30 ▶ print STDERR '...G()=', $G, "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 4 26 30
498 30 return $G;
499 }
500  
501  
502 =item tree_to_string()
503  
504 print tree_to_string( $t );
505  
506 String representation of decomposition tree. Returns empty string for
507 an empty decomposition tree. Needs to be explicitly imported. If
508 Graph::vertices returns the vertices in unsorted order, then isomorphic
509 trees can have different string representations.
510  
511 =cut
512  
513 106 ▶sub tree_to_string {
Subroutine tree_to_string: called CC=6 SCAR=17.9
Pod documented
514 106 my $t = shift;
515 106 my $s = '';
516 106 ▶ return $s unless defined $t->{type};
Branch: 1 branch
BranchTrueFalseTotal
unless defined $t->{"type"} 6 100 106
517 100 ▶ $s .= $t->{type} if $t->{type} ne 'leaf';
Branch: 1 branch
BranchTrueFalseTotal
if $t->{"type"} ne "leaf" 28 72 100
518 100 ▶ $s .= '_' . $t->{col} if ( $t->{type} eq 'complete' );
Branch: 1 branch
BranchTrueFalseTotal
if $t->{"type"} eq "complete" 6 94 100
519 100 $s .= '[' . $t->{value} . ']';
520 100 ▶ if ( $t->{type} ne 'leaf' ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($t->{"type"} ne "leaf") 28 72 100
521 28 my $sep = '';
522 28 $s .= '(';
523 28 foreach ( @{$t->{children}} ) {
524 73 $s .= $sep . tree_to_string( $_ );
525 73 $sep = ';';
526 }
527 28 $s .= ')';
528 }
529 100 return $s;
530 }
531  
532  
533 =item partition_to_string
534  
535 print partition_to_string([['h'], [qw(c a b)], [qw(d e f g)]]);
536 # a+b+c,d+e+f+g,h
537  
538 String representation of partition. Returns empty string for an
539 empty partition. Needs to be explicitly imported.
540  
541 =cut
542  
543 36 ▶sub partition_to_string {
Subroutine partition_to_string: called CC=1 SCAR=0.0
Pod documented
544 36 return join ',', sort (map { join $QSEP, sort @{$_} } @{+shift});
545 }
546  
547  
548 =item modular_decomposition_EGMS()
549  
550 use Graph::ModularDecomposition;
551 $g = new Graph::ModularDecomposition;
552 $m = $g->modular_decomposition_EGMS;
553  
554 Compute modular decomposition tree of the input, which must be
555 a Graph::ModularDecomposition object, using algorithm 6.1 of
556 A. Ehrenfeucht, H. N. Gabow, R. M. McConnell, S. J. Sullivan, "An
557 O(n^2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition
558 of Two-Structures and Modular Decomposition of Graphs", Journal of
559 Algorithms 16 (1994), pp. 283-294.
560  
561 The decomposition tree consists of nodes with attributes: 'type' is
562 a string matching /^leaf|primitive|complete|linear$/, 'children' is
563 a reference to a potentially empty list of pointers to other nodes,
564 'value' is a string with the vertices in the decomposition defined
565 by the tree, separated by '|' (VSEP), and 'col' is a string containing the
566 colour of the module, matching /^0|1|01$/. A node with 'type' of
567 'complete' is parallel if 'col' is '0' and series if 'col' is '1'.
568 A node with 'type' of 'linear' has 'col' of '01'. Use the function
569 tree_to_string() to convert the tree into a more generally usable form.
570  
571 =cut
572  
573 57 ▶sub modular_decomposition_EGMS {
Subroutine modular_decomposition_EGMS: called CC=34 SCAR=35.4
Pod documented
574 57 my $g = shift;
575 57 my $md = 0;
576 57 $md ++;
577 57 my $B = ' 'x$md;
578 57 ▶ print STDERR $B, 'MD(', $g, ")=...\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 9 48 57
579 57 my $v = ($g->vertices)[0];
580 57 ▶ print STDERR $B, 'v=', (defined($v) ? $v : 'undef'), "\n" if $MD_Debug;
Branch: 2 branches
BranchTrueFalseTotal
if $MD_Debug 9 48 57
defined $v ? : 7 2 9
581  
582 57 my $t = {};
583 57 ▶ unless ( $v ) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($v) 3 54 57
584 3 ▶ print STDERR $B, '...MD=', tree_to_string( $t ), "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 2 1 3
585 3 $md --;
586 3 return $t;
587 }
588 54 $t->{type} = 'leaf';
589 54 $t->{children} = [];
590 54 ▶ if ($g->canonical_form()) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->canonical_form) { } 54 0 54
591 54 $t->{value} = join($VSEP, sort($g->vertices));
592 } else {
593 0 $t->{value} = join($VSEP, $g->vertices);
594 }
595 54 $t->{col} = '0';
596  
597 54 ▶ if ( scalar $g->vertices == 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (scalar $g->vertices == 1) 35 19 54
598 35 ▶ print STDERR $B, '...MD=', tree_to_string( $t ), "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 4 31 35
599 35 $md --;
600 35 return $t;
601 }
602  
603 19 my $p = partition( $g, $v );
604 19 push @{$p}, [ $v ];
605 19 my $gd = $g->factor( $p );
606 19 ▶ print STDERR $B, 'gd = ', $gd, "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 16 19
607 19 my $Gdd = $gd->G($v)->strongly_connected_graph;
608 19 ▶ print STDERR $B, 'Gdd = [', $Gdd, '], ', scalar $Gdd->vertices, "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 16 19
609  
610 19 my $u = $t;
611 19 my @f;
612 19 ▶ while ( @f = grep( $Gdd->out_degree($_) == 0 , $Gdd->vertices ) ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@f = grep(($Gdd->out_degree($_) == 0), $Gdd->vertices)) 24 19 43
613 24 ▶ print STDERR $B, "\@f=[@f]\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 21 24
614 24 my @s;
615 24 foreach my $s ( $Gdd->vertices ) {
616 35 push @s, split(/$PSEP/, $s);
617 }
618 24 ▶ if ($g->canonical_form()) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->canonical_form) { } 24 0 24
619 24 $u->{value} = join('', sort($v, @s));
620 } else {
621 0 $u->{value} = join('', ($v, @s));
622 }
623 24 my $w = {};
624 24 $w->{type} = 'leaf';
625 24 $w->{children} = [];
626 24 $w->{value} = $v;
627 24 $w->{col} = '0';
628 24 push @{$u->{children}}, $w;
629  
630 24 $Gdd->delete_vertices( @f );
631 24 my @F;
632 24 foreach my $f ( @f ) {
633 25 foreach my $F ( split /$PSEP/, $f ) {
634 39 ▶ push @F, $F unless grep $F eq $_, @F;
Branch: 1 branch
BranchTrueFalseTotal
unless grep(($F eq $_), @F) 39 0 39
635 }
636 }
637 24 ▶ print STDERR $B, "\@F=@F\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 21 24
638 24 ▶ if ( @f == 1 and @F > 1 ) {
Branch: 1 branch
BranchTrueFalseTotal
if (@f == 1 and @F > 1) { } 7 17 24
Condition100%3/3
@f == 1 and @F > 1
!ll&&!rl&&r
1167
MC/DC100%2/2
@f == 1 and @F > 1
@f == 1 @F > 1
Truth table100%3/3
A and B
A= @f == 1B= @F > 1
ABresult
0X0
100
111
639 7 $u->{type} = 'primitive';
640 7 $u->{col} = '0';
641 } else {
642 17 my $x = substr $F[0], 0, 1; # single-char vertex names!
643 17 ▶ if ( $g->has_edge($v, $x) == $g->has_edge($x, $v) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($g->has_edge($v, $x) == $g->has_edge($x, $v)) { } 6 11 17
644 6 $u->{type} = 'complete'; # 0 parallel, 1 series
645 6 ▶ $u->{col} = $g->has_edge($v, $x) ? '1' : '0';
Branch: 1 branch
BranchTrueFalseTotal
$g->has_edge($v, $x) ? : 0 6 6
646 } else {
647 11 $u->{type} = 'linear';
648 11 $u->{col} = '01';
649 }
650 }
651 24 ▶ print STDERR $B, 'u = ', tree_to_string( $u ), "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 21 24
652 24 foreach my $X ( @F ) {
653 39 my $m = $g->restriction( split /$WSEP/, $X )
654 ->modular_decomposition_EGMS;
655 39 ▶ if ( defined $m->{col}
Branch: 1 branch
BranchTrueFalseTotal
if (defined $m->{'col'} and $u->{'col'} eq $m->{'col'} and $u->{'type'} eq 'complete' && $m->{'type'} eq 'complete' || $u->{'type'} eq 'linear' && $m->{'type'} eq 'linear') { } 2 37 39
Condition73%11/15
defined $m->{"col"} and $u->{"col"} eq $m->{"col"} and $u->{"type"} eq "complete" && $m->{"type"} eq "complete" || $u->{"type"} eq "linear" && $m->{"type"} eq "linear"
!ll&&!rl&&r
12252
defined $m->{"col"} and $u->{"col"} eq $m->{"col"}
!ll&&!rl&&r
01227
$u->{"type"} eq "complete" and $m->{"type"} eq "complete" or $u->{"type"} eq "linear" and $m->{"type"} eq "linear"
l!l&&r!l&&!r
0225
$u->{"type"} eq "complete" and $m->{"type"} eq "complete"
!ll&&!rl&&r
2340
$u->{"type"} eq "linear" and $m->{"type"} eq "linear"
!ll&&!rl&&r
2502
MC/DC33%2/6
defined $m->{"col"} and $u->{"col"} eq $m->{"col"} and $u->{"type"} eq "complete" && $m->{"type"} eq "complete" || $u->{"type"} eq "linear" && $m->{"type"} eq "linear"
defined $m->{"col"} $u->{"col"} eq $m->{"col"} $u->{"type"} eq "complete" $m->{"type"} eq "complete" $u->{"type"} eq "linear" $m->{"type"} eq "linear"
Truth table44%4/9
A and B and C and D or E and F
A= defined $m->{"col"}B= $u->{"col"} eq $m->{"col"}C= $u->{"type"} eq "complete"D= $m->{"type"} eq "complete"E= $u->{"type"} eq "linear"F= $m->{"type"} eq "linear"
ABCDEFresult
0XXXXX0
10XXXX0
110X0X0
110X100
11100X0
1110100
1111XX1
110X111
1110111
656 and ( $u->{col} eq $m->{col} )
657 and (
658 ( $u->{type} eq 'complete' and $m->{type} eq 'complete' )
659 or ( $u->{type} eq 'linear' and $m->{type} eq 'linear' )
660 )
661 ) {
662 2 ▶ if ( $MD_Debug ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($MD_Debug) 1 1 2
663 1 print STDERR $B, "u->children= @{$u->{children}}\n";
664 1 print STDERR $B, 'm->children= ';
665 1 my $sep = '';
666 1 foreach ( @{$m->{children}} ) {
667 2 print STDERR $sep, '[', tree_to_string( $_ ), ']';
668 2 $sep = ', ';
669 }
670 1 print STDERR "\n";
671 }
672 2 push @{$u->{children}}, @{$m->{children}};
673 } else {
674 37 push @{$u->{children}}, $m;
675 }
676 }
677 24 $u = $w;
678 }
679 19 ▶ print STDERR $B, '...MD=', tree_to_string( $t ), "\n" if $MD_Debug;
Branch: 1 branch
BranchTrueFalseTotal
if $MD_Debug 3 16 19
680 19 $md --;
681 19 return $t;
682 }
683  
684  
685 =item classify()
686  
687 use Graph::ModularDecomposition;
688 my $g = new Graph::ModularDecomposition;
689 my $c = classify( $g );
690 $c = $g->classify; # same thing
691  
692 Based on the modular decomposition tree, returns:
693 n non-transitive
694 i indecomposable
695 d decomposable but not SP, at least one non-primitive node
696 s series-parallel
697 p decomposable but each module is primitive or series
698 u unclassified: should not happen
699  
700 =cut
701  
702 17 ▶sub classify {
Subroutine classify: called CC=7 SCAR=19.5
Pod documented
703 17 my $g = shift;
704 17 ▶ return 'n' unless $g->check_transitive;
Branch: 1 branch
BranchTrueFalseTotal
unless $g->check_transitive 3 14 17
705 14 my $s = tree_to_string( $g->modular_decomposition_EGMS );
706 14 ▶ return 'i' if $s =~ m/^primitive\[[^\]]+\]\([^\(]*$/;
Branch: 1 branch
BranchTrueFalseTotal
if $s =~ /^primitive\[[^\]]+\]\([^\(]*$/ 3 11 14
707 11 ▶ return 'd' if $s =~ m/primitive/ and $s =~ m/complete_|linear/;
Branch: 1 branch
BranchTrueFalseTotal
if $s =~ /primitive/ and $s =~ /complete_|linear/ 1 10 11
Condition100%3/3
$s =~ /primitive/ and $s =~ /complete_|linear/
!ll&&!rl&&r
911
MC/DC100%2/2
$s =~ /primitive/ and $s =~ /complete_|linear/
$s =~ /primitive/ $s =~ /complete_|linear/
Truth table100%3/3
A and B
A= $s =~ /primitive/B= $s =~ /complete_|linear/
ABresult
0X0
100
111
708 10 ▶ return 's' if $s !~ m/primitive|complete_1/; # matches empty string
Branch: 1 branch
BranchTrueFalseTotal
unless $s =~ /primitive|complete_1/ 9 1 10
709 1 ▶ return 'p' if $s =~ m/primitive|complete_1/;
Branch: 1 branch
BranchTrueFalseTotal
if $s =~ /primitive|complete_1/ 1 0 1
710 0 return 'u';
711 }
712  
713  
714 =item to_bitvector2()
715  
716 $b = $g->to_bitvector2;
717  
718 Convert input graph to Bitvector2 output.
719 L<Graph::Directed|Graph::Directed> version 20104 permits
720 multi-edges; these will be collapsed into a single edge in the
721 output Bitvector2. The Bitvector2 is relative to the unique
722 lexicographic ordering of the vertices. This method is only present
723 if L<Graph::Bitvector2|Graph::Bitvector2> is found.
724  
725 =cut
726  
727 0 ▶eval {require Graph::Bitvector2; 1} and # alas, circular dependency here
Branch: 1 branch
BranchTrueFalseTotal
eval { do { require Graph::Bitvector2; 1 } } and eval "\n sub to_bitvector2 {\n\tmy \$g = shift;\n\tmy \@v = sort \$g->vertices;\n\tmy \@bits;\n\twhile ( \@v ) {\n\t my \$x = shift \@v;\n\t foreach my \$y ( \@v ) {\n\t\tpush \@bits, (\n\t\t \$g->has_edge( \$x, \$y )\n\t\t ? 1\n\t\t : ( \$g->has_edge( \$y, \$x ) ? 2 : 0 )\n\t\t);\n\t }\n\t}\n\treturn new Graph::Bitvector2 (join '', \@bits);\n }\n" 0 19 19
728 eval q{
729 sub to_bitvector2 {
730 my $g = shift;
731 my @v = sort $g->vertices;
732 my @bits;
733 while ( @v ) {
734 my $x = shift @v;
735 foreach my $y ( @v ) {
736 push @bits, (
737 $g->has_edge( $x, $y )
738 ? 1
739 : ( $g->has_edge( $y, $x ) ? 2 : 0 )
740 );
741 }
742 }
743 return new Graph::Bitvector2 (join '', @bits);
744 }
745 };
746  
747  
748 =back
749  
750 =cut
751  
752 19 1;
753 __END__
↑ Summary