Hello community, here is the log from the commit of package perl-Graph for openSUSE:Factory checked in at 2013-06-06 13:23:31 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/perl-Graph (Old) and /work/SRC/openSUSE:Factory/.perl-Graph.new (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "perl-Graph" Changes: -------- --- /work/SRC/openSUSE:Factory/perl-Graph/perl-Graph.changes 2011-11-21 12:40:42.000000000 +0100 +++ /work/SRC/openSUSE:Factory/.perl-Graph.new/perl-Graph.changes 2013-06-06 13:23:33.000000000 +0200 @@ -1,0 +2,28 @@ +Wed Jun 5 05:50:19 UTC 2013 - co...@suse.com + +- updated to 0.96 + * Address rt.cpan.org #85449: + "Graph-0.94 tests fail under perl 5.18.0" + + * Address rt.cpan.org #82324: + "Test failures due to hash randomisation in perl 5.17.6" + + The two above fixes were the same: the biconnectedness + code was rewritten from scratch. The new code behaves + differently (but I believe more correctly) on certain + edge cases, in general it will generate more biconnected + components and bridges, for example for "a=b=c" it will + now return the same two biconnected components and bridges + (cut edges), namely "a=b" and "b=c", the "b" of course being + the articulation point (cut vertex). + + * Address rt.cpan.org #67213: + "[PATCH] pod fixes" + + * Remove the t/u_bo.t and t/u_bo1.t since they die in 5.18 due + to some strange failure, looks unrelated to Graph as such, + probably some fix/change made by newer Perls. + + * Release as 0.95. + +------------------------------------------------------------------- Old: ---- Graph-0.94.tar.gz New: ---- Graph-0.96.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ perl-Graph.spec ++++++ --- /var/tmp/diff_new_pack.0RPw5Z/_old 2013-06-06 13:23:34.000000000 +0200 +++ /var/tmp/diff_new_pack.0RPw5Z/_new 2013-06-06 13:23:34.000000000 +0200 @@ -1,7 +1,7 @@ # # spec file for package perl-Graph # -# Copyright (c) 2011 SUSE LINUX Products GmbH, Nuernberg, Germany. +# Copyright (c) 2013 SUSE LINUX Products GmbH, Nuernberg, Germany. # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -15,55 +15,31 @@ # Please submit bugfixes or comments via http://bugs.opensuse.org/ # -# norootforbuild - -%bcond_with pod Name: perl-Graph +Version: 0.96 +Release: 0 %define cpan_name Graph Summary: Graph data structures and algorithms -Version: 0.94 -Release: 1 -License: GPL-1.0+ or Artistic-1.0 +License: Artistic-1.0 or GPL-1.0+ Group: Development/Libraries/Perl Url: http://search.cpan.org/dist/Graph/ -#Source: http://www.cpan.org/modules/by-module/Graph/Graph-%{version}.tar.gz -Source: %{cpan_name}-%{version}.tar.gz +Source: http://www.cpan.org/authors/id/J/JH/JHI/%{cpan_name}-%{version}.tar.gz BuildArch: noarch BuildRoot: %{_tmppath}/%{name}-%{version}-build -%{perl_requires} BuildRequires: perl BuildRequires: perl-macros -%if %{with pod} -BuildRequires: perl(Test::Pod) >= 1.00 -BuildRequires: perl(Test::Pod::Coverage) >= 1.00 -%endif -BuildRequires: perl(Test::More) -BuildRequires: perl(List::Util) -BuildRequires: perl(Math::Complex) -BuildRequires: perl(Scalar::Util) -# further mention if perl >= 5.008 -BuildRequires: perl(Safe) -BuildRequires: perl(Storable) >= 2.05 -# -Requires: perl(List::Util) -Requires: perl(Math::Complex) -Requires: perl(Scalar::Util) -# further mention if perl >= 5.008 +# MANUAL further mention if perl >= 5.008 Requires: perl(Safe) Requires: perl(Storable) >= 2.05 +%{perl_requires} %description -Graph::Directed allows you to create directed graphs. -For the available methods, see Graph. -http://search.cpan.org/~jhi/Graph-0.94/lib/Graph.pod - -Authors: --------- - Jarkko Hietaniemi <j...@iki.fi> +graph data structures and algorithms %prep %setup -q -n %{cpan_name}-%{version} +find . -type f -print0 | xargs -0 chmod 644 %build %{__perl} Makefile.PL INSTALLDIRS=vendor @@ -74,20 +50,11 @@ %install %perl_make_install -# do not perl_process_packlist (noarch) -# remove .packlist file -%{__rm} -rf $RPM_BUILD_ROOT%perl_vendorarch -# remove perllocal.pod file -%{__rm} -rf $RPM_BUILD_ROOT%perl_archlib -# rpmlint: auto directory is included in the perl package -%{__rm} -rf $RPM_BUILD_ROOT%perl_vendorlib/auto +%perl_process_packlist %perl_gen_filelist -%clean -%{__rm} -rf $RPM_BUILD_ROOT - %files -f %{name}.files -%defattr(-,root,root,-) -%doc Changes DESIGN README RELEASE TODO +%defattr(-,root,root,755) +%doc Changes DESIGN README RELEASE TODO util %changelog ++++++ Graph-0.94.tar.gz -> Graph-0.96.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/Changes new/Graph-0.96/Changes --- old/Graph-0.94/Changes 2010-03-13 22:12:06.000000000 +0100 +++ new/Graph-0.96/Changes 2013-05-25 01:00:20.000000000 +0200 @@ -1,3 +1,37 @@ +As of 0.95 Graph is unsupported, sorry about that. See README. + +2013-05-24 Jarkko Hietaniemi <j...@iki.fi> + + * Mop-up release for 0.95. Still is and will be unsupported. + + * Release as 0.96. + +2013-05-23 Jarkko Hietaniemi <j...@iki.fi> + + * Address rt.cpan.org #85449: + "Graph-0.94 tests fail under perl 5.18.0" + + * Address rt.cpan.org #82324: + "Test failures due to hash randomisation in perl 5.17.6" + + The two above fixes were the same: the biconnectedness + code was rewritten from scratch. The new code behaves + differently (but I believe more correctly) on certain + edge cases, in general it will generate more biconnected + components and bridges, for example for "a=b=c" it will + now return the same two biconnected components and bridges + (cut edges), namely "a=b" and "b=c", the "b" of course being + the articulation point (cut vertex). + + * Address rt.cpan.org #67213: + "[PATCH] pod fixes" + + * Remove the t/u_bo.t and t/u_bo1.t since they die in 5.18 due + to some strange failure, looks unrelated to Graph as such, + probably some fix/change made by newer Perls. + + * Release as 0.95. + 2010-03-13 Jarkko Hietaniemi <j...@iki.fi> * Address rt.cpan.org #43580: diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/MANIFEST new/Graph-0.96/MANIFEST --- old/Graph-0.94/MANIFEST 2010-03-13 20:57:52.000000000 +0100 +++ new/Graph-0.96/MANIFEST 2013-05-24 12:35:31.000000000 +0200 @@ -137,8 +137,6 @@ t/u_bill.t t/u_bb_rv.t t/u_bf.t -t/u_bo.t -t/u_bo1.t t/u_bo_ap1.t t/u_bo_ap2.t t/u_bo_apx.t @@ -163,3 +161,4 @@ util/renum.pl util/size.pl util/srand.pl +META.json Module JSON meta-data (added by MakeMaker) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/META.json new/Graph-0.96/META.json --- old/Graph-0.94/META.json 1970-01-01 01:00:00.000000000 +0100 +++ new/Graph-0.96/META.json 2013-05-25 01:04:13.000000000 +0200 @@ -0,0 +1,46 @@ +{ + "abstract" : "unknown", + "author" : [ + "Jarkko Hietaniemi <j...@iki.fi>" + ], + "dynamic_config" : 1, + "generated_by" : "ExtUtils::MakeMaker version 6.66, CPAN::Meta::Converter version 2.120921", + "license" : [ + "perl_5" + ], + "meta-spec" : { + "url" : "http://search.cpan.org/perldoc?CPAN::Meta::Spec";, + "version" : "2" + }, + "name" : "Graph", + "no_index" : { + "directory" : [ + "t", + "inc" + ] + }, + "prereqs" : { + "build" : { + "requires" : { + "ExtUtils::MakeMaker" : "0" + } + }, + "configure" : { + "requires" : { + "ExtUtils::MakeMaker" : "0" + } + }, + "runtime" : { + "requires" : { + "List::Util" : "0", + "Math::Complex" : "0", + "Safe" : "0", + "Scalar::Util" : "0", + "Storable" : "2.05", + "Test::More" : "0" + } + } + }, + "release_status" : "stable", + "version" : "0.96" +} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/META.yml new/Graph-0.96/META.yml --- old/Graph-0.94/META.yml 2010-03-13 22:13:46.000000000 +0100 +++ new/Graph-0.96/META.yml 2013-05-25 01:04:13.000000000 +0200 @@ -1,27 +1,27 @@ ---- #YAML:1.0 -name: Graph -version: 0.94 -abstract: ~ +--- +abstract: unknown author: - - Jarkko Hietaniemi <j...@iki.fi> -license: perl -distribution_type: module -configure_requires: - ExtUtils::MakeMaker: 0 + - 'Jarkko Hietaniemi <j...@iki.fi>' build_requires: - ExtUtils::MakeMaker: 0 -requires: - List::Util: 0 - Math::Complex: 0 - Safe: 0 - Scalar::Util: 0 - Storable: 2.05 - Test::More: 0 -no_index: - directory: - - t - - inc -generated_by: ExtUtils::MakeMaker version 6.55_02 + ExtUtils::MakeMaker: 0 +configure_requires: + ExtUtils::MakeMaker: 0 +dynamic_config: 1 +generated_by: 'ExtUtils::MakeMaker version 6.66, CPAN::Meta::Converter version 2.120921' +license: perl meta-spec: - url: http://module-build.sourceforge.net/META-spec-v1.4.html - version: 1.4 + url: http://module-build.sourceforge.net/META-spec-v1.4.html + version: 1.4 +name: Graph +no_index: + directory: + - t + - inc +requires: + List::Util: 0 + Math::Complex: 0 + Safe: 0 + Scalar::Util: 0 + Storable: 2.05 + Test::More: 0 +version: 0.96 diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/README new/Graph-0.96/README --- old/Graph-0.94/README 2005-01-01 14:31:25.000000000 +0100 +++ new/Graph-0.96/README 2013-05-24 03:54:58.000000000 +0200 @@ -1,3 +1,17 @@ +*** +*** As of Graph 0.95 the Graph module is unsupported since I have +*** utterly and completely ran out of time to support it. It still +*** mostly works, amazingly enough, but what is broken or unfinished +*** will remain so. Three year interval between releases should tell +*** you something. +*** +*** If someone feels like rewriting Graph, I can offer some ideas. +*** But the existing code as such is an unmaintainable pile of horrors. +*** My apologies. +*** +*** <gandalf>I have no memory of this place.</gandalf> +*** + This is Graph, a Perl module for dealing with graphs, the abstract data structures. (If you were looking for pie charts, I'm sorry.) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/lib/Graph/Traversal/BFS.pm new/Graph-0.96/lib/Graph/Traversal/BFS.pm --- old/Graph-0.94/lib/Graph/Traversal/BFS.pm 2004-10-30 11:18:14.000000000 +0200 +++ new/Graph-0.96/lib/Graph/Traversal/BFS.pm 2013-05-24 03:21:38.000000000 +0200 @@ -31,7 +31,7 @@ my $g = Graph->new; $g->add_edge(...); use Graph::Traversal::BFS; - my $b = Graph::Traversal::BFS->new(%opt); + my $b = Graph::Traversal::BFS->new($g, %opt); $b->bfs; # Do the traversal. =head1 DESCRIPTION @@ -46,9 +46,10 @@ =over 4 -=item dfs +=item bfs -Traverse the graph in depth-first order. +Traverse the graph in breadth-first order. Returns all vertices +traversed in post-order. =back diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/lib/Graph/Traversal/DFS.pm new/Graph-0.96/lib/Graph/Traversal/DFS.pm --- old/Graph-0.94/lib/Graph/Traversal/DFS.pm 2004-10-30 11:17:57.000000000 +0200 +++ new/Graph-0.96/lib/Graph/Traversal/DFS.pm 2013-05-24 03:22:06.000000000 +0200 @@ -31,7 +31,7 @@ my $g = Graph->new; $g->add_edge(...); use Graph::Traversal::DFS; - my $d = Graph::Traversal::DFS->new(%opt); + my $d = Graph::Traversal::DFS->new($g, %opt); $d->dfs; # Do the traversal. =head1 DESCRIPTION @@ -48,7 +48,8 @@ =item dfs -Traverse the graph in depth-first order. +Traverse the graph in depth-first order. Returns all vertices +traversed in post-order. =back diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/lib/Graph/Traversal.pm new/Graph-0.96/lib/Graph/Traversal.pm --- old/Graph-0.94/lib/Graph/Traversal.pm 2008-11-28 03:24:44.000000000 +0100 +++ new/Graph-0.96/lib/Graph/Traversal.pm 2013-05-24 03:20:49.000000000 +0200 @@ -471,7 +471,7 @@ my $g = Graph->new; $g->add_edge(...); use Graph::Traversal::...; - my $t = Graph::Traversal::...->new(%opt); + my $t = Graph::Traversal::...->new($g, %opt); $t->... =head1 DESCRIPTION diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/lib/Graph.pm new/Graph-0.96/lib/Graph.pm --- old/Graph-0.94/lib/Graph.pm 2010-03-13 21:33:09.000000000 +0100 +++ new/Graph-0.96/lib/Graph.pm 2013-05-25 01:01:16.000000000 +0200 @@ -14,7 +14,7 @@ use vars qw($VERSION); -$VERSION = '0.94'; +$VERSION = '0.96'; require 5.006; # Weak references are absolutely required. @@ -2595,19 +2595,22 @@ *toposort = \&topological_sort; +sub _undirected_copy_compute { + my $g = shift; + my $c = Graph::Undirected->new; + for my $v ($g->isolated_vertices) { # TODO: if iv ... + $c->add_vertex($v); + } + for my $e ($g->edges05) { + $c->add_edge(@$e); + } + return $c; +} + sub undirected_copy { my $g = shift; - $g->expect_directed; - - my $c = Graph::Undirected->new; - for my $v ($g->isolated_vertices) { # TODO: if iv ... - $c->add_vertex($v); - } - for my $e ($g->edges05) { - $c->add_edge(@$e); - } - return $c; + return _check_cache($g, 'undirected', \&_undirected_copy_compute); } *undirected_copy_graph = \&undirected_copy; @@ -2640,6 +2643,7 @@ 'biconnectivity' => '_bcc', 'SPT_Dijkstra' => '_spt_di', 'SPT_Bellman_Ford' => '_spt_bf', + 'undirected' => '_undirected', ); sub _check_cache { @@ -2694,6 +2698,11 @@ _clear_cache($g, 'SPT_Bellman_Ford'); } +sub undirected_copy_clear_cache { + my $g = shift; + _clear_cache($g, 'undirected_copy'); +} + ### # Connected components. # @@ -2796,7 +2805,7 @@ my ($CCE, $CCI) = $g->_connected_components(); my $u = shift; my $c = $CCE->{ $u }; - for my $v ( @_) { + for my $v ( @_ ) { return 0 unless defined $CCE->{ $v } && $CCE->{ $v } eq $c; @@ -3082,175 +3091,121 @@ # Biconnectivity. # -sub _make_bcc { - my ($S, $v, $c) = @_; - my %b; - while (@$S) { - my $t = pop @$S; - $b{ $t } = $t; - last if $t eq $v; +sub _biconnectivity_out { + my ($state, $u, $v) = @_; + if (exists $state->{stack}) { + my @BC; + while (@{$state->{stack}}) { + my $e = pop @{$state->{stack}}; + push @BC, $e; + last if defined $u && $e->[0] eq $u && $e->[1] eq $v; + } + if (@BC) { + push @{$state->{BC}}, \@BC; + } + } +} + +sub _biconnectivity_dfs { + my ($g, $u, $state) = @_; + $state->{num}->{$u} = $state->{dfs}++; + $state->{low}->{$u} = $state->{num}->{$u}; + for my $v ($g->successors($u)) { + unless (exists $state->{num}->{$v}) { + push @{$state->{stack}}, [$u, $v]; + $state->{pred}->{$v} = $u; + $state->{succ}->{$u}->{$v}++; + _biconnectivity_dfs($g, $v, $state); + if ($state->{low}->{$v} < $state->{low}->{$u}) { + $state->{low}->{$u} = $state->{low}->{$v}; + } + if ($state->{low}->{$v} >= $state->{num}->{$u}) { + _biconnectivity_out($state, $u, $v); + } + } elsif (defined $state->{pred}->{$u} && + $state->{pred}->{$u} ne $v && + $state->{num}->{$v} < $state->{num}->{$u}) { + push @{$state->{stack}}, [$u, $v]; + if ($state->{num}->{$v} < $state->{low}->{$u}) { + $state->{low}->{$u} = $state->{num}->{$v}; + } } - return [ values %b, $c ]; + } } sub _biconnectivity_compute { - my $g = shift; - my ($opt, $unseenh, $unseena, $r, $next, $code, $attr) = - $g->_root_opt(@_); - return () unless defined $r; - my %P; - my %I; - for my $v ($g->vertices) { - $I{ $v } = 0; + my ($g) = @_; + my %state; + @{$state{BC}} = (); + @{$state{BR}} = (); + %{$state{V2BC}} = (); + %{$state{BC2V}} = (); + @{$state{AP}} = (); + $state{dfs} = 0; + my @u = _shuffle $g->vertices; + for my $u (@u) { + unless (exists $state{num}->{$u}) { + _biconnectivity_dfs($g, $u, \%state); + _biconnectivity_out(\%state); + delete $state{stack}; + } } - $I{ $r } = 1; - my %U; - my %S; # Self-loops. - for my $e ($g->edges) { - my ($u, $v) = @$e; - $U{ $u }{ $v } = 0; - $U{ $v }{ $u } = 0; - $S{ $u } = 1 if $u eq $v; - } - my $i = 1; - my $v = $r; - my %AP; - my %L = ( $r => 1 ); - my @S = ( $r ); - my %A; - my @V = $g->vertices; - - # print "V : @V\n"; - # print "r : $r\n"; - - my %T; @T{ @V } = @V; - - for my $w (@V) { - my @s = $g->successors( $w ); - if (@s) { - @s = grep { $_ eq $w ? ( delete $T{ $w }, 0 ) : 1 } @s; - @{ $A{ $w } }{ @s } = @s; - } elsif ($g->predecessors( $w ) == 0) { - delete $T{ $w }; - if ($w eq $r) { - delete $I { $r }; - $r = $v = each %T; - if (defined $r) { - %L = ( $r => 1 ); - @S = ( $r ); - $I{ $r } = 1; - # print "r : $r\n"; - } - } + + # Mark the components each vertex belongs to. + my $bci = 0; + for my $bc (@{$state{BC}}) { + for my $e (@$bc) { + for my $v (@$e) { + $state{V2BC}->{$v}->{$bci}++; } + } + $bci++; } - # use Data::Dumper; - # print "T : ", Dumper(\%T); - # print "A : ", Dumper(\%A); - - my %V2BC; - my @BR; - my @BC; - - my @C; - my $Avok; - - while (keys %T) { - # print "T = ", Dumper(\%T); - do { - my $w; - do { - my @w = _shuffle values %{ $A{ $v } }; - # print "w = @w\n"; - $w = first { !$U{ $v }{ $_ } } @w; - if (defined $w) { - # print "w = $w\n"; - $U{ $v }{ $w }++; - $U{ $w }{ $v }++; - if ($I{ $w } == 0) { - $P{ $w } = $v; - $i++; - $I{ $w } = $i; - $L{ $w } = $i; - push @S, $w; - $v = $w; - } else { - $L{ $v } = $I{ $w } if $I{ $w } < $L{ $v }; - } - } - } while (defined $w); - # print "U = ", Dumper(\%U); - # print "P = ", Dumper(\%P); - # print "L = ", Dumper(\%L); - if (!defined $P{ $v }) { - # Do nothing. - } elsif ($P{ $v } ne $r) { - if ($L{ $v } < $I{ $P{ $v } }) { - $L{ $P{ $v } } = $L{ $v } if $L{ $v } < $L{ $P{ $v } }; - } else { - $AP{ $P{ $v } } = $P{ $v }; - push @C, _make_bcc(\@S, $v, $P{ $v } ); - } - } else { - my $e; - for my $w (_shuffle keys %{ $A{ $r } }) { - # print "w = $w\n"; - unless ($U{ $r }{ $w }) { - $e = $r; - # print "e = $e\n"; - last; - } - } - $AP{ $e } = $e if defined $e; - push @C, _make_bcc(\@S, $v, $r); - } - # print "AP = ", Dumper(\%AP); - # print "C = ", Dumper(\@C); - # print "L = ", Dumper(\%L); - $v = defined $P{ $v } ? $P{ $v } : $r; - # print "v = $v\n"; - $Avok = 0; - if (defined $v) { - if (keys %{ $A{ $v } }) { - if (!exists $P{ $v }) { - for my $w (keys %{ $A{ $v } }) { - $Avok++ if $U{ $v }{ $w }; - } - # print "Avok/1 = $Avok\n"; - $Avok = 0 unless $Avok == keys %{ $A{ $v } }; - # print "Avok/2 = $Avok\n"; - } - } else { - $Avok = 1; - # print "Avok/3 = $Avok\n"; - } - } - } until ($Avok); + # Any isolated vertices get each their own component. + for my $v ($g->vertices) { + unless (exists $state{V2BC}->{$v}) { + $state{V2BC}->{$v}->{$bci++}++; + } + } - last if @C == 0 && !exists $S{$v}; + for my $v ($g->vertices) { + for my $bc (keys %{$state{V2BC}->{$v}}) { + $state{BC2V}->{$bc}->{$v}->{$bc}++; + } + } - for (my $i = 0; $i < @C; $i++) { - for my $v (@{ $C[ $i ]}) { - $V2BC{ $v }{ $i }++; - delete $T{ $v }; - } - } + # Articulation points / cut vertices are the vertices + # which belong to more than one component. + for my $v (keys %{$state{V2BC}}) { + if (keys %{$state{V2BC}->{$v}} > 1) { + push @{$state{AP}}, $v; + } + } - for (my $i = 0; $i < @C; $i++) { - if (@{ $C[ $i ] } == 2) { - push @BR, $C[ $i ]; - } else { - push @BC, $C[ $i ]; - } - } + # Bridges / cut edges are the components of two vertices. + for my $v (keys %{$state{BC2V}}) { + my @v = keys %{$state{BC2V}->{$v}}; + if (@v == 2) { + push @{$state{BR}}, \@v; + } + } - if (keys %T) { - $r = $v = each %T; - } + # Create the subgraph components. + my @sg; + for my $bc (@{$state{BC}}) { + my %v; + my $w = Graph::Undirected->new(); + for my $e (@$bc) { + my ($u, $v) = @$e; + $v{$u}++; + $v{$v}++; + $w->add_edge($u, $v); + } + push @sg, [ keys %v ]; } - - return [ [values %AP], \@BC, \@BR, \%V2BC ]; + + return [ $state{AP}, \@sg, $state{BR}, $state{V2BC}, ]; } sub biconnectivity { @@ -3263,26 +3218,26 @@ sub is_biconnected { my $g = shift; - my ($ap, $bc) = ($g->biconnectivity(@_))[0, 1]; - return defined $ap ? @$ap == 0 && $g->vertices >= 3 : undef; + my ($ap) = ($g->biconnectivity(@_))[0]; + return $g->edges >= 2 ? @$ap == 0 : undef ; } sub is_edge_connected { my $g = shift; my ($br) = ($g->biconnectivity(@_))[2]; - return defined $br ? @$br == 0 && $g->edges : undef; + return $g->edges >= 2 ? @$br == 0 : undef; } sub is_edge_separable { my $g = shift; - my $c = $g->is_edge_connected; - defined $c ? !$c && $g->edges : undef; + my ($br) = ($g->biconnectivity(@_))[2]; + return $g->edges >= 2 ? @$br > 0 : undef; } sub articulation_points { my $g = shift; my ($ap) = ($g->biconnectivity(@_))[0]; - return defined $ap ? @$ap : (); + return @$ap; } *cut_vertices = \&articulation_points; @@ -3290,14 +3245,14 @@ sub biconnected_components { my $g = shift; my ($bc) = ($g->biconnectivity(@_))[1]; - return defined $bc ? @$bc : (); + return @$bc; } sub biconnected_component_by_index { my $g = shift; my $i = shift; my ($bc) = ($g->biconnectivity(@_))[1]; - return defined $bc ? $bc->[ $i ] : undef; + return $bc->[ $i ]; } sub biconnected_component_by_vertex { diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/lib/Graph.pod new/Graph-0.96/lib/Graph.pod --- old/Graph-0.94/lib/Graph.pod 2010-03-13 20:54:12.000000000 +0100 +++ new/Graph-0.96/lib/Graph.pod 2013-05-25 00:59:53.000000000 +0200 @@ -28,6 +28,11 @@ # And many, many more, see below. +=head1 UNSUPPORTED + +Unfortunately, as of release 0.95, this module is unsupported, +and will no more be maintained. Sorry about that. + =head1 DESCRIPTION =head2 Non-Description @@ -171,6 +176,12 @@ Create an undirected shallow copy (vertices and edges) of the directed graph so that for any directed edge (u, v) there is an undirected edge (u, v). +=item undirected_copy_clear_cache + + @path = $g->undirected_copy_clear_cache; + +See L</"Clearing cached results">. + =item directed_copy =item directed_copy_graph @@ -728,6 +739,9 @@ For an undirected graph, return true if the graph is edge-connected (if it has no bridges). +Note: more precisely, this would be called is_edge_biconnected, +since there is a more general concept of being k-connected. + =item is_edge_separable $g->is_edge_separable @@ -735,6 +749,9 @@ For an undirected graph, return true if the graph is edge-separable (if it has bridges). +Note: more precisely, this would be called is_edge_biseparable, +since there is a more general concept of being k-connected. + =item articulation_points =item cut_vertices @@ -758,8 +775,9 @@ $i = $g->biconnected_component_by_index($v) -For an undirected graph, return an index identifying the biconnected -component the vertex belongs to, the indexing starting from zero. +For an undirected graph, return the indices identifying the biconnected +components the vertex belongs to, the indexing starting from zero. +The order of of the components is undefined. For the inverse, see L</connected_component_by_index>. @@ -2847,15 +2865,6 @@ =back -=head2 POSSIBLE FUTURES - -A possible future direction is a new graph module written for speed: -this may very possibly mean breaking or limiting some of the APIs or -behaviour as compared with this release of the module. - -What definitely won't happen in future releases is carrying over -the Graph 0.2xxxx backward compatibility API. - =head1 ACKNOWLEDGEMENTS All bad terminology, bugs, and inefficiencies are naturally mine, all @@ -2894,7 +2903,7 @@ =head1 COPYRIGHT -Copyright (c) 1998-2010 Jarkko Hietaniemi. All rights reserved. +Copyright (c) 1998-2013 Jarkko Hietaniemi. All rights reserved. =head1 LICENSE diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/t/62_bcc.t new/Graph-0.96/t/62_bcc.t --- old/Graph-0.94/t/62_bcc.t 2005-11-29 09:26:44.000000000 +0100 +++ new/Graph-0.96/t/62_bcc.t 2013-05-25 01:02:45.000000000 +0200 @@ -1,6 +1,6 @@ use Graph; -use Test::More tests => 385; +use Test::More tests => 394; my $N = 5; @@ -34,31 +34,31 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0a->biconnectivity; - is("@{[sort { $a <=> $b } defined @$ap ? @$ap : ()]}", ""); + is("@{[sort { $a <=> $b } @$ap? @$ap : ()]}", ""); is("@{[prettyn($bc)]}", ""); is("@{[prettyn($br)]}", ""); } ok(!$g0a->is_biconnected); -ok(!$g0a->is_edge_connected); -ok(!$g0a->is_edge_separable); +is( $g0a->is_edge_connected, undef); +is( $g0a->is_edge_separable, undef); is("@{[sort { $a <=> $b } $g0a->articulation_points]}", ""); is("@{[prettyn([$g0a->biconnected_components])]}", ""); is("@{[prettyn([$g0a->bridges])]}", ""); my $g0b = Graph->new(undirected => 1); -$g0b->add_vertex(0); +$g0b->add_vertex("a"); for (0..$N-1) { my ($ap, $bc, $br) = $g0b->biconnectivity; - is("@{[sort { $a <=> $b } defined @$ap ? @$ap : ()]}", ""); + is("@{[sort { $a <=> $b } @$ap? @$ap : ()]}", ""); is("@{[prettyn($bc)]}", ""); is("@{[prettyn($br)]}", ""); } ok(!$g0b->is_biconnected); -ok(!$g0b->is_edge_connected); -ok(!$g0b->is_edge_separable); +is( $g0b->is_edge_connected, undef); +is( $g0b->is_edge_separable, undef); is("@{[sort { $a <=> $b } $g0b->articulation_points]}", ""); is("@{[prettyn([$g0b->biconnected_components])]}", ""); is("@{[prettyn([$g0b->bridges])]}", ""); @@ -68,16 +68,17 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0c->biconnectivity; - is("@{[sort { $a <=> $b } defined @$ap ? @$ap : ()]}", ""); - is("@{[prettya($bc)]}", ""); + is(@$ap, 0); + is("@{[sort { $a <=> $b } @$ap? @$ap : ()]}", ""); + is("@{[prettya($bc)]}", "a b"); is("@{[prettya($br)]}", "a b"); } ok(!$g0c->is_biconnected); -ok(!$g0c->is_edge_connected); -ok( $g0c->is_edge_separable); -is("@{[sort $g0c->articulation_points]}", ""); -is("@{[prettya([$g0c->biconnected_components])]}", ""); +is( $g0c->is_edge_connected, undef); +is( $g0c->is_edge_separable, undef); +is("@{[sort { $a <=> $b } $g0c->articulation_points]}", ""); +is("@{[prettya([$g0c->biconnected_components])]}", "a b"); is("@{[prettya([$g0c->bridges])]}", "a b"); my $g0d = Graph->new(undirected => 1); @@ -86,8 +87,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0d->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b"); - is("@{[prettya($bc)]}", ""); + is("@{[sort @$ap? @$ap : ()]}", "b"); + is("@{[prettya($bc)]}", "a b; b c"); is("@{[prettya($br)]}", "a b; b c"); } @@ -95,7 +96,7 @@ ok(!$g0d->is_edge_connected); ok( $g0d->is_edge_separable); is("@{[sort $g0d->articulation_points]}", "b"); -is("@{[prettya([$g0d->biconnected_components])]}", ""); +is("@{[prettya([$g0d->biconnected_components])]}", "a b; b c"); is("@{[prettya([$g0d->bridges])]}", "a b; b c"); my $g0e = Graph->new(undirected => 1); @@ -105,8 +106,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0e->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b c"); - is("@{[prettya($bc)]}", ""); + is("@{[sort @$ap? @$ap : ()]}", "b c"); + is("@{[prettya($bc)]}", "a b; b c; c d"); is("@{[prettya($br)]}", "a b; b c; c d"); } @@ -114,7 +115,7 @@ ok(!$g0e->is_edge_connected); ok( $g0e->is_edge_separable); is("@{[sort $g0e->articulation_points]}", "b c"); -is("@{[prettya([$g0e->biconnected_components])]}", ""); +is("@{[prettya([$g0e->biconnected_components])]}", "a b; b c; c d"); is("@{[prettya([$g0e->bridges])]}", "a b; b c; c d"); my $g0f = Graph->new(undirected => 1); @@ -123,7 +124,7 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0f->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", ""); + is("@{[sort @$ap? @$ap : ()]}", ""); is("@{[prettya($bc)]}", "a b c"); is("@{[prettya($br)]}", ""); } @@ -141,7 +142,7 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0g->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", ""); + is("@{[sort @$ap? @$ap : ()]}", ""); is("@{[prettya($bc)]}", "a b c d"); is("@{[prettya($br)]}", ""); } @@ -160,8 +161,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0h->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b"); - is("@{[prettya($bc)]}", "a b c"); + is("@{[sort @$ap? @$ap : ()]}", "b"); + is("@{[prettya($bc)]}", "a b c; b d"); is("@{[prettya($br)]}", "b d"); } @@ -169,7 +170,7 @@ ok(!$g0h->is_edge_connected); ok( $g0h->is_edge_separable); is("@{[sort $g0h->articulation_points]}", "b"); -is("@{[prettya([$g0h->biconnected_components])]}", "a b c"); +is("@{[prettya([$g0h->biconnected_components])]}", "a b c; b d"); is("@{[prettya([$g0h->bridges])]}", "b d"); my $g0i = Graph->new(undirected => 1); @@ -180,8 +181,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0i->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b d"); - is("@{[prettya($bc)]}", "a b c"); + is("@{[sort @$ap? @$ap : ()]}", "b d"); + is("@{[prettya($bc)]}", "a b c; b d; d e"); is("@{[prettya($br)]}", "b d; d e"); } @@ -189,7 +190,7 @@ ok(!$g0i->is_edge_connected); ok( $g0i->is_edge_separable); is("@{[sort $g0i->articulation_points]}", "b d"); -is("@{[prettya([$g0i->biconnected_components])]}", "a b c"); +is("@{[prettya([$g0i->biconnected_components])]}", "a b c; b d; d e"); is("@{[prettya([$g0i->bridges])]}", "b d; d e"); my $g0j = Graph->new(undirected => 1); @@ -199,7 +200,7 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0j->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b"); + is("@{[sort @$ap? @$ap : ()]}", "b"); is("@{[prettya($bc)]}", "a b c; b d e"); is("@{[prettya($br)]}", ""); } @@ -219,8 +220,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0k->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b d"); - is("@{[prettya($bc)]}", "a b c; d e f"); + is("@{[sort @$ap? @$ap : ()]}", "b d"); + is("@{[prettya($bc)]}", "a b c; d e f; b d"); is("@{[prettya($br)]}", "b d"); } @@ -228,7 +229,7 @@ ok(!$g0k->is_edge_connected); ok( $g0k->is_edge_separable); is("@{[sort $g0k->articulation_points]}", "b d"); -is("@{[prettya([$g0k->biconnected_components])]}", "a b c; d e f"); +is("@{[prettya([$g0k->biconnected_components])]}", "a b c; d e f; b d"); is("@{[prettya([$g0k->bridges])]}", "b d"); my $g0l = Graph->new(undirected => 1); @@ -241,8 +242,8 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0l->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b d g"); - is("@{[prettya($bc)]}", "a b c; d e f; g h i"); + is("@{[sort @$ap? @$ap : ()]}", "b d g"); + is("@{[prettya($bc)]}", "a b c; d e f; g h i; b d; d g"); is("@{[prettya($br)]}", "b d; d g"); } @@ -250,7 +251,8 @@ ok(!$g0l->is_edge_connected); ok( $g0l->is_edge_separable); is("@{[sort $g0l->articulation_points]}", "b d g"); -is("@{[prettya([$g0l->biconnected_components])]}", "a b c; d e f; g h i"); +is("@{[prettya([$g0l->biconnected_components])]}", + "a b c; d e f; g h i; b d; d g"); is("@{[prettya([$g0l->bridges])]}", "b d; d g"); my $g0m = Graph->new(undirected => 1); @@ -261,7 +263,7 @@ for (0..$N-1) { my ($ap, $bc, $br) = $g0m->biconnectivity; - is("@{[sort defined @$ap ? @$ap : ()]}", "b"); + is("@{[sort @$ap? @$ap : ()]}", "b"); is("@{[prettya($bc)]}", "a b c; b d e; b h i"); is("@{[prettya($br)]}", ""); } @@ -288,7 +290,7 @@ for (0..2*$N-1) { my ($ap, $bc, $br) = $g1->biconnectivity; is("@{[sort { $a <=> $b } @$ap]}", "0 4 5 6 7 11"); - is("@{[prettyn($bc)]}", "0 1 2 6; 3 4 5; 4 9 11; 7 8 10"); + is("@{[prettyn($bc)]}", "0 1 2 6; 3 4 5; 4 9 11; 7 8 10; 0 5; 6 7; 11 12"); is("@{[prettyn($br)]}", "0 5; 6 7; 11 12"); } @@ -305,7 +307,7 @@ for (0..2*$N-1) { my ($ap, $bc, $br) = $g2->biconnectivity; is("@{[sort @$ap]}", "c d f h i j"); - is("@{[prettya($bc)]}", "a b c; d e f; f g h"); + is("@{[prettya($bc)]}", "a b c; d e f; f g h; c d; h i; i j; j k"); is("@{[prettya($br)]}", "c d; h i; i j; j k"); } @@ -321,50 +323,53 @@ for (0..2*$N-1) { my ($ap, $bc, $br) = $g3->biconnectivity; is("@{[sort @$ap]}", "e h i s"); - is("@{[prettya($bc)]}", "a b e f s; c d g h s; i j k"); + is("@{[prettya($bc)]}", "a b e f s; c d g h s; i j k; e i; h l"); is("@{[prettya($br)]}", "e i; h l"); } -is( $g3->biconnected_components, 3 ); +is( $g3->biconnected_components, 5 ); my $c0a = $g3->biconnected_component_by_index(0); my $c0b = $g3->biconnected_component_by_index(0); my $c0c = $g3->biconnected_component_by_index(0); +my $c0d = $g3->biconnected_component_by_index(0); +my $c0e = $g3->biconnected_component_by_index(0); my $c1a = $g3->biconnected_component_by_index(1); my $c1b = $g3->biconnected_component_by_index(1); my $c1c = $g3->biconnected_component_by_index(1); +my $c1d = $g3->biconnected_component_by_index(1); +my $c1e = $g3->biconnected_component_by_index(1); my $c2a = $g3->biconnected_component_by_index(2); my $c2b = $g3->biconnected_component_by_index(2); my $c2c = $g3->biconnected_component_by_index(2); +my $c2d = $g3->biconnected_component_by_index(2); +my $c2e = $g3->biconnected_component_by_index(2); is( "@$c0a", "@$c0b" ); is( "@$c0a", "@$c0c" ); +is( "@$c0a", "@$c0d" ); +is( "@$c0a", "@$c0e" ); is( "@$c1a", "@$c1b" ); is( "@$c1a", "@$c1c" ); +is( "@$c1a", "@$c1d" ); +is( "@$c1a", "@$c1e" ); is( "@$c2a", "@$c2b" ); is( "@$c2a", "@$c2c" ); +is( "@$c2a", "@$c2d" ); +is( "@$c2a", "@$c2e" ); isnt( "@$c0a", "@$c1a" ); isnt( "@$c0a", "@$c2a" ); -isnt( "@$c1a", "@$c2a" ); - -my @c0a = sort @$c0a; -my @c1a = sort @$c1a; -my @c2a = sort @$c2a; - -ok( (grep { $_ eq 'i' } @c0a) || - (grep { $_ eq 'i' } @c1a) || - (grep { $_ eq 'i' } @c2a) ); -is( $g3->biconnected_component_by_index(3), undef ); +is( $g3->biconnected_component_by_index(5), undef ); my $g3c = $g3->biconnected_graph(); -is( $g3c, "a+b+e+f+s=c+d+g+h+s,i+j+k" ); +is( $g3c, "a+b+e+f+s=c+d+g+h+s,a+b+e+f+s=e+i,c+d+g+h+s=h+l,e+i=i+j+k"); ok( $g3->same_biconnected_components('a', 'b') ); ok( $g3->same_biconnected_components('a', 'b', 'e') ); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/t/u_bo.t new/Graph-0.96/t/u_bo.t --- old/Graph-0.94/t/u_bo.t 2006-09-10 19:28:58.000000000 +0200 +++ new/Graph-0.96/t/u_bo.t 1970-01-01 01:00:00.000000000 +0100 @@ -1,224 +0,0 @@ -use Test::More tests => 95; - -use strict; -use Graph; - -use lib "t"; -require "simple.pl"; - -sub rt_17159 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1, $v2, $v3, $v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - for my $v ($v1, $v2, $v3, $v4) { - rt_17159_check($v); - } - my @ap = $g->articulation_points; - for my $ap (@ap) { - rt_17159_check($ap); - } - sub rt_17159_check { - my $z = shift; - ok($z->xyz()); - } -} - -rt_17159(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17159(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17159(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -sub rt_17160 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1, $v2, $v3, $v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - for my $v ($v1, $v2, $v3, $v4) { - rt_17160_check($v); - } - my @cc = $g->connected_components; - for my $ref (@cc) { - for (@$ref) { - rt_17160_check($_); - } - } - sub rt_17160_check { - my $z = shift; - ok($z->xyz()); - } -} - -rt_17160(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17160(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17160(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -sub rt_17161 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1, $v2, $v3, $v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - for my $v ($v1, $v2, $v3, $v4) { - rt_17161_check($v); - } - my @b = $g->bridges; - for my $ref (@b) { - for (@$ref) { - rt_17161_check($_); - } - } - sub rt_17161_check { - my $z = shift; - ok($z->xyz()); - } -} - -rt_17160(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17160(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17160(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -sub rt_17162 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1, $v2, $v3, $v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - for my $v ($v1, $v2, $v3, $v4) { - rt_17162_check($v); - } - my $cl = ref $v1; - my $cg = $g->connected_graph(super_component => sub { - $cl->new(); - }); - my @cv = $cg->vertices; - for my $ref (@cv) { - rt_17162_check($ref); - } - sub rt_17162_check { - my $z = shift; - ok($z->xyz()); - } -} - -rt_17162(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17162(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17162(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -sub rt_17163 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1,$v2,$v3,$v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - my @spd = $g->SP_Dijkstra($v1,$v4); - ok(@spd >= 2); -} - -rt_17163(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17163(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17163(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -sub rt_17164 { - my $g = Graph::Undirected->new; - my ($v1, $v2, $v3, $v4) = @_; - $g->add_vertices($v1,$v2,$v3,$v4); - $g->add_edges([$v1,$v2],[$v3,$v4],[$v3,$v2]); - my @spbf = $g->SP_Bellman_Ford($v1,$v4); - ok(@spbf >= 2); - is($spbf[ 0], $v1); - is($spbf[-1], $v4); -} - -rt_17164(Foo->new(), - Foo->new(), - Foo->new(), - Foo->new()); - -rt_17164(Bar->new(1), - Bar->new(2), - Bar->new(3), - Bar->new(4)); - -rt_17164(Bar->new(), - Bar->new(), - Bar->new(), - Bar->new()); - -{ - # rt.cpan.org: 17592: articulation_points doesn't find all vertices - - my $g = Graph::Undirected->new; - - my $v1 = Foo->new(); - my $v2 = Foo->new(); - my $v3 = Foo->new(); - my $v4 = Foo->new(); - my $v5 = Foo->new(); - my $v6 = Foo->new(); - my $v7 = Foo->new(); - - $g->add_vertices($v1,$v2,$v3,$v4,$v5,$v6,$v7); - - $g->add_edges([$v1,$v2],[$v2,$v3],[$v3,$v4], - [$v5,$v6],[$v6,$v7]); - - my @rts = $g->articulation_points; - my %rts; @rts{@rts} = @rts; - - is(@rts, 3); - ok($rts{$v2}); - ok($rts{$v3}); - ok($rts{$v6}); -} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.94/t/u_bo1.t new/Graph-0.96/t/u_bo1.t --- old/Graph-0.94/t/u_bo1.t 2006-06-01 18:05:35.000000000 +0200 +++ new/Graph-0.96/t/u_bo1.t 1970-01-01 01:00:00.000000000 +0100 @@ -1,80 +0,0 @@ -use Test::More tests => 20; - -require Graph::Undirected; -require Graph::Traversal::DFS; - -use lib "t"; -require "simple.pl"; - -# -# The purpose of these tests is to check to see if particular -# bugs have been fixed in Perl's Graph -# -my $g = Graph::Undirected->new(refvertexed => 1); - -ok 1; - -my $seq1 = Foo->new; -my $seq2 = Foo->new; -my $seq3 = Foo->new; -my $seq4 = Foo->new; - -my $str = "ljfgouyouiyougs"; - -$g->add_vertices($seq1,$seq2,$seq3,$seq4); -$g->add_edges([$seq1,$seq2],[$seq3,$seq4],[$seq3,$seq2]); - -my @vs = $g->vertices; # OK -ok $vs[0]->xyz($str); - -my $c = $g->complete; # OK -@vs = $c->vertices; -ok $vs[0]->xyz($str); - -my $comp = $g->complement; # OK -@vs = $comp->vertices; -ok $vs[0]->xyz($str); - -@vs = $g->interior_vertices; # OK -ok $vs[0]->xyz($str); - -my $apsp = $g->APSP_Floyd_Warshall; -@vs = $apsp->path_vertices($seq1,$seq4); # OK -ok $vs[0]->xyz($str); - -my $seq = $g->random_vertex; # OK -ok $seq->xyz($str); - -my @rts = $g->articulation_points; -ok @rts; - -my $t = Graph::Traversal::DFS->new($g); -$t->dfs; -@vs = $t->seen; -for my $seq (@vs) { - ok $seq->xyz($str); # NOT OK in version .73 -} - -@vs = $g->articulation_points; -ok $vs[0]->xyz($str); # OK in version .70 -is scalar @vs, 2; - -my @cc = $g->connected_components; -for my $ref (@cc) { - for my $seq (@$ref) { - ok $seq->xyz($str); # OK in version .70 - } -} - -my @bs = $g->bridges; -ok $bs[0][0]->xyz($str); # NOT OK in version .73 - -my $cg = $g->connected_graph(super_component => sub { $_[0] }); -@vs = $cg->vertices; -ok $vs[0]->xyz($str); # OK in version .73 - -my @spd = $g->SP_Dijkstra($seq1,$seq4); # OK in version .70 - -my @spbf = $g->SP_Bellman_Ford($seq1,$seq4); # OK in version .70 - -__END__ -- To unsubscribe, e-mail: opensuse-commit+unsubscr...@opensuse.org For additional commands, e-mail: opensuse-commit+h...@opensuse.org
