The result weights of vertices can be retrieved from the result graph by

	my $w = $sptg->get_vertex_attribute($v, 'weight');

The predecessor vertex of a vertex in the result graph
can be retrieved by

	my $u = $sptg->get_vertex_attribute($v, 'p');

("A successor vertex" cannot be retrieved as simply because a single
vertex can have several successors.  You can first find the
C<neighbors()> vertices and then remove the predecessor vertex.)

If you want to find the shortest path between two vertices,
see L</SP_Dijkstra>.

=item SSSP_Dijkstra

=item single_source_shortest_paths

Aliases for SPT_Dijkstra.

=item SP_Dijkstra

    @path = $g->SP_Dijkstra($u, $v)

Return the vertices in the shortest path in the graph $g between the
two vertices $u, $v.  If no path can be found, an empty list is returned.

Uses SPT_Dijkstra().

=item SPT_Dijkstra_clear_cache

    $g->SPT_Dijkstra_clear_cache

See L</"Clearing cached results">.

=item SPT_Bellman_Ford

    $sptg = $g->SPT_Bellman_Ford(%opt)

Return as a graph the single-source shortest paths of the graph using
Bellman-Ford's algorithm.  The graph can contain negative edges but
not negative cycles (negative cycles cause the algorithm to abort
with an error message C<Graph::SPT_Bellman_Ford: negative cycle exists/>).

You can choose the start 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_Bellman_Ford_root>).

The result weights of vertices can be retrieved from the result graph by

	my $w = $sptg->get_vertex_attribute($v, 'weight');

The predecessor vertex of a vertex in the result graph
can be retrieved by

	my $u = $sptg->get_vertex_attribute($v, 'p');

("A successor vertex" cannot be retrieved as simply because a single
vertex can have several successors.  You can first find the
C<neighbors()> vertices and then remove the predecessor vertex.)

If you want to find the shortes path between two vertices,
see L</SP_Bellman_Ford>.

=item SSSP_Bellman_Ford

Alias for SPT_Bellman_Ford.

=item SP_Bellman_Ford

    @path = $g->SP_Bellman_Ford($u, $v)

Return the vertices in the shortest path in the graph $g between the
two vertices $u, $v.  If no path can be found, an empty list is returned.

Uses SPT_Bellman_Ford().

=item SPT_Bellman_Ford_clear_cache

    $g->SPT_Bellman_Ford_clear_cache

See L</"Clearing cached results">.

=back

=head2 All-Pairs Shortest Paths (APSP)

For either a directed or an undirected graph, return the APSP object
describing all the possible paths between any two vertices of the
graph.  If no weight is defined for an edge, 1 (one) is assumed.

=over 4

=item APSP_Floyd_Warshall

=item all_pairs_shortest_paths

    my $apsp = $g->APSP_Floyd_Warshall(...);

Return the all-pairs shortest path object computed from the graph
using Floyd-Warshall's algorithm.  The length of a path between two
vertices is the sum of weight attribute of the edges along the
shortest path between the two vertices.  If no weight attribute name
is specified explicitly

    $g->APSP_Floyd_Warshall(attribute_name => 'height');

the attribute C<weight> is assumed.

B<If an edge has no defined weight attribute, the value of one is
assumed when getting the attribute.>

Once computed, you can query the APSP object with

=over 8

=item path_length

    my $l = $apsp->path_length($u, $v);

Return the length of the shortest path between the two vertices.

=item path_vertices

    my @v = $apsp->path_vertices($u, $v);

Return the list of vertices along the shortest path.

=item path_predecessor

   my $u = $apsp->path_predecessor($v);

Returns the predecessor of vertex $v in the all-pairs shortest paths.

=back

=over 8

=item average_path_length

    my $apl = $g->average_path_length; # All vertex pairs.

    my $apl = $g->average_path_length($u); # From $u.
    my $apl = $g->average_path_length($u, undef); # From $u.

    my $apl = $g->average_path_length($u, $v); # From $u to $v.

    my $apl = $g->average_path_length(undef, $v); # To $v.

Return the average (shortest) path length over all the vertex pairs of
the graph, from a vertex, between two vertices, and to a vertex.

=item longest_path

    my @lp = $g->longest_path;
    my $lp = $g->longest_path;

In scalar context return the I<longest shortest> path length over all
the vertex pairs of the graph.  In list context return the vertices
along a I<longest shortest> path.  Note that there might be more than
one such path; this interfaces return a random one of them.

=item diameter

=item graph_diameter

    my $gd = $g->diameter;

The longest path over all the vertex pairs is known as the
I<graph diameter>.

=item shortest_path

    my @sp = $g->shortest_path;
    my $sp = $g->shortest_path;

In scalar context return the shortest length over all the vertex pairs
of the graph.  In list context return the vertices along a shortest
path.  Note that there might be more than one such path; this
interface returns a random one of them.

=item radius

    my $gr = $g->radius;

The I<shortest longest> path over all the vertex pairs is known as the
I<graph radius>.  See also L</diameter>.

=item center_vertices

=item centre_vertices

    my @c = $g->center_vertices;
    my @c = $g->center_vertices($delta);

The I<graph center> is the set of vertices for which the I<vertex
eccentricity> is equal to the I<graph radius>.  The vertices are
returned in random order.  By specifying a delta value you can widen
the criterion from strict equality (handy for non-integer edge weights).

=item vertex_eccentricity

    my $ve = $g->vertex_eccentricity($v);

The longest path to a vertex is known as the I<vertex eccentricity>.
If the graph is unconnected, returns Inf.

=back

You can walk through the matrix of the shortest paths by using

=over 4

=item for_shortest_paths

    $n = $g->for_shortest_paths($callback)

The number of shortest paths is returned (this should be equal to V*V).
The $callback is a sub reference that receives four arguments:
the transitive closure object from Graph::TransitiveClosure, the two
vertices, and the index to the current shortest paths (0..V*V-1).

=back

=back

=head2 Clearing cached results

For many graph algorithms there are several different but equally valid
results.  (Pseudo)Randomness is used internally by the Graph module to
for example pick a random starting vertex, and to select random edges
from a vertex.

For efficiency the computed result is often cached to avoid
recomputing the potentially expensive operation, and this also gives
additional determinism (once a correct result has been computed, the
same result will always be given).

However, sometimes the exact opposite is desireable, and the possible
alternative results are wanted (within the limits of the pseudorandomness:
not all the possible solutions are guaranteed to be returned, usually only
a subset is retuned).  To undo the caching, the following methods are
available:

=over 4

=item *

connectivity_clear_cache

Affects L</connected_components>, L</connected_component_by_vertex>,
L</connected_component_by_index>, L</same_connected_components>,
L</connected_graph>, L</is_connected>, L</is_weakly_connected>,
L</weakly_connected_components>, L</weakly_connected_component_by_vertex>,
L</weakly_connected_component_by_index>, L</same_weakly_connected_components>,
L</weakly_connected_graph>.

=item *

biconnectivity_clear_cache

Affects L</biconnected_components>,
L</biconnected_component_by_vertex>,
L</biconnected_component_by_index>, L</is_edge_connected>,
L</is_edge_separable>, L</articulation_points>, L</cut_vertices>,
L</is_biconnected>, L</biconnected_graph>,
L</same_biconnected_components>, L</bridges>.

=item *

strong_connectivity_clear_cache

Affects L</strongly_connected_components>,
L</strongly_connected_component_by_vertex>,
L</strongly_connected_component_by_index>,
L</same_strongly_connected_components>, L</is_strongly_connected>,
L</strongly_connected>, L</strongly_connected_graph>.

=item *

SPT_Dijkstra_clear_cache

Affects L</SPT_Dijkstra>, L</SSSP_Dijkstra>, L</single_source_shortest_paths>,
L</SP_Dijkstra>.

=item *

SPT_Bellman_Ford_clear_cache

Affects L</SPT_Bellman_Ford>, L</SSSP_Bellman_Ford>, L</SP_Bellman_Ford>.

=back

Note that any such computed and cached results are of course always
automatically discarded whenever the graph is modified.

=head2 Random

You can either ask for random elements of existing graphs or create
random graphs.

=over 4

=item random_vertex

    my $v = $g->random_vertex;

Return a random vertex of the graph, or undef if there are no vertices.

=item random_edge

    my $e = $g->random_edge;

Return a random edge of the graph as an array reference having the
vertices as elements, or undef if there are no edges.

=item random_successor

    my $v = $g->random_successor($v);

Return a random successor of the vertex in the graph, or undef if there
are no successors.

=item random_predecessor

    my $u = $g->random_predecessor($v);

Return a random predecessor of the vertex in the graph, or undef if there
are no predecessors.

=item random_graph

    my $g = Graph->random_graph(%opt);

Construct a random graph.  The I<%opt> B<must> contain the C<vertices>
argument

    vertices => vertices_def

where the I<vertices_def> is one of

=over 8

=item *

an array reference where the elements of the array reference are the
vertices

=item *

a number N in which case the vertices will be integers 0..N-1

=back

=back

The %opt may have either of the argument C<edges> or the argument
C<edges_fill>.  Both are used to define how many random edges to
add to the graph; C<edges> is an absolute number, while C<edges_fill>
is a relative number (relative to the number of edges in a complete
graph, C).  The number of edges can be larger than C, but only if the
graph is countedged.  The random edges will not include self-loops.
If neither C<edges> nor C<edges_fill> is specified, an C<edges_fill>
of 0.5 is assumed.

If you want repeatable randomness (what is an oxymoron?)
you can use the C<random_seed> option:

    $g = Graph->random_graph(vertices => 10, random_seed => 1234);

As this uses the standard Perl srand(), the usual caveat applies:
use it sparingly, and consider instead using a single srand() call
at the top level of your application.

The default random distribution of edges is flat, that is, any pair of
vertices is equally likely to appear.  To define your own distribution,
use the C<random_edge> option:

    $g = Graph->random_graph(vertices => 10, random_edge => \&d);

where C<d> is a code reference receiving I<($g, $u, $v, $p)> as
parameters, where the I<$g> is the random graph, I<$u> and I<$v> are
the vertices, and the I<$p> is the probability ([0,1]) for a flat
distribution.  It must return a probability ([0,1]) that the vertices
I<$u> and I<$v> have an edge between them.  Note that returning one
for a particular pair of vertices doesn't guarantee that the edge will
be present in the resulting graph because the required number of edges
might be reached before that particular pair is tested for the
possibility of an edge.  Be very careful to adjust also C<edges>
or C<edges_fill> so that there is a possibility of the filling process
terminating.

=head2 Attributes

You can attach free-form attributes (key-value pairs, in effect a full
Perl hash) to each vertex, edge, and the graph itself.

Note that attaching attributes does slow down some other operations
on the graph by a factor of three to ten.  For example adding edge
attributes does slow down anything that walks through all the edges.

For vertex attributes:

=over 4

=item set_vertex_attribute

    $g->set_vertex_attribute($v, $name, $value)

Set the named vertex attribute.

If the vertex does not exist, the set_...() will create it, and the
other vertex attribute methods will return false or empty.

B<NOTE: any attributes beginning with an underscore/underline (_)
are reserved for the internal use of the Graph module.>

=item get_vertex_attribute

    $value = $g->get_vertex_attribute($v, $name)

Return the named vertex attribute.

=item has_vertex_attribute

    $g->has_vertex_attribute($v, $name)

Return true if the vertex has an attribute, false if not.

=item delete_vertex_attribute

    $g->delete_vertex_attribute($v, $name)

Delete the named vertex attribute.

=item set_vertex_attributes

    $g->set_vertex_attributes($v, $attr)

Set all the attributes of the vertex from the anonymous hash $attr.

B<NOTE>: any attributes beginning with an underscore (C<_>) are
reserved for the internal use of the Graph module.

=item get_vertex_attributes

    $attr = $g->get_vertex_attributes($v)

Return all the attributes of the vertex as an anonymous hash.

=item get_vertex_attribute_names

    @name = $g->get_vertex_attribute_names($v)

Return the names of vertex attributes.

=item get_vertex_attribute_values

    @value = $g->get_vertex_attribute_values($v)

Return the values of vertex attributes.

=item has_vertex_attributes

    $g->has_vertex_attributes($v)

Return true if the vertex has any attributes, false if not.

=item delete_vertex_attributes

    $g->delete_vertex_attributes($v)

Delete all the attributes of the named vertex.

=back

If you are using multivertices, use the I<by_id> variants:

=over 4

=item set_vertex_attribute_by_id

=item get_vertex_attribute_by_id

=item has_vertex_attribute_by_id

=item delete_vertex_attribute_by_id

=item set_vertex_attributes_by_id

=item get_vertex_attributes_by_id

=item get_vertex_attribute_names_by_id

=item get_vertex_attribute_values_by_id

=item has_vertex_attributes_by_id

=item delete_vertex_attributes_by_id

    $g->set_vertex_attribute_by_id($v, $id, $name, $value)