New Upstream Release - libgraph-perl
Ready changes
Summary
Merged new upstream version: 0.9727 (was: 0.9726).
Resulting package
Built on 2023-08-06T17:07 (took 6m57s)
The resulting binary packages can be installed (if you have the apt repository enabled) by running one of:
apt install -t fresh-releases libgraph-perl
Lintian Result
Diff
diff --git a/Changes b/Changes
index 5c1fd4c..2f2b9b0 100644
--- a/Changes
+++ b/Changes
@@ -1,3 +1,6 @@
+0.9727 2023-06-25
+- fix biconnectivity to work with refvertexed (#29) - thanks @merkys for report
+
0.9726 2023-02-11
- fix subgraph of undirected (#28) - thanks @merkys for report
diff --git a/META.json b/META.json
index e0854bc..d062648 100644
--- a/META.json
+++ b/META.json
@@ -68,6 +68,6 @@
"web" : "https://github.com/graphviz-perl/Graph"
}
},
- "version" : "0.9726",
+ "version" : "0.9727",
"x_serialization_backend" : "JSON::PP version 4.04"
}
diff --git a/META.yml b/META.yml
index 345135a..687b2d7 100644
--- a/META.yml
+++ b/META.yml
@@ -30,5 +30,5 @@ requires:
resources:
bugtracker: https://github.com/graphviz-perl/Graph/issues
repository: git://github.com/graphviz-perl/Graph.git
-version: '0.9726'
+version: '0.9727'
x_serialization_backend: 'CPAN::Meta::YAML version 0.018'
diff --git a/debian/changelog b/debian/changelog
index fe39b74..f02f5d4 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+libgraph-perl (1:0.9727-1) UNRELEASED; urgency=low
+
+ * New upstream release.
+
+ -- Debian Janitor <janitor@jelmer.uk> Sun, 06 Aug 2023 17:00:48 -0000
+
libgraph-perl (1:0.9726-1) unstable; urgency=medium
* Team upload.
diff --git a/lib/Graph.pm b/lib/Graph.pm
index 3ece4f6..0afb0ff 100644
--- a/lib/Graph.pm
+++ b/lib/Graph.pm
@@ -14,7 +14,7 @@ BEGIN {
use Graph::AdjacencyMap qw(:flags :fields);
-our $VERSION = '0.9726';
+our $VERSION = '0.9727';
require 5.006; # Weak references are absolutely required.
@@ -2114,14 +2114,13 @@ sub _biconnectivity_out {
}
sub _biconnectivity_dfs {
- my ($g, $u, $state) = @_;
+ my ($E, $u, $state) = @_;
$state->{low}{$u} = $state->{num}{$u} = $state->{dfs}++;
- for my $v ($g->successors($u)) {
+ for my $v ($E->successors($u)) {
if (!exists $state->{num}{$v}) {
push @{$state->{stack}}, [$u, $v];
$state->{pred}{$v} = $u;
- $state->{succ}{$u}{$v}++;
- _biconnectivity_dfs($g, $v, $state);
+ _biconnectivity_dfs($E, $v, $state);
$state->{low}{$u} = List::Util::min(@{ $state->{low} }{$u, $v});
_biconnectivity_out($state, $u, $v)
if $state->{low}{$v} >= $state->{num}{$u};
@@ -2137,11 +2136,12 @@ sub _biconnectivity_dfs {
sub _biconnectivity_compute {
require List::Util;
my ($g) = @_;
+ my ($V, $E) = @$g[ _V, _E ];
my %state = (BC=>[], dfs=>0);
- my @u = $g->vertices;
+ my @u = $V->ids;
for my $u (@u) {
next if exists $state{num}->{$u};
- _biconnectivity_dfs($g, $u, \%state);
+ _biconnectivity_dfs($E, $u, \%state);
push @{$state{BC}}, delete $state{stack} if @{ $state{stack} || _empty_array };
}
@@ -2172,7 +2172,8 @@ sub _biconnectivity_compute {
# Create the subgraph components.
my @sg = map [ List::Util::uniq( map @$_, @$_ ) ], @{$state{BC}};
- return [ \@ap, \@sg, \@br, \%v2bc, \%v2bc_vec, $Z ];
+ my ($apdeep, $sgv, $brv) = $V->get_paths_by_ids([[\@ap], \@sg, \@br], 1);
+ return [ @$apdeep, $sgv, $brv, \%v2bc, \%v2bc_vec, $Z ];
}
sub biconnectivity {
@@ -2212,12 +2213,16 @@ sub biconnected_component_by_vertex {
my ($v) = splice @_, 1, 1;
my $v2bc = (&biconnectivity)[3];
splice @_, 1, 0, $v;
+ my $V = $_[0]->[ _V ];
+ ($v) = $V->get_ids_by_paths([$v]);
return defined $v2bc->{ $v } ? keys %{ $v2bc->{ $v } } : ();
}
sub same_biconnected_components {
my ($v2bc, $Z) = (&biconnectivity)[4,5];
- return 0 if grep !defined, my @vecs = @$v2bc{ @_[1..$#_] };
+ my $V = $_[0]->[ _V ];
+ my @vs = $V->get_ids_by_paths([@_[1..$#_]]);
+ return 0 if grep !defined, my @vecs = @$v2bc{ @vs };
my $accumulator = $vecs[0];
$accumulator &= $_ for @vecs[1..$#vecs]; # accumulate 0s -> all in same
$accumulator ne $Z;
diff --git a/lib/Graph/AdjacencyMap.pm b/lib/Graph/AdjacencyMap.pm
index efe3529..adbcc0a 100644
--- a/lib/Graph/AdjacencyMap.pm
+++ b/lib/Graph/AdjacencyMap.pm
@@ -334,6 +334,10 @@ sub paths {
grep defined, @{ $_[0]->[ _i ] || Graph::_empty_array() };
}
+sub ids {
+ values %{ $_[0]->[ _pi ] || Graph::_empty_array() };
+}
+
sub get_ids_by_paths {
my ($f, $a, $pi, $m, $list, $ensure, $deep) = ( @{ $_[0] }[ _f, _arity, _pi ], @_ );
$deep ||= 0;
@@ -460,7 +464,11 @@ Return true if the Map has the path by a multi(vertex) id, false if not.
=head2 paths
-Return all the paths of the Map.
+Return all the paths (left-hand sides) of the Map.
+
+=head2 ids
+
+Return all the right-hand sides of the Map, unsorted.
=head2 set_paths(\@seq1, \@seq2, ...)
diff --git a/t/62_bcc.t b/t/62_bcc.t
index c387418..d88286e 100644
--- a/t/62_bcc.t
+++ b/t/62_bcc.t
@@ -395,9 +395,7 @@ sub _bicon_graphvizify {
#print $fh GraphViz2->from_graph($g_gv)->dot_input;
ok !$g4->same_biconnected_components(qw(a b c));
-my $d = Graph->new;
-
-eval { $d->biconnectivity };
+eval { Graph->new->biconnectivity };
like($@, qr/Graph::biconnectivity: expected undirected graph, got directed/);
done_testing;
diff --git a/t/65_ref.t b/t/65_ref.t
index d9eab50..c8d48cd 100644
--- a/t/65_ref.t
+++ b/t/65_ref.t
@@ -63,6 +63,8 @@ sub test_adjmap {
isnt( $m->${ \$map->{has} }(@$path_maybe_id), undef, $label );
$m->${ \$map->{set} }(@$path_maybe_id); # second time
is( $m->_get_path_count($path), $maybe_count, $label );
+ my @ids = $m->ids;
+ isnt 0+@ids, 0, $label;
ok( $m->${ \$map->{del} }(@$path_maybe_id), $label ) for 1..$maybe_count;
ok( !$m->has_any_paths, $label ) or diag explain $m;
is( $m->${ \$map->{has} }(@$path_maybe_id), undef, $label );
@@ -80,6 +82,8 @@ sub test_adjmap {
is_deeply( $got, [ [$path] ], $label ) or diag explain $got;
$got = [ $m->get_ids_by_paths([ [$path, $path] ], 0, 1) ];
is_deeply $got, [ [1, 1] ], $label or diag explain $got;
+ $got = [ $m->get_paths_by_ids([ [[1,1]] ], 1) ];
+ is_deeply $got, [ [[$path, $path]] ], $label or diag explain $got;
}
eval { $m->stringify };
is $@, '', $label;
@@ -284,46 +288,30 @@ my $o6a = bless \*foo, 'G';
my $o6b = bless \*bar, 'G';
{ package G; use overload '""' => sub { "g" } }
-for my $i ($o1a, $o2a, $o3a, $o4a, $o5a, $o6a) {
+for my $d (1, 0) {
+ for my $i ($o1a, $o2a, $o3a, $o4a, $o5a, $o6a) {
for my $j ($o1b, $o2b, $o3b, $o4b, $o5b, $o6b) {
- note "i = $i, j = $j";
-
- my $g1 = Graph->new(refvertexed => 1, directed => 1);
-
- ok( $g1->add_edge($i, $j));
- note "g1 = $g1";
- ok( $g1->has_vertex($i));
- ok( $g1->has_vertex($j));
- ok( $g1->has_edge($i, $j));
- ok( $g1->delete_vertex($i));
- note "g1 = $g1";
- ok(!$g1->has_vertex($i));
- ok( $g1->has_vertex($j));
- ok(!$g1->has_edge($i, $j));
- ok($g1->delete_vertex($j));
- note "g1 = $g1, i=$i, j=$j";
- ok(!$g1->has_vertex($i));
- ok(!$g1->has_vertex($j));
- ok(!$g1->has_edge($i, $j));
-
- my $g2 = Graph->new(refvertexed => 1, directed => 0);
-
- ok( $g2->add_edge($i, $j));
- note "g2 = $g2";
- ok( $g2->has_vertex($i));
- ok( $g2->has_vertex($j));
- ok( $g2->has_edge($i, $j));
- ok( $g2->delete_vertex($i));
- note "g2 = $g2";
- ok(!$g2->has_vertex($i));
- ok( $g2->has_vertex($j));
- ok(!$g2->has_edge($i, $j));
- ok($g2->delete_vertex($j));
- note "g2 = $g2, i=$i, j=$j";
- ok(!$g2->has_vertex($i));
- ok(!$g2->has_vertex($j));
- ok(!$g2->has_edge($i, $j));
+ note "d = $d, i = $i, j = $j";
+ my $g = Graph->new(refvertexed => 1, directed => $d);
+ ok( $g->add_edge($i, $j));
+ note "g = $g";
+ ok( $g->has_vertex($i));
+ ok( $g->has_vertex($j));
+ ok( $g->has_edge($i, $j));
+ if (!$d) { # bridges only for undirected
+ eval {ok $g->has_vertex($_) for map @$_, $g->bridges}; is $@, '';
+ }
+ ok( $g->delete_vertex($i));
+ note "g = $g";
+ ok(!$g->has_vertex($i));
+ ok( $g->has_vertex($j));
+ ok(!$g->has_edge($i, $j));
+ ok($g->delete_vertex($j));
+ ok(!$g->has_vertex($i));
+ ok(!$g->has_vertex($j));
+ ok(!$g->has_edge($i, $j));
}
+ }
}
my $g_ref = Graph->new(refvertexed => 1);
Debdiff
File lists identical (after any substitutions)
No differences were encountered in the control files