Creating a subgraph of a graph induced by node list
Domanda
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?
Soluzione
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.
Altri suggerimenti
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.