Konstantin S. Uvarin > Graph-Subgraph > Graph::Subgraph

Download:
Graph-Subgraph-0.0204.tar.gz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 0.0204   Source  

NAME ^

Graph::Subgraph - A subgraph() method for Graph module.

VERSION ^

Version 0.02

SYNOPSIS ^

    use Graph;
    use Graph::Subgraph;

    my $foo = Graph->new();
    $foo->add_edges(qw(x y y z));
    my $bar = $foo->subgraph(['x', 'y']);
    # $bar is now 'x-y'

METHODS ^

The only method resides in the Graph package (not Graph::Subgraph) so that any descendant of Graph can call it.

subgraph( \@src, [ \@dst ] );

subgraph( @src );

Returns a subgraph of the original graph induced by two sets of vertices.

A vertex is copied if and only if it belongs to one of the sets. An edge is copied if and only if it starts in the first set and ends in the second set.

If only one set is given, it is used as both. (So that is "subgraph induced by a set of vertices").

The sets may be given as one or two array references, or list.

The properties of the original graph (directedness etc.) are preserved, however the properties of vertices and edges are not.

Complexity: This method has a computational complexity of O(N(src)*N(dst)).

In theory, O(N(egdes_in_initial_graph)) is also possible, and the algorithm should choose whichever is better. This is not done yet.

Feel free to file a bug report if there's anything faster.

AUTHOR ^

Konstantin S. Uvarin, <khedin at gmail.com>

BUGS ^

This module should be merged into Graph.

Please report any bugs or feature requests to bug-graph-subgraph at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Graph-Subgraph. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT ^

You can find documentation for this module with the perldoc command.

    perldoc Graph::Subgraph

You can also look for information at:

LICENSE AND COPYRIGHT ^

Copyright 2012 Konstantin S. Uvarin.

This program is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.

syntax highlighting: