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::Undirected. 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 vertices.

$G->has_vertices(@v)

In list context returns a list which contains the vertex 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 vertex.

$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 actually 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 actually 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 actually 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->density_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 topologically.

@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 concatenating 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->TransitiveClosure_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 reachable 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_augmenting_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 representations) are identical. This means really identical: they must have identical vertex names and identical 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.