[OpenSPARC-T2-DV] / tools / perl-5.8.0 / man / man3 / Graph::Base.3

.\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sh \" Subsection heading
.br
.if t .Sp
.ne 5
.PP
\fB\\$1\fR
.PP
..
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  | will give a
.\" real vertical bar.  \*(C+ will give a nicer C++.  Capital omega is used to
.\" do unbreakable dashes and therefore won't be available.  \*(C` and \*(C'
.\" expand to `' in nroff, nothing in troff, for use with C<>.
.tr \(*W-|\(bv\*(Tr
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
'br\}
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.if \nF \{\
.    de IX
.    tm Index:\\$1\t\\n%\t"\\$2"
..
.    nr % 0
.    rr F
.\}
.\"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.hy 0
.if n .na
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Graph::Base 3"
.TH Graph::Base 3 "2004-04-04" "perl v5.8.0" "User Contributed Perl Documentation"
.SH "NAME"
Graph::Base \- graph base class
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 2
\&    use Graph::Directed;
\&    use Graph::Undirected;
.Ve
.PP
.Vb 3
\&    $d1 = new Graph;
\&    $d2 = new Graph::Directed;
\&    $u  = new Graph::Undirected;
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
You create new graphs by calling the \f(CW\*(C`new\*(C'\fR constructors of classes
\&\f(CW\*(C`Graph\*(C'\fR, \f(CW\*(C`Graph::Directed\*(C'\fR, and \f(CW\*(C`Graph::Undirected\*(C'\fR.  The classes
\&\f(CW\*(C`Graph\*(C'\fR and \f(CW\*(C`Graph::Directed\*(C'\fR are identical.  After creating the
graph you can modify and explore the graph with following methods.
.IP "new" 4
.IX Item "new"
.Vb 1
\&        $G = Graph->new(@V)
.Ve
.Sp
Returns a new graph \f(CW$G\fR with the optional vertices \f(CW@V\fR.
.IP "add_vertices" 4
.IX Item "add_vertices"
.Vb 1
\&        $G = $G->add_vertices(@v)
.Ve
.Sp
Adds the vertices to the graph \f(CW$G\fR, returns the graph.
.IP "add_vertex" 4
.IX Item "add_vertex"
.Vb 1
\&        $G = $G->add_vertex($v)
.Ve
.Sp
Adds the vertex \f(CW$v\fR to the graph \f(CW$G\fR, returns the graph.
.IP "vertices" 4
.IX Item "vertices"
.Vb 1
\&        @V = $G->vertices
.Ve
.Sp
In list context returns the vertices \f(CW@V\fR of the graph \f(CW$G\fR.
In scalar context returns the number of the vertices.
.IP "has_vertices" 4
.IX Item "has_vertices"
.Vb 1
\&        $G->has_vertices(@v)
.Ve
.Sp
In list context returns a list which contains the vertex
of the vertices \f(CW@v\fR if the vertex exists in the graph \f(CW$G\fR
and undef if it doesn't.  In scalar context returns the
number of the existing vertices.
.IP "has_vertex" 4
.IX Item "has_vertex"
.Vb 1
\&        $b = $G->has_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR exists in
the graph \f(CW$G\fR and false if it doesn't.
.IP "vertex" 4
.IX Item "vertex"
.Vb 1
\&        $v = $G->has_vertex($v)
.Ve
.Sp
Returns the vertex \f(CW$v\fR if the vertex exists in the graph \f(CW$G\fR
or undef if it doesn't.
.IP "directed" 4
.IX Item "directed"
.Vb 1
\&        $b = $G->directed($d)
.Ve
.Sp
Set the directedness of the graph \f(CW$G\fR to \f(CW$d\fR or return the
current directedness.  Directedness defaults to true.
.IP "undirected" 4
.IX Item "undirected"
.Vb 1
\&        $b = $G->undirected($d)
.Ve
.Sp
Set the undirectedness of the graph \f(CW$G\fR to \f(CW$u\fR or return the
current undirectedness.  Undirectedness defaults to false.
.IP "has_edge" 4
.IX Item "has_edge"
.Vb 1
\&        $b = $G->has_edge($u, $v)
.Ve
.Sp
Return true if the graph \f(CW$G\fR has the edge between
the vertices \f(CW$u\fR, \f(CW$v\fR.
.IP "has_edges" 4
.IX Item "has_edges"
.Vb 1
\&        $G->has_edges($u1, $v1, $u2, $v2, ...)
.Ve
.Sp
In list context returns a list which contains true for each
edge in the graph \f(CW$G\fR defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ...,
and false for each non-existing edge.  In scalar context
returns the number of the existing edges.
.IP "has_path" 4
.IX Item "has_path"
.Vb 1
\&        $G->has_path($u, $v, ...)
.Ve
.Sp
Return true if the graph \f(CW$G\fR has the cycle defined by
the vertices \f(CW$u\fR, \f(CW$v\fR, ..., false otherwise.
.IP "has_cycle" 4
.IX Item "has_cycle"
.Vb 1
\&        $G->has_cycle($u, $v, ...)
.Ve
.Sp
Return true if the graph \f(CW$G\fR has the cycle defined by
the vertices \f(CW$u\fR, \f(CW$v\fR, ...,false otherwise.
.IP "vertex_set" 4
.IX Item "vertex_set"
.Vb 1
\&        $s = $G->vertex_set($v)
.Ve
.Sp
Returns the vertex set of the vertex \f(CW$v\fR in the graph \f(CW$G\fR.
A \*(L"vertex set\*(R" is represented by its parent vertex.
.IP "add_edge" 4
.IX Item "add_edge"
.Vb 1
\&        $G = $G->add_edge($u, $v)
.Ve
.Sp
Adds the edge defined by the vertices \f(CW$u\fR, \f(CW$v\fR, to the graph \f(CW$G\fR.
Also implicitly adds the vertices.  Returns the graph.
.IP "add_edges" 4
.IX Item "add_edges"
.Vb 1
\&        $G = $G->add_edges($u1, $v1, $u2, $v2, ...)
.Ve
.Sp
Adds the edge defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ...,
to the graph \f(CW$G\fR.  Also implicitly adds the vertices.
Returns the graph.
.IP "add_path" 4
.IX Item "add_path"
.Vb 1
\&        $G->add_path($u, $v, ...)
.Ve
.Sp
Adds the path defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ...,
to the graph \f(CW$G\fR.   Also implicitly adds the vertices.
Returns the graph.
.IP "add_cycle" 4
.IX Item "add_cycle"
.Vb 1
\&        $G = $G->add_cycle($u, $v, ...)
.Ve
.Sp
Adds the cycle defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ...,
to the graph \f(CW$G\fR.  Also implicitly adds the vertices.
Returns the graph.
.IP "neighbors" 4
.IX Item "neighbors"
.Vb 1
\&        @n = $G->neighbors($v)
.Ve
.Sp
Returns the neighbor vertices of the vertex in the graph.
(Also 'neighbours' works.)
.IP "successors" 4
.IX Item "successors"
.Vb 1
\&        @s = $G->successors($v)
.Ve
.Sp
Returns the successor vertices of the vertex in the graph.
.IP "predecessors" 4
.IX Item "predecessors"
.Vb 1
\&        @p = $G->predecessors($v)
.Ve
.Sp
Returns the predecessor vertices of the vertex in the graph.
.IP "out_edges" 4
.IX Item "out_edges"
.Vb 1
\&        @e = $G->out_edges($v)
.Ve
.Sp
Returns the edges leading out of the vertex \f(CW$v\fR in the graph \f(CW$G\fR.
In list context returns the edges as ($start_vertex, \f(CW$end_vertex\fR)
pairs.  In scalar context returns the number of the edges.
.IP "in_edges" 4
.IX Item "in_edges"
.Vb 1
\&        @e = $G->in_edges($v)
.Ve
.Sp
Returns the edges leading into the vertex \f(CW$v\fR in the graph \f(CW$G\fR.
In list context returns the edges as ($start_vertex, \f(CW$end_vertex\fR)
pairs; in scalar context returns the number of the edges.
.IP "edges" 4
.IX Item "edges"
.Vb 1
\&        @e = $G->edges($u, $v)
.Ve
.Sp
Returns the edges between the vertices \f(CW$u\fR and \f(CW$v\fR, or if \f(CW$v\fR
is undefined, the edges leading into or out of the vertex \f(CW$u\fR,
or if \f(CW$u\fR is undefined, returns all the edges, of the graph \f(CW$G\fR.
In list context returns the edges as a list of
\&\f(CW$start_vertex\fR, \f(CW$end_vertex\fR pairs; in scalar context
returns the number of the edges.
.IP "delete_edge" 4
.IX Item "delete_edge"
.Vb 1
\&        $G = $G->delete_edge($u, $v)
.Ve
.Sp
Deletes an edge defined by the vertices \f(CW$u\fR, \f(CW$v\fR from the graph \f(CW$G\fR.
Note that the edge need not actually exist.
Returns the graph.
.IP "delete_edges" 4
.IX Item "delete_edges"
.Vb 1
\&        $G = $G->delete_edges($u1, $v1, $u2, $v2, ..)
.Ve
.Sp
Deletes edges defined by the vertices \f(CW$u1\fR, \f(CW$v1\fR, ...,
from the graph \f(CW$G\fR.
Note that the edges need not actually exist.
Returns the graph.
.IP "delete_path" 4
.IX Item "delete_path"
.Vb 1
\&        $G = $G->delete_path($u, $v, ...)
.Ve
.Sp
Deletes a path defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., from the graph \f(CW$G\fR.
Note that the path need not actually exist. Returns the graph.
.IP "delete_cycle" 4
.IX Item "delete_cycle"
.Vb 1
\&        $G = $G->delete_cycle($u, $v, ...)
.Ve
.Sp
Deletes a cycle defined by the vertices \f(CW$u\fR, \f(CW$v\fR, ..., from the graph \f(CW$G\fR.
Note that the cycle need not actually exist. Returns the graph.
.IP "delete_vertex" 4
.IX Item "delete_vertex"
.Vb 1
\&        $G = $G->delete_vertex($v)
.Ve
.Sp
Deletes the vertex \f(CW$v\fR and all its edges from the graph \f(CW$G\fR.
Note that the vertex need not actually exist.
Returns the graph.
.IP "delete_vertices" 4
.IX Item "delete_vertices"
.Vb 1
\&        $G = $G->delete_vertices(@v)
.Ve
.Sp
Deletes the vertices \f(CW@v\fR and all their edges from the graph \f(CW$G\fR.
Note that the vertices need not actually exist.
Returns the graph.
.IP "in_degree" 4
.IX Item "in_degree"
.Vb 1
\&        $d = $G->in_degree($v)
.Ve
.Sp
Returns the in-degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR,
or, if \f(CW$v\fR is undefined, the total in-degree of all the
vertices of the graph, or undef if the vertex doesn't
exist in the graph.
.IP "out_degree" 4
.IX Item "out_degree"
.Vb 1
\&        $d = $G->out_degree($v)
.Ve
.Sp
Returns the out-degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR,
or, if \f(CW$v\fR is undefined, the total out-degree of all the
vertices of the graph, of undef if the vertex doesn't
exist in the graph.
.IP "degree" 4
.IX Item "degree"
.Vb 1
\&        $d = $G->degree($v)
.Ve
.Sp
Returns the degree of the vertex \f(CW$v\fR in the graph \f(CW$G\fR
or, if \f(CW$v\fR is undefined, the total degree of all the
vertices of the graph, or undef if the vertex \f(CW$v\fR
doesn't exist in the graph.
.IP "average_degree" 4
.IX Item "average_degree"
.Vb 1
\&        $d = $G->average_degree
.Ve
.Sp
Returns the average degree of the vertices of the graph \f(CW$G\fR.
.IP "is_source_vertex" 4
.IX Item "is_source_vertex"
.Vb 1
\&        $b = $G->is_source_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a source vertex of the graph \f(CW$G\fR.
.IP "is_sink_vertex" 4
.IX Item "is_sink_vertex"
.Vb 1
\&        $b = $G->is_sink_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a sink vertex of the graph \f(CW$G\fR.
.IP "is_isolated_vertex" 4
.IX Item "is_isolated_vertex"
.Vb 1
\&        $b = $G->is_isolated_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a isolated vertex of the graph \f(CW$G\fR.
.IP "is_exterior_vertex" 4
.IX Item "is_exterior_vertex"
.Vb 1
\&        $b = $G->is_exterior_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a exterior vertex of the graph \f(CW$G\fR.
.IP "is_interior_vertex" 4
.IX Item "is_interior_vertex"
.Vb 1
\&        $b = $G->is_interior_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a interior vertex of the graph \f(CW$G\fR.
.IP "is_self_loop_vertex" 4
.IX Item "is_self_loop_vertex"
.Vb 1
\&        $b = $G->is_self_loop_vertex($v)
.Ve
.Sp
Returns true if the vertex \f(CW$v\fR is a self-loop vertex of the graph \f(CW$G\fR.
.IP "source_vertices" 4
.IX Item "source_vertices"
.Vb 1
\&        @s = $G->source_vertices
.Ve
.Sp
Returns the source vertices \f(CW@s\fR of the graph \f(CW$G\fR.
.IP "sink_vertices" 4
.IX Item "sink_vertices"
.Vb 1
\&        @s = $G->sink_vertices
.Ve
.Sp
Returns the sink vertices \f(CW@s\fR of the graph \f(CW$G\fR.
.IP "isolated_vertices" 4
.IX Item "isolated_vertices"
.Vb 1
\&        @i = $G->isolated_vertices
.Ve
.Sp
Returns the isolated vertices \f(CW@i\fR of the graph \f(CW$G\fR.
.IP "exterior_vertices" 4
.IX Item "exterior_vertices"
.Vb 1
\&        @e = $G->exterior_vertices
.Ve
.Sp
Returns the exterior vertices \f(CW@e\fR of the graph \f(CW$G\fR.
.IP "interior_vertices" 4
.IX Item "interior_vertices"
.Vb 1
\&        @i = $G->interior_vertices
.Ve
.Sp
Returns the interior vertices \f(CW@i\fR of the graph \f(CW$G\fR.
.IP "self_loop_vertices" 4
.IX Item "self_loop_vertices"
.Vb 1
\&        @s = $G->self_loop_vertices
.Ve
.Sp
Returns the self-loop vertices \f(CW@s\fR of the graph \f(CW$G\fR.
.IP "density_limits" 4
.IX Item "density_limits"
.Vb 1
\&        ($sparse, $dense, $complete) = $G->density_limits
.Ve
.Sp
Returns the density limits for the number of edges
in the graph \f(CW$G\fR.  Note that reaching \f(CW$complete\fR 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.
.IP "density" 4
.IX Item "density"
.Vb 1
\&        $d = $G->density
.Ve
.Sp
Returns the density \f(CW$d\fR of the graph \f(CW$G\fR.
.IP "is_sparse" 4
.IX Item "is_sparse"
.Vb 1
\&        $d = $G->is_sparse
.Ve
.Sp
Returns true if the graph \f(CW$G\fR is sparse.
.IP "is_dense" 4
.IX Item "is_dense"
.Vb 1
\&        $d = $G->is_dense
.Ve
.Sp
Returns true if the graph \f(CW$G\fR is dense.
.IP "complete" 4
.IX Item "complete"
.Vb 1
\&        $C = $G->complete;
.Ve
.Sp
Returns a new complete graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
.IP "complement" 4
.IX Item "complement"
.Vb 1
\&        $C = $G->complement;
.Ve
.Sp
Returns a new complement graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
.IP "copy" 4
.IX Item "copy"
.Vb 1
\&        $C = $G->copy;
.Ve
.Sp
Returns a new graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
.IP "transpose" 4
.IX Item "transpose"
.Vb 1
\&        $T = $G->transpose;
.Ve
.Sp
Returns a new transpose graph \f(CW$T\fR corresponding to the graph \f(CW$G\fR.
.IP "set_attribute" 4
.IX Item "set_attribute"
.Vb 3
\&        $G->set_attribute($attribute, $value)
\&        $G->set_attribute($attribute, $v, $value)
\&        $G->set_attribute($attribute, $u, $v, $value)
.Ve
.Sp
Sets the \f(CW$attribute\fR of graph/vertex/edge to \f(CW$value\fR
but only if the vertex/edge already exists.  Returns
true if the attribute is set successfully, false if not.
.IP "get_attribute" 4
.IX Item "get_attribute"
.Vb 3
\&        $value = $G->get_attribute($attribute)
\&        $value = $G->get_attribute($attribute, $v)
\&        $value = $G->get_attribute($attribute, $u, $v)
.Ve
.Sp
Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge.
.IP "has_attribute" 4
.IX Item "has_attribute"
.Vb 3
\&        $value = $G->has_attribute($attribute)
\&        $value = $G->has_attribute($attribute, $v)
\&        $value = $G->has_attribute($attribute, $u, $v)
.Ve
.Sp
Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge.
.IP "get_attributes" 4
.IX Item "get_attributes"
.Vb 3
\&        %attributes = $G->get_attributes()
\&        %attributes = $G->get_attributes($v)
\&        %attributes = $G->get_attributes($u, $v)
.Ve
.Sp
Returns as a hash all the attribute names and values
of graph/vertex/edge.
.IP "delete_attribute" 4
.IX Item "delete_attribute"
.Vb 3
\&        $G->delete_attribute($attribute)
\&        $G->delete_attribute($attribute, $v)
\&        $G->delete_attribute($attribute, $u, $v)
.Ve
.Sp
Deletes the \f(CW$attribute\fR of graph/vertex/edge.
.IP "delete_attributes" 4
.IX Item "delete_attributes"
.Vb 3
\&        $G->delete_attributes()
\&        $G->delete_attributes($v)
\&        $G->delete_attributes($u, $v)
.Ve
.Sp
Deletes all the attributes of graph/vertex/edge.
.IP "add_weighted_edge" 4
.IX Item "add_weighted_edge"
.Vb 1
\&        $G->add_weighted_edge($u, $w, $v, $a)
.Ve
.Sp
Adds in the graph \f(CW$G\fR an edge from vertex \f(CW$u\fR to vertex \f(CW$v\fR
and the edge attribute 'weight' set to \f(CW$w\fR.
.IP "add_weighted_edges" 4
.IX Item "add_weighted_edges"
.Vb 1
\&        $G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)
.Ve
.Sp
Adds in the graph \f(CW$G\fR the weighted edges.
.IP "add_weighted_path" 4
.IX Item "add_weighted_path"
.Vb 1
\&        $G->add_weighted_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn)
.Ve
.Sp
Adds in the graph \f(CW$G\fR the n edges defined by the path \f(CW$v1\fR ... \f(CW$vn\fR
with the n\-1 'weight' attributes \f(CW$w1\fR ... \f(CW$wnm1\fR
.IP "MST_Kruskal" 4
.IX Item "MST_Kruskal"
.Vb 1
\&        $MST = $G->MST_Kruskal;
.Ve
.Sp
Returns Kruskal's Minimum Spanning Tree (as a graph) of
the graph \f(CW$G\fR based on the 'weight' attributes of the edges.
(Needs the \->\fIvertex_set()\fR method.)
.IP "edge_classify" 4
.IX Item "edge_classify"
.Vb 1
\&        @C = $G->edge_classify(%param)
.Ve
.Sp
Returns the edge classification as a list where each element
is a triplet [$u, \f(CW$v\fR, \f(CW$class\fR] the \f(CW$u\fR, \f(CW$v\fR being the vertices
of an edge and \f(CW$class\fR being the class.  The \f(CW%param\fR can be
used to control the search.
.IP "toposort" 4
.IX Item "toposort"
.Vb 1
\&        @toposort = $G->toposort
.Ve
.Sp
Returns the vertices of the graph \f(CW$G\fR sorted topologically.
.IP "strongly_connected_components" 4
.IX Item "strongly_connected_components"
.Vb 1
\&        @S = $G->strongly_connected_components
.Ve
.Sp
Returns the strongly connected components \f(CW@S\fR of the graph \f(CW$G\fR
as a list of anonymous lists of vertices, each anonymous list
containing the vertices belonging to one strongly connected
component.
.IP "strongly_connected_graph" 4
.IX Item "strongly_connected_graph"
.Vb 1
\&        $T = $G->strongly_connected_graph
.Ve
.Sp
Returns the strongly connected graph \f(CW$T\fR of the graph \f(CW$G\fR.
The names of the strongly connected components are
formed from their constituent vertices by concatenating
their names by '+'\-characters: \*(L"a\*(R" and \*(L"b\*(R" \-\-> \*(L"a+b\*(R".
.IP "APSP_Floyd_Warshall" 4
.IX Item "APSP_Floyd_Warshall"
.Vb 1
\&        $APSP = $G->APSP_Floyd_Warshall
.Ve
.Sp
Returns the All-pairs Shortest Paths graph of the graph \f(CW$G\fR
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 \*(L"weight\*(R" and \*(L"path\*(R"; for the length of
the shortest path and for the path (an anonymous list) itself.
.IP "TransitiveClosure_Floyd_Warshall" 4
.IX Item "TransitiveClosure_Floyd_Warshall"
.Vb 1
\&        $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall
.Ve
.Sp
Returns the Transitive Closure graph of the graph \f(CW$G\fR 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.
.IP "articulation points" 4
.IX Item "articulation points"
.Vb 1
\&        @A = $G->articulation_points(%param)
.Ve
.Sp
Returns the articulation points (vertices) \f(CW@A\fR of the graph \f(CW$G\fR.
The \f(CW%param\fR can be used to control the search.
.IP "is_biconnected" 4
.IX Item "is_biconnected"
.Vb 1
\&        $b = $G->is_biconnected
.Ve
.Sp
Returns true is the graph \f(CW$G\fR is biconnected
(has no articulation points), false otherwise.
.IP "largest_out_degree" 4
.IX Item "largest_out_degree"
.Vb 1
\&        $v = $G->largest_out_degree( @V )
.Ve
.Sp
Selects the vertex \f(CW$v\fR from the vertices \f(CW@V\fR having
the largest out degree in the graph \f(CW$G\fR.
.IP "MST_Prim" 4
.IX Item "MST_Prim"
.Vb 1
\&        $MST = $G->MST_Prim($u)
.Ve
.Sp
Returns Prim's Minimum Spanning Tree (as a graph) of
the graph \f(CW$G\fR based on the 'weight' attributes of the edges.
The optional start vertex is \f(CW$u\fR, if none is given, a hopefully
good one (a vertex with a large out degree) is chosen.
.IP "SSSP_Dijkstra" 4
.IX Item "SSSP_Dijkstra"
.Vb 1
\&        $SSSP = $G->SSSP_Dijkstra($s)
.Ve
.Sp
Returns the Single-source Shortest Paths (as a graph)
of the graph \f(CW$G\fR starting from the vertex \f(CW$s\fR using Dijktra's
\&\s-1SSSP\s0 algorithm.
.IP "SSSP_Bellman_Ford" 4
.IX Item "SSSP_Bellman_Ford"
.Vb 1
\&        $SSSP = $G->SSSP_Bellman_Ford($s)
.Ve
.Sp
Returns the Single-source Shortest Paths (as a graph)
of the graph \f(CW$G\fR starting from the vertex \f(CW$s\fR using Bellman-Ford
\&\s-1SSSP\s0 algorithm.  If there are one or more negatively weighted
cycles, returns undef.
.IP "\s-1SSSP_DAG\s0" 4
.IX Item "SSSP_DAG"
.Vb 1
\&        $SSSP = $G->SSSP_DAG($s)
.Ve
.Sp
Returns the Single-source Shortest Paths (as a graph)
of the \s-1DAG\s0 \f(CW$G\fR starting from vertex \f(CW$s\fR.
.IP "add_capacity_edge" 4
.IX Item "add_capacity_edge"
.Vb 1
\&        $G->add_capacity_edge($u, $w, $v, $a)
.Ve
.Sp
Adds in the graph \f(CW$G\fR an edge from vertex \f(CW$u\fR to vertex \f(CW$v\fR
and the edge attribute 'capacity' set to \f(CW$w\fR.
.IP "add_capacity_edges" 4
.IX Item "add_capacity_edges"
.Vb 1
\&        $G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)
.Ve
.Sp
Adds in the graph \f(CW$G\fR the capacity edges.
.IP "add_capacity_path" 4
.IX Item "add_capacity_path"
.Vb 1
\&        $G->add_capacity_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn)
.Ve
.Sp
Adds in the graph \f(CW$G\fR the n edges defined by the path \f(CW$v1\fR ... \f(CW$vn\fR
with the n\-1 'capacity' attributes \f(CW$w1\fR ... \f(CW$wnm1\fR
.IP "Flow_Ford_Fulkerson" 4
.IX Item "Flow_Ford_Fulkerson"
.Vb 1
\&        $F = $G->Flow_Ford_Fulkerson($S)
.Ve
.Sp
Returns the (maximal) flow network of the flow network \f(CW$G\fR,
parametrized by the state \f(CW$S\fR.  The \f(CW$G\fR must have 'capacity'
attributes on its edges.  \f(CW$S\fR\->{ source } must contain the
source vertex and \f(CW$S\fR\->{ sink } the sink vertex, and
most importantly \f(CW$S\fR\->{ next_augmenting_path } must contain
an anonymous subroutine which takes \f(CW$F\fR and \f(CW$S\fR as arguments
and returns the next potential augmenting path.
Flow_Ford_Fulkerson will do the augmenting.
The result graph \f(CW$F\fR will have 'flow' and (residual) 'capacity'
attributes on its edges.
.IP "Flow_Edmonds_Karp" 4
.IX Item "Flow_Edmonds_Karp"
.Vb 1
\&        $F = $G->Flow_Edmonds_Karp($source, $sink)
.Ve
.Sp
Return the maximal flow network of the graph \f(CW$G\fR built
using the Edmonds-Karp version of Ford\-Fulkerson.
The input graph \f(CW$G\fR must have 'capacity' attributes on
its edges; resulting flow graph will have 'capacity' and 'flow'
attributes on its edges.
.IP "eq" 4
.IX Item "eq"
.Vb 1
\&        $G->eq($H)
.Ve
.Sp
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.)
.SH "COPYRIGHT"
.IX Header "COPYRIGHT"
Copyright 1999, O'Reilly & Associates.
.PP
This code is distributed under the same copyright terms as Perl itself.