--- name: "Graph::Base" section: "3pm" platform: "linux" package: "libgraph-perl" version: "0.20102-1" release: "Debian 3.1 (Sarge)" platforms: ["linux"] url: "https://new.carta.tech/Graph::Base" --- # Graph::Base(3pm) graph base class ## 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. - 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`. - is\_sink\_vertex ``` $b = $G->is_sink_vertex($v) ``` Returns true if the vertex `$v` is a sink vertex of the graph `$G`. - 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`. - 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.