Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Graph(3)	      User Contributed Perl Documentation	      Graph(3)

NAME
       Graph - graph data structures and algorithms

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.

DESCRIPTION
   Non-Description
       This module is not for drawing or rendering any sort of graphics	or
       images, business, visualization,	or otherwise.

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

   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.

   Constructors
       new Create an empty graph.

       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:

	   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 "new()" constructor of the Graph::Directed class.

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

	   undirected
		   A boolean option telling that an undirected graph should be
		   created.  One could also use	the "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().

	   refvertexed
	   refvertexed_stringified
		   If you want to use references (including Perl objects) as
		   vertices, use "refvertexed".

		   Note	that using "refvertexed" means that internally the
		   memory address of the reference (for	example, a Perl
		   object) is used as the "identifier" of the vertex, not the
		   stringified form of the reference, even if you have defined
		   your	own stringification using "overload".

		   This	avoids the problem of the stringified references
		   potentially being identical (because	they are identical in
		   value, for example) even if the references are different.
		   If you really want to use references	and their stringified
		   forms as the	identities, use	the "refvertexed_stringified".
		   But please do not stringify different objects to the	same
		   stringified value.

	   unionfind
		   If the graph	is undirected, you can specify the "unionfind"
		   parameter to	use the	so-called union-find scheme to speed
		   up the computation of connected components of the graph
		   (see	"is_connected",	"connected_components",
		   "connected_component_by_vertex",
		   "connected_component_by_index", and
		   "same_connected_components").  If "unionfind" is used,
		   adding edges	(and vertices) becomes slower, but
		   connectedness queries become	faster.	 You must not delete
		   edges or vertices of	an unionfind graph, only add them.
		   You can test	a graph	for "union-findness" with

	   has_union_find
		   Returns true	if the graph was created with a	true
		   "unionfind" parameter.

	   vertices
		   An array reference of vertices to add.

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

       copy
       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
	   "deep_copy".	 The copy will have the	same directedness as the
	   original.

	   Also	the following vertex/edge attributes are copied:

	     refvertexed/hypervertexed/countvertexed/multivertexed
	     hyperedged/countedged/multiedged/omniedged

	   NOTE: You can get an	even shallower copy of a graph by

	       my $c = $g->new;

	   This	will copy only the graph properties (directed, and so forth),
	   but none of the vertices or edges.

	   As of 0.9712, you can also copy the graph properties	of an existing
	   object, but with overrides:

	       my $c = $g->new(multiedged => 0);

       deep_copy
       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 "copy".

	   Note	that copying code references only works	with Perls 5.8 or
	   later, and even then	only if	B::Deparse can reconstruct your	code.
	   This	functionality uses either Storable or Data::Dumper behind the
	   scenes, depending on	which is available (Storable is	preferred).

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

       undirected_copy_clear_cache
	       @path = $g->undirected_copy_clear_cache;

	   See "Clearing cached	results".

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

       transpose
       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

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

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

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

       subgraph
	      my $c = $g->subgraph(\@src, \@dst);
	      my $c = $g->subgraph(\@src);

	   Creates a subgraph of a given graph.	 The created subgraph has the
	   same	graph properties (directedness,	and so forth) as the original
	   graph, but none of the attributes (graph, vertex, or	edge).

	   A vertex is added to	the subgraph if	it is in the original graph.

	   An edge is added to the subgraph if there is	an edge	in the
	   original graph that starts from the "src" set of vertices and ends
	   in the "dst"	set of vertices.

	   You can leave out "dst" in which case "dst" is assumed to be	the
	   same: this is called	a vertex-induced subgraph.

       See also	"random_graph" for a random constructor.

   Basics
       add_vertex
	       $g->add_vertex($v)

	   Add the vertex to the graph.	 Returns the graph.

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

	   A vertex is also known as a node.

	   Adding "undef" as vertex is not allowed.

	   Note	that unless you	have isolated vertices (or countvertexed
	   vertices), you do not need to explicitly use	"add_vertex" since
	   "add_edge" will implicitly add its vertices.

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

	   An edge is also known as an arc.

       has_vertex
	       $g->has_vertex($v)

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

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

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

       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 multivertexed or countvertexed	and a
	   vertex has been added multiple times, the vertex will require at
	   least an equal number of deletions to become	completely deleted.

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

	   Delete the vertices from the	graph.	Returns	the graph, even	if
	   none	of the vertices	existed	in the graph.

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

       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 multiedged or countedged and an edge
	   has been added multiple times, the edge will	require	at least an
	   equal number	of deletions to	become completely deleted.

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

	   Delete the edges from the graph.  Returns the graph,	even if	none
	   of the edges	existed	in the graph.

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

   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

       stringify

   Boolean
       Graphs have boolifying overload,	so you can do things like

	   if ($g) { print "The	graph is: $g\n"	}

       which works even	if the graph is	empty.	In fact, the boolify always
       returns true.  If you want to test for example for vertices, test for
       vertices.

       boolify

   Comparing
       Testing for equality can	be done	either by the overloaded "eq" operator

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

       or by the method

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

       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 "ne" operator
       and the method

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

       See also	"Isomorphism".

   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.

       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.

       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.

       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.

       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.

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

	   NOTE: This does not detect cycles, see "has_a_cycle"	and
	   "find_a_cycle".

       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.

       has_a_cycle
	      $g->has_a_cycle

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

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

   Graph Types
       is_simple_graph
	       $g->is_simple_graph

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

       is_pseudo_graph
	       $g->is_pseudo_graph

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

       is_multi_graph
	       $g->is_multi_graph

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

       is_directed_acyclic_graph
       is_dag
	       $g->is_directed_acyclic_graph
	       $g->is_dag

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

       is_cyclic
	       $g->is_cyclic

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

	   To find at least one	such cycle, see	"find_a_cycle".

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

       To find a cycle,	use "find_a_cycle".

   Transitivity
       is_transitive
	       $g->is_transitive

	   Return true if the graph is transitive, false otherwise.

       TransitiveClosure_Floyd_Warshall
       transitive_closure
	       $tcg = $g->TransitiveClosure_Floyd_Warshall

	   Return the transitive closure graph of the graph.

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

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

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

       With

       transitive_closure_matrix
	      $tcm = $g->transitive_closure_matrix;

       you can (create if not existing and) query the transitive closure
       matrix that underlies the transitive closure graph.  See
       Graph::TransitiveClosure::Matrix	for more information.

   Mutators
       add_vertices
	       $g->add_vertices('d', 'e', 'f')

	   Add zero or more vertices to	the graph.  Returns the	graph.

       add_edges
	       $g->add_edges(['d', 'e'], ['f', 'g'])
	       $g->add_edges(qw(d e f g));

	   Add zero or more edges to the graph.	 The edges are specified as a
	   list	of array references, or	as a list of vertices where the	even
	   (0th, 2nd, 4th, ...)	items are start	vertices and the odd (1st,
	   3rd,	5th, ...) are the corresponding	end vertices.  Returns the
	   graph.

       rename_vertex
	       $g->rename_vertex('d', 'e')

	   Renames a vertex. It	retains	all of its edges. Throws exception if
	   doesn't exist.

	   Returns the graph.

       rename_vertices
	       $g->rename_vertices(sub { uc $_[0] })

	   Calls a function for	each vertex-name, renaming it to the return
	   value.

	   Returns the graph.

       ingest
	       $g->ingest($g2)

	   Ingests all the vertices and	edges of the given graph, including
	   attributes. Returns the ingesting graph.

   Accessors
       is_directed
       directed
	       $g->is_directed()
	       $g->directed()

	   Return true if the graph is directed, false otherwise.

       is_undirected
       undirected
	       $g->is_undirected()
	       $g->undirected()

	   Return true if the graph is undirected, false otherwise.

       is_refvertexed
       is_refvertexed_stringified
       refvertexed
       refvertexed_stringified
	   Return true if the graph can	handle references (including Perl
	   objects) as vertices.

       vertices
	       my $V = $g->vertices
	       my @V = $g->vertices

	   In scalar context, return the number	of vertices in the graph.  In
	   list	context, return	the vertices, in no particular order.

       has_vertices
	       $g->has_vertices()

	   Return true if the graph has	any vertices, false otherwise.

       edges
	       my $E = $g->edges
	       my @E = $g->edges

	   In scalar context, return the number	of edges in the	graph.	In
	   list	context, return	the edges, in no particular order.  The	edges
	   are returned	as anonymous arrays listing the	vertices.

       has_edges
	       $g->has_edges()

	   Return true if the graph has	any edges, false otherwise.

       is_connected
	       $g->is_connected

	   For an undirected graph, return true	is the graph is	connected,
	   false otherwise.  Being connected means that	from every vertex it
	   is possible to reach	every other vertex.

	   If the graph	has been created with a	true "unionfind" parameter,
	   the time complexity is (essentially)	O(V), otherwise	O(V log	V).

	   See also "connected_components", "connected_component_by_index",
	   "connected_component_by_vertex", and	"same_connected_components",
	   and "biconnectivity".

	   For directed	graphs,	see "is_strongly_connected" and
	   "is_weakly_connected".

       connected_components
	       @cc = $g->connected_components()

	   For an undirected graph, returns the	vertices of the	connected
	   components of the graph as a	list of	anonymous arrays.  The
	   ordering of the anonymous arrays or the ordering of the vertices
	   inside the anonymous	arrays (the components)	is undefined.

	   For directed	graphs,	see "strongly_connected_components" and
	   "weakly_connected_components".

       connected_component_by_vertex
	       $i = $g->connected_component_by_vertex($v)

	   For an undirected graph, return an index identifying	the connected
	   component the vertex	belongs	to, the	indexing starting from zero.

	   For the inverse, see	"connected_component_by_index".

	   If the graph	has been created with a	true "unionfind" parameter,
	   the time complexity is (essentially)	O(1), otherwise	O(V log	V).

	   See also "biconnectivity".

	   For directed	graphs,	see "strongly_connected_component_by_vertex"
	   and "weakly_connected_component_by_vertex".

       connected_component_by_index
	       @v = $g->connected_component_by_index($i)

	   For an undirected graph, return the vertices	of the ith connected
	   component, the indexing starting from zero.	The order of vertices
	   is undefined, while the order of the	connected components is	same
	   as from connected_components().

	   For the inverse, see	"connected_component_by_vertex".

	   For directed	graphs,	see "strongly_connected_component_by_index"
	   and "weakly_connected_component_by_index".

       same_connected_components
	       $g->same_connected_components($u, $v, ...)

	   For an undirected graph, return true	if the vertices	are in the
	   same	connected component.

	   If the graph	has been created with a	true "unionfind" parameter,
	   the time complexity is (essentially)	O(1), otherwise	O(V log	V).

	   For directed	graphs,	see "same_strongly_connected_components" and
	   "same_weakly_connected_components".

       connected_graph
	       $cg = $g->connected_graph

	   For an undirected graph, return its connected graph.

       connectivity_clear_cache
	       $g->connectivity_clear_cache

	   See "Clearing cached	results".

	   See "Connected Graphs and Their Components" for further discussion.

       biconnectivity
	       my ($ap,	$bc, $br) = $g->biconnectivity

	   For an undirected graph, return the various biconnectivity
	   components of the graph: the	articulation points (cut vertices),
	   biconnected components, and bridges.

	   Note: currently only	handles	connected graphs.

       is_biconnected
	      $g->is_biconnected

	   For an undirected graph, return true	if the graph is	biconnected
	   (if it has no articulation points, also known as cut	vertices).

       is_edge_connected
	      $g->is_edge_connected

	   For an undirected graph, return true	if the graph is	edge-connected
	   (if it has no bridges).

	   Note: more precisely, this would be called is_edge_biconnected,
	   since there is a more general concept of being k-connected.

       is_edge_separable
	      $g->is_edge_separable

	   For an undirected graph, return true	if the graph is	edge-separable
	   (if it has bridges).

	   Note: more precisely, this would be called is_edge_biseparable,
	   since there is a more general concept of being k-connected.

       articulation_points
       cut_vertices
	      $g->articulation_points

	   For an undirected graph, return the articulation points (cut
	   vertices) of	the graph as a list of vertices.  The order is
	   undefined.

       biconnected_components
	      $g->biconnected_components

	   For an undirected graph, return the biconnected components of the
	   graph as a list of anonymous	arrays of vertices in the components.
	   The ordering	of the anonymous arrays	or the ordering	of the
	   vertices inside the anonymous arrays	(the components) is undefined.
	   Also	note that one vertex can belong	to more	than one biconnected
	   component.

       biconnected_component_by_vertex
	      $i = $g->biconnected_component_by_index($v)

	   For an undirected graph, return the indices identifying the
	   biconnected components the vertex belongs to, the indexing starting
	   from	zero.  The order of of the components is undefined.

	   For the inverse, see	"connected_component_by_index".

	   For directed	graphs,	see "strongly_connected_component_by_index"
	   and "weakly_connected_component_by_index".

       biconnected_component_by_index
	      @v = $g->biconnected_component_by_index($i)

	   For an undirected graph, return the vertices	in the ith biconnected
	   component of	the graph as an	anonymous arrays of vertices in	the
	   component.  The ordering of the vertices within a component is
	   undefined.  Also note that one vertex can belong to more than one
	   biconnected component.

       same_biconnected_components
	       $g->same_biconnected_components($u, $v, ...)

	   For an undirected graph, return true	if the vertices	are in the
	   same	biconnected component.

       biconnected_graph
	       $bcg = $g->biconnected_graph

	   For an undirected graph, return its biconnected graph.

	   See "Connected Graphs and Their Components" for further discussion.

       bridges
	      $g->bridges

	   For an undirected graph, return the bridges of the graph as a list
	   of anonymous	arrays of vertices in the bridges.  The	order of
	   bridges and the order of vertices in	them is	undefined.

       biconnectivity_clear_cache
	       $g->biconnectivity_clear_cache

	   See "Clearing cached	results".

       strongly_connected
       is_strongly_connected
	       $g->is_strongly_connected

	   For a directed graph, return	true is	the directed graph is strongly
	   connected, false if not.

	   See also "is_weakly_connected".

	   For undirected graphs, see "is_connected", or "is_biconnected".

       strongly_connected_component_by_vertex
	       $i = $g->strongly_connected_component_by_vertex($v)

	   For a directed graph, return	an index identifying the strongly
	   connected component the vertex belongs to, the indexing starting
	   from	zero.

	   For the inverse, see	"strongly_connected_component_by_index".

	   See also "weakly_connected_component_by_vertex".

	   For undirected graphs, see "connected_components" or
	   "biconnected_components".

       strongly_connected_component_by_index
	       @v = $g->strongly_connected_component_by_index($i)

	   For a directed graph, return	the vertices of	the ith	connected
	   component, the indexing starting from zero.	The order of vertices
	   within a component is undefined, while the order of the connected
	   components is the as	from strongly_connected_components().

	   For the inverse, see	"strongly_connected_component_by_vertex".

	   For undirected graphs, see "weakly_connected_component_by_index".

       same_strongly_connected_components
	       $g->same_strongly_connected_components($u, $v, ...)

	   For a directed graph, return	true if	the vertices are in the	same
	   strongly connected component.

	   See also "same_weakly_connected_components".

	   For undirected graphs, see "same_connected_components" or
	   "same_biconnected_components".

       strong_connectivity_clear_cache
	       $g->strong_connectivity_clear_cache

	   See "Clearing cached	results".

       weakly_connected
       is_weakly_connected
	       $g->is_weakly_connected

	   For a directed graph, return	true is	the directed graph is weakly
	   connected, false if not.

	   Weakly connected graph is also known	as semiconnected graph.

	   See also "is_strongly_connected".

	   For undirected graphs, see "is_connected" or	"is_biconnected".

       weakly_connected_components
	       @wcc = $g->weakly_connected_components()

	   For a directed graph, returns the vertices of the weakly connected
	   components of the graph as a	list of	anonymous arrays.  The
	   ordering of the anonymous arrays or the ordering of the vertices
	   inside the anonymous	arrays (the components)	is undefined.

	   See also "strongly_connected_components".

	   For undirected graphs, see "connected_components" or
	   "biconnected_components".

       weakly_connected_component_by_vertex
	       $i = $g->weakly_connected_component_by_vertex($v)

	   For a directed graph, return	an index identifying the weakly
	   connected component the vertex belongs to, the indexing starting
	   from	zero.

	   For the inverse, see	"weakly_connected_component_by_index".

	   For undirected graphs, see "connected_component_by_vertex" and
	   "biconnected_component_by_vertex".

       weakly_connected_component_by_index
	       @v = $g->weakly_connected_component_by_index($i)

	   For a directed graph, return	the vertices of	the ith	weakly
	   connected component,	the indexing starting zero.  The order of
	   vertices within a component is undefined, while the order of	the
	   weakly connected components is same as from
	   weakly_connected_components().

	   For the inverse, see	"weakly_connected_component_by_vertex".

	   For undirected graphs, see connected_component_by_index and
	   biconnected_component_by_index.

       same_weakly_connected_components
	       $g->same_weakly_connected_components($u,	$v, ...)

	   Return true if the vertices are in the same weakly connected
	   component.

       weakly_connected_graph
	       $wcg = $g->weakly_connected_graph

	   For a directed graph, return	its weakly connected graph.

	   For undirected graphs, see "connected_graph"	and
	   "biconnected_graph".

       strongly_connected_components
	      my @scc =	$g->strongly_connected_components;

	   For a directed graph, return	the strongly connected components as a
	   list	of anonymous arrays.  The elements in the anonymous arrays are
	   the vertices	belonging to the strongly connected component; both
	   the elements	and the	components are in no particular	order.

	   Note	that strongly connected	components can have single-element
	   components even without self-loops: if a vertex is any of isolated,
	   sink, or a source, the vertex is alone in its own strong component.

	   See also "weakly_connected_components".

	   For undirected graphs, see "connected_components", or see
	   "biconnected_components".

       strongly_connected_graph
	      my $scg =	$g->strongly_connected_graph;

	   See "Connected Graphs and Their Components" for further discussion.

	   Strongly connected graphs are also known as kernel graphs.

	   See also "weakly_connected_graph".

	   For undirected graphs, see "connected_graph", or
	   "biconnected_graph".

       is_sink_vertex
	       $g->is_sink_vertex($v)

	   Return true if the vertex $v	is a sink vertex, false	if not.	 A
	   sink	vertex is defined as a vertex with predecessors	but no
	   successors: this definition means that isolated vertices are	not
	   sink	vertices.  If you want also isolated vertices, use
	   is_successorless_vertex().

       is_source_vertex
	       $g->is_source_vertex($v)

	   Return true if the vertex $v	is a source vertex, false if not.  A
	   source vertex is defined as a vertex	with successors	but no
	   predecessors: the definition	means that isolated vertices are not
	   source vertices.  If	you want also isolated vertices, use
	   is_predecessorless_vertex().

       is_successorless_vertex
	       $g->is_successorless_vertex($v)

	   Return true if the vertex $v	has no successors (no edges leaving
	   the vertex),	false if it has.

	   Isolated vertices will return true: if you do not want this,	use
	   is_sink_vertex().

       is_successorful_vertex
	       $g->is_successorful_vertex($v)

	   Return true if the vertex $v	has successors,	false if not.

       is_predecessorless_vertex
	       $g->is_predecessorless_vertex($v)

	   Return true if the vertex $v	has no predecessors (no	edges entering
	   the vertex),	false if it has.

	   Isolated vertices will return true: if you do not want this,	use
	   is_source_vertex().

       is_predecessorful_vertex
	       $g->is_predecessorful_vertex($v)

	   Return true if the vertex $v	has predecessors, false	if not.

       is_isolated_vertex
	       $g->is_isolated_vertex($v)

	   Return true if the vertex $v	is an isolated vertex: no successors
	   and no predecessors.

       is_interior_vertex
	       $g->is_interior_vertex($v)

	   Return true if the vertex $v	is an interior vertex: both successors
	   and predecessors.

       is_exterior_vertex
	       $g->is_exterior_vertex($v)

	   Return true if the vertex $v	is an exterior vertex: has either no
	   successors or no predecessors, or neither.

       is_self_loop_vertex
	       $g->is_self_loop_vertex($v)

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

       sink_vertices
	       @v = $g->sink_vertices()

	   Return the sink vertices of the graph.  In scalar context return
	   the number of sink vertices.	 See "is_sink_vertex" for the
	   definition of a sink	vertex.

       source_vertices
	       @v = $g->source_vertices()

	   Return the source vertices of the graph.  In	scalar context return
	   the number of source	vertices.  See "is_source_vertex" for the
	   definition of a source vertex.

       successorful_vertices
	       @v = $g->successorful_vertices()

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

       successorless_vertices
	       @v = $g->successorless_vertices()

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

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

	   Return the immediate	successor vertices of the vertex.

	   See also "all_successors", "all_neighbours",	and "all_reachable".

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

	   For a directed graph, returns all successor vertices	of the
	   argument vertices, recursively.

	   For undirected graphs, see "all_neighbours" and "all_reachable".

	   See also "successors".

       neighbors
       neighbours
	       @n = $g->neighbours($v)

	   Return the neighboring/neighbouring vertices.  Also known as	the
	   adjacent vertices.

	   See also "all_neighbours" and "all_reachable".

       all_neighbors
       all_neighbours
	      @n = $g->all_neighbours(@v)

	   Return the neighboring/neighbouring vertices	of the argument
	   vertices, recursively.  For a directed graph, recurses up
	   predecessors	and down successors.  For an undirected	graph, returns
	   all the vertices reachable from the argument	vertices: equivalent
	   to "all_reachable".

	   See also "neighbours" and "all_reachable".

       all_reachable
	       @r = $g->all_reachable(@v)

	   Return all the vertices reachable from of the argument vertices,
	   recursively.	 For a directed	graph, equivalent to "all_successors".
	   For an undirected graph, equivalent to "all_neighbours".  The
	   argument vertices are not included in the results unless there are
	   explicit self-loops.

	   See also "neighbours", "all_neighbours", and	"all_successors".

       predecessorful_vertices
	       @v = $g->predecessorful_vertices()

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

       predecessorless_vertices
	       @v = $g->predecessorless_vertices()

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

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

	   Return the immediate	predecessor vertices of	the vertex.

	   See also "all_predecessors",	"all_neighbours", and "all_reachable".

       all_predecessors
	       @p = $g->all_predecessors(@v)

	   For a directed graph, returns all predecessor vertices of the
	   argument vertices, recursively.

	   For undirected graphs, see "all_neighbours" and "all_reachable".

	   See also "predecessors".

       isolated_vertices
	       @v = $g->isolated_vertices()

	   Return the isolated vertices	of the graph.  In scalar context
	   return the number of	isolated vertices.  See	"is_isolated_vertex"
	   for the definition of an isolated vertex.

       interior_vertices
	       @v = $g->interior_vertices()

	   Return the interior vertices	of the graph.  In scalar context
	   return the number of	interior vertices.  See	"is_interior_vertex"
	   for the definition of an interior vertex.

       exterior_vertices
	       @v = $g->exterior_vertices()

	   Return the exterior vertices	of the graph.  In scalar context
	   return the number of	exterior vertices.  See	"is_exterior_vertex"
	   for the definition of an exterior vertex.

       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 "is_self_loop_vertex"
	   for the definition of a self-loop vertex.

       as_hashes
	       ($nodes,	$edges)	= $g->as_hashes

	   Return hash-refs which map vertices to their	attributes, and	for
	   edges, a two-level hash mapping the predecessor to its successors,
	   mapped to the attributes.

	   If "multivertexed" is true, the vertices hash will have the second-
	   level values	be the multivertex's ID, and the third level will be
	   attributes as above.

	   If "multiedged" is true, similar will be true for the edges hash.

   Connected Graphs and	Their Components
       In this discussion connected graph refers to any	of connected graphs,
       biconnected graphs, and strongly	connected graphs.

       NOTE: if	the vertices of	the original graph are Perl objects, (in other
       words, references, so you must be using "refvertexed") the vertices of
       the 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 connected graph are formed from the
       names of	the vertices of	the original graph by (alphabetically sorting
       them and) concatenating their names with	"+".  The vertex attribute
       "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
       "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.

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

       degree
       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
	   (identical to "in_degree()",	"out_degree()").

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

	   For directed	graphs:	the number of incoming edges at	the vertex.

	   For undirected graphs: the number of	edges at the vertex (identical
	   to "out_degree()", "degree()", "vertex_degree()").

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

	   For directed	graphs:	The number of outgoing edges at	the vertex.

	   For undirected graphs: the number of	edges at the vertex (identical
	   to "in_degree()", "degree()", "vertex_degree()").

       average_degree
	      my $ad = $g->average_degree;

	   Return the average degree (as in "degree()" or "vertex_degree()")
	   taken over all vertices.

       Related methods are

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

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

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

	   The edges leaving the vertex.

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

	   The edges entering the vertex.

       See also	"average_degree".

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

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

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

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

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

   Multiedges, Multivertices, Multigraphs
       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 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 refcounted,
       or reference counted, if	that sounds more familiar.

       The stronger kind is called (true) 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

       is_countedged
       countedged
	       $g->is_countedged
	       $g->countedged

	   Return true if the graph is countedged.

       is_countvertexed
       countvertexed
	       $g->is_countvertexed
	       $g->countvertexed

	   Return true if the graph is countvertexed.

       is_multiedged
       multiedged
	       $g->is_multiedged
	       $g->multiedged

	   Return true if the graph is multiedged.

       is_multivertexed
       multivertexed
	       $g->is_multivertexed
	       $g->multivertexed

	   Return true if the graph is multivertexed.

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

       NOTE: The various graph algorithms do not in general work well with
       multigraphs (they often assume 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

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

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

       add_vertex_by_id
       has_vertex_by_id
       delete_vertex_by_id
       add_edge_by_id
       has_edge_by_id
       delete_edge_by_id

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

       These interfaces	only apply to multivertices and	multiedges.  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

       add_vertex_get_id
       add_edge_get_id

	   $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

       get_multivertex_ids
       get_multiedge_ids

	   $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):

       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.

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

       add_weighted_edge_by_id
       add_weighted_edges_by_id
       add_weighted_path_by_id
       add_weighted_vertex_by_id
       add_weighted_vertices_by_id
       delete_edge_weight_by_id
       delete_vertex_weight_by_id
       get_edge_weight_by_id
       get_vertex_weight_by_id
       has_edge_weight_by_id
       has_vertex_weight_by_id
       set_edge_weight_by_id
       set_vertex_weight_by_id

   Topological Sort
       topological_sort
       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 "eval" to	trap that, or supply the "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.

   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.

       MST_Kruskal
	       $mstg = $g->MST_Kruskal;

	   Returns the Kruskal MST of the graph.

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

	   Returns the Prim MST	of the graph.

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

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

	   Aliases for MST_Prim.

   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.

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

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

	   NOTE: after the first reachable tree	from the first start vertex
	   has been finished, and if there still are unvisited vertices,
	   SPT_Dijkstra	will keep on selecting unvisited vertices.

	   The next roots (in case the first tree doesn't visit	all the
	   vertices) can be chosen by setting one of the following options to
	   true: "next_root", "next_alphabetic", "next_numeric",
	   "next_random".

	   The "next_root" is the most customizable: the value needs to	be a
	   subroutine reference	which will receive the graph and the unvisited
	   vertices as hash reference.	If you want to only visit the first
	   tree, use "next_root	=" sub { undef }>.  The	rest of	these options
	   are booleans.  If none of them are true, a random unvisited vertex
	   will	be selected.

	   The first start vertex is be	available as the graph attribute
	   "SPT_Dijkstra_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
	   "neighbors()" vertices and then remove the predecessor vertex.)

	   If you want to find the shortest path between two vertices, see
	   "SP_Dijkstra".

       SSSP_Dijkstra
       single_source_shortest_paths
	   Aliases for SPT_Dijkstra.

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

       SPT_Dijkstra_clear_cache
	       $g->SPT_Dijkstra_clear_cache

	   See "Clearing cached	results".

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

	   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
	   "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
	   "neighbors()" vertices and then remove the predecessor vertex.)

	   If you want to find the shortest path between two vertices, see
	   "SP_Bellman_Ford".

       SSSP_Bellman_Ford
	   Alias for SPT_Bellman_Ford.

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

       SPT_Bellman_Ford_clear_cache
	       $g->SPT_Bellman_Ford_clear_cache

	   See "Clearing cached	results".

   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.

       Note that weight	of 0 (zero) does not mean do not use this edge,	it
       means essentially the opposite: an edge that has	zero cost, an edge
       that makes the vertices the same.

       APSP_Floyd_Warshall
       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 "weight" is assumed.

	   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

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

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

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

		   Return the list of vertices along the shortest path.

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

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

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

		   Return list of array-refs with all the paths	from $u	to $v.

	   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 non-
		   zero	paths between vertex pairs of the graph's transitive
		   closure. Depending on the arguments,	this can be from a
		   vertex, between two vertices, or to a vertex. An undefined
		   (or not-given) vertex will match all.

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

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

		   NOTE: this returns the longest shortest path, not the
		   longest path.

	   diameter
	   graph_diameter
		       my $gd =	$g->diameter;

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

		   For an unconnected graph, single-vertex, or empty graph,
		   returns "undef".

	   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.

		   For an unconnected, single-vertex, or empty graph, returns
		   "undef" or an empty list.

	   radius
		       my $gr =	$g->radius;

		   The shortest	longest	path over all the vertex pairs is
		   known as the	graph radius.  See also	"diameter".

		   For an unconnected, single-vertex, or empty graph, returns
		   Infinity.

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

		   The graph center is the set of vertices for which the
		   vertex eccentricity is equal	to the 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).

		   For an unconnected, single-vertex, or empty graph, returns
		   an empty list.

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

		   The longest path to a vertex	is known as the	vertex
		   eccentricity.

		   If the graph	is unconnected,	single-vertex, or empty	graph,
		   returns Inf.

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

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

   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:

       o   connectivity_clear_cache

	   Affects "connected_components", "connected_component_by_vertex",
	   "connected_component_by_index", "same_connected_components",
	   "connected_graph", "is_connected", "is_weakly_connected",
	   "weakly_connected_components",
	   "weakly_connected_component_by_vertex",
	   "weakly_connected_component_by_index",
	   "same_weakly_connected_components", "weakly_connected_graph".

       o   biconnectivity_clear_cache

	   Affects "biconnected_components",
	   "biconnected_component_by_vertex",
	   "biconnected_component_by_index", "is_edge_connected",
	   "is_edge_separable",	"articulation_points", "cut_vertices",
	   "is_biconnected", "biconnected_graph",
	   "same_biconnected_components", "bridges".

       o   strong_connectivity_clear_cache

	   Affects "strongly_connected_components",
	   "strongly_connected_component_by_vertex",
	   "strongly_connected_component_by_index",
	   "same_strongly_connected_components", "is_strongly_connected",
	   "strongly_connected", "strongly_connected_graph".

       o   SPT_Dijkstra_clear_cache

	   Affects "SPT_Dijkstra", "SSSP_Dijkstra",
	   "single_source_shortest_paths", "SP_Dijkstra".

       o   SPT_Bellman_Ford_clear_cache

	   Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".

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

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

       random_vertex
	       my $v = $g->random_vertex;

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

       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.

       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.

       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.

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

	   Construct a random graph.  The %opt must contain the	"vertices"
	   argument

	       vertices	=> vertices_def

	   where the vertices_def is one of

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

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

       The %opt	may have either	of the argument	"edges"	or the argument
       "edges_fill".  Both are used to define how many random edges to add to
       the graph; "edges" is an	absolute number, while "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
       "edges" nor "edges_fill"	is specified, an "edges_fill" of 0.5 is
       assumed.

       If you want repeatable randomness (what is an oxymoron?)	 you can use
       the "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 "random_edge" option:

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

       where "d" is a code reference receiving ($g, $u,	$v, $p)	as parameters,
       where the $g is the random graph, $u and	$v are the vertices, and the
       $p is the probability ([0,1]) for a flat	distribution.  It must return
       a probability ([0,1]) that the vertices $u and $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 "edges" or "edges_fill" so that there is a
       possibility of the filling process terminating.

       NOTE: a known problem with randomness in	openbsd	pre-perl-5.20 is that
       using a seed does not give you deterministic randomness.	This affects
       any Perl	code, not just Graph.

   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:

       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.

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

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

	   Return the named vertex attribute.

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

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

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

	   Delete the named vertex attribute.

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

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

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

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

	   Return all the attributes of	the vertex as an anonymous hash, or
	   "undef" if no such vertex.

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

	   Return the names of vertex attributes.

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

	   Return the values of	vertex attributes.

       has_vertex_attributes
	       $g->has_vertex_attributes($v)

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

       delete_vertex_attributes
	       $g->delete_vertex_attributes($v)

	   Delete all the attributes of	the named vertex.

       If you are using	multivertices, use the by_id variants:

       set_vertex_attribute_by_id
       get_vertex_attribute_by_id
       has_vertex_attribute_by_id
       delete_vertex_attribute_by_id
       set_vertex_attributes_by_id
       get_vertex_attributes_by_id
       get_vertex_attribute_names_by_id
       get_vertex_attribute_values_by_id
       has_vertex_attributes_by_id
       delete_vertex_attributes_by_id
	       $g->set_vertex_attribute_by_id($v, $id, $name, $value)
	       $g->get_vertex_attribute_by_id($v, $id, $name)
	       $g->has_vertex_attribute_by_id($v, $id, $name)
	       $g->delete_vertex_attribute_by_id($v, $id, $name)
	       $g->set_vertex_attributes_by_id($v, $id,	$attr)
	       $g->get_vertex_attributes_by_id($v, $id)
	       $g->get_vertex_attribute_values_by_id($v, $id)
	       $g->get_vertex_attribute_names_by_id($v,	$id)
	       $g->has_vertex_attributes_by_id($v, $id)
	       $g->delete_vertex_attributes_by_id($v, $id)

       For edge	attributes:

       set_edge_attribute
	       $g->set_edge_attribute($u, $v, $name, $value)

	   Set the named edge attribute.

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

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

       get_edge_attribute
	       $value =	$g->get_edge_attribute($u, $v, $name)

	   Return the named edge attribute.

       has_edge_attribute
	       $g->has_edge_attribute($u, $v, $name)

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

       delete_edge_attribute
	       $g->delete_edge_attribute($u, $v, $name)

	   Delete the named edge attribute.

       set_edge_attributes
	       $g->set_edge_attributes($u, $v, $attr)

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

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

       get_edge_attributes
	       $attr = $g->get_edge_attributes($u, $v)

	   Return all the attributes of	the edge as an anonymous hash, or
	   "undef" if no such edge.

       get_edge_attribute_names
	       @name = $g->get_edge_attribute_names($u,	$v)

	   Return the names of edge attributes.

       get_edge_attribute_values
	       @value =	$g->get_edge_attribute_values($u, $v)

	   Return the values of	edge attributes.

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

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

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

	   Delete all the attributes of	the named edge.

       If you are using	multiedges, use	the by_id variants:

       set_edge_attribute_by_id
       get_edge_attribute_by_id
       has_edge_attribute_by_id
       delete_edge_attribute_by_id
       set_edge_attributes_by_id
       get_edge_attributes_by_id
       get_edge_attribute_names_by_id
       get_edge_attribute_values_by_id
       has_edge_attributes_by_id
       delete_edge_attributes_by_id
	       $g->set_edge_attribute_by_id($u,	$v, $id, $name,	$value)
	       $g->get_edge_attribute_by_id($u,	$v, $id, $name)
	       $g->has_edge_attribute_by_id($u,	$v, $id, $name)
	       $g->delete_edge_attribute_by_id($u, $v, $id, $name)
	       $g->set_edge_attributes_by_id($u, $v, $id, $attr)
	       $g->get_edge_attributes_by_id($u, $v, $id)
	       $g->get_edge_attribute_values_by_id($u, $v, $id)
	       $g->get_edge_attribute_names_by_id($u, $v, $id)
	       $g->has_edge_attributes_by_id($u, $v, $id)
	       $g->delete_edge_attributes_by_id($u, $v,	$id)

       For graph attributes:

       set_graph_attribute
	       $g->set_graph_attribute($name, $value)

	   Set the named graph attribute.

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

       get_graph_attribute
	       $value =	$g->get_graph_attribute($name)

	   Return the named graph attribute.

       has_graph_attribute
	       $g->has_graph_attribute($name)

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

       delete_graph_attribute
	       $g->delete_graph_attribute($name)

	   Delete the named graph attribute.

       set_graph_attributes
	       $g->get_graph_attributes($attr)

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

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

       get_graph_attributes
	       $attr = $g->get_graph_attributes()

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

       get_graph_attribute_names
	       @name = $g->get_graph_attribute_names()

	   Return the names of graph attributes.

       get_graph_attribute_values
	       @value =	$g->get_graph_attribute_values()

	   Return the values of	graph attributes.

       has_graph_attributes
	       $g->has_graph_attributes()

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

       delete_graph_attributes
	       $g->delete_graph_attributes()

	   Delete all the attributes of	the named graph.

   Weighted
       As convenient shortcuts the following methods add, query, and
       manipulate the attribute	"weight" with the specified value to the
       respective Graph	elements.

       add_weighted_edge
	       $g->add_weighted_edge($u, $v, $weight)

       add_weighted_edges
	       $g->add_weighted_edges($u1, $v1,	$weight1, ...)

       add_weighted_path
	       $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3,	...)

       add_weighted_vertex
	       $g->add_weighted_vertex($v, $weight)

       add_weighted_vertices
	       $g->add_weighted_vertices($v1, $weight1,	$v2, $weight2, ...)

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

       delete_vertex_weight
	       $g->delete_vertex_weight($v)

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

       get_vertex_weight
	       $g->get_vertex_weight($v)

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

       has_vertex_weight
	       $g->has_vertex_weight($v)

       set_edge_weight
	       $g->set_edge_weight($u, $v, $weight)

       set_vertex_weight
	       $g->set_vertex_weight($v, $weight)

   Isomorphism
       Two graphs being	isomorphic means that they are structurally the	same
       graph, the difference being that	the vertices might have	been renamed
       or substituted.	For example in the below example $g0 and $g1 are
       isomorphic: the vertices	"b c d"	have been renamed as "z	x y".

	       $g0 = Graph->new;
	       $g0->add_edges(qw(a b a c c d));
	       $g1 = Graph->new;
	       $g1->add_edges(qw(a x x y a z));

       In the general case determining isomorphism is NP-hard, in other	words,
       really hard (time-consuming), no	other ways of solving the problem are
       known than brute	force check of of all the possibilities	(with possible
       optimization tricks, of course, but brute force still rules at the end
       of the day).

       A very rough guess at whether two graphs	could be isomorphic is
       possible	via the	method

       could_be_isomorphic
	       $g0->could_be_isomorphic($g1)

       If the graphs do	not have the same number of vertices and edges,	false
       is returned.  If	the distribution of in-degrees and out-degrees at the
       vertices	of the graphs does not match, false is returned.  Otherwise,
       true is returned.

       What is actually	returned is the	maximum	number of possible isomorphic
       graphs between the two graphs, after the	above sanity checks have been
       conducted.  It is basically the product of the factorials of the
       absolute	values of in-degrees and out-degree pairs at each vertex, with
       the isolated vertices ignored (since they could be reshuffled and
       renamed arbitrarily).  Note that	for large graphs the product of	these
       factorials can overflow the maximum presentable number (the floating
       point number) in	your computer (in Perl)	and you	might get for example
       Infinity	as the result.

   Miscellaneous
       betweenness
	       %b = $g->betweenness

	   Returns a map of vertices to	their Freeman's	betweennesses:

	     C_b(v) = \sum_{s \neq v \neq t \in	V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}

	   It is described in:

	       Freeman,	A set of measures of centrality	based on betweenness, http://arxiv.org/pdf/cond-mat/0309045

	   and based on	the algorithm from:

	       "A Faster Algorithm for Betweenness Centrality"

       clustering_coefficient
	       $gamma =	$g->clustering_coefficient()
	       ($gamma,	%clustering) = $g->clustering_coefficient()

	   Returns the clustering coefficient gamma as described in

	       Duncan J. Watts and Steven Strogatz, Collective dynamics	of 'small-world' networks, https://web.archive.org/web/20120616204225/http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf

	   In scalar context returns just the average gamma, in	list context
	   returns the average gamma and a hash	of vertices to clustering
	   coefficients.

	   Returns an empty list (and therefore	undefined in scalar context)
	   if the graph	has no vertices.

       subgraph_by_radius
	       $s = $g->subgraph_by_radius($n, $radius);

	   Returns a subgraph representing the ball of $radius around node $n
	   (breadth-first search).

       The "expect" methods can	be used	to test	a graph	and croak if the graph
       call is not as expected.

       expect_acyclic
       expect_dag
       expect_directed
       expect_hyperedged
       expect_hypervertexed
       expect_multiedged
       expect_multivertexed
       expect_no_args
       expect_non_multiedged
       expect_non_multivertexed
       expect_non_unionfind
       expect_undirected

       In many algorithms it is	useful to have a value representing the
       infinity.  The Graph provides (and itself uses):

       Infinity
	   (Not	exported, use Graph::Infinity explicitly)

   Size	Requirements
       A graph takes up	at least 1172 bytes of memory.

       A vertex	takes up at least 100 bytes of memory.

       An edge takes up	at least 400 bytes of memory.

       (A Perl scalar value takes 16 bytes, or 12 bytes	if it's	a reference.)

       These size approximations are very approximate and optimistic (they are
       based on	total_size() of	Devel::Size).  In real life many factors
       affect these numbers, for example how Perl is configured.  The numbers
       are for a 32-bit	platform and for Perl 5.8.8.

       Roughly,	the above numbers mean that in a megabyte of memory you	can
       fit for example a graph of about	1000 vertices and about	2500 edges.

   Hyperedges, hypervertices, hypergraphs
       BEWARE: this is a rather	thinly tested feature, and the theory is even
       less so.	 Do not	expect this to stay as it is (or at all) in future
       releases.

       NOTE: most usual	graph algorithms (and basic concepts) break horribly
       (or at least will look funny) with these	hyperthingies.	Caveat emptor.

       Hyperedges are edges that connect a number of vertices different	from
       the usual two.

       Hypervertices are vertices that consist of a number of vertices
       different from the usual	one.

       Note that for hypervertices there is an asymmetry: when adding
       hypervertices, the single vertices are also implicitly added.

       Hypergraphs are graphs with hyperedges.

       To enable hyperness when	constructing Graphs use	the "hyperedged" and
       "hypervertexed" attributes:

	  my $h	= Graph->new(hyperedged	=> 1, hypervertexed => 1);

       To add hypervertexes, either explicitly use more	than one vertex	(or,
       indeed, no vertices) when using add_vertex()

	  $h->add_vertex("a", "b")
	  $h->add_vertex()

       or implicitly with array	references when	using add_edge()

	  $h->add_edge(["a", "b"], "c")
	  $h->add_edge()

       Testing for existence and deletion of hypervertices and hyperedges
       works similarly.

       To test for hyperness of	a graph	use the

       is_hypervertexed
       hypervertexed
	       $g->is_hypervertexed
	       $g->hypervertexed

       is_hyperedged
       hyperedged
	       $g->is_hyperedged
	       $g->hyperedged

       Since hypervertices consist of more than	one vertex:

       vertices_at
	       $g->vertices_at($v)

       Return the vertices at the vertex.  This	may return just	the vertex or
       also other vertices.

       To go with the concept of undirected in normal (non-hyper) graphs,
       there is	a similar concept of omnidirected (this	is my own coinage,
       "all-directions") for hypergraphs, and you can naturally	test for it by

       is_omnidirected
       omnidirected
       is_omniedged
       omniedged
	      $g->is_omniedged

	      $g->omniedged

	      $g->is_omnidirected

	      $g->omnidirected

	   Return true if the graph is omnidirected (edges have	no direction),
	   false if not.

       You may be wondering why	on earth did I make up this new	concept, why
       didn't the "undirected" work for	me?  Well, because of this:

	  $g = Graph->new(hypervertexed	=> 1, omnivertexed => 1);

       That's right, vertices can be omni, too - and that is indeed the
       default.	 You can turn it off and then $g->add_vertex(qw(a b)) no more
       means adding also the (hyper)vertex qw(b	a).  In	other words, the
       "directivity" is	orthogonal to (or independent of) the number of
       vertices	in the vertex/edge.

       is_omnivertexed
       omnivertexed

       Another oddity that fell	out of the implementation is the uniqueness
       attribute, that comes naturally in "uniqedged" and "uniqvertexed"
       flavours.  It does what it sounds like, to unique or not	the vertices
       participating in	edges and vertices (is the hypervertex qw(a b a) the
       same as the hypervertex qw(a b),	for example).  Without too much
       explanation:

       is_uniqedged
       uniqedged
       is_uniqvertexed
       uniqvertexed

   DIAGNOSTICS
       o   Graph::...Map...: arguments X expected Y ...

	   If you see these (more user-friendly	error messages should have
	   been	triggered above	and before these) please report	any such
	   occurrences,	but in general you should be happy to see these	since
	   it means that an attempt to call something with a wrong number of
	   arguments was caught	in time.

       o   Graph::add_edge: graph is not hyperedged ...

	   Maybe you used add_weighted_edge() with only	the two	vertex
	   arguments.

       o   Not an ARRAY	reference at lib/Graph.pm ...

	   One possibility is that you have code based on Graph	0.2xxxx	that
	   assumes Graphs being	blessed	hash references, possibly also
	   assuming that certain hash keys are available to use	for your own
	   purposes.  In Graph 0.50 none of this is true.  Please do not
	   expect any particular internal implementation of Graphs.  Use
	   inheritance and graph/vertex/edge attributes	instead.

	   Another possibility is that you meant to have objects (blessed
	   references) as graph	vertices, but forgot to	use "refvertexed" (see
	   "refvertexed") when creating	the graph.

ACKNOWLEDGEMENTS
       All bad terminology, bugs, and inefficiencies are naturally mine, all
       mine, and not the fault of the below.

       Thanks to Nathan	Goodman	and Andras Salamon for bravely betatesting my
       pre-0.50	code.  If they missed something, that was only because of my
       fiendish	code.

       The following literature	for algorithms and some	test cases:

       o   Algorithms in C, Third Edition, Part	5, Graph Algorithms, Robert
	   Sedgewick, Addison Wesley

       o   Introduction	to Algorithms, First Edition, Cormen-Leiserson-Rivest,
	   McGraw Hill

       o   Graphs, Networks and	Algorithms, Dieter Jungnickel, Springer

SEE ALSO
       Persistent/Serialized graphs?  You want to read/write Graphs?  See the
       Graph::Reader and Graph::Writer in CPAN.

AUTHOR
       Jarkko Hietaniemi jhi@iki.fi

       Now being maintained by Neil Bowers <neilb@cpan.org>

COPYRIGHT AND LICENSE
       Copyright (c) 1998-2014 Jarkko Hietaniemi.  All rights reserved.

       This is free software; you can redistribute it and/or modify it under
       the same	terms as the Perl 5 programming	language system	itself.

perl v5.32.1			  2020-12-05			      Graph(3)

NAME | SYNOPSIS | DESCRIPTION | ACKNOWLEDGEMENTS | SEE ALSO | AUTHOR | COPYRIGHT AND LICENSE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Graph&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help