Graph::Base(3)

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.

        $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
Copyright 1999, O'Reilly & Associates.

This code is distributed under the same copyright terms as Perl itself.