$g->is_self_loop_vertex($v)

Return true if the vertex $v is a self loop vertex: has an edge
from itself to itself.

=item sink_vertices

    @v = $g->sink_vertices()

Return the sink vertices of the graph.
In scalar context return the number of sink vertices.
See L</is_sink_vertex> for the definition of a sink vertex.

=item source_vertices

    @v = $g->source_vertices()

Return the source vertices of the graph.
In scalar context return the number of source vertices.
See L</is_source_vertex> for the definition of a source vertex.

=item successorful_vertices

    @v = $g->successorful_vertices()

Return the successorful vertices of the graph.
In scalar context return the number of successorful vertices.

=item successorless_vertices

    @v = $g->successorless_vertices()

Return the successorless vertices of the graph.
In scalar context return the number of successorless vertices.

=item successors

    @s = $g->successors($v)

Return the immediate successor vertices of the vertex.

=item neighbors

=item neighbours

Return the neighbo(u)ring vertices.  Also known as the I<adjacent vertices>.

=item predecessorful_vertices

    @v = $g->predecessorful_vertices()

Return the predecessorful vertices of the graph.
In scalar context return the number of predecessorful vertices.

=item predecessorless_vertices

    @v = $g->predecessorless_vertices()

Return the predecessorless vertices of the graph.
In scalar context return the number of predecessorless vertices.

=item predecessors

    @s = $g->predecessors($v)

Return the immediate predecessor vertices of the vertex.

=item isolated_vertices

    @v = $g->isolated_vertices()

Return the isolated vertices of the graph.
In scalar context return the number of isolated vertices.
See L</is_isolated_vertex> for the definition of an isolated vertex.

=item interior_vertices

    @v = $g->interior_vertices()

Return the interior vertices of the graph.
In scalar context return the number of interior vertices.
See L</is_interior_vertex> for the definition of an interior vertex.

=item exterior_vertices

    @v = $g->exterior_vertices()

Return the exterior vertices of the graph.
In scalar context return the number of exterior vertices.
See L</is_exterior_vertex> for the definition of an exterior vertex.

=item self_loop_vertices

    @v = $g->self_loop_vertices()

Return the self-loop vertices of the graph.
In scalar context return the number of self-loop vertices.
See L</is_self_loop_vertex> for the definition of a self-loop vertex.

=back

=head2 Connected Graphs and Their Components

In this discussion I<connected graph> refers to any of
I<connected graphs>, I<biconnected graphs>, and I<strongly
connected graphs>.

B<NOTE>: if the vertices of the original graph are Perl objects,
(in other words, references, so you must be using C<refvertexed>) 
the vertices of the I<connected graph> are NOT by default usable
as Perl objects because they are blessed into a package with
a rather unusable name.

By default, the vertex names of the I<connected graph> are formed from
the names of the vertices of the original graph by (alphabetically
sorting them and) concatenating their names with C<+>.  The vertex
attribute C<subvertices> is also used to store the list (as an array
reference) of the original vertices.  To change the 'supercomponent'
vertex names and the whole logic of forming these supercomponents
use the C<super_component>) option to the method calls:

  $g->connected_graph(super_component => sub { ... })
  $g->biconnected_graph(super_component => sub { ... })
  $g->strongly_connected_graph(super_component => sub { ... })

The subroutine reference gets the 'subcomponents' (the vertices of the
original graph) as arguments, and it is supposed to return the new
supercomponent vertex, the "stringified" form of which is used as the
vertex name.

=head2 Degree

A vertex has a degree based on the number of incoming and outgoing edges.
This really makes sense only for directed graphs.

=over 4

=item degree

=item vertex_degree

    $d = $g->degree($v)
    $d = $g->vertex_degree($v)

For directed graphs: the in-degree minus the out-degree at the vertex.
For undirected graphs: the number of edges at the vertex.

=item in_degree

    $d = $g->in_degree($v)

The number of incoming edges at the vertex.

=item out_degree

    $o = $g->out_degree($v)

The number of outgoing edges at the vertex.

=item average_degree

   my $ad = $g->average_degree;

Return the average degree taken over all vertices.

=back

Related methods are

=over 4

=item edges_at

    @e = $g->edges_at($v)

The union of edges from and edges to at the vertex.

=item edges_from

    @e = $g->edges_from($v)

The edges leaving the vertex.

=item edges_to

    @e = $g->edges_to($v)

The edges entering the vertex.

=back

See also L</average_degree>.

=head2 Counted Vertices

I<Counted vertices> are vertices with more than one instance, normally
adding vertices is idempotent.  To enable counted vertices on a graph,
give the C<countvertexed> parameter a true value

    use Graph;
    my $g = Graph->new(countvertexed => 1);

To find out how many times the vertex has been added:

=over 4

=item get_vertex_count

    my $c = $g->get_vertex_count($v);

Return the count of the vertex, or undef if the vertex does not exist.

=back

=head2 Multiedges, Multivertices, Multigraphs

I<Multiedges> are edges with more than one "life", meaning that one
has to delete them as many times as they have been added.  Normally
adding edges is idempotent (in other words, adding edges more than
once makes no difference).

There are two kinds or degrees of creating multiedges and multivertices.
The two kinds are mutually exclusive.

The weaker kind is called I<counted>, in which the edge or vertex has
a count on it: add operations increase the count, and delete
operations decrease the count, and once the count goes to zero, the
edge or vertex is deleted.  If there are attributes, they all are
attached to the same vertex.  You can think of this as the graph
elements being I<refcounted>, or I<reference counted>, if that sounds
more familiar.

The stronger kind is called (true) I<multi>, in which the edge or vertex
really has multiple separate identities, so that you can for example
attach different attributes to different instances.

To enable multiedges on a graph:

    use Graph;
    my $g0 = Graph->new(countedged => 1);
    my $g0 = Graph->new(multiedged => 1);

Similarly for vertices

    use Graph;
    my $g1 = Graph->new(countvertexed => 1);
    my $g1 = Graph->new(multivertexed => 1);

You can test for these by

=over 4

=item is_countedged

=item countedged

    $g->is_countedged
    $g->countedged

Return true if the graph is countedged.

=item is_countvertexed

=item countvertexed

    $g->is_countvertexed
    $g->countvertexed

Return true if the graph is countvertexed.

=item is_multiedged

=item multiedged

    $g->is_multiedged
    $g->multiedged

Return true if the graph is multiedged.

=item is_multivertexed

=item multivertexed

    $g->is_multivertexed
    $g->multivertexed

Return true if the graph is multivertexed.

=back

A multiedged (either the weak kind or the strong kind) graph is
a I<multigraph>, for which you can test with C<is_multi_graph()>.

B<NOTE>: The various graph algorithms do not in general work well with
multigraphs (they often assume I<simple graphs>, that is, no
multiedges or loops), and no effort has been made to test the
algorithms with multigraphs.

vertices() and edges() will return the multiple elements: if you want
just the unique elements, use

=over 4

=item unique_vertices

=item unique_edges

    @uv = $g->unique_vertices; # unique
    @mv = $g->vertices;        # possible multiples
    @ue = $g->unique_edges;
    @me = $g->edges;

=back

If you are using (the stronger kind of) multielements, you should use
the I<by_id> variants:

=over 4

=item add_vertex_by_id

=item has_vertex_by_id

=item delete_vertex_by_id

=item add_edge_by_id

=item has_edge_by_id

=item delete_edge_by_id

=back

    $g->add_vertex_by_id($v, $id)
    $g->has_vertex_by_id($v, $id)
    $g->delete_vertex_by_id($v, $id)

    $g->add_edge_by_id($u, $v, $id)
    $g->has_edge_by_id($u, $v, $id)
    $g->delete_edge_by_id($u, $v, $id)

When you delete the last vertex/edge in a multivertex/edge, the whole
vertex/edge is deleted.  You can use add_vertex()/add_edge() on
a multivertex/multiedge graph, in which case an id is generated
automatically.  To find out which the generated id was, you need
to use

=over 4

=item add_vertex_get_id

=item add_edge_get_id

=back

    $idv = $g->add_vertex_get_id($v)
    $ide = $g->add_edge_get_id($u, $v)

To return all the ids of vertices/edges in a multivertex/multiedge, use

=over 4

=item get_multivertex_ids

=item get_multiedge_ids

=back

    $g->get_multivertex_ids($v)
    $g->get_multiedge_ids($u, $v)

The ids are returned in random order.

To find out how many times the edge has been added (this works for
either kind of multiedges):

=over 4

=item get_edge_count

    my $c = $g->get_edge_count($u, $v);

Return the count (the "countedness") of the edge, or undef if the
edge does not exist.

=back

The following multi-entity utility functions exist, mirroring
the non-multi vertices and edges:

=over 4

=item add_weighted_edge_by_id

=item add_weighted_edges_by_id

=item add_weighted_path_by_id

=item add_weighted_vertex_by_id

=item add_weighted_vertices_by_id

=item delete_edge_weight_by_id

=item delete_vertex_weight_by_id

=item get_edge_weight_by_id

=item get_vertex_weight_by_id

=item has_edge_weight_by_id

=item has_vertex_weight_by_id

=item set_edge_weight_by_id

=item set_vertex_weight_by_id

=back

=head2 Topological Sort

=over 4

=item topological_sort

=item toposort

    my @ts = $g->topological_sort;

Return the vertices of the graph sorted topologically.  Note that
there may be several possible topological orderings; one of them
is returned.

If the graph contains a cycle, a fatal error is thrown, you
can either use C<eval> to trap that, or supply the C<empty_if_cyclic>
argument with a true value

    my @ts = $g->topological_sort(empty_if_cyclic => 1);

in which case an empty array is returned if the graph is cyclic.

=back

=head2 Minimum Spanning Trees (MST)

Minimum Spanning Trees or MSTs are tree subgraphs derived from an
undirected graph.  MSTs "span the graph" (covering all the vertices)
using as lightly weighted (hence the "minimum") edges as possible.

=over 4

=item MST_Kruskal

    $mstg = $g->MST_Kruskal;

Returns the Kruskal MST of the graph.

=item MST_Prim

    $mstg = $g->MST_Prim(%opt);

Returns the Prim MST of the graph.

You can choose the first vertex with $opt{ first_root }.

=item MST_Dijkstra

=item minimum_spanning_tree

    $mstg = $g->MST_Dijkstra;
    $mstg = $g->minimum_spanning_tree;

Aliases for MST_Prim.

=back

=head2 Single-Source Shortest Paths (SSSP)

Single-source shortest paths, also known as Shortest Path Trees
(SPTs).  For either a directed or an undirected graph, return a (tree)
subgraph that from a single start vertex (the "single source") travels
the shortest possible paths (the paths with the lightest weights) to
all the other vertices.  Note that the SSSP is neither reflexive (the
shortest paths do not include the zero-length path from the source
vertex to the source vertex) nor transitive (the shortest paths do not
include transitive closure paths).  If no weight is defined for an
edge, 1 (one) is assumed.

=over 4

=item SPT_Dijkstra

    $sptg = $g->SPT_Dijkstra($root)
    $sptg = $g->SPT_Dijkstra(%opt)

Return as a graph the the single-source shortest paths of the graph
using Dijkstra's algorithm.  The graph cannot contain negative edges
(negative edges cause the algorithm to abort with an error message
C<Graph::SPT_Dijkstra: edge ... is negative>).

You can choose the first vertex of the result with either a single
vertex argument or with $opt{ first_root }, otherwise a random vertex
is chosen.

B<NOTE>: note that all the vertices might not be reachable from the
selected (explicit or random) start vertex.

The start vertex is be available as the graph attribute
C<SPT_Dijkstra_root>).