NAME
    Data::Graph::Util - Utilities related to graph data structure

VERSION
    This document describes version 0.007 of Data::Graph::Util (from Perl
    distribution Data-Graph-Util), released on 2023-12-20.

SYNOPSIS
     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"]})

DESCRIPTION
    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.

FUNCTIONS
    None are exported by default, but they are exportable.

  toposort
    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.

  is_cyclic
    Usage:

     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
    Usage:

     is_acyclic(\%graph) => bool

    Return true if graph is acyclic, i.e. contains no cycles. The opposite
    of "is_cyclic".

  connected_components
    Usage:

     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).

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>.

SEE ALSO
  Articles
    <https://en.wikipedia.org/wiki/Graph_(abstract_data_type)>

    <https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm>

  Related modules
    Graph contains more graph-related algorithms.

   Topological sort
    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.

AUTHOR
    perlancar <perlancar@cpan.org>

CONTRIBUTOR
    Jose Luis Martínez Torres <joseluis.martinez@capside.com>

CONTRIBUTING
    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.

COPYRIGHT AND LICENSE
    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.

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.