.\" Automatically generated by Pod::Man v1.34, Pod::Parser v1.13
.\" ========================================================================
.de Sh \" Subsection heading
.de Sp \" Vertical space (when we can't use .PP)
.de Vb \" Begin verbatim text
.de Ve \" End verbatim text
.\" 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<>.
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
. 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
.\" 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.
. tm Index:\\$1\t\\n%\t"\\$2"
.\" For nroff, turn off justification. Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.\" 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
. ds #H ((1u-(\\\\n(.fu%2u))*.13m)
. \" simple accents for nroff and troff
. 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 \
.\" ========================================================================
.IX Title "Graph::Base 3"
.TH Graph::Base 3 "2004-04-04" "perl v5.8.0" "User Contributed Perl Documentation"
Graph::Base \- graph base class
\& use Graph::Undirected;
\& $d2 = new Graph::Directed;
\& $u = new Graph::Undirected;
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.
Returns a new graph \f(CW$G\fR with the optional vertices \f(CW@V\fR.
\& $G = $G->add_vertices(@v)
Adds the vertices to the graph \f(CW$G\fR, returns the graph.
\& $G = $G->add_vertex($v)
Adds the vertex \f(CW$v\fR to the graph \f(CW$G\fR, returns the graph.
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.
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.
\& $b = $G->has_vertex($v)
Returns true if the vertex \f(CW$v\fR exists in
the graph \f(CW$G\fR and false if it doesn't.
\& $v = $G->has_vertex($v)
Returns the vertex \f(CW$v\fR if the vertex exists in the graph \f(CW$G\fR
Set the directedness of the graph \f(CW$G\fR to \f(CW$d\fR or return the
current directedness. Directedness defaults to true.
\& $b = $G->undirected($d)
Set the undirectedness of the graph \f(CW$G\fR to \f(CW$u\fR or return the
current undirectedness. Undirectedness defaults to false.
\& $b = $G->has_edge($u, $v)
Return true if the graph \f(CW$G\fR has the edge between
the vertices \f(CW$u\fR, \f(CW$v\fR.
\& $G->has_edges($u1, $v1, $u2, $v2, ...)
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.
\& $G->has_path($u, $v, ...)
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.
\& $G->has_cycle($u, $v, ...)
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.
\& $s = $G->vertex_set($v)
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.
\& $G = $G->add_edge($u, $v)
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.
\& $G = $G->add_edges($u1, $v1, $u2, $v2, ...)
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.
\& $G->add_path($u, $v, ...)
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.
\& $G = $G->add_cycle($u, $v, ...)
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.
\& @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 \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.
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.
\& @e = $G->edges($u, $v)
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.
\& $G = $G->delete_edge($u, $v)
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.
\& $G = $G->delete_edges($u1, $v1, $u2, $v2, ..)
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.
\& $G = $G->delete_path($u, $v, ...)
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.
\& $G = $G->delete_cycle($u, $v, ...)
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.
\& $G = $G->delete_vertex($v)
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.
.IX Item "delete_vertices"
\& $G = $G->delete_vertices(@v)
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.
\& $d = $G->in_degree($v)
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
\& $d = $G->out_degree($v)
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
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.
.IX Item "average_degree"
\& $d = $G->average_degree
Returns the average degree of the vertices of the graph \f(CW$G\fR.
.IX Item "is_source_vertex"
\& $b = $G->is_source_vertex($v)
Returns true if the vertex \f(CW$v\fR is a source vertex of the graph \f(CW$G\fR.
.IX Item "is_sink_vertex"
\& $b = $G->is_sink_vertex($v)
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"
\& $b = $G->is_isolated_vertex($v)
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"
\& $b = $G->is_exterior_vertex($v)
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"
\& $b = $G->is_interior_vertex($v)
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"
\& $b = $G->is_self_loop_vertex($v)
Returns true if the vertex \f(CW$v\fR is a self-loop vertex of the graph \f(CW$G\fR.
.IX Item "source_vertices"
\& @s = $G->source_vertices
Returns the source vertices \f(CW@s\fR of the graph \f(CW$G\fR.
\& @s = $G->sink_vertices
Returns the sink vertices \f(CW@s\fR of the graph \f(CW$G\fR.
.IP "isolated_vertices" 4
.IX Item "isolated_vertices"
\& @i = $G->isolated_vertices
Returns the isolated vertices \f(CW@i\fR of the graph \f(CW$G\fR.
.IP "exterior_vertices" 4
.IX Item "exterior_vertices"
\& @e = $G->exterior_vertices
Returns the exterior vertices \f(CW@e\fR of the graph \f(CW$G\fR.
.IP "interior_vertices" 4
.IX Item "interior_vertices"
\& @i = $G->interior_vertices
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"
\& @s = $G->self_loop_vertices
Returns the self-loop vertices \f(CW@s\fR of the graph \f(CW$G\fR.
.IX Item "density_limits"
\& ($sparse, $dense, $complete) = $G->density_limits
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
Returns the density \f(CW$d\fR of the graph \f(CW$G\fR.
Returns true if the graph \f(CW$G\fR is sparse.
Returns true if the graph \f(CW$G\fR is dense.
Returns a new complete graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
Returns a new complement graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
Returns a new graph \f(CW$C\fR corresponding to the graph \f(CW$G\fR.
Returns a new transpose graph \f(CW$T\fR corresponding to the graph \f(CW$G\fR.
\& $G->set_attribute($attribute, $value)
\& $G->set_attribute($attribute, $v, $value)
\& $G->set_attribute($attribute, $u, $v, $value)
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.
\& $value = $G->get_attribute($attribute)
\& $value = $G->get_attribute($attribute, $v)
\& $value = $G->get_attribute($attribute, $u, $v)
Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge.
\& $value = $G->has_attribute($attribute)
\& $value = $G->has_attribute($attribute, $v)
\& $value = $G->has_attribute($attribute, $u, $v)
Returns the \f(CW$value\fR of \f(CW$attribute\fR of graph/vertex/edge.
.IX Item "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
.IX Item "delete_attribute"
\& $G->delete_attribute($attribute)
\& $G->delete_attribute($attribute, $v)
\& $G->delete_attribute($attribute, $u, $v)
Deletes the \f(CW$attribute\fR of graph/vertex/edge.
.IP "delete_attributes" 4
.IX Item "delete_attributes"
\& $G->delete_attributes()
\& $G->delete_attributes($v)
\& $G->delete_attributes($u, $v)
Deletes all the attributes of graph/vertex/edge.
.IP "add_weighted_edge" 4
.IX Item "add_weighted_edge"
\& $G->add_weighted_edge($u, $w, $v, $a)
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"
\& $G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)
Adds in the graph \f(CW$G\fR the weighted edges.
.IP "add_weighted_path" 4
.IX Item "add_weighted_path"
\& $G->add_weighted_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn)
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
\& $MST = $G->MST_Kruskal;
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.)
\& @C = $G->edge_classify(%param)
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.
\& @toposort = $G->toposort
Returns the vertices of the graph \f(CW$G\fR sorted topologically.
.IP "strongly_connected_components" 4
.IX Item "strongly_connected_components"
\& @S = $G->strongly_connected_components
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
.IP "strongly_connected_graph" 4
.IX Item "strongly_connected_graph"
\& $T = $G->strongly_connected_graph
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"
\& $APSP = $G->APSP_Floyd_Warshall
Returns the All-pairs Shortest Paths graph of the graph \f(CW$G\fR
computed using the Floyd-Warshall algorithm and the attribute
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"
\& $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall
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"
\& @A = $G->articulation_points(%param)
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.
.IX Item "is_biconnected"
\& $b = $G->is_biconnected
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"
\& $v = $G->largest_out_degree( @V )
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.
\& $MST = $G->MST_Prim($u)
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.
\& $SSSP = $G->SSSP_Dijkstra($s)
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
.IP "SSSP_Bellman_Ford" 4
.IX Item "SSSP_Bellman_Ford"
\& $SSSP = $G->SSSP_Bellman_Ford($s)
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
\& $SSSP = $G->SSSP_DAG($s)
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"
\& $G->add_capacity_edge($u, $w, $v, $a)
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"
\& $G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...)
Adds in the graph \f(CW$G\fR the capacity edges.
.IP "add_capacity_path" 4
.IX Item "add_capacity_path"
\& $G->add_capacity_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn)
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"
\& $F = $G->Flow_Ford_Fulkerson($S)
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'
.IP "Flow_Edmonds_Karp" 4
.IX Item "Flow_Edmonds_Karp"
\& $F = $G->Flow_Edmonds_Karp($source, $sink)
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'
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 1999, O'Reilly & Associates.
This code is distributed under the same copyright terms as Perl itself.
projects / OpenSPARC-T2-DV / blob