Hello community, here is the log from the commit of package perl-Graph for openSUSE:Factory checked in at 2020-12-01 14:23:37 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/perl-Graph (Old) and /work/SRC/openSUSE:Factory/.perl-Graph.new.5913 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "perl-Graph" Tue Dec 1 14:23:37 2020 rev:18 rq:852063 version:0.9711 Changes: -------- --- /work/SRC/openSUSE:Factory/perl-Graph/perl-Graph.changes 2020-11-23 18:54:57.077638723 +0100 +++ /work/SRC/openSUSE:Factory/.perl-Graph.new.5913/perl-Graph.changes 2020-12-01 14:23:59.573671616 +0100 @@ -1,0 +2,13 @@ +Sat Nov 28 03:06:17 UTC 2020 - Tina Müller <[email protected]> + +- updated to 0.9711 + see /usr/share/doc/packages/perl-Graph/Changes + + 0.9711 2020-11-27 + - ingest handle multivertexed, multiedged right + + 0.9710 2020-11-27 + - all_paths method + - as_hashes handle multivertexed, multiedged right + +------------------------------------------------------------------- Old: ---- Graph-0.9709.tar.gz New: ---- Graph-0.9711.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ perl-Graph.spec ++++++ --- /var/tmp/diff_new_pack.ppldMy/_old 2020-12-01 14:24:00.057672140 +0100 +++ /var/tmp/diff_new_pack.ppldMy/_new 2020-12-01 14:24:00.061672144 +0100 @@ -17,7 +17,7 @@ Name: perl-Graph -Version: 0.9709 +Version: 0.9711 Release: 0 %define cpan_name Graph Summary: Graph data structures and algorithms ++++++ Graph-0.9709.tar.gz -> Graph-0.9711.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/Changes new/Graph-0.9711/Changes --- old/Graph-0.9709/Changes 2020-11-22 20:16:27.000000000 +0100 +++ new/Graph-0.9711/Changes 2020-11-27 04:51:27.000000000 +0100 @@ -1,3 +1,10 @@ +0.9711 2020-11-27 +- ingest handle multivertexed, multiedged right + +0.9710 2020-11-27 +- all_paths method +- as_hashes handle multivertexed, multiedged right + 0.9709 2020-11-22 - add path_count option to TransitiveClosure - get_{edge,vertex}_attributes undef if no such entity, in list context diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/META.json new/Graph-0.9711/META.json --- old/Graph-0.9709/META.json 2020-11-22 20:18:08.000000000 +0100 +++ new/Graph-0.9711/META.json 2020-11-27 04:52:11.000000000 +0100 @@ -67,6 +67,6 @@ "web" : "https://github.com/graphviz-perl/Graph"; } }, - "version" : "0.9709", + "version" : "0.9711", "x_serialization_backend" : "JSON::PP version 4.00" } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/META.yml new/Graph-0.9711/META.yml --- old/Graph-0.9709/META.yml 2020-11-22 20:18:08.000000000 +0100 +++ new/Graph-0.9711/META.yml 2020-11-27 04:52:11.000000000 +0100 @@ -29,5 +29,5 @@ resources: bugtracker: https://github.com/graphviz-perl/Graph/issues repository: git://github.com/graphviz-perl/Graph.git -version: '0.9709' +version: '0.9711' x_serialization_backend: 'CPAN::Meta::YAML version 0.018' diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/lib/Graph/TransitiveClosure/Matrix.pm new/Graph-0.9711/lib/Graph/TransitiveClosure/Matrix.pm --- old/Graph-0.9709/lib/Graph/TransitiveClosure/Matrix.pm 2020-11-21 00:04:27.000000000 +0100 +++ new/Graph-0.9711/lib/Graph/TransitiveClosure/Matrix.pm 2020-11-27 01:06:22.000000000 +0100 @@ -5,6 +5,13 @@ use Graph::AdjacencyMatrix; use Graph::Matrix; +use Scalar::Util qw(weaken); + +sub _A() { 0 } # adjacency +sub _D() { 1 } # distance +sub _P() { 2 } # predecessors +sub _V() { 3 } # vertices +sub _G() { 4 } # the original graph (OG) sub _new { my ($g, $class, $opt, $want_transitive, $want_reflexive, $want_path, $want_path_vertices, $want_path_count) = @_; @@ -188,7 +195,8 @@ $pm->[0] = \@pi; $pm->[1] = \%pi; } - bless [ $am, $dm, $pm, \%V ], $class; + weaken(my $og = $g); + bless [ $am, $dm, $pm, \%V, $og ], $class; } sub new { @@ -220,7 +228,7 @@ sub has_vertices { my $tc = shift; for my $v (@_) { - return 0 unless exists $tc->[3]->{ $v }; + return 0 unless exists $tc->[ _V ]->{ $v }; } return 1; } @@ -229,7 +237,7 @@ my ($tc, $u, $v) = @_; return undef unless $tc->has_vertices($u, $v); return 1 if $u eq $v; - $tc->[0]->get($u, $v); + $tc->[ _A ]->get($u, $v); } sub is_transitive { @@ -238,7 +246,7 @@ } else { # A TC graph. my ($tc, $u, $v) = @_; return undef unless $tc->has_vertices($u, $v); - $tc->[0]->get($u, $v); + $tc->[ _A ]->get($u, $v); } } @@ -251,14 +259,14 @@ my ($tc, $u, $v) = @_; return undef unless $tc->has_vertices($u, $v); return 0 if $u eq $v; - $tc->[1]->get($u, $v); + $tc->[ _D ]->get($u, $v); } sub path_predecessor { my ($tc, $u, $v) = @_; return undef if $u eq $v; return undef unless $tc->has_vertices($u, $v); - $tc->[2]->get($u, $v); + $tc->[ _P ]->get($u, $v); } sub path_vertices { @@ -270,10 +278,23 @@ last unless defined($u = $tc->path_predecessor($u, $v)); push @v, $u; } - $tc->[2]->set($u, $v, [ @v ]) if @v; + $tc->[ _P ]->set($u, $v, [ @v ]) if @v; return @v; } +sub all_paths { + my ($tc, $u, $v) = @_; + return if $u eq $v; + my @found; + push @found, [$u, $v] if $tc->[ _G ]->has_edge($u, $v); + push @found, + map [$u, @$_], + map $tc->all_paths($_, $v), + grep $tc->is_reachable($_, $v), + grep $_ ne $v, $tc->[ _G ]->successors($u); + @found; +} + 1; __END__ =pod @@ -425,6 +446,10 @@ Return the predecessor of vertex $v in the transitive closure path going back to vertex $u. +=item all_paths($u, $v) + +Return list of array-refs with all the paths from $u to $v. + =back =head1 RETURN VALUES diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/lib/Graph/TransitiveClosure.pm new/Graph-0.9711/lib/Graph/TransitiveClosure.pm --- old/Graph-0.9709/lib/Graph/TransitiveClosure.pm 2020-11-09 20:27:19.000000000 +0100 +++ new/Graph-0.9711/lib/Graph/TransitiveClosure.pm 2020-11-27 00:12:50.000000000 +0100 @@ -99,6 +99,10 @@ my $tcg = Graph::TransitiveClosure->new($g, path_vertices => 1); $tcg->path_vertices($u, $v) + # see how many paths exist from $u to $v + my $tcg = Graph::TransitiveClosure->new($g, path_count => 1); + $tcg->path_length($u, $v) + # Both path_length and path_vertices. my $tcg = Graph::TransitiveClosure->new($g, path => 1); $tcg->path_vertices($u, $v) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/lib/Graph.pm new/Graph-0.9711/lib/Graph.pm --- old/Graph-0.9709/lib/Graph.pm 2020-11-22 20:16:42.000000000 +0100 +++ new/Graph-0.9711/lib/Graph.pm 2020-11-27 04:51:41.000000000 +0100 @@ -13,7 +13,7 @@ use Graph::AdjacencyMap qw(:flags :fields); -our $VERSION = '0.9709'; +our $VERSION = '0.9711'; require 5.006; # Weak references are absolutely required. @@ -1736,18 +1736,49 @@ sub as_hashes { my ($g) = @_; - my %e; - $e{ $_->[0] }{ $_->[1] } = $g->get_edge_attributes(@$_) || {} for $g->edges; - my %n = map +( $_ => $g->get_vertex_attributes($_) || {} ), $g->vertices; + my (%n, %e); + if ($g->is_multivertexed) { + for my $v ($g->vertices) { + $n{$v} = { + map +($_ => $g->get_vertex_attributes_by_id($v, $_) || {}), + $g->get_multivertex_ids($v) + }; + } + } else { + %n = map +($_ => $g->get_vertex_attributes($_) || {}), $g->vertices; + } + if ($g->is_multiedged) { + for my $e ($g->edges) { + $e{ $e->[0] }{ $e->[1] } = { + map +($_ => $g->get_edge_attributes_by_id(@$e, $_) || {}), + $g->get_multiedge_ids(@$e) + }; + } + } else { + $e{ $_->[0] }{ $_->[1] } = $g->get_edge_attributes(@$_) || {} + for $g->edges; + } ( \%n, \%e ); } sub ingest { my ($g, $g2) = @_; for my $v ($g2->vertices) { - $g->set_vertex_attributes($v, $g2->get_vertex_attributes($v)); - $g->set_edge_attributes(@$_, $g2->get_edge_attributes(@$_)) - for $g2->edges_from($v); + if ($g->is_multivertexed) { + $g->set_vertex_attributes_by_id($v, $_, $g2->get_vertex_attributes_by_id($v, $_)) + for $g2->get_multivertex_ids($v); + } else { + $g->set_vertex_attributes($v, $g2->get_vertex_attributes($v)); + } + if ($g->is_multiedged) { + for my $e ($g2->edges_from($v)) { + $g->set_edge_attributes_by_id(@$e, $_, $g2->get_edge_attributes_by_id(@$e, $_)) + for $g2->get_multiedge_ids(@$e); + } + } else { + $g->set_edge_attributes(@$_, $g2->get_edge_attributes(@$_)) + for $g2->edges_from($v); + } } $g; } @@ -3687,6 +3718,12 @@ $tcm->path_vertices(@_); } +sub all_paths { + my $g = shift; + my $tcm = $g->transitive_closure_matrix; + $tcm->all_paths(@_); +} + sub is_reachable { my $g = shift; my $tcm = $g->transitive_closure_matrix; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/lib/Graph.pod new/Graph-0.9711/lib/Graph.pod --- old/Graph-0.9709/lib/Graph.pod 2020-11-22 20:11:58.000000000 +0100 +++ new/Graph-0.9711/lib/Graph.pod 2020-11-27 02:47:54.000000000 +0100 @@ -1281,6 +1281,12 @@ a two-level hash mapping the predecessor to its successors, mapped to the attributes. +If C<multivertexed> is true, the vertices hash will have the second-level +values be the multivertex's ID, and the third level will be attributes +as above. + +If C<multiedged> is true, similar will be true for the edges hash. + =back =head2 Connected Graphs and Their Components @@ -1864,9 +1870,11 @@ Returns the predecessor of vertex $v in the all-pairs shortest paths. -=back +=item all_paths -=over 8 + my @paths = $apsp->all_paths($u, $v); + +Return list of array-refs with all the paths from $u to $v. =item average_path_length diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/t/51_multivertex_attributes.t new/Graph-0.9711/t/51_multivertex_attributes.t --- old/Graph-0.9709/t/51_multivertex_attributes.t 2020-10-20 05:06:19.000000000 +0200 +++ new/Graph-0.9711/t/51_multivertex_attributes.t 2020-11-27 04:35:52.000000000 +0100 @@ -1,5 +1,5 @@ use strict; use warnings; -use Test::More tests => 69; +use Test::More tests => 60; use Graph; my $g = Graph->new(multivertexed => 1); @@ -35,13 +35,9 @@ my @name = $g->get_vertex_attribute_names_by_id("a", "hot"); my @val = $g->get_vertex_attribute_values_by_id("a", "hot"); -is( scalar keys %$attr, 1 ); -is( scalar @name, 1 ); -is( scalar @val, 1 ); - -is( $attr->{color}, "green" ); -is( $name[0], "color" ); -is( $val[0], "green" ); +is_deeply $attr, { color => "green" }; +is_deeply \@name, [ "color" ]; +is_deeply \@val, [ "green" ]; ok( $g->set_vertex_attribute_by_id("a", "hot", "taste", "rhubarb") ); @@ -58,16 +54,10 @@ @name = sort $g->get_vertex_attribute_names_by_id("a", "hot"); @val = sort $g->get_vertex_attribute_values_by_id("a", "hot"); -is( scalar keys %$attr, 2 ); -is( scalar @name, 2 ); -is( scalar @val, 2 ); - -is( $attr->{color}, "green" ); -is( $attr->{taste}, "rhubarb" ); -is( $name[0], "color" ); -is( $val[0], "green" ); -is( $name[1], "taste" ); -is( $val[1], "rhubarb" ); +is_deeply $attr, { color => "green", taste => "rhubarb" }; +is_deeply \@name, [ "color", "taste" ]; +is_deeply \@val, [ "green", "rhubarb" ]; +is_deeply(($g->as_hashes)[0], { a => { hot => { color => "green", taste => "rhubarb" } } }); ok( $g->delete_vertex_attribute_by_id("a", "hot", "color" ) ); @@ -86,9 +76,9 @@ @name = $g->get_vertex_attribute_names_by_id("a", "hot"); @val = $g->get_vertex_attribute_values_by_id("a", "hot"); -is( scalar keys %$attr, 0 ); -is( scalar @name, 0 ); -is( scalar @val, 0 ); +is_deeply $attr, undef; +is_deeply \@name, []; +is_deeply \@val, []; is( $g->vertices, 0 ); # No "a" anymore. @@ -108,9 +98,7 @@ ok($g->set_vertex_attributes_by_id('a', 'hot', { 'color' => 'pearl', 'weight' => 'heavy' })); $attr = $g->get_vertex_attributes_by_id('a', 'hot'); -is(scalar keys %$attr, 2); -is($attr->{color}, 'pearl'); -is($attr->{weight}, 'heavy'); +is_deeply $attr, { color => "pearl", weight => 'heavy' }; ok( $g->set_vertex_weight_by_id("a", "hot", 42)); is( $g->get_vertex_weight_by_id("a", "hot"), 42); @@ -122,6 +110,12 @@ my $h = Graph->new(multivertexed => 1); -eval '$h->set_vertex_attribute("foo", "color", "gold")'; +eval { $h->set_vertex_attribute("foo", "color", "gold") }; like($@, qr/set_vertex_attribute: expected non-multivertexed/); +$h->ingest($g); +is_deeply(($h->as_hashes)[0], { + a => { hot => { color => 'pearl' } }, + b => { cool => { weight => 43 } }, + c => { cool => { weight => 44 } } +}); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/t/53_multiedge_attributes.t new/Graph-0.9711/t/53_multiedge_attributes.t --- old/Graph-0.9709/t/53_multiedge_attributes.t 2020-10-20 05:06:19.000000000 +0200 +++ new/Graph-0.9711/t/53_multiedge_attributes.t 2020-11-27 04:49:07.000000000 +0100 @@ -1,5 +1,5 @@ use strict; use warnings; -use Test::More tests => 74; +use Test::More tests => 65; use Graph; my $g = Graph->new(multiedged => 1); @@ -35,13 +35,9 @@ my @name = $g->get_edge_attribute_names_by_id("a", "b", "hot"); my @val = $g->get_edge_attribute_values_by_id("a", "b", "hot"); -is( scalar keys %$attr, 1 ); -is( scalar @name, 1 ); -is( scalar @val, 1 ); - -is( $attr->{color}, "green" ); -is( $name[0], "color" ); -is( $val[0], "green" ); +is_deeply $attr, { color => "green" }; +is_deeply \@name, [ "color" ]; +is_deeply \@val, [ "green" ]; ok( $g->set_edge_attribute_by_id("a", "b", "hot", "taste", "rhubarb") ); @@ -58,16 +54,10 @@ @name = sort $g->get_edge_attribute_names_by_id("a", "b", "hot"); @val = sort $g->get_edge_attribute_values_by_id("a", "b", "hot"); -is( scalar keys %$attr, 2 ); -is( scalar @name, 2 ); -is( scalar @val, 2 ); - -is( $attr->{color}, "green" ); -is( $attr->{taste}, "rhubarb" ); -is( $name[0], "color" ); -is( $val[0], "green" ); -is( $name[1], "taste" ); -is( $val[1], "rhubarb" ); +is_deeply $attr, { color => "green", taste => "rhubarb" }; +is_deeply \@name, [ "color", "taste" ]; +is_deeply \@val, [ "green", "rhubarb" ]; +is_deeply(($g->as_hashes)[1], { a => { b => { hot => { color => "green", taste => "rhubarb" } } } }); ok( $g->delete_edge_attribute_by_id("a", "b", "hot", "color" ) ); @@ -86,9 +76,9 @@ @name = $g->get_edge_attribute_names_by_id("a", "b", "hot"); @val = $g->get_edge_attribute_values_by_id("a", "b", "hot"); -is( scalar keys %$attr, 0 ); -is( scalar @name, 0 ); -is( scalar @val, 0 ); +is_deeply $attr, undef; +is_deeply \@name, []; +is_deeply \@val, []; is( $g->edges, 0 ); # No "a", "b" anymore. @@ -122,9 +112,7 @@ ok($u->set_edge_attributes_by_id('a', 'b', 'hot', { 'color' => 'pearl', 'weight' => 'heavy' })); $attr = $u->get_edge_attributes_by_id('a', 'b', 'hot'); -is(scalar keys %$attr, 2); -is($attr->{color}, 'pearl'); -is($attr->{weight}, 'heavy'); +is_deeply $attr, { color => "pearl", weight => 'heavy' }; ok( $g->set_edge_weight_by_id("a", "b", "hot", 42)); is( $g->get_edge_weight_by_id("a", "b", "hot"), 42); @@ -136,5 +124,13 @@ my $h = Graph->new(multiedged => 1); -eval '$h->set_edge_attribute("foo", "bar", "color", "gold")'; +eval { $h->set_edge_attribute("foo", "bar", "color", "gold") }; like($@, qr/set_edge_attribute: expected non-multiedged/); + +$h->ingest($g); +my $got = ($h->as_hashes)[1]; +is_deeply $got, { + c => { d => { hot => { weight => 45 } } }, + d => { e => { hot => { weight => 46 } } }, + e => { f => { hot => { weight => 44 } } } +} or diag explain $got; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/Graph-0.9709/t/72_transitive.t new/Graph-0.9711/t/72_transitive.t --- old/Graph-0.9709/t/72_transitive.t 2020-11-21 00:04:12.000000000 +0100 +++ new/Graph-0.9711/t/72_transitive.t 2020-11-27 01:29:24.000000000 +0100 @@ -1,5 +1,5 @@ use strict; use warnings; -use Test::More tests => 243; +use Test::More tests => 255; use Graph::Directed; use Graph::Undirected; @@ -451,3 +451,32 @@ is $path_counts->path_length($u, $v), $count, "count $u $v"; } } + +{ + my @example = ( [ 1, 2 ], + [ 1, 3 ], + [ 1, 4 ], # direct link to two away + [ 3, 4 ] ); + my $g = Graph::Directed->new; + $g->add_edge(@$_) for @example; + my $tcg = $g->transitive_closure; + my @paths = ( + [ 1, 2, [[1,2]] ], + [ 1, 3, [[1,3]] ], + [ 1, 4, [[1,3,4], [1,4]] ], + [ 2, 1, [] ], + [ 2, 3, [] ], + [ 2, 4, [] ], + [ 3, 1, [] ], + [ 3, 2, [] ], + [ 3, 4, [[3,4]] ], + [ 4, 1, [] ], + [ 4, 2, [] ], + [ 4, 3, [] ], + ); + foreach my $t (@paths) { + my ($u, $v, $paths) = @$t; + my $got = [ sort { $a->[1] <=> $b->[1] } $g->all_paths($u, $v) ]; + is_deeply $got, $paths, "paths $u $v" or diag explain $got; + } +} _______________________________________________ openSUSE Commits mailing list -- [email protected] To unsubscribe, email [email protected] List Netiquette: https://en.opensuse.org/openSUSE:Mailing_list_netiquette List Archives: https://lists.opensuse.org/archives/list/[email protected]
