|
Graph::Base - graph base class |
Graph::Base - graph base class
use Graph::Directed;
use Graph::Undirected;
$d1 = new Graph;
$d2 = new Graph::Directed;
$u = new Graph::Undirected;
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 1999, O'Reilly & Associates.
This code is distributed under the same copyright terms as Perl itself.
|
Graph::Base - graph base class |