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.

new

$G = Graph->new(@V)

Returns a new graph $G with the optional vertices @V.

add_vertices

$G = $G->add_vertices(@v)

Adds the vertices to the graph $G, returns the graph.

add_vertex

$G = $G->add_vertex($v)

Adds the vertex $v to the graph $G, returns the graph.

vertices

@V = $G->vertices

In list context returns the vertices @V of the graph $G. In scalar context returns the number of the vertices.

By default this sorts the vertices. To avoid this extra overhead, use

@V = $G->vertices_unsorted

or do

use Graph vertices_unsorted => 1;

which will make vertices() to return unsorted results.

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

has_vertex

$b = $G->has_vertex($v)

Returns true if the vertex $v exists in the graph $G and false if it doesn't.

vertex

$v = $G->has_vertex($v)

Returns the vertex $v if the vertex exists in the graph $G or undef if it doesn't.

directed

$b = $G->directed($d)

Set the directedness of the graph $G to $d or return the current directedness. Directedness defaults to true.

undirected

$b = $G->undirected($d)

Set the undirectedness of the graph $G to $u or return the current undirectedness. Undirectedness defaults to false.

has_edge

$b = $G->has_edge($u, $v)

Return true if the graph $G has the edge between the vertices $u, $v.

has_edges

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

has_path

$G->has_path($u, $v, ...)

Return true if the graph $G has the cycle defined by the vertices $u, $v, ..., false otherwise.

has_cycle

$G->has_cycle($u, $v, ...)

Return true if the graph $G has the cycle defined by the vertices $u, $v, ...,false otherwise.

vertex_set

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

add_edge

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

add_edges

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

add_path

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

add_cycle

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

neighbors

@n = $G->neighbors($v)

Returns the neighbor vertices of the vertex in the graph. (Also 'neighbours' works.)

successors

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

Returns the successor vertices of the vertex in the graph.

predecessors

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

Returns the predecessor vertices of the vertex in the graph.

out_edges

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

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

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.

delete_edge

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

delete_edges

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

delete_path

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

delete_cycle

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

delete_vertex

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

delete_vertices

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

in_degree

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

out_degree

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

degree

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

average_degree

$d = $G->average_degree

Returns the average degree of the vertices of the graph $G.

is_source_vertex

$b = $G->is_source_vertex($v)

Returns true if the vertex $v is a source vertex of the graph $G.

A source vertex means that there are only outgoing egdes, and at least one of them (so that isolated vertices are not source vertices). If you want to test for no predecessors, use is_precessorless_vertex().

is_sink_vertex

$b = $G->is_sink_vertex($v)

Returns true if the vertex $v is a sink vertex of the graph $G.

A sink vertex means that there are only incoming egdes, and at least one of them (so that isolated vertices are not sink vertices). If you want to test for no successors, use is_successorless_vertex().

is_predecessorless_vertex

$b = $G->is_predecessorless_vertex($v)

Returns true if the vertex $v is a predecessorless vertex of the graph $G.

If you want to test for source vertices, use is_source_vertex().

is_successorless_vertex

$b = $G->is_successorless_vertex($v)

Returns true if the vertex $v is a successorless vertex of the graph $G.

If you want to test for sink vertices, use is_sink_vertex().

is_isolated_vertex

$b = $G->is_isolated_vertex($v)

Returns true if the vertex $v is a isolated vertex of the graph $G.

is_exterior_vertex

$b = $G->is_exterior_vertex($v)

Returns true if the vertex $v is a exterior vertex of the graph $G.

is_interior_vertex

$b = $G->is_interior_vertex($v)

Returns true if the vertex $v is a interior vertex of the graph $G.

is_self_loop_vertex

$b = $G->is_self_loop_vertex($v)

Returns true if the vertex $v is a self-loop vertex of the graph $G.

source_vertices

@s = $G->source_vertices

Returns the source vertices @s of the graph $G.

sink_vertices

@s = $G->sink_vertices

Returns the sink vertices @s of the graph $G.

successorless_vertices

@s = $G->successorless_vertices

Returns the successorless vertices @s of the graph $G.

predecessorless_vertices

@s = $G->predecessorless_vertices

Returns the predecessorless vertices @s of the graph $G.

isolated_vertices

@i = $G->isolated_vertices

Returns the isolated vertices @i of the graph $G.

exterior_vertices

@e = $G->exterior_vertices

Returns the exterior vertices @e of the graph $G.

interior_vertices

@i = $G->interior_vertices

Returns the interior vertices @i of the graph $G.

self_loop_vertices

@s = $G->self_loop_vertices

Returns the self-loop vertices @s of the graph $G.

density_limits

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

density

$d = $G->density

Returns the density $d of the graph $G.

is_sparse

$d = $G->is_sparse

Returns true if the graph $G is sparse.

is_dense

$d = $G->is_dense

Returns true if the graph $G is dense.

complete

$C = $G->complete;

Returns a new complete graph $C corresponding to the graph $G.

complement

$C = $G->complement;

Returns a new complement graph $C corresponding to the graph $G.

copy

$C = $G->copy;

Returns a new graph $C corresponding to the graph $G.

transpose

$T = $G->transpose;

Returns a new transpose graph $T corresponding to the graph $G.

set_attribute

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

get_attribute

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

has_attribute

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

get_attributes

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

delete_attribute

$G->delete_attribute($attribute)
$G->delete_attribute($attribute, $v)
$G->delete_attribute($attribute, $u, $v)

Deletes the $attribute of graph/vertex/edge.

delete_attributes

$G->delete_attributes()
$G->delete_attributes($v)
$G->delete_attributes($u, $v)

Deletes all the attributes of graph/vertex/edge.

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

add_weighted_edges

$G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)

Adds in the graph $G the weighted edges.

add_weighted_path

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

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

edge_classify

@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

@toposort = $G->toposort

Returns the vertices of the graph $G sorted topologically.

strongly_connected_components

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

strongly_connected_graph

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

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

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

articulation points

@A = $G->articulation_points(%param)

Returns the articulation points (vertices) @A of the graph $G. The %param can be used to control the search.

is_biconnected

$b = $G->is_biconnected

Returns true is the graph $G is biconnected (has no articulation points), false otherwise.

largest_out_degree

$v = $G->largest_out_degree( @V )

Selects the vertex $v from the vertices @V having the largest out degree in the graph $G.

MST_Prim

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

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

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

$SSSP = $G->SSSP_DAG($s)

Returns the Single-source Shortest Paths (as a graph) of the DAG $G starting from vertex $s.

add_capacity_edge

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

add_capacity_edges

$G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)

Adds in the graph $G the capacity edges.

add_capacity_path

$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

Flow_Ford_Fulkerson

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

Flow_Edmonds_Karp

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

eq

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