graph


SYNOPSIS
               use Graph;
               my $g0 = Graph->new;             # A directed graph.

               use Graph::Directed;
               my $g1 = Graph::Directed->new;   # A directed graph.

               use Graph::Undirected;
               my $g2 = Graph::Undirected->new; # An undirected graph.

               $g->add_edge(...);
               $g->has_edge(...)
               $g->delete_edge(...);

               $g->add_vertex(...);
               $g->has_vertex(...);
               $g->delete_vertex(...);

               $g->vertices(...)
               $g->edges(...)

               # And many, many more, see below.

UNSUPPORTED
       Unfortunately, as of release 0.95, this module is unsupported, and will
       no more be maintained.  Sorry about that.

DESCRIPTION
   Non-Description
       This module is not for drawing or rendering any sort of graphics or
       images, business, visualization, or otherwise.

   Description
       Instead, this module is for creating abstract data structures called
       graphs, and for doing various operations on those.

   Perl 5.6.0 minimum
       The implementation depends on a Perl feature called "weak references"
       and Perl 5.6.0 was the first to have those.

   Constructors
       new Create an empty graph.

       Graph->new(%options)
           The options are a hash with option names as the hash keys and the
           option values as the hash values.

           The following options are available:

           directed
                   A boolean option telling that a directed graph should be
                   created.  Often somewhat redundant because a directed graph
                   is the default for the Graph class or one could simply use
                   edges going both ways, in this module directed graphs and
                   undirected graphs are two different things that often
                   behave differently.

                   You can test the directness of a graph with
                   $g->is_directed() and $g->is_undirected().

           refvertexed
           refvertexed_stringified
                   If you want to use references (including Perl objects) as
                   vertices, use "refvertexed".

                   Note that using "refvertexed" means that internally the
                   memory address of the reference (for example, a Perl
                   object) is used as the "identifier" of the vertex, not the
                   stringified form of the reference, even if you have defined
                   your own stringification using "overload".

                   This avoids the problem of the stringified references
                   potentially being identical (because they are identical in
                   value, for example) even if the references are different.
                   If you really want to use references and their stringified
                   forms as the identities, use the "refvertexed_stringified".
                   But please do not stringify different objects to the same
                   stringified value.

           unionfind
                   If the graph is undirected, you can specify the "unionfind"
                   parameter to use the so-called union-find scheme to speed
                   up the computation of connected components of the graph
                   (see "is_connected", "connected_components",
                   "connected_component_by_vertex",
                   "connected_component_by_index", and
                   "same_connected_components").  If "unionfind" is used,
                   adding edges (and vertices) becomes slower, but
                   connectedness queries become faster.  You must not delete
                   egdes or vertices of an unionfind graph, only add them.
                   You can test a graph for "union-findness" with

           has_union_find
                   Returns true if the graph was created with a true
                   "unionfind" parameter.

           vertices
                   An array reference of vertices to add.

           edges   An array reference of array references of edge vertices to
                   add.

       copy
       copy_graph
               my $c = $g->copy_graph;

           Create a shallow copy of the structure (vertices and edges) of the
               my $c = $g->deep_copy_graph;

           Create a deep copy of the graph (vertices, edges, and attributes)
           of the graph.  If you want a shallow copy that does not include
           attributes, see "copy".

           Note that copying code references only works with Perls 5.8 or
           later, and even then only if B::Deparse can reconstruct your code.
           This functionality uses either Storable or Data::Dumper behind the
           scenes, depending on which is available (Storable is preferred).

       undirected_copy
       undirected_copy_graph
               my $c = $g->undirected_copy_graph;

           Create an undirected shallow copy (vertices and edges) of the
           directed graph so that for any directed edge (u, v) there is an
           undirected edge (u, v).

       undirected_copy_clear_cache
               @path = $g->undirected_copy_clear_cache;

           See "Clearing cached results".

       directed_copy
       directed_copy_graph
               my $c = $g->directed_copy_graph;

           Create a directed shallow copy (vertices and edges) of the
           undirected graph so that for any undirected edge (u, v) there are
           two directed edges (u, v) and (v, u).

       transpose
       transpose_graph
               my $t = $g->transpose_graph;

           Create a directed shallow transposed copy (vertices and edges) of
           the directed graph so that for any directed edge (u, v) there is a
           directed edge (v, u).

           You can also transpose a single edge with

           transpose_edge
                       $g->transpose_edge($u, $v)

       complete_graph
       complete
               my $c = $g->complete_graph;

           Create a complete graph that has the same vertices as the original
           graph.  A complete graph has an edge between every pair of
           vertices.

       complement_graph

           Add the vertex to the graph.  Returns the graph.

           By default idempotent, but a graph can be created countvertexed.

           A vertex is also known as a node.

           Adding "undef" as vertex is not allowed.

           Note that unless you have isolated vertices (or countvertexed
           vertices), you do not need to explicitly use "add_vertex" since
           "add_edge" will implicitly add its vertices.

       add_edge
               $g->add_edge($u, $v)

           Add the edge to the graph.  Implicitly first adds the vertices if
           the graph does not have them.  Returns the graph.

           By default idempotent, but a graph can be created countedged.

           An edge is also known as an arc.

       has_vertex
               $g->has_vertex($v)

           Return true if the vertex exists in the graph, false otherwise.

       has_edge
               $g->has_edge($u, $v)

           Return true if the edge exists in the graph, false otherwise.

       delete_vertex
               $g->delete_vertex($v)

           Delete the vertex from the graph.  Returns the graph, even if the
           vertex did not exist in the graph.

           If the graph has been created multivertexed or countvertexed and a
           vertex has been added multiple times, the vertex will require at
           least an equal number of deletions to become completely deleted.

       delete_vertices
               $g->delete_vertices($v1, $v2, ...)

           Delete the vertices from the graph.  Returns the graph.

           If the graph has been created multivertexed or countvertexed and a
           vertex has been added multiple times, the vertex will require at
           least an equal number of deletions to become completely deleteted.

       delete_edge
               $g->delete_edge($u, $v)

           If the graph has been created multivertexed or countedged and an
           edge has been added multiple times, the edge will require at least
           an equal number of deletions to become completely deleted.

   Displaying
       Graphs have stringification overload, so you can do things like

           print "The graph is $g\n"

       One-way (directed, unidirected) edges are shown as '-', two-way
       (undirected, bidirected) edges are shown as '='.  If you want to, you
       can call the stringification via the method

       stringify

   Comparing
       Testing for equality can be done either by the overloaded "eq" operator

           $g eq "a-b,a-c,d"

       or by the method

       eq
               $g->eq("a-b,a-c,d")

       The equality testing compares the stringified forms, and therefore it
       assumes total equality, not isomorphism: all the vertices must be named
       the same, and they must have identical edges between them.

       For unequality there are correspondingly the overloaded "ne" operator
       and the method

       ne
               $g->ne("a-b,a-c,d")

       See also "Isomorphism".

   Paths and Cycles
       Paths and cycles are simple extensions of edges: paths are edges
       starting from where the previous edge ended, and cycles are paths
       returning back to the start vertex of the first edge.

       add_path
              $g->add_path($a, $b, $c, ..., $x, $y, $z)

           Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
           Returns the graph.

       has_path
              $g->has_path($a, $b, $c, ..., $x, $y, $z)

           Return true if the graph has all the edges $a-$b, $b-$c, ...,
           $x-$y, $y-$z, false otherwise.

       has_cycle
              $g->has_cycle($a, $b, $c, ..., $x, $y, $z)

           Return true if the graph has all the edges $a-$b, $b-$c, ...,
           $x-$y, $y-$z, and $z-$a, false otherwise.

           NOTE: This does not detect cycles, see "has_a_cycle" and
           "find_a_cycle".

       delete_cycle
              $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)

           Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and
           $z-$a (regardless of whether they exist or not).  Returns the
           graph.

       has_a_cycle
              $g->has_a_cycle

           Returns true if the graph has a cycle, false if not.

       find_a_cycle
              $g->find_a_cycle

           Returns a cycle if the graph has one (as a list of vertices), an
           empty list if no cycle can be found.

           Note that this just returns the vertices of a cycle: not any
           particular cycle, just the first one it finds.  A repeated call
           might find the same cycle, or it might find a different one, and
           you cannot call this repeatedly to find all the cycles.

   Graph Types
       is_simple_graph
               $g->is_simple_graph

           Return true if the graph has no multiedges, false otherwise.

       is_pseudo_graph
               $g->is_pseudo_graph

           Return true if the graph has any multiedges or any self-loops,
           false otherwise.

       is_multi_graph
               $g->is_multi_graph

           Return true if the graph has any multiedges but no self-loops,
           false otherwise.

       is_directed_acyclic_graph
       is_dag
               $g->is_directed_acyclic_graph

       is_acyclic
           Return true if the graph is acyclic (does not contain any cycles).

       To find a cycle, use "find_a_cycle".

   Transitivity
       is_transitive
               $g->is_transitive

           Return true if the graph is transitive, false otherwise.

       TransitiveClosure_Floyd_Warshall
       transitive_closure
               $tcg = $g->TransitiveClosure_Floyd_Warshall

           Return the transitive closure graph of the graph.

       You can query the reachability from $u to $v with

       is_reachable
               $tcg->is_reachable($u, $v)

       See Graph::TransitiveClosure for more information about creating and
       querying transitive closures.

       With

       transitive_closure_matrix
              $tcm = $g->transitive_closure_matrix;

       you can (create if not existing and) query the transitive closure
       matrix that underlies the transitive closure graph.  See
       Graph::TransitiveClosure::Matrix for more information.

   Mutators
       add_vertices
               $g->add_vertices('d', 'e', 'f')

           Add zero or more vertices to the graph.  Returns the graph.

       add_edges
               $g->add_edges(['d', 'e'], ['f', 'g'])
               $g->add_edges(qw(d e f g));

           Add zero or more edges to the graph.  The edges are specified as a
           list of array references, or as a list of vertices where the even
           (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
           3rd, 5th, ...) are the corresponding end vertices.  Returns the
           graph.

   Accessors
       is_directed
       directed
               $g->is_directed()

       is_refvertexed_stringified
       refvertexed
       refvertexed_stringified
           Return true if the graph can handle references (including Perl
           objects) as vertices.

       vertices
               my $V = $g->vertices
               my @V = $g->vertices

           In scalar context, return the number of vertices in the graph.  In
           list context, return the vertices, in no particular order.

       has_vertices
               $g->has_vertices()

           Return true if the graph has any vertices, false otherwise.

       edges
               my $E = $g->edges
               my @E = $g->edges

           In scalar context, return the number of edges in the graph.  In
           list context, return the edges, in no particular order.  The edges
           are returned as anonymous arrays listing the vertices.

       has_edges
               $g->has_edges()

           Return true if the graph has any edges, false otherwise.

       is_connected
               $g->is_connected

           For an undirected graph, return true is the graph is connected,
           false otherwise.  Being connected means that from every vertex it
           is possible to reach every other vertex.

           If the graph has been created with a true "unionfind" parameter,
           the time complexity is (essentially) O(V), otherwise O(V log V).

           See also "connected_components", "connected_component_by_index",
           "connected_component_by_vertex", and "same_connected_components",
           and "biconnectivity".

           For directed graphs, see "is_strongly_connected" and
           "is_weakly_connected".

       connected_components
               @cc = $g->connected_components()

           For an undirected graph, returns the vertices of the connected
           components of the graph as a list of anonymous arrays.  The
           ordering of the anonymous arrays or the ordering of the vertices

           If the graph has been created with a true "unionfind" parameter,
           the time complexity is (essentially) O(1), otherwise O(V log V).

           See also "biconnectivity".

           For directed graphs, see "strongly_connected_component_by_vertex"
           and "weakly_connected_component_by_vertex".

       connected_component_by_index
               @v = $g->connected_component_by_index($i)

           For an undirected graph, return the vertices of the ith connected
           component, the indexing starting from zero.  The order of vertices
           is undefined, while the order of the connected components is same
           as from connected_components().

           For the inverse, see "connected_component_by_vertex".

           For directed graphs, see "strongly_connected_component_by_index"
           and "weakly_connected_component_by_index".

       same_connected_components
               $g->same_connected_components($u, $v, ...)

           For an undirected graph, return true if the vertices are in the
           same connected component.

           If the graph has been created with a true "unionfind" parameter,
           the time complexity is (essentially) O(1), otherwise O(V log V).

           For directed graphs, see "same_strongly_connected_components" and
           "same_weakly_connected_components".

       connected_graph
               $cg = $g->connected_graph

           For an undirected graph, return its connected graph.

       connectivity_clear_cache
               $g->connectivity_clear_cache

           See "Clearing cached results".

           See "Connected Graphs and Their Components" for further discussion.

       biconnectivity
               my ($ap, $bc, $br) = $g->biconnectivity

           For an undirected graph, return the various biconnectivity
           components of the graph: the articulation points (cut vertices),
           biconnected components, and bridges.

           Note: currently only handles connected graphs.

           Note: more precisely, this would be called is_edge_biconnected,
           since there is a more general concept of being k-connected.

       is_edge_separable
              $g->is_edge_separable

           For an undirected graph, return true if the graph is edge-separable
           (if it has bridges).

           Note: more precisely, this would be called is_edge_biseparable,
           since there is a more general concept of being k-connected.

       articulation_points
       cut_vertices
              $g->articulation_points

           For an undirected graph, return the articulation points (cut
           vertices) of the graph as a list of vertices.  The order is
           undefined.

       biconnected_components
              $g->biconnected_components

           For an undirected graph, return the biconnected components of the
           graph as a list of anonymous arrays of vertices in the components.
           The ordering of the anonymous arrays or the ordering of the
           vertices inside the anonymous arrays (the components) is undefined.
           Also note that one vertex can belong to more than one biconnected
           component.

       biconnected_component_by_vertex
              $i = $g->biconnected_component_by_index($v)

           For an undirected graph, return the indices identifying the
           biconnected components the vertex belongs to, the indexing starting
           from zero.  The order of of the components is undefined.

           For the inverse, see "connected_component_by_index".

           For directed graphs, see "strongly_connected_component_by_index"
           and "weakly_connected_component_by_index".

       biconnected_component_by_index
              @v = $g->biconnected_component_by_index($i)

           For an undirected graph, return the vertices in the ith biconnected
           component of the graph as an anonymous arrays of vertices in the
           component.  The ordering of the vertices within a component is
           undefined.  Also note that one vertex can belong to more than one
           biconnected component.

       same_biconnected_components
               $g->same_biconnected_components($u, $v, ...)

              $g->bridges

           For an undirected graph, return the bridges of the graph as a list
           of anonymous arrays of vertices in the bridges.  The order of
           bridges and the order of vertices in them is undefined.

       biconnectivity_clear_cache
               $g->biconnectivity_clear_cache

           See "Clearing cached results".

       strongly_connected
       is_strongly_connected
               $g->is_strongly_connected

           For a directed graph, return true is the directed graph is strongly
           connected, false if not.

           See also "is_weakly_connected".

           For undirected graphs, see "is_connected", or "is_biconnected".

       strongly_connected_component_by_vertex
               $i = $g->strongly_connected_component_by_vertex($v)

           For a directed graph, return an index identifying the strongly
           connected component the vertex belongs to, the indexing starting
           from zero.

           For the inverse, see "strongly_connected_component_by_index".

           See also "weakly_connected_component_by_vertex".

           For undirected graphs, see "connected_components" or
           "biconnected_components".

       strongly_connected_component_by_index
               @v = $g->strongly_connected_component_by_index($i)

           For a directed graph, return the vertices of the ith connected
           component, the indexing starting from zero.  The order of vertices
           within a component is undefined, while the order of the connected
           components is the as from strongly_connected_components().

           For the inverse, see "strongly_connected_component_by_vertex".

           For undirected graphs, see "weakly_connected_component_by_index".

       same_strongly_connected_components
               $g->same_strongly_connected_components($u, $v, ...)

           For a directed graph, return true if the vertices are in the same
           strongly connected component.

               $g->is_weakly_connected

           For a directed graph, return true is the directed graph is weakly
           connected, false if not.

           Weakly connected graph is also known as semiconnected graph.

           See also "is_strongly_connected".

           For undirected graphs, see "is_connected" or "is_biconnected".

       weakly_connected_components
               @wcc = $g->weakly_connected_components()

           For a directed graph, returns the vertices of the weakly connected
           components of the graph as a list of anonymous arrays.  The
           ordering of the anonymous arrays or the ordering of the vertices
           inside the anonymous arrays (the components) is undefined.

           See also "strongly_connected_components".

           For undirected graphs, see "connected_components" or
           "biconnected_components".

       weakly_connected_component_by_vertex
               $i = $g->weakly_connected_component_by_vertex($v)

           For a directed graph, return an index identifying the weakly
           connected component the vertex belongs to, the indexing starting
           from zero.

           For the inverse, see "weakly_connected_component_by_index".

           For undirected graphs, see "connected_component_by_vertex" and
           "biconnected_component_by_vertex".

       weakly_connected_component_by_index
               @v = $g->weakly_connected_component_by_index($i)

           For a directed graph, return the vertices of the ith weakly
           connected component, the indexing starting zero.  The order of
           vertices within a component is undefined, while the order of the
           weakly connected components is same as from
           weakly_connected_components().

           For the inverse, see "weakly_connected_component_by_vertex".

           For undirected graphs, see connected_component_by_index and
           biconnected_component_by_index.

       same_weakly_connected_components
               $g->same_weakly_connected_components($u, $v, ...)

           Return true if the vertices are in the same weakly connected

           For a directed graph, return the strongly connected components as a
           list of anonymous arrays.  The elements in the anonymous arrays are
           the vertices belonging to the strongly connected component; both
           the elements and the components are in no particular order.

           Note that strongly connected components can have single-element
           components even without self-loops: if a vertex is any of isolated,
           sink, or a source, the vertex is alone in its own strong component.

           See also "weakly_connected_components".

           For undirected graphs, see "connected_components", or see
           "biconnected_components".

       strongly_connected_graph
              my $scg = $g->strongly_connected_graph;

           See "Connected Graphs and Their Components" for further discussion.

           Strongly connected graphs are also known as kernel graphs.

           See also "weakly_connected_graph".

           For undirected graphs, see "connected_graph", or
           "biconnected_graph".

       is_sink_vertex
               $g->is_sink_vertex($v)

           Return true if the vertex $v is a sink vertex, false if not.  A
           sink vertex is defined as a vertex with predecessors but no
           successors: this definition means that isolated vertices are not
           sink vertices.  If you want also isolated vertices, use
           is_successorless_vertex().

       is_source_vertex
               $g->is_source_vertex($v)

           Return true if the vertex $v is a source vertex, false if not.  A
           source vertex is defined as a vertex with successors but no
           predecessors: the definition means that isolated vertices are not
           source vertices.  If you want also isolated vertices, use
           is_predecessorless_vertex().

       is_successorless_vertex
               $g->is_successorless_vertex($v)

           Return true if the vertex $v has no succcessors (no edges leaving
           the vertex), false if it has.

           Isolated vertices will return true: if you do not want this, use
           is_sink_vertex().

           is_source_vertex().

       is_predecessorful_vertex
               $g->is_predecessorful_vertex($v)

           Return true if the vertex $v has predecessors, false if not.

       is_isolated_vertex
               $g->is_isolated_vertex($v)

           Return true if the vertex $v is an isolated vertex: no successors
           and no predecessors.

       is_interior_vertex
               $g->is_interior_vertex($v)

           Return true if the vertex $v is an interior vertex: both successors
           and predecessors.

       is_exterior_vertex
               $g->is_exterior_vertex($v)

           Return true if the vertex $v is an exterior vertex: has either no
           successors or no predecessors, or neither.

       is_self_loop_vertex
               $g->is_self_loop_vertex($v)

           Return true if the vertex $v is a self loop vertex: has an edge
           from itself to itself.

       sink_vertices
               @v = $g->sink_vertices()

           Return the sink vertices of the graph.  In scalar context return
           the number of sink vertices.  See "is_sink_vertex" for the
           definition of a sink vertex.

       source_vertices
               @v = $g->source_vertices()

           Return the source vertices of the graph.  In scalar context return
           the number of source vertices.  See "is_source_vertex" for the
           definition of a source vertex.

       successorful_vertices
               @v = $g->successorful_vertices()

           Return the successorful vertices of the graph.  In scalar context
           return the number of successorful vertices.

       successorless_vertices
               @v = $g->successorless_vertices()


           For a directed graph, returns all successor vertices of the
           argument vertices, recursively.

           For undirected graphs, see "all_neighbours" and "all_reachable".

           See also "successors".

       neighbors
       neighbours
               @n = $g->neighbours($v)

           Return the neighboring/neighbouring vertices.  Also known as the
           adjacent vertices.

           See also "all_neighbours" and "all_reachable".

       all_neighbors
       all_neighbours
              @n = $g->all_neighbours(@v)

           Return the neighboring/neighbouring vertices of the argument
           vertices, recursively.  For a directed graph, recurses up
           predecessors and down successors.  For an undirected graph, returns
           all the vertices reachable from the argument vertices: equivalent
           to "all_reachable".

           See also "neighbours" and "all_reachable".

       all_reachable
               @r = $g->all_reachable(@v)

           Return all the vertices reachable from of the argument vertices,
           recursively.  For a directed graph, equivalent to "all_successors".
           For an undirected graph, equivalent to "all_neighbours".  The
           argument vertices are not included in the results unless there are
           explicit self-loops.

           See also "neighbours", "all_neighbours", and "all_successors".

       predecessorful_vertices
               @v = $g->predecessorful_vertices()

           Return the predecessorful vertices of the graph.  In scalar context
           return the number of predecessorful vertices.

       predecessorless_vertices
               @v = $g->predecessorless_vertices()

           Return the predecessorless vertices of the graph.  In scalar
           context return the number of predecessorless vertices.

       predecessors
               @p = $g->predecessors($v)

           See also "predecessors".

       isolated_vertices
               @v = $g->isolated_vertices()

           Return the isolated vertices of the graph.  In scalar context
           return the number of isolated vertices.  See "is_isolated_vertex"
           for the definition of an isolated vertex.

       interior_vertices
               @v = $g->interior_vertices()

           Return the interior vertices of the graph.  In scalar context
           return the number of interior vertices.  See "is_interior_vertex"
           for the definition of an interior vertex.

       exterior_vertices
               @v = $g->exterior_vertices()

           Return the exterior vertices of the graph.  In scalar context
           return the number of exterior vertices.  See "is_exterior_vertex"
           for the definition of an exterior vertex.

       self_loop_vertices
               @v = $g->self_loop_vertices()

           Return the self-loop vertices of the graph.  In scalar context
           return the number of self-loop vertices.  See "is_self_loop_vertex"
           for the definition of a self-loop vertex.

   Connected Graphs and Their Components
       In this discussion connected graph refers to any of connected graphs,
       biconnected graphs, and strongly connected graphs.

       NOTE: if the vertices of the original graph are Perl objects, (in other
       words, references, so you must be using "refvertexed") the vertices of
       the connected graph are NOT by default usable as Perl objects because
       they are blessed into a package with a rather unusable name.

       By default, the vertex names of the connected graph are formed from the
       names of the vertices of the original graph by (alphabetically sorting
       them and) concatenating their names with "+".  The vertex attribute
       "subvertices" is also used to store the list (as an array reference) of
       the original vertices.  To change the 'supercomponent' vertex names and
       the whole logic of forming these supercomponents use the
       "super_component") option to the method calls:

         $g->connected_graph(super_component => sub { ... })
         $g->biconnected_graph(super_component => sub { ... })
         $g->strongly_connected_graph(super_component => sub { ... })

       The subroutine reference gets the 'subcomponents' (the vertices of the
       original graph) as arguments, and it is supposed to return the new
           For directed graphs: the in-degree minus the out-degree at the
           vertex.

           For undirected graphs: the number of edges at the vertex
           (identical to "in_degree()", "out_degree()").

       in_degree
               $d = $g->in_degree($v)

           For directed graphs: the number of incoming edges at the vertex.

           For undirected graphs: the number of edges at the vertex (identical
           to "out_degree()", "degree()", "vertex_degree()").

       out_degree
               $o = $g->out_degree($v)

           For directed graphs: The number of outgoing edges at the vertex.

           For undirected graphs: the number of edges at the vertex (identical
           to "in_degree()", "degree()", "vertex_degree()").

       average_degree
              my $ad = $g->average_degree;

           Return the average degree (as in "degree()" or "vertex_degree()")
           taken over all vertices.

       Related methods are

       edges_at
               @e = $g->edges_at($v)

           The union of edges from and edges to at the vertex.

       edges_from
               @e = $g->edges_from($v)

           The edges leaving the vertex.

       edges_to
               @e = $g->edges_to($v)

           The edges entering the vertex.

       See also "average_degree".

   Counted Vertices
       Counted vertices are vertices with more than one instance, normally
       adding vertices is idempotent.  To enable counted vertices on a graph,
       give the "countvertexed" parameter a true value

           use Graph;
           my $g = Graph->new(countvertexed => 1);

       edges is idempotent (in other words, adding edges more than once makes
       no difference).

       There are two kinds or degrees of creating multiedges and
       multivertices.  The two kinds are mutually exclusive.

       The weaker kind is called counted, in which the edge or vertex has a
       count on it: add operations increase the count, and delete operations
       decrease the count, and once the count goes to zero, the edge or vertex
       is deleted.  If there are attributes, they all are attached to the same
       vertex.  You can think of this as the graph elements being refcounted,
       or reference counted, if that sounds more familiar.

       The stronger kind is called (true) multi, in which the edge or vertex
       really has multiple separate identities, so that you can for example
       attach different attributes to different instances.

       To enable multiedges on a graph:

           use Graph;
           my $g0 = Graph->new(countedged => 1);
           my $g0 = Graph->new(multiedged => 1);

       Similarly for vertices

           use Graph;
           my $g1 = Graph->new(countvertexed => 1);
           my $g1 = Graph->new(multivertexed => 1);

       You can test for these by

       is_countedged
       countedged
               $g->is_countedged
               $g->countedged

           Return true if the graph is countedged.

       is_countvertexed
       countvertexed
               $g->is_countvertexed
               $g->countvertexed

           Return true if the graph is countvertexed.

       is_multiedged
       multiedged
               $g->is_multiedged
               $g->multiedged

           Return true if the graph is multiedged.

       is_multivertexed
       multivertexed

       vertices() and edges() will return the multiple elements: if you want
       just the unique elements, use

       unique_vertices
       unique_edges
               @uv = $g->unique_vertices; # unique
               @mv = $g->vertices;        # possible multiples
               @ue = $g->unique_edges;
               @me = $g->edges;

       If you are using (the stronger kind of) multielements, you should use
       the by_id variants:

       add_vertex_by_id
       has_vertex_by_id
       delete_vertex_by_id
       add_edge_by_id
       has_edge_by_id
       delete_edge_by_id

           $g->add_vertex_by_id($v, $id)
           $g->has_vertex_by_id($v, $id)
           $g->delete_vertex_by_id($v, $id)

           $g->add_edge_by_id($u, $v, $id)
           $g->has_edge_by_id($u, $v, $id)
           $g->delete_edge_by_id($u, $v, $id)

       These interfaces only apply to multivertices and multiedges.  When you
       delete the last vertex/edge in a multivertex/edge, the whole
       vertex/edge is deleted.  You can use add_vertex()/add_edge() on a
       multivertex/multiedge graph, in which case an id is generated
       automatically.  To find out which the generated id was, you need to use

       add_vertex_get_id
       add_edge_get_id

           $idv = $g->add_vertex_get_id($v)
           $ide = $g->add_edge_get_id($u, $v)

       To return all the ids of vertices/edges in a multivertex/multiedge, use

       get_multivertex_ids
       get_multiedge_ids

           $g->get_multivertex_ids($v)
           $g->get_multiedge_ids($u, $v)

       The ids are returned in random order.

       To find out how many times the edge has been added (this works for
       either kind of multiedges):

       add_weighted_vertex_by_id
       add_weighted_vertices_by_id
       delete_edge_weight_by_id
       delete_vertex_weight_by_id
       get_edge_weight_by_id
       get_vertex_weight_by_id
       has_edge_weight_by_id
       has_vertex_weight_by_id
       set_edge_weight_by_id
       set_vertex_weight_by_id

   Topological Sort
       topological_sort
       toposort
               my @ts = $g->topological_sort;

           Return the vertices of the graph sorted topologically.  Note that
           there may be several possible topological orderings; one of them is
           returned.

           If the graph contains a cycle, a fatal error is thrown, you can
           either use "eval" to trap that, or supply the "empty_if_cyclic"
           argument with a true value

               my @ts = $g->topological_sort(empty_if_cyclic => 1);

           in which case an empty array is returned if the graph is cyclic.

   Minimum Spanning Trees (MST)
       Minimum Spanning Trees or MSTs are tree subgraphs derived from an
       undirected graph.  MSTs "span the graph" (covering all the vertices)
       using as lightly weighted (hence the "minimum") edges as possible.

       MST_Kruskal
               $mstg = $g->MST_Kruskal;

           Returns the Kruskal MST of the graph.

       MST_Prim
               $mstg = $g->MST_Prim(%opt);

           Returns the Prim MST of the graph.

           You can choose the first vertex with $opt{ first_root }.

       MST_Dijkstra
       minimum_spanning_tree
               $mstg = $g->MST_Dijkstra;
               $mstg = $g->minimum_spanning_tree;

           Aliases for MST_Prim.

   Single-Source Shortest Paths (SSSP)
       Single-source shortest paths, also known as Shortest Path Trees (SPTs).

           Return as a graph the the single-source shortest paths of the graph
           using Dijkstra's algorithm.  The graph cannot contain negative
           edges (negative edges cause the algorithm to abort with an error
           message "Graph::SPT_Dijkstra: edge ... is negative").

           You can choose the first vertex of the result with either a single
           vertex argument or with $opt{ first_root }, otherwise a random
           vertex is chosen.

           NOTE: note that all the vertices might not be reachable from the
           selected (explicit or random) start vertex.

           The start vertex is be available as the graph attribute
           "SPT_Dijkstra_root").

           The result weights of vertices can be retrieved from the result
           graph by

                   my $w = $sptg->get_vertex_attribute($v, 'weight');

           The predecessor vertex of a vertex in the result graph can be
           retrieved by

                   my $u = $sptg->get_vertex_attribute($v, 'p');

           ("A successor vertex" cannot be retrieved as simply because a
           single vertex can have several successors.  You can first find the
           "neighbors()" vertices and then remove the predecessor vertex.)

           If you want to find the shortest path between two vertices, see
           "SP_Dijkstra".

       SSSP_Dijkstra
       single_source_shortest_paths
           Aliases for SPT_Dijkstra.

       SP_Dijkstra
               @path = $g->SP_Dijkstra($u, $v)

           Return the vertices in the shortest path in the graph $g between
           the two vertices $u, $v.  If no path can be found, an empty list is
           returned.

           Uses SPT_Dijkstra().

       SPT_Dijkstra_clear_cache
               $g->SPT_Dijkstra_clear_cache

           See "Clearing cached results".

       SPT_Bellman_Ford
               $sptg = $g->SPT_Bellman_Ford(%opt)


           The start vertex is be available as the graph attribute
           "SPT_Bellman_Ford_root").

           The result weights of vertices can be retrieved from the result
           graph by

                   my $w = $sptg->get_vertex_attribute($v, 'weight');

           The predecessor vertex of a vertex in the result graph can be
           retrieved by

                   my $u = $sptg->get_vertex_attribute($v, 'p');

           ("A successor vertex" cannot be retrieved as simply because a
           single vertex can have several successors.  You can first find the
           "neighbors()" vertices and then remove the predecessor vertex.)

           If you want to find the shortes path between two vertices, see
           "SP_Bellman_Ford".

       SSSP_Bellman_Ford
           Alias for SPT_Bellman_Ford.

       SP_Bellman_Ford
               @path = $g->SP_Bellman_Ford($u, $v)

           Return the vertices in the shortest path in the graph $g between
           the two vertices $u, $v.  If no path can be found, an empty list is
           returned.

           Uses SPT_Bellman_Ford().

       SPT_Bellman_Ford_clear_cache
               $g->SPT_Bellman_Ford_clear_cache

           See "Clearing cached results".

   All-Pairs Shortest Paths (APSP)
       For either a directed or an undirected graph, return the APSP object
       describing all the possible paths between any two vertices of the
       graph.  If no weight is defined for an edge, 1 (one) is assumed.

       APSP_Floyd_Warshall
       all_pairs_shortest_paths
               my $apsp = $g->APSP_Floyd_Warshall(...);

           Return the all-pairs shortest path object computed from the graph
           using Floyd-Warshall's algorithm.  The length of a path between two
           vertices is the sum of weight attribute of the edges along the
           shortest path between the two vertices.  If no weight attribute
           name is specified explicitly

               $g->APSP_Floyd_Warshall(attribute_name => 'height');
                   vertices.

           path_vertices
                       my @v = $apsp->path_vertices($u, $v);

                   Return the list of vertices along the shortest path.

           path_predecessor
                      my $u = $apsp->path_predecessor($v);

                   Returns the predecessor of vertex $v in the all-pairs
                   shortest paths.

           average_path_length
                       my $apl = $g->average_path_length; # All vertex pairs.

                       my $apl = $g->average_path_length($u); # From $u.
                       my $apl = $g->average_path_length($u, undef); # From $u.

                       my $apl = $g->average_path_length($u, $v); # From $u to $v.

                       my $apl = $g->average_path_length(undef, $v); # To $v.

                   Return the average (shortest) path length over all the
                   vertex pairs of the graph, from a vertex, between two
                   vertices, and to a vertex.

           longest_path
                       my @lp = $g->longest_path;
                       my $lp = $g->longest_path;

                   In scalar context return the longest shortest path length
                   over all the vertex pairs of the graph.  In list context
                   return the vertices along a longest shortest path.  Note
                   that there might be more than one such path; this
                   interfaces return a random one of them.

           diameter
           graph_diameter
                       my $gd = $g->diameter;

                   The longest path over all the vertex pairs is known as the
                   graph diameter.

           shortest_path
                       my @sp = $g->shortest_path;
                       my $sp = $g->shortest_path;

                   In scalar context return the shortest length over all the
                   vertex pairs of the graph.  In list context return the
                   vertices along a shortest path.  Note that there might be
                   more than one such path; this interface returns a random
                   one of them.

                   vertex eccentricity is equal to the graph radius.  The
                   vertices are returned in random order.  By specifying a
                   delta value you can widen the criterion from strict
                   equality (handy for non-integer edge weights).

           vertex_eccentricity
                       my $ve = $g->vertex_eccentricity($v);

                   The longest path to a vertex is known as the vertex
                   eccentricity.  If the graph is unconnected, returns Inf.

           You can walk through the matrix of the shortest paths by using

           for_shortest_paths
                   $n = $g->for_shortest_paths($callback)

               The number of shortest paths is returned (this should be equal
               to V*V).  The $callback is a sub reference that receives four
               arguments: the transitive closure object from
               Graph::TransitiveClosure, the two vertices, and the index to
               the current shortest paths (0..V*V-1).

   Clearing cached results
       For many graph algorithms there are several different but equally valid
       results.  (Pseudo)Randomness is used internally by the Graph module to
       for example pick a random starting vertex, and to select random edges
       from a vertex.

       For efficiency the computed result is often cached to avoid recomputing
       the potentially expensive operation, and this also gives additional
       determinism (once a correct result has been computed, the same result
       will always be given).

       However, sometimes the exact opposite is desireable, and the possible
       alternative results are wanted (within the limits of the
       pseudorandomness: not all the possible solutions are guaranteed to be
       returned, usually only a subset is retuned).  To undo the caching, the
       following methods are available:

       o   connectivity_clear_cache

           Affects "connected_components", "connected_component_by_vertex",
           "connected_component_by_index", "same_connected_components",
           "connected_graph", "is_connected", "is_weakly_connected",
           "weakly_connected_components",
           "weakly_connected_component_by_vertex",
           "weakly_connected_component_by_index",
           "same_weakly_connected_components", "weakly_connected_graph".

       o   biconnectivity_clear_cache

           Affects "biconnected_components",
           "biconnected_component_by_vertex",
           "biconnected_component_by_index", "is_edge_connected",

       o   SPT_Dijkstra_clear_cache

           Affects "SPT_Dijkstra", "SSSP_Dijkstra",
           "single_source_shortest_paths", "SP_Dijkstra".

       o   SPT_Bellman_Ford_clear_cache

           Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".

       Note that any such computed and cached results are of course always
       automatically discarded whenever the graph is modified.

   Random
       You can either ask for random elements of existing graphs or create
       random graphs.

       random_vertex
               my $v = $g->random_vertex;

           Return a random vertex of the graph, or undef if there are no
           vertices.

       random_edge
               my $e = $g->random_edge;

           Return a random edge of the graph as an array reference having the
           vertices as elements, or undef if there are no edges.

       random_successor
               my $v = $g->random_successor($v);

           Return a random successor of the vertex in the graph, or undef if
           there are no successors.

       random_predecessor
               my $u = $g->random_predecessor($v);

           Return a random predecessor of the vertex in the graph, or undef if
           there are no predecessors.

       random_graph
               my $g = Graph->random_graph(%opt);

           Construct a random graph.  The %opt must contain the "vertices"
           argument

               vertices => vertices_def

           where the vertices_def is one of

           o       an array reference where the elements of the array
                   reference are the vertices

           o       a number N in which case the vertices will be integers

       the "random_seed" option:

           $g = Graph->random_graph(vertices => 10, random_seed => 1234);

       As this uses the standard Perl srand(), the usual caveat applies: use
       it sparingly, and consider instead using a single srand() call at the
       top level of your application.

       The default random distribution of edges is flat, that is, any pair of
       vertices is equally likely to appear.  To define your own distribution,
       use the "random_edge" option:

           $g = Graph->random_graph(vertices => 10, random_edge => \&d);

       where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
       where the $g is the random graph, $u and $v are the vertices, and the
       $p is the probability ([0,1]) for a flat distribution.  It must return
       a probability ([0,1]) that the vertices $u and $v have an edge between
       them.  Note that returning one for a particular pair of vertices
       doesn't guarantee that the edge will be present in the resulting graph
       because the required number of edges might be reached before that
       particular pair is tested for the possibility of an edge.  Be very
       careful to adjust also "edges" or "edges_fill" so that there is a
       possibility of the filling process terminating.

   Attributes
       You can attach free-form attributes (key-value pairs, in effect a full
       Perl hash) to each vertex, edge, and the graph itself.

       Note that attaching attributes does slow down some other operations on
       the graph by a factor of three to ten.  For example adding edge
       attributes does slow down anything that walks through all the edges.

       For vertex attributes:

       set_vertex_attribute
               $g->set_vertex_attribute($v, $name, $value)

           Set the named vertex attribute.

           If the vertex does not exist, the set_...() will create it, and the
           other vertex attribute methods will return false or empty.

           NOTE: any attributes beginning with an underscore/underline (_) are
           reserved for the internal use of the Graph module.

       get_vertex_attribute
               $value = $g->get_vertex_attribute($v, $name)

           Return the named vertex attribute.

       has_vertex_attribute
               $g->has_vertex_attribute($v, $name)

           NOTE: any attributes beginning with an underscore ("_") are
           reserved for the internal use of the Graph module.

       get_vertex_attributes
               $attr = $g->get_vertex_attributes($v)

           Return all the attributes of the vertex as an anonymous hash.

       get_vertex_attribute_names
               @name = $g->get_vertex_attribute_names($v)

           Return the names of vertex attributes.

       get_vertex_attribute_values
               @value = $g->get_vertex_attribute_values($v)

           Return the values of vertex attributes.

       has_vertex_attributes
               $g->has_vertex_attributes($v)

           Return true if the vertex has any attributes, false if not.

       delete_vertex_attributes
               $g->delete_vertex_attributes($v)

           Delete all the attributes of the named vertex.

       If you are using multivertices, use the by_id variants:

       set_vertex_attribute_by_id
       get_vertex_attribute_by_id
       has_vertex_attribute_by_id
       delete_vertex_attribute_by_id
       set_vertex_attributes_by_id
       get_vertex_attributes_by_id
       get_vertex_attribute_names_by_id
       get_vertex_attribute_values_by_id
       has_vertex_attributes_by_id
       delete_vertex_attributes_by_id
               $g->set_vertex_attribute_by_id($v, $id, $name, $value)
               $g->get_vertex_attribute_by_id($v, $id, $name)
               $g->has_vertex_attribute_by_id($v, $id, $name)
               $g->delete_vertex_attribute_by_id($v, $id, $name)
               $g->set_vertex_attributes_by_id($v, $id, $attr)
               $g->get_vertex_attributes_by_id($v, $id)
               $g->get_vertex_attribute_values_by_id($v, $id)
               $g->get_vertex_attribute_names_by_id($v, $id)
               $g->has_vertex_attributes_by_id($v, $id)
               $g->delete_vertex_attributes_by_id($v, $id)

       For edge attributes:

       set_edge_attribute

           Return the named edge attribute.

       has_edge_attribute
               $g->has_edge_attribute($u, $v, $name)

           Return true if the edge has an attribute, false if not.

       delete_edge_attribute
               $g->delete_edge_attribute($u, $v, $name)

           Delete the named edge attribute.

       set_edge_attributes
               $g->set_edge_attributes($u, $v, $attr)

           Set all the attributes of the edge from the anonymous hash $attr.

           NOTE: any attributes beginning with an underscore ("_") are
           reserved for the internal use of the Graph module.

       get_edge_attributes
               $attr = $g->get_edge_attributes($u, $v)

           Return all the attributes of the edge as an anonymous hash.

       get_edge_attribute_names
               @name = $g->get_edge_attribute_names($u, $v)

           Return the names of edge attributes.

       get_edge_attribute_values
               @value = $g->get_edge_attribute_values($u, $v)

           Return the values of edge attributes.

       has_edge_attributes
               $g->has_edge_attributes($u, $v)

           Return true if the edge has any attributes, false if not.

       delete_edge_attributes
               $g->delete_edge_attributes($u, $v)

           Delete all the attributes of the named edge.

       If you are using multiedges, use the by_id variants:

       set_edge_attribute_by_id
       get_edge_attribute_by_id
       has_edge_attribute_by_id
       delete_edge_attribute_by_id
       set_edge_attributes_by_id
       get_edge_attributes_by_id
               $g->has_edge_attributes_by_id($u, $v, $id)
               $g->delete_edge_attributes_by_id($u, $v, $id)

       For graph attributes:

       set_graph_attribute
               $g->set_graph_attribute($name, $value)

           Set the named graph attribute.

           NOTE: any attributes beginning with an underscore ("_") are
           reserved for the internal use of the Graph module.

       get_graph_attribute
               $value = $g->get_graph_attribute($name)

           Return the named graph attribute.

       has_graph_attribute
               $g->has_graph_attribute($name)

           Return true if the graph has an attribute, false if not.

       delete_graph_attribute
               $g->delete_graph_attribute($name)

           Delete the named graph attribute.

       set_graph_attributes
               $g->get_graph_attributes($attr)

           Set all the attributes of the graph from the anonymous hash $attr.

           NOTE: any attributes beginning with an underscore ("_") are
           reserved for the internal use of the Graph module.

       get_graph_attributes
               $attr = $g->get_graph_attributes()

           Return all the attributes of the graph as an anonymous hash.

       get_graph_attribute_names
               @name = $g->get_graph_attribute_names()

           Return the names of graph attributes.

       get_graph_attribute_values
               @value = $g->get_graph_attribute_values()

           Return the values of graph attributes.

       has_graph_attributes
               $g->has_graph_attributes()

       add_weighted_edge
               $g->add_weighted_edge($u, $v, $weight)

       add_weighted_edges
               $g->add_weighted_edges($u1, $v1, $weight1, ...)

       add_weighted_path
               $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)

       add_weighted_vertex
               $g->add_weighted_vertex($v, $weight)

       add_weighted_vertices
               $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)

       delete_edge_weight
               $g->delete_edge_weight($u, $v)

       delete_vertex_weight
               $g->delete_vertex_weight($v)

       get_edge_weight
               $g->get_edge_weight($u, $v)

       get_vertex_weight
               $g->get_vertex_weight($v)

       has_edge_weight
               $g->has_edge_weight($u, $v)

       has_vertex_weight
               $g->has_vertex_weight($v)

       set_edge_weight
               $g->set_edge_weight($u, $v, $weight)

       set_vertex_weight
               $g->set_vertex_weight($v, $weight)

   Isomorphism
       Two graphs being isomorphic means that they are structurally the same
       graph, the difference being that the vertices might have been renamed
       or substituted.  For example in the below example $g0 and $g1 are
       isomorphic: the vertices "b c d" have been renamed as "z x y".

               $g0 = Graph->new;
               $g0->add_edges(qw(a b a c c d));
               $g1 = Graph->new;
               $g1->add_edges(qw(a x x y a z));

       In the general case determining isomorphism is NP-hard, in other words,
       really hard (time-consuming), no other ways of solving the problem are
       known than brute force check of of all the possibilities (with possible
       optimization tricks, of course, but brute force still rules at the end

       What is actually returned is the maximum number of possible isomorphic
       graphs between the two graphs, after the above sanity checks have been
       conducted.  It is basically the product of the factorials of the
       absolute values of in-degrees and out-degree pairs at each vertex, with
       the isolated vertices ignored (since they could be reshuffled and
       renamed arbitrarily).  Note that for large graphs the product of these
       factorials can overflow the maximum presentable number (the floating
       point number) in your computer (in Perl) and you might get for example
       Infinity as the result.

   Miscellaneous
       betweenness
               %b = $g->betweenness

           Returns a map of vertices to their Freeman's betweennesses:

             C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}

           It is described in:

               Freeman, A set of measures of centrality based on betweenness, http://arxiv.org/pdf/cond-mat/0309045

           and based on the algorithm from:

               "A Faster Algorithm for Betweenness Centrality"

       clustering_coefficient
               $gamma = $g->clustering_coefficient()
               ($gamma, %clustering) = $g->clustering_coefficient()

           Returns the clustering coefficient gamma as described in

               Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf

           In scalar context returns just the average gamma, in list context
           returns the average gamma and a hash of vertices to clustering
           coefficients.

       subgraph_by_radius
               $s = $g->subgraph_by_radius($n, $radius);

           Returns a subgraph representing the ball of $radius around node $n
           (breadth-first search).

       The "expect" methods can be used to test a graph and croak if the graph
       is not as expected.

       expect_acyclic
       expect_dag
       expect_directed
       expect_multiedged
       expect_multivertexed
       expect_non_multiedged

       A vertex takes up at least 100 bytes of memory.

       An edge takes up at least 400 bytes of memory.

       (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)

       These size approximations are very approximate and optimistic (they are
       based on total_size() of Devel::Size).  In real life many factors
       affect these numbers, for example how Perl is configured.  The numbers
       are for a 32-bit platform and for Perl 5.8.8.

       Roughly, the above numbers mean that in a megabyte of memory you can
       fit for example a graph of about 1000 vertices and about 2500 edges.

   Hyperedges, hypervertices, hypergraphs
       BEWARE: this is a rather thinly tested feature, and the theory is even
       less so.  Do not expect this to stay as it is (or at all) in future
       releases.

       NOTE: most usual graph algorithms (and basic concepts) break horribly
       (or at least will look funny) with these hyperthingies.  Caveat emptor.

       Hyperedges are edges that connect a number of vertices different from
       the usual two.

       Hypervertices are vertices that consist of a number of vertices
       different from the usual one.

       Note that for hypervertices there is an asymmetry: when adding
       hypervertices, the single vertices are also implicitly added.

       Hypergraphs are graphs with hyperedges.

       To enable hyperness when constructing Graphs use the "hyperedged" and
       "hypervertexed" attributes:

          my $h = Graph->new(hyperedged => 1, hypervertexed => 1);

       To add hypervertexes, either explicitly use more than one vertex (or,
       indeed, no vertices) when using add_vertex()

          $h->add_vertex("a", "b")
          $h->add_vertex()

       or implicitly with array references when using add_edge()

          $h->add_edge(["a", "b"], "c")
          $h->add_edge()

       Testing for existence and deletion of hypervertices and hyperedges
       works similarly.

       To test for hyperness of a graph use the

       vertices_at
               $g->vertices_at($v)

       Return the vertices at the vertex.  This may return just the vertex or
       also other vertices.

       To go with the concept of undirected in normal (non-hyper) graphs,
       there is a similar concept of omnidirected (this is my own coinage,
       "all-directions") for hypergraphs, and you can naturally test for it by

       is_omnidirected
       omnidirected
       is_omniedged
       omniedged
              $g->is_omniedged

              $g->omniedged

              $g->is_omnidirected

              $g->omnidirected

           Return true if the graph is omnidirected (edges have no direction),
           false if not.

       You may be wondering why on earth did I make up this new concept, why
       didn't the "undirected" work for me?  Well, because of this:

          $g = Graph->new(hypervertexed => 1, omnivertexed => 1);

       That's right, vertices can be omni, too - and that is indeed the
       default.  You can turn it off and then $g->add_vertex(qw(a b)) no more
       means adding also the (hyper)vertex qw(b a).  In other words, the
       "directivity" is orthogonal to (or independent of) the number of
       vertices in the vertex/edge.

       is_omnivertexed
       omnivertexed

       Another oddity that fell out of the implementation is the uniqueness
       attribute, that comes naturally in "uniqedged" and "uniqvertexed"
       flavours.  It does what it sounds like, to unique or not the vertices
       participating in edges and vertices (is the hypervertex qw(a b a) the
       same as the hypervertex qw(a b), for example).  Without too much
       explanation:

       is_uniqedged
       uniqedged
       is_uniqvertexed
       uniqvertexed

   Backward compatibility with Graph 0.2
       The Graph 0.2 (and 0.2xxxx) had the following features
           being the edge begin vertices, and the secondary key being the edge
           end vertices.

       o   The attribute API was oddly position dependent and dependent on the
           number of arguments.  Use ..._graph_attribute(),
           ..._vertex_attribute(), ..._edge_attribute() instead.

       In future releases of Graph (any release after 0.50) the 0.2xxxx
       compatibility will be removed.  Upgrade your code now.

       If you want to continue using these (mis)features you can use the
       "compat02" flag when creating a graph:

           my $g = Graph->new(compat02 => 1);

       This will change the vertices() and edges() appropriately.  This,
       however, is not recommended, since it complicates all the code using
       vertices() and edges().  Instead it is recommended that the
       vertices02() and edges02() methods are used.  The corresponding new
       style (unsorted, and edges() returning a list of references) methods
       are called vertices05() and edges05().

       To test whether a graph has the compatibility turned on

       is_compat02
       compat02
               $g->is_compat02
               $g->compat02

       The following are not backward compatibility methods, strictly
       speaking, because they did not exist before.

       edges02
           Return the edges as a flat list of vertices, elements at even
           indices being the start vertices and elements at odd indices being
           the end vertices.

       edges05
           Return the edges as a list of array references, each element
           containing the vertices of each edge.  (This is not a backward
           compatibility interface as such since it did not exist before.)

       vertices02
           Return the vertices in sorted order.

       vertices05
           Return the vertices in random order.

       For the attributes the recommended way is to use the new API.

       Do not expect new methods to work for compat02 graphs.

       The following compatibility methods exist:

           now always returns the vertices in an unsorted order.  You can also
           use the unsorted_vertices import, but only with a true value (false
           values will cause an error).

       density_limits
               my ($sparse, $dense, $complete) = $g->density_limits;

           Return the "density limits" used to classify graphs as "sparse" or
           "dense".  The first limit is C/4 and the second limit is 3C/4,
           where C is the number of edges in a complete graph (the last
           "limit").

       density
               my $density = $g->density;

           Return the density of the graph, the ratio of the number of edges
           to the number of edges in a complete graph.

       vertex
               my $v = $g->vertex($v);

           Return the vertex if the graph has the vertex, undef otherwise.

       out_edges
       in_edges
       edges($v)
           This is now called edges_at($v).

   DIAGNOSTICS
       o   Graph::...Map...: arguments X expected Y ...

           If you see these (more user-friendly error messages should have
           been triggered above and before these) please report any such
           occurrences, but in general you should be happy to see these since
           it means that an attempt to call something with a wrong number of
           arguments was caught in time.

       o   Graph::add_edge: graph is not hyperedged ...

           Maybe you used add_weighted_edge() with only the two vertex
           arguments.

       o   Not an ARRAY reference at lib/Graph.pm ...

           One possibility is that you have code based on Graph 0.2xxxx that
           assumes Graphs being blessed hash references, possibly also
           assuming that certain hash keys are available to use for your own
           purposes.  In Graph 0.50 none of this is true.  Please do not
           expect any particular internal implementation of Graphs.  Use
           inheritance and graph/vertex/edge attributes instead.

           Another possibility is that you meant to have objects (blessed
           references) as graph vertices, but forgot to use "refvertexed" (see
           "refvertexed") when creating the graph.
           Sedgewick, Addison Wesley

       o   Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
           McGraw Hill

       o   Graphs, Networks and Algorithms, Dieter Jungnickel, Springer

SEE ALSO
       Persistent/Serialized graphs?  You want to read/write Graphs?  See the
       Graph::Reader and Graph::Writer in CPAN.

AUTHOR AND COPYRIGHT
       Jarkko Hietaniemi jhi@iki.fi

COPYRIGHT
       Copyright (c) 1998-2013 Jarkko Hietaniemi.  All rights reserved.

LICENSE
       This program is free software; you can redistribute it and/or modify it
       under the same terms as Perl 5 itself.



perl v5.18.1                      2013-05-24                        Graph(3pm)
Man Pages Copyright Respective Owners. Site Copyright (C) 1994 - 2017 Hurricane Electric. All Rights Reserved.