graph::base(3)
NAME
Graph::Base - graph base class
SYNOPSIS
use Graph::Directed; use Graph::Undirected; $d1 = new Graph; $d2 = new Graph::Directed; $u = new Graph::Undirected;
DESCRIPTION
- You create new graphs by calling the "new" constructors of
classes "Graph", "Graph::Directed", and "Graph::Undi
rected". The classes "Graph" and "Graph::Directed" are
identical. After creating the graph you can modify and
explore the graph with following methods. - $G = Graph->new(@V)
- Returns a new graph $G with the optional vertices @V.
$G = $G->add_vertices(@v)- Adds the vertices to the graph $G, returns the graph.
$G = $G->add_vertex($v)- Adds the vertex $v to the graph $G, returns the graph.
@V = $G->vertices- In list context returns the vertices @V of the graph
$G. In scalar context returns the number of the ver
tices.
$G->has_vertices(@v)- In list context returns a list which contains the ver
tex of the vertices @v if the vertex exists in the
graph $G and undef if it doesn't. In scalar context
returns the number of the existing vertices.
$b = $G->has_vertex($v)- Returns true if the vertex $v exists in the graph $G
and false if it doesn't.
$v = $G->has_vertex($v)- Returns the vertex $v if the vertex exists in the
graph $G or undef if it doesn't.
$b = $G->directed($d)- Set the directedness of the graph $G to $d or return
the current directedness. Directedness defaults to
true.
$b = $G->undirected($d)- Set the undirectedness of the graph $G to $u or return
the current undirectedness. Undirectedness defaults
to false.
$b = $G->has_edge($u, $v)- Return true if the graph $G has the edge between the
vertices $u, $v.
$G->has_edges($u1, $v1, $u2, $v2, ...)- In list context returns a list which contains true for
each edge in the graph $G defined by the vertices $u1,
$v1, ..., and false for each non-existing edge. In
scalar context returns the number of the existing
edges.
$G->has_path($u, $v, ...)- Return true if the graph $G has the cycle defined by
the vertices $u, $v, ..., false otherwise.
$G->has_cycle($u, $v, ...)- Return true if the graph $G has the cycle defined by
the vertices $u, $v, ...,false otherwise.
$s = $G->vertex_set($v)- Returns the vertex set of the vertex $v in the graph
$G. A "vertex set" is represented by its parent ver
tex.
$G = $G->add_edge($u, $v)- Adds the edge defined by the vertices $u, $v, to the
graph $G. Also implicitly adds the vertices. Returns
the graph.
$G = $G->add_edges($u1, $v1, $u2, $v2, ...)- Adds the edge defined by the vertices $u1, $v1, ...,
to the graph $G. Also implicitly adds the vertices.
Returns the graph.
$G->add_path($u, $v, ...)- Adds the path defined by the vertices $u, $v, ..., to
the graph $G. Also implicitly adds the vertices.
Returns the graph.
$G = $G->add_cycle($u, $v, ...)- Adds the cycle defined by the vertices $u, $v, ..., to
the graph $G. Also implicitly adds the vertices.
Returns the graph.
@n = $G->neighbors($v)- Returns the neighbor vertices of the vertex in the
graph. (Also 'neighbours' works.)
@s = $G->successors($v)- Returns the successor vertices of the vertex in the
graph.
@p = $G->predecessors($v)- Returns the predecessor vertices of the vertex in the
graph.
@e = $G->out_edges($v)- Returns the edges leading out of the vertex $v in the
graph $G. In list context returns the edges as
($start_vertex, $end_vertex) pairs. In scalar context
returns the number of the edges.
@e = $G->in_edges($v)- Returns the edges leading into the vertex $v in the
graph $G. In list context returns the edges as
($start_vertex, $end_vertex) pairs; in scalar context
returns the number of the edges.
@e = $G->edges($u, $v)- Returns the edges between the vertices $u and $v, or
if $v is undefined, the edges leading into or out of
the vertex $u, or if $u is undefined, returns all the
edges, of the graph $G. In list context returns the
edges as a list of $start_vertex, $end_vertex pairs;
in scalar context returns the number of the edges.
$G = $G->delete_edge($u, $v)- Deletes an edge defined by the vertices $u, $v from
the graph $G. Note that the edge need not actually
exist. Returns the graph.
$G = $G->delete_edges($u1, $v1, $u2, $v2, ..)- Deletes edges defined by the vertices $u1, $v1, ...,
from the graph $G. Note that the edges need not actu
ally exist. Returns the graph.
$G = $G->delete_path($u, $v, ...)- Deletes a path defined by the vertices $u, $v, ...,
from the graph $G. Note that the path need not actu
ally exist. Returns the graph.
$G = $G->delete_cycle($u, $v, ...)- Deletes a cycle defined by the vertices $u, $v, ...,
from the graph $G. Note that the cycle need not actu
ally exist. Returns the graph.
$G = $G->delete_vertex($v)- Deletes the vertex $v and all its edges from the graph
$G. Note that the vertex need not actually exist.
Returns the graph.
$G = $G->delete_vertices(@v)- Deletes the vertices @v and all their edges from the
graph $G. Note that the vertices need not actually
exist. Returns the graph.
$d = $G->in_degree($v)- Returns the in-degree of the vertex $v in the graph
$G, or, if $v is undefined, the total in-degree of all
the vertices of the graph, or undef if the vertex
doesn't exist in the graph.
$d = $G->out_degree($v)- Returns the out-degree of the vertex $v in the graph
$G, or, if $v is undefined, the total out-degree of
all the vertices of the graph, of undef if the vertex
doesn't exist in the graph.
$d = $G->degree($v)- Returns the degree of the vertex $v in the graph $G
or, if $v is undefined, the total degree of all the
vertices of the graph, or undef if the vertex $v
doesn't exist in the graph.
$d = $G->average_degree- Returns the average degree of the vertices of the
graph $G.
$b = $G->is_source_vertex($v)- Returns true if the vertex $v is a source vertex of
the graph $G.
$b = $G->is_sink_vertex($v)- Returns true if the vertex $v is a sink vertex of the
graph $G.
$b = $G->is_isolated_vertex($v)- Returns true if the vertex $v is a isolated vertex of
the graph $G.
$b = $G->is_exterior_vertex($v)- Returns true if the vertex $v is a exterior vertex of
the graph $G.
$b = $G->is_interior_vertex($v)- Returns true if the vertex $v is a interior vertex of
the graph $G.
$b = $G->is_self_loop_vertex($v)- Returns true if the vertex $v is a self-loop vertex of
the graph $G.
@s = $G->source_vertices- Returns the source vertices @s of the graph $G.
@s = $G->sink_vertices- Returns the sink vertices @s of the graph $G.
@i = $G->isolated_vertices- Returns the isolated vertices @i of the graph $G.
@e = $G->exterior_vertices- Returns the exterior vertices @e of the graph $G.
@i = $G->interior_vertices- Returns the interior vertices @i of the graph $G.
@s = $G->self_loop_vertices- Returns the self-loop vertices @s of the graph $G.
($sparse, $dense, $complete) = $G->densi- ty_limits
- Returns the density limits for the number of edges in
the graph $G. Note that reaching $complete edges does
not really guarantee completeness because we can have
multigraphs. The limit of sparse is less than 1/4 of
the edges of the complete graph, the limit of dense is
more than 3/4 of the edges of the complete graph.
$d = $G->density- Returns the density $d of the graph $G.
$d = $G->is_sparse- Returns true if the graph $G is sparse.
$d = $G->is_dense- Returns true if the graph $G is dense.
$C = $G->complete;- Returns a new complete graph $C corresponding to the
graph $G.
$C = $G->complement;- Returns a new complement graph $C corresponding to the
graph $G.
$C = $G->copy;- Returns a new graph $C corresponding to the graph $G.
$T = $G->transpose;- Returns a new transpose graph $T corresponding to the
graph $G.
$G->set_attribute($attribute, $value)
$G->set_attribute($attribute, $v, $value)
$G->set_attribute($attribute, $u, $v, $value)- Sets the $attribute of graph/vertex/edge to $value but
only if the vertex/edge already exists. Returns true
if the attribute is set successfully, false if not.
$value = $G->get_attribute($attribute)
$value = $G->get_attribute($attribute, $v)
$value = $G->get_attribute($attribute, $u, $v)- Returns the $value of $attribute of graph/vertex/edge.
$value = $G->has_attribute($attribute)
$value = $G->has_attribute($attribute, $v)
$value = $G->has_attribute($attribute, $u, $v)- Returns the $value of $attribute of graph/vertex/edge.
%attributes = $G->get_attributes()
%attributes = $G->get_attributes($v)
%attributes = $G->get_attributes($u, $v)- Returns as a hash all the attribute names and values
of graph/vertex/edge.
$G->delete_attribute($attribute)
$G->delete_attribute($attribute, $v)
$G->delete_attribute($attribute, $u, $v)- Deletes the $attribute of graph/vertex/edge.
$G->delete_attributes()
$G->delete_attributes($v)
$G->delete_attributes($u, $v)- Deletes all the attributes of graph/vertex/edge.
$G->add_weighted_edge($u, $w, $v, $a)- Adds in the graph $G an edge from vertex $u to vertex
$v and the edge attribute 'weight' set to $w.
$G->add_weighted_edges($u1, $w1, $v1, $u2,- $w2, $v2, ...)
- Adds in the graph $G the weighted edges.
$G->add_weighted_path($v1, $w1, $v2, $w2, ...,- $wnm1, $vn)
- Adds in the graph $G the n edges defined by the path
$v1 ... $vn with the n-1 'weight' attributes $w1 ...
$wnm1
$MST = $G->MST_Kruskal;- Returns Kruskal's Minimum Spanning Tree (as a graph)
of the graph $G based on the 'weight' attributes of
the edges. (Needs the ->vertex_set() method.)
@C = $G->edge_classify(%param)- Returns the edge classification as a list where each
element is a triplet [$u, $v, $class] the $u, $v being
the vertices of an edge and $class being the class.
The %param can be used to control the search.
@toposort = $G->toposort- Returns the vertices of the graph $G sorted topologi
cally.
@S = $G->strongly_connected_components- Returns the strongly connected components @S of the
graph $G as a list of anonymous lists of vertices,
each anonymous list containing the vertices belonging
to one strongly connected component.
$T = $G->strongly_connected_graph- Returns the strongly connected graph $T of the graph
$G. The names of the strongly connected components
are formed from their constituent vertices by concate
nating their names by '+'-characters: "a" and "b" -->
"a+b".
$APSP = $G->APSP_Floyd_Warshall- Returns the All-pairs Shortest Paths graph of the
graph $G computed using the Floyd-Warshall algorithm
and the attribute 'weight' on the edges. The returned
graph has an edge for each shortest path. An edge has
attributes "weight" and "path"; for the length of the
shortest path and for the path (an anonymous list)
itself.
$TransitiveClosure = $G->TransitiveClo- sure_Floyd_Warshall
- Returns the Transitive Closure graph of the graph $G
computed using the Floyd-Warshall algorithm. The
resulting graph has an edge between each *ordered*
pair of vertices in which the second vertex is reach
able from the first.
@A = $G->articulation_points(%param)- Returns the articulation points (vertices) @A of the
graph $G. The %param can be used to control the
search.
$b = $G->is_biconnected- Returns true is the graph $G is biconnected (has no
articulation points), false otherwise.
$v = $G->largest_out_degree( @V )- Selects the vertex $v from the vertices @V having the
largest out degree in the graph $G.
$MST = $G->MST_Prim($u)- Returns Prim's Minimum Spanning Tree (as a graph) of
the graph $G based on the 'weight' attributes of the
edges. The optional start vertex is $u, if none is
given, a hopefully good one (a vertex with a large out
degree) is chosen.
$SSSP = $G->SSSP_Dijkstra($s)- Returns the Single-source Shortest Paths (as a graph)
of the graph $G starting from the vertex $s using
Dijktra's SSSP algorithm.
$SSSP = $G->SSSP_Bellman_Ford($s)- Returns the Single-source Shortest Paths (as a graph)
of the graph $G starting from the vertex $s using
Bellman-Ford SSSP algorithm. If there are one or more
negatively weighted cycles, returns undef.
$SSSP = $G->SSSP_DAG($s)- Returns the Single-source Shortest Paths (as a graph)
of the DAG $G starting from vertex $s.
$G->add_capacity_edge($u, $w, $v, $a)- Adds in the graph $G an edge from vertex $u to vertex
$v and the edge attribute 'capacity' set to $w.
$G->add_capacity_edges($u1, $w1, $v1, $u2,- $w2, $v2, ...)
- Adds in the graph $G the capacity edges.
$G->add_capacity_path($v1, $w1, $v2, $w2, ...,- $wnm1, $vn)
- Adds in the graph $G the n edges defined by the path
$v1 ... $vn with the n-1 'capacity' attributes $w1 ...
$wnm1
$F = $G->Flow_Ford_Fulkerson($S)- Returns the (maximal) flow network of the flow network
$G, parametrized by the state $S. The $G must have
'capacity' attributes on its edges. $S->{ source }
must contain the source vertex and $S->{ sink } the
sink vertex, and most importantly $S->{ next_augment
ing_path } must contain an anonymous subroutine which
takes $F and $S as arguments and returns the next
potential augmenting path. Flow_Ford_Fulkerson will
do the augmenting. The result graph $F will have
'flow' and (residual) 'capacity' attributes on its
edges.
$F = $G->Flow_Edmonds_Karp($source, $sink)- Return the maximal flow network of the graph $G built
using the Edmonds-Karp version of Ford-Fulkerson. The
input graph $G must have 'capacity' attributes on its
edges; resulting flow graph will have 'capacity' and
'flow' attributes on its edges.
$G->eq($H)- Return true if the graphs (actually, their string rep
resentations) are identical. This means really iden
tical: they must have identical vertex names and iden
tical edges between the vertices, and they must be
similarly directed. (Just isomorphism isn't enough.)
COPYRIGHT
Copyright 1999, O'Reilly & Associates.
- This code is distributed under the same copyright terms as
Perl itself.