Creating a subgraph of a graph induced by node list

Question

I'm currently using Graph, however it lacks a method to create a subgraph of the original graph induced by given list of vertices.

I've written a stub which does it using Graph's accessors, but

Here's my code:

# subgraph ($graph, @node_list); 
# return subgraph (with the same setup) 
# induced by node list
sub subgraph {
    my $self = shift;
    my $new = $self->new;
    my @edges;
    foreach my $v(@_) {
        $self->has_vertex($v) or next;
        $new->add_vertex($v);
        foreach my $u(@_) {
            $self->has_edge($u, $v) and push @edges, $u, $v;
        };
    };
    $new->add_edges(@edges);
    return $new;
};

NOTE:

• The $Graph->new behaviour is undocumented, however as the Graph's source shows it would copy the attributes, but not vertices/edges.

• There's already a feature request on CPAN: https://rt.cpan.org/Ticket/Display.html?id=65497

So, is there some other module (probably XS), or should I patch Graph, or everyone writes a graph class themselves and I should do it, too?

Answer 1

So I've posted the code from the question to github (with some 10 unit-tests).

https://github.com/dallaylaen/perl-Graph-Subgraph

I would appreciate critique, bug reports and more test cases. Hope it gets into main module some day.

UPDATE: Now available via CPAN: Graph::Subgraph. Yet the above paragraph still holds.

Answer 2

If you have a list of all the vertices and the list of vertices you want, then compute the set difference between the two and use

$graph->delete_vertices(@unwanted_vertices);

I've used somethiing like this previously to prune down a large graph.