graphviz-perl / graph Goto Github PK

That's not to say that you need to do anything, so this could just be feedback.

Although the original versions of this module had its problems, it was lightweight and easy to use. It hasn't had a major version bump but now it's a much different experience.

I noticed that my CI builds have been taking much longer and I've traced it back to the inclusion of Set::Object in this module. It has a "recommends" dependency on Moose, which explodes the runtime by about 400%. I can do various things to turn that off, but not testing dependencies is something I'd rather not do.

I'm likely to drop this module because it's now much too heavy for my uses. I'm thinking about choosing some earlier version to use internally. Moose and everything else that comes with it is just too much of a maintenance hassle, no matter what convenience its users see at the code level.

bridges() returns memory addresses instead of objects for refvertexed graphs. Minimal failing example:

use strict;
use warnings;
use Data::Dumper;
use Graph::Undirected;

my $g = Graph::Undirected->new( refvertexed => 1 );
$g->add_edge( { name => 'A' }, { name => 'B' } );
print $Graph::VERSION, "\n";
print Dumper [ $g->edges ];
print Dumper [ $g->bridges ];

Output:

0.9726
$VAR1 = [
          [
            {
              'name' => 'A'
            },
            {
              'name' => 'B'
            }
          ]
        ];
$VAR1 = [
          [
            'HASH(0x5575f773e250)',
            'HASH(0x5575f7b67f48)'
          ]
        ];

I would expect $g->bridges to return the same as $g->edges (without respect to order).

POD section "Connected Graphs and Their Components" talks about Perl objects...

blessed into a package with a rather unusable name.

Are they really unusable? Seems that should instead say "unusual".

@neilb similar request to eserte/graphviz-makefile#4:

I'm hoping to make the GitHub Actions work completely including Coveralls operation. Could you either create the relevant secret on the repo and say here, so I can update the config, or make me a collaborator (I think) so I can do it myself? As a stretch goal, could you transfer this repo to the https://github.com/graphviz-perl organisation?

According to https://metacpan.org/release/Graph latest version is 0.9704 but there is no here coresponding git tag.

There's an RT issue also mentioning metadata; is this repo the authoritative source? Should GH issues be the bugtracker?

MWE:

use Graph::Undirected;

my $orig = Graph::Undirected->new;
$orig->add_edge( { name => 'A' }, { name => 'B' } );

my $copy = $orig->deep_copy;

for my $g ($orig, $copy) {
    for ($g->vertices) {
        print scalar $g->neighbours( $_ );
    }
    print "\n";
}

Expected output would be

11
11

meaning that both graphs have two vertices with one neighbour each. However, I get

11
00

meaning that something is wrong with adjacency table in deep-copied graph. The same result is acquired when copying a graph with clone() from Clone.

I am using Graph v0.9722. Same results with Storable 2.62 and 3.25, Data::Dumper 2.167 and 2.183.

Hello,

A sample script illustrates the problem.
It would appear that Graph::TransitiveClosure::Matrix::all_paths does not detect cycles properly.
Unfortunately, I am unsure how to fix it.

#! /usr/bin/env perl
use 5.010;
use strict;
use warnings;

use Graph::Undirected;
use Data::Dumper;

my $G = Graph::Undirected->new;
$G->add_weighted_edge("A", "B", 50);
$G->add_weighted_edge("C", "A", 50);
$G->add_weighted_edge("D", "A", 200);
$G->add_weighted_edge("E", "F", 800);
$G->add_weighted_edge("G", "E", 800);
$G->add_weighted_edge("F", "H", 8000);
$G->add_weighted_edge("I", "F", 50);
$G->add_weighted_edge("F", "J", 200);
$G->add_weighted_edge("F", "K", 80);
$G->add_weighted_edge("F", "L", 50);
$G->add_weighted_edge("M", "N", 200);
$G->add_weighted_edge("O", "N", 200);
$G->add_weighted_edge("L", "M", 50);
$G->add_weighted_edge("M", "P", 50);
$G->add_weighted_edge("M", "B", 50);
$G->add_weighted_edge("Q", "K", 80);
$G->add_weighted_edge("Q", "I", 80);
$G->add_weighted_edge("R", "P", 50);
$G->add_weighted_edge("R", "S", 200);
$G->add_weighted_edge("R", "C", 50);
$G->add_weighted_edge("I", "T", 200);
$G->add_weighted_edge("U", "L", 200);
$G->add_weighted_edge("L", "O", 200);
$G->add_weighted_edge("I", "G", 800);
$G->add_weighted_edge("I", "H", 8000);
$G->add_weighted_edge("I", "L", 50);
$G->add_weighted_edge("I", "P", 50);
$G->add_weighted_edge("S", "D", 200);

my $apsp = $G->all_pairs_shortest_paths;
my @paths = $apsp->all_paths("N", "K");
print Dumper \@paths;

A side note:
I do not actually need all_paths(), I would be happy to have an ability to find all shortest paths (there is more than one) instead of a random one, but it does not look like this is currently possible.

Graph::Directed::all_successors($g, 0) omits the vertex itself when the vertex is only indirectly reachable.

sub _all_successors {
    my $g = shift;
    my @init = @_;
    my %todo;
    @todo{@init} = @init;
    my %seen;
    my %init = %todo;
    my %self;
    while (keys %todo) {
      my @todo = values %todo;
      for my $t (@todo) {
	$seen{$t} = delete $todo{$t};
	for my $s ($g->successors($t)) {
	  $self{$s} = $s if exists $init{$s};
	  $todo{$s} = $s unless exists $seen{$s};
	}
      }
    }
    for my $v (@init) {
      delete $seen{$v} unless $g->has_edge($v, $v) || $self{$v};
    }
    return values %seen;
}

The test $self{$v} towards the end has to use exists just as the test before does.

% perl -MGraph::Directed -E 'my $g = Graph::Directed->new; $g->add_edge(2,1); $g->add_edge(1,2); say for $g->all_successors(2)'
1
2
% perl -MGraph::Directed -E 'my $g = Graph::Directed->new; $g->add_edge(0,1); $g->add_edge(1,0); say for $g->all_successors(0)'
1

The backward-compatible method average_degree was removed in commit ...4a2cc4a7 (2020-12-02) but remains in the documentation.

Hi Neil, I'm trying to write some code to find Hamilton cycles, and it would be useful to check is_biconnected() first to avoid unnecessary work. Unfortunately the helper function _biconnectivity_dfs() is recursive - essentially one level per node - which gets noisy on large graphs (my ultimate goal is to investigate a graph of 9,641 nodes), and is unlikely to be maximally efficient.

I had hoped that I could simply implement a stack of nodes to act on, but the current implementation relies on $v having been processed before the following two statements, and I don't understand the algorithm well enough to know if those checks can somehow be deferred. If you have any suggestions, if you're available to meet up in London some time to have a brainstorm through the code, or if you have a reference to the algorithm being implemented that would help me understand it better, I'd appreciate it.

Failing that, I think at the very least the function needs a no warnings qw{recursion}.

Hugo

Hi

Ian Jackson is reporting in Debian bug #987095 project that the result of transitive_closure() is wrong. It used to be correct in version 0.9704.

I've bisected this issue to commit 3ded9c7 with the following script:

#!/usr/bin/perl -w

use strict;
use Graph::Directed;

my $input = Graph::Directed->new;

foreach my $e (qw(
		  A-C
		  A-NOTA
		  B-A
		  B-C
		  B-NOTA
		)) {
  my ($x,$y) = split /-/, $e;
  $input->add_edge($x,$y); 
}

$input->delete_vertex('C');

print "input: $input\n";

my $output = $input->transitive_closure();
print "output 1: $output\n";

exit (1) unless $output eq 'A-A,A-NOTA,B-A,B-B,B-NOTA,NOTA-NOTA';

foreach my $x (qw(A B C N)) {
  $output->delete_edge($x,$x);
}
print "output 2: $output\n";
exit (1) unless $output eq 'A-NOTA,B-A,B-NOTA,NOTA-NOTA';

All the best

MWE:

open( my $inp, $0 );
while( <$inp> ) {
    print "BEFORE $.\n";
    my $g = Graph->new;
    $g->add_path( 'A', 'B', 'C', 'D' );
    my $h = $g->deep_copy;
    print "AFTER  $.\n";
}
close $inp;

Expected output:

BEFORE 1
AFTER  1
BEFORE 2
AFTER  2
...

Actual output:

BEFORE 1
AFTER  0
BEFORE 2
AFTER  2

Thus some code in deep_copy must interfere with $.. Strangely, its value is restored on the second iteration of the cycle. To me it seems that the issue appeared in version 0.9705.

My build process warns me about some unexpected files: installed by Graph module

   /usr/share/perl5/vendor_perl/Heap071/Elem.pm
   /usr/share/perl5/vendor_perl/Heap071/Fibonacci.pm
   /usr/share/perl5/vendor_perl/auto/Heap071/Elem/autosplit.ix
   /usr/share/perl5/vendor_perl/auto/Heap071/Fibonacci/autosplit.ix

I'm not sure for what those files are and are they really should be installed so better is to ask :P
always some .ix files should be installed when some DSO module is produced but in case of this module there is no such things.

In v0.9716 and earlier call to

scalar $graph->neighbours( $v );

used to return the number of neighbours. Starting with v0.9717 neighbours() seems to ignore the context of the caller always returning an array. This change might be intentional, as earlier behaviour was not documented. Can you confirm that the current (v0.9717 and later) behaviour is the correct one and will stay?

If there is no undirected path between two vertices, weakly_connected_components reports the vertices as being in different components, but weakly_connected_component_by_vertex returns the same id for both.

% perl -MGraph::Directed -MData::Dumper -e 'print Dumper [ Graph::Directed->new(edges => [[qw/a a/], [qw/b b/]])->weakly_connected_components ]'
$VAR1 = [
          [
            'a'
          ],
          [
            'b'
          ]
        ];

% perl -MGraph::Directed -MData::Dumper -e 'print Dumper [ Graph::Directed->new(edges => [[qw/a a/], [qw/b b/]])->weakly_connected_component_by_vertex("a") ]'
$VAR1 = [
          1
        ];

% perl -MGraph::Directed -MData::Dumper -e 'print Dumper [ Graph::Directed->new(edges => [[qw/a a/], [qw/b b/]])->weakly_connected_component_by_vertex("b") ]'
$VAR1 = [
          1
        ];

This may be just me, but reading

An edge is added to the subgraph if there is an edge in the original graph that starts from the src set of vertices and ends in the dst set of vertices.

I understand this should also work on undirected graphs. However, the following gives no results:

my $g = Graph::Undirected->new;
$g->add_edge( "A", "B" );
print $g->subgraph( ["A"], ["B"] )->edges;

Are src and dst supposed to be used only with directed graphs? If so, the following sentence also is a bit confusing

You can leave out dst in which case dst is assumed to be the same: this is called a vertex-induced subgraph.

as subgraph() with src only works correctly with undirected graphs.

Edit: Observed in v0.9725.

This test failure seems to be being caused by the different handling of Inf on perl 5.22 compared to earlier. If I comment out the special casing on line 60 of Graph.pm the test passes.

t/73_diameter.t (Wstat: 3840 Tests: 77 Failed: 15)
Failed tests:  22-24, 37-41, 45, 52-53, 60-61, 66-67
Non-zero exit status: 15

I see no CI is configured to this repo. Shall I send a pull request to set up GitHub Actions?

Hi,

I have found what appears to be a bug in the APSP_Floyd_Warshall() function in version 0.9704 (platform: Strawberry Perl 5.22 on 64-bit Windows 10). I was merely trying to apply this function to the example on Rosetta Code, http://rosettacode.org/wiki/Floyd-Warshall_algorithm . The output is non-deterministically incorrect for two of the possible pairs of vertices. The code below together with the Rosetta Code page should make the problem clear and reproducible. I was hoping to showcase the Graph module on this Rosetta Code page, so I would greatly appreciate it if you could take a look.

Regards,
Jon

use strict;
use Graph::Directed;  # Version 0.9704.

my @example = ( {from => 1, to => 3, weight => -2},
                {from => 3, to => 4, weight =>  2},
                {from => 4, to => 2, weight => -1},
                {from => 2, to => 1, weight =>  4},
                {from => 2, to => 3, weight =>  3} );
my $g = Graph::Directed->new;
foreach my $e (@example) {
    $g->add_weighted_edge($e->{from}, $e->{to}, $e->{weight});
}
my $apsp = $g->APSP_Floyd_Warshall();
# The output from APSP_Floyd_Warshall() is *non-deterministically*
# incorrect for two of the possible vertex pairs:
# * The distance from 1 -> 2 is sometimes indicated as 0 (incorrect),
#   sometimes as -1 (correct).  The list of *vertices* in the shortest
#   path is always correct, though (!).
# * The distance from 2 -> 4 is sometimes indicated as 5 (incorrect),
#   sometimes as 4 (correct). The corresponding list of vertices is
#   sometimes indicated as 2 -> 3 -> 4 (incorrect), sometimes as
#   2 -> 1 -> 3 -> 4 (correct).
print "Pair\tDist\tPath\n";
my @bad_edges = ( [1, 2], [2, 4] );
foreach my $e (@bad_edges) {
    my ($u, $v) = @{$e};
    my @spvs = $apsp->path_vertices($u, $v);
    print "$u -> $v", "\t",
          $apsp->path_length($u, $v), "\t",
          join(' -> ', @spvs), "\n";
}

Sample transcript:

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  -1      1 -> 3 -> 4 -> 2
2 -> 4  5       2 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  0       1 -> 3 -> 4 -> 2
2 -> 4  5       2 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  0       1 -> 3 -> 4 -> 2
2 -> 4  4       2 -> 1 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  0       1 -> 3 -> 4 -> 2
2 -> 4  5       2 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  0       1 -> 3 -> 4 -> 2
2 -> 4  4       2 -> 1 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  0       1 -> 3 -> 4 -> 2
2 -> 4  5       2 -> 3 -> 4

...>floyd_warshall.pl
Pair    Dist    Path
1 -> 2  -1      1 -> 3 -> 4 -> 2
2 -> 4  5       2 -> 3 -> 4

This is probably a very rare case, but I bumped into it recently:

use strict;
use warnings;
use Graph::Undirected;

{
    package Wrapper;
    sub new { return bless $_[1] }
}

$\ = "\n";

my $g = Graph::Undirected->new;

my $A = {};
my $B = {};

$g->add_edge( $A, $B );
print $g;

my $C = Wrapper->new( $A );
print $g; # This shows the same vertex appearing twice in the graph
print 'vertices: ', scalar $g->vertices; # OK
print 'edges:    ', scalar $g->edges;    # OK
print 'degrees:';
for ($g->vertices) {
    print scalar $g->neighbours( $_ ); # Should be 1 and 1, but prints 0 and 1
}

It seems that blessing a vertex breaks the adjacency table. The blessed reference does not change its address in the memory (0x... stays the same), but it changes its type. I assume that in Graph object vertices are identified by their string representation, HASH(0x...), which after blessing becomes Wrapper=HASH(0x...) resulting in broken adjacency tables.

It might be that this will not fix in the general case. If so, it would be nice to have a caveat message for this.

Edit: Observed on Graph 0.9724.