Data::Graph::Util - Utilities related to graph data structure
This document describes version 0.007 of Data::Graph::Util (from Perl distribution Data-Graph-Util), released on 2023-12-20.
use Data::Graph::Util qw( toposort is_cyclic is_acyclic connected_components ); # return nodes of a graph. a must come before b, b must come before c & d, and # d must come before c. my @sorted = toposort( { a=>["b"], b=>["c", "d"], d=>["c"] }, ); # => ("a", "b", "d", "c") # sort nodes specified in 2nd argument using the graph. nodes not mentioned in # the graph will be put at the end. duplicates are not removed. my @sorted = toposort( { a=>["b"], b=>["c", "d"], d=>["c"] }, ["e", "a", "b", "a"] ); # => ("a", "a", "b", "e") # check if a graph is cyclic say is_cyclic ({a=>["b"]}); # => 0 say is_acyclic({a=>["b"]}); # => 1 # check if a graph is acyclic (not cyclic) say is_cyclic ({a=>["b"], b=>["c"], c=>["a"]}); # => 1 say is_acyclic({a=>["b"], b=>["c"], c=>["a"]}); # => 0 # return connected subgraphs, sorted by the largest my @subgraphs = connected_components( { a=>["b"], b=>["c", "d"], d=>["c"] }, ); # => return 1 element, all nodes are connected as a single graph # return connected subgraphs, sorted by the largest my @subgraphs = connected_components( { a=>["b"], b=>["c", "d"], d=>["c"], e=>["f"], g=>["h", "i"], j=>["a"], }, ); # => return 3 elements, there are 3 separate subgraphs # ({a=>["b"], b=>["c", "d"], d=>["c"], j=>["a"]}, {e=>["f"]}, {g=>["h","i"]})
Early release. More functions will be added later.
This module provides some functions related to the graph data structure.
Keywords: topological ordering, dependency sorting, dependency ordering.
None are exported by default, but they are exportable.
Usage:
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.
\@nodes
@nodes
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".
connected_components(\%graph) => list of subgraphs
Return list of subgraphs that are not connected to one another, sorted by descending size. If all the nodes are connected, will return a single subgraph (the original graph itself).
Please visit the project's homepage at https://metacpan.org/release/Data-Graph-Util.
Source repository is at https://github.com/perlancar/perl-Data-Graph-Util.
https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
Graph contains more graph-related algorithms.
Algorithm::Dependency can also do topological sorting, but it is more finicky with input: graph cannot be epmty and all nodes need to be specified.
Sort::Topological can also sort a DAG, but cannot handle cyclical graph. It also performs poorly and eats too much RAM on larger graphs.
See Bencher::Scenario::GraphTopologicalSortModules for benchmarks.
perlancar <perlancar@cpan.org>
Jose Luis Martínez Torres <joseluis.martinez@capside.com>
To contribute, you can send patches by email/via RT, or send pull requests on GitHub.
Most of the time, you don't need to build the distribution yourself. You can simply modify the code, then test via:
% prove -l
If you want to build the distribution (e.g. to try to install it locally on your system), you can install Dist::Zilla, Dist::Zilla::PluginBundle::Author::PERLANCAR, Pod::Weaver::PluginBundle::Author::PERLANCAR, and sometimes one or two other Dist::Zilla- and/or Pod::Weaver plugins. Any additional steps required beyond that are considered a bug and can be reported to me.
This software is copyright (c) 2023, 2019, 2017, 2016 by perlancar <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.
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.
To install Data::Graph::Util, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Data::Graph::Util
CPAN shell
perl -MCPAN -e shell install Data::Graph::Util
For more information on module installation, please visit the detailed CPAN module installation guide.