=pod

=head1 NAME

Graph - graph data structures and algorithms

=head1 SYNOPSIS

	use Graph;
	my $g0 = Graph->new;             # A directed graph.

	use Graph::Directed;
	my $g1 = Graph::Directed->new;   # A directed graph.

	use Graph::Undirected;
	my $g2 = Graph::Undirected->new; # An undirected graph.

        $g->add_edge(...);
        $g->has_edge(...)
        $g->delete_edge(...);

        $g->add_vertex(...);
        $g->has_vertex(...);
        $g->delete_vertex(...);

        $g->vertices(...)
        $g->edges(...)

        # And many, many more, see below.

=head1 DESCRIPTION

=head2 Non-Description

This module is not for B<drawing> any sort of I<graphics>, business or
otherwise.

=head2 Description

Instead, this module is for creating I<abstract data structures>
called graphs, and for doing various operations on those.

=head2 Perl 5.6.0 minimum

The implementation depends on a Perl feature called "weak references"
and Perl 5.6.0 was the first to have those.

=head2 Constructors

=over 4

=item new

Create an empty graph.

=item Graph->new(%options)

The options are a hash with option names as the hash keys and the option
values as the hash values.

The following options are available:

=over 8

=item *

directed

A boolean option telling that a directed graph should be created.
Often somewhat redundant because a directed graph is the default
for the Graph class or one could simply use the C<new()> constructor
of the Graph::Directed class.

You can test the directness of a graph with $g->is_directed() and
$g->is_undirected().

=item *

undirected

A boolean option telling that an undirected graph should be created.
One could also use the C<new()> constructor the Graph::Undirected class
instead.

Note that while often it is possible to think undirected graphs as
bidirectional graphs, or as directed graphs with edges going both ways,
in this module directed graphs and undirected graphs are two different
things that often behave differently.

You can test the directness of a graph with $g->is_directed() and
$g->is_undirected().

=item *

refvertexed

If you want to use references (including Perl objects) as vertices.

=item *

unionfind

If the graph is undirected, you can specify the C<unionfind> parameter
to use the so-called union-find scheme to speed up the computation of
I<connected components> of the graph (see L</is_connected>,
L</connected_components>, L</connected_component_by_vertex>,
L</connected_component_by_index>, and L</same_connected_components>).
If C<unionfind> is used, adding edges (and vertices) becomes slower,
but connectedness queries become faster.  You can test a graph for
"union-findness" with

=over 8

=item has_union_find

    has_union_find

=back

=item *

vertices

An array reference of vertices to add.

=item *

edges

An array reference of array references of edge vertices to add.

=back

=item copy

=item copy_graph

    my $c = $g->copy_graph;

Create a shallow copy of the structure (vertices and edges) of the graph.
If you want a deep copy that includes attributes, see L</deep_copy>.
The copy will have the same directedness as the original.

=item deep_copy

=item deep_copy_graph

    my $c = $g->deep_copy_graph;

Create a deep copy of the graph (vertices, edges, and attributes) of
the graph.  If you want a shallow copy that does not include attributes,
see L</copy>.  (Uses Data::Dumper behind the scenes.  Note that copying
code references only works with Perls 5.8 or later, and even then only
if B::Deparse can reconstruct your code.)

=item undirected_copy

=item undirected_copy_graph

    my $c = $g->undirected_copy_graph;

Create an undirected shallow copy (vertices and edges) of the directed graph
so that for any directed edge (u, v) there is an undirected edge (u, v).

=item directed_copy

=item directed_copy_graph

    my $c = $g->directed_copy_graph;

Create a directed shallow copy (vertices and edges) of the undirected graph
so that for any undirected edge (u, v) there are two directed edges (u, v)
and (v, u).

=item transpose

=item transpose_graph

    my $t = $g->transpose_graph;

Create a directed shallow transposed copy (vertices and edges) of the
directed graph so that for any directed edge (u, v) there is a directed
edge (v, u).

You can also transpose a single edge with

=over 8

=item transpose_edge

    $g->transpose_edge($u, $v)

=back

=item complete_graph

=item complete

    my $c = $g->complete_graph;

Create a complete graph that has the same vertices as the original graph.
A complete graph has an edge between every pair of vertices.

=item complement_graph

=item complement

    my $c = $g->complement_graph;

Create a complement graph that has the same vertices as the original graph.
A complement graph has an edge (u,v) if and only if the original
graph does not have edge (u,v).

=back

See also L</random_graph> for a random constructor.

=head2 Basics

=over 4

=item add_vertex

    $g->add_vertex($v)

Add the vertex to the graph.  Returns the graph.

By default idempotent, but a graph can be created I<countvertexed>.

A vertex is also known as a I<node>.

Adding C<undef> as vertex is not allowed.

Note that unless you have isolated vertices (or I<countvertexed>
vertices), you do not need to explicitly use C<add_vertex> since
L</add_edge> will implicitly add its vertices.

=item add_edge

    $g->add_edge($u, $v)

Add the edge to the graph.  Implicitly first adds the vertices if the
graph does not have them.  Returns the graph.

By default idempotent, but a graph can be created I<countedged>.

An edge is also known as an I<arc>.

=item has_vertex

    $g->has_vertex($v)

Return true if the vertex exists in the graph, false otherwise.

=item has_edge

    $g->has_edge($u, $v)

Return true if the edge exists in the graph, false otherwise.

=item delete_vertex

    $g->delete_vertex($v)

Delete the vertex from the graph.  Returns the graph, even
if the vertex did not exist in the graph.

If the graph has been created I<multivertexed> or I<countvertexed>
and a vertex has been added multiple times, the vertex will require
at least an equal number of deletions to become completely deleted.

=item delete_vertices

    $g->delete_vertices($v1, $v2, ...)

Delete the vertices from the graph.  Returns the graph.

If the graph has been created I<multivertexed> or I<countvertexed>
and a vertex has been added multiple times, the vertex will require
at least an equal number of deletions to become completely deleteted.

=item delete_edge

    $g->delete_edge($u, $v)

Delete the edge from the graph.  Returns the graph, even
if the edge did not exist in the graph.

If the graph has been created I<multivertexed> or I<countedged>
and an edge has been added multiple times, the edge will require
at least an equal number of deletions to become completely deleted.

=item delete_edges

    $g->delete_edges($u1, $v1, $u2, $v2, ...)

Delete the edges from the graph.  Returns the graph.

If the graph has been created I<multivertexed> or I<countedged>
and an edge has been added multiple times, the edge will require
at least an equal number of deletions to become completely deleted.

=back

=head2 Displaying

Graphs have stringification overload, so you can do things like

    print "The graph is $g\n"

One-way (directed, unidirected) edges are shown as '-', two-way
(undirected, bidirected) edges are shown as '='.  If you want to,
you can call the stringification via the method

=over 4

=item stringify

=back

=head2 Comparing

Testing for equality can be done either by the overloaded C<eq>
operator

    $g eq "a-b,a-c,d"

or by the method

=over 4

=item eq

    $g->eq("a-b,a-c,d")

=back

The equality testing compares the stringified forms, and therefore it
assumes total equality, not isomorphism: all the vertices must be
named the same, and they must have identical edges between them.

For unequality there are correspondingly the overloaded C<ne>
operator and the method

=over 4

=item ne

    $g->ne("a-b,a-c,d")

=back

See also L</Isomorphism>.

=head2 Paths and Cycles

Paths and cycles are simple extensions of edges: paths are edges
starting from where the previous edge ended, and cycles are paths
returning back to the start vertex of the first edge.

=over 4

=item add_path

   $g->add_path($a, $b, $c, ..., $x, $y, $z)

Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
Returns the graph.

=item has_path

   $g->has_path($a, $b, $c, ..., $x, $y, $z)

Return true if the graph has all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z,
false otherwise.

=item delete_path

   $g->delete_path($a, $b, $c, ..., $x, $y, $z)

Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z
(regardless of whether they exist or not).  Returns the graph.

=item add_cycle

   $g->add_cycle($a, $b, $c, ..., $x, $y, $z)

Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the graph.
Returns the graph.

=item has_cycle

   $g->has_cycle($a, $b, $c, ..., $x, $y, $z)

Return true if the graph has all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z,
and $z-$a, false otherwise.

B<NOTE:> This does not I<detect> cycles, see L</has_a_cycle> and
L</find_a_cycle>.

=item delete_cycle

   $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)

Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a
(regardless of whether they exist or not).  Returns the graph.

=item has_a_cycle

   $g->has_a_cycle

Returns true if the graph has a cycle, false if not.

=item find_a_cycle

   $g->find_a_cycle

Returns a cycle if the graph has one (as a list of vertices), an empty
list if no cycle can be found.

Note that this just returns the vertices of I<a cycle>: not any
particular cycle, just the first one it finds.  A repeated call
might find the same cycle, or it might find a different one, and
you cannot call this repeatedly to find all the cycles.

=back

=head2 Graph Types

=over 4

=item is_simple_graph

    $g->is_simple_graph

Return true if the graph has no multiedges, false otherwise.

=item is_pseudo_graph

    $g->is_pseudo_graph

Return true if the graph has any multiedges or any self-loops,
false otherwise.

=item is_multi_graph

    $g->is_multi_graph

Return true if the graph has any multiedges but no self-loops,
false otherwise.

=item is_directed_acyclic_graph

=item is_dag

    $g->is_directed_acyclic_graph
    $g->is_dag

Return true if the graph is directed and acyclic, false otherwise.

=item is_cyclic

    $g->is_cyclic

Return true if the graph is cyclic (contains at least one cycle).
(This is identical to C<has_a_cycle>.)

To find at least that one cycle, see L</find_a_cycle>.

=item is_acyclic

Return true if the graph is acyclic (does not contain any cycles).

=back

To find a cycle, use L<find_a_cycle>.

=head2 Transitivity

=over 4

=item is_transitive

    $g->is_transitive

Return true if the graph is transitive, false otherwise.

=item TransitiveClosure_Floyd_Warshall

=item transitive_closure

    $tcg = $g->TransitiveClosure_Floyd_Warshall

Return the transitive closure graph of the graph.

=back

You can query the reachability from $u to $v with

=over 4

=item is_reachable

    $tcg->is_reachable($u, $v)

=back

See L<Graph::TransitiveClosure> for more information about creating
and querying transitive closures.