NAME
Data::Graph::Util - Utilities related to graph data structure
VERSION
This document describes version 0.003 of Data::Graph::Util (from Perl distribution Data-Graph-Util), released on 2017-07-04.
SYNOPSIS
use Data::Graph::Util qw(toposort is_cyclic is_acyclic);
my @sorted = toposort(
{ a=>["b"], b=>["c", "d"], d=>["c"] },
); # => ("a", "b", "d", "c")
# sort specified nodes (nodes not mentioned in the graph will be put at the
# end), duplicates not removed
my @sorted = toposort(
{ a=>["b"], b=>["c", "d"], d=>["c"] },
["e", "a", "b", "a"]
); # => ("a", "a", "b", "e")
say is_cyclic ({a=>["b"]}); # => 0
say is_acyclic({a=>["b"]}); # => 1
say is_cyclic ({a=>["b"], b=>["c"], c=>["a"]}); # => 1
say is_acyclic({a=>["b"], b=>["c"], c=>["a"]}); # => 0DESCRIPTION
Early release. More functions will be added later.
FUNCTIONS
None are exported by default, but they are exportable.
toposort(\%graph[ , \@nodes ]) => sorted list
Perform a topological sort on graph (currently using the Kahn algorithm). Will return the nodes of the graph sorted topologically. Will die if graph cannot be sorted, e.g. when graph is cyclic.
If \@nodes is specified, will instead return @nodes sorted according to the topological order. Duplicates are allowed and not removed. Nodes not mentioned in graph are also allowed and will be put at the end.
is_cyclic(\%graph) => bool
Return true if graph contains at least one cycle. Currently implemented by attempting a topological sort on the graph. If it can't be performed, this means the graph contains cycle(s).
is_acyclic(\%graph) => bool
Return true if graph is acyclic, i.e. contains no cycles. The opposite of is_cyclic().
HOMEPAGE
Please visit the project's homepage at https://metacpan.org/release/Data-Graph-Util.
SOURCE
Source repository is at https://github.com/perlancar/perl-Data-Graph-Util.
BUGS
Please report any bugs or feature requests on the bugtracker website https://rt.cpan.org/Public/Dist/Display.html?Name=Data-Graph-Util
When submitting a bug or request, please include a test-file or a patch to an existing test-file that illustrates the bug or desired feature.
SEE ALSO
https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
Sort::Topological can also sort a DAG, but cannot handle cyclical graph.
AUTHOR
perlancar <perlancar@cpan.org>
COPYRIGHT AND LICENSE
This software is copyright (c) 2017, 2016 by perlancar@cpan.org.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.