graph
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:
o 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
behave differently.
You can test the directness of a graph with
$g->is_directed() and $g->is_undirected().
o refvertexed
If you want to use references (including Perl objects) as
vertices.
o 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 can test a graph
for "union-findness" with
has_union_find
has_union_find
o vertices
An array reference of vertices to add.
o 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, and if the original was a "compat02" graph, the copy will
be, too.
Also the following vertex/edge attributes are copied:
refvertexed/hypervertexed/countvertexed/multivertexed
hyperedged/countedged/multiedged/omniedged
deep_copy
deep_copy_graph
my $c = $g->deep_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).
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).
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.
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.
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 deleteted.
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 multivertexed 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.
If the graph has been created multivertexed 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
$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
$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.
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 that one 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
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.
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
refvertexed
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 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".
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).
is_edge_separable
$g->is_edge_separable
For an undirected graph, return true if the graph is edge-separable
(if it has bridges).
articulation_points
cut_vertices
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 an index identifying the
biconnected component the vertex belongs to, the indexing starting
from zero.
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
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
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.
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.
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 succcessors (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.
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 neighbo(u)ring vertices. Also known as the adjacent
vertices.
See also "all_neighbours" and "all_reachable".
all_neighbors
all_neighbours
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".
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"
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()").
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);
$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)
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
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.
The 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
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 shortes path between two vertices, see
"SP_Bellman_Ford".
SSSP_Bellman_Ford
Alias for SPT_Bellman_Ford.
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.
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.
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.
interfaces return a random one of them.
diameter
graph_diameter
my $gd = $g->diameter;
The longest path over all the vertex pairs is known as the
graph diameter.
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.
radius
my $gr = $g->radius;
The shortest longest path over all the vertex pairs is
known as the graph radius. See also "diameter".
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).
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, 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
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 $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
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.
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.
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)
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.
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)
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://links.jstor.org/sici?sici=0038-0431(197703)40%3A1%3C35%3AASOMOC%3E2.0.CO%3B2-H
In scalar context returns just the average gamma, in list context
returns the average gamma and a hash of vertices to clustering
coefficients.
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
is not as expected.
expect_acyclic
expect_dag
expect_directed
expect_multiedged
expect_multivertexed
expect_non_multiedged
expect_non_multivertexed
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
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),
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
Backward compatibility with Graph 0.2
The Graph 0.2 (and 0.2xxxx) had the following features
o vertices() always sorted the vertex list, which most of the time is
unnecessary and wastes CPU.
o edges() returned a flat list where the begin and end vertices of
the edges were intermingled: every even index had an edge begin
vertex, and every odd index had an edge end vertex. This had the
unfortunate consequence of "scalar(@e = edges)" being twice the
number of edges, and complicating any algorithm walking through the
edges.
o The vertex list returned by edges() was sorted, the primary key
being the edge begin vertices, and the secondary key being the edge
end vertices.
o The attribute API was oddly position dependent and dependent on the
number of arguments. Use ..._graph_attribute(),
..._vertex_attribute(), ..._edge_attribute() instead.
In future releases of Graph (any release after 0.50) the 0.2xxxx
compatibility will be removed. Upgrade your code now.
If you want to continue using these (mis)features you can use the
"compat02" flag when creating a graph:
my $g = Graph->new(compat02 => 1);
This will change the vertices() and edges() appropriately. This,
however, is not recommended, since it complicates all the code using
vertices() and edges(). Instead it is recommended that the
vertices02() and edges02() methods are used. The corresponding new
style (unsorted, and edges() returning a list of references) methods
are called vertices05() and edges05().
To test whether a graph has the compatibility turned on
edges05
Return the edges as a list of array references, each element
containing the vertices of each edge. (This is not a backward
compatibility interface as such since it did not exist before.)
vertices02
Return the vertices in sorted order.
vertices05
Return the vertices in random order.
For the attributes the recommended way is to use the new API.
Do not expect new methods to work for compat02 graphs.
The following compatibility methods exist:
has_attribute
has_attributes
get_attribute
get_attributes
set_attribute
set_attributes
delete_attribute
delete_attributes
Do not use the above, use the new attribute interfaces instead.
vertices_unsorted
Alias for vertices() (or rather, vertices05()) since the vertices()
now always returns the vertices in an unsorted order. You can also
use the unsorted_vertices import, but only with a true value (false
values will cause an error).
density_limits
my ($sparse, $dense, $complete) = $g->density_limits;
Return the "density limits" used to classify graphs as "sparse" or
"dense". The first limit is C/4 and the second limit is 3C/4,
where C is the number of edges in a complete graph (the last
"limit").
density
my $density = $g->density;
Return the density of the graph, the ratio of the number of edges
to the number of edges in a complete graph.
vertex
my $v = $g->vertex($v);
Return the vertex if the graph has the vertex, undef otherwise.
out_edges
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.
POSSIBLE FUTURES
A possible future direction is a new graph module written for speed:
this may very possibly mean breaking or limiting some of the APIs or
behaviour as compared with this release of the module.
What definitely won't happen in future releases is carrying over the
Graph 0.2xxxx backward compatibility API.
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 AND COPYRIGHT
Jarkko Hietaniemi jhi@iki.fi
LICENSE
This module is licensed under the same terms as Perl itself.
Man Pages Copyright Respective Owners. Site Copyright (C) 1994 - 2013
Hurricane Electric.
All Rights Reserved.