Graph - graph data structures and algorithms

        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.

This module is not for drawing any sort of graphics, business or otherwise.

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

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 the CWnew() constructor of the Graph::Directed class. You can test the directness of a graph with CW$g->is_directed() and CW$g->is_undirected().

*

undirected A boolean option telling that an undirected graph should be created. One could also use the CWnew() constructor the Graph::Undirected class instead. Note that while often it is possible to think undirected graphs as bidirectional graphs, or as directed graphs with 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 CW$g->is_directed() and CW$g->is_undirected().

*

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

*

unionfind If the graph is undirected, you can specify the CWunionfind 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 CWunionfind is used, adding edges (and vertices) becomes slower, but connectedness queries become faster. You can test a graph for union-findness with

has_union_find

    has_union_find

*

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 graph. If you want a deep copy that includes attributes, see deep_copy. The copy will have the same directedness as the original.

deep_copy

deep_copy_graph

    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. (Uses Data::Dumper behind the scenes. Note that copying code references only works with Perls 5.8 or later, and even then only if B::Deparse can reconstruct your code.)

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).

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

complement

    my $c = $g->complement_graph;

Create a complement graph that has the same vertices as the original graph. A complete graph has an edge (v,u) for every original edge (u,v).

See also random_graph for a random constructor.

add_vertex

    $g->add_vertex($v)

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.

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 an equal number of deletions to become completely deleteted.

delete_vertices

    $g->delete_vertices($v)

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 an equal number of deletions to become completely deleteted.

delete_edge

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

Delete the edge from the graph. Returns the graph, even if the edge did not exist in the graph. If the graph has been created multivertexed or countedged and an edge has been added multiple times, the edge will require an equal number of deletions to become completely deleted.

delete_edges

    $g->delete_edges($u1, $v1, $u2, $v2, ...)

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

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

Testing for equality can be done either by the overloaded CWeq 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 CWne operator and the method

ne

See also Isomorphism.

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 CW$a-$b, CW$b-$c, ..., CW$x-$y, CW$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 CW$a-$b, CW$b-$c, ..., CW$x-$y, CW$y-$z, false otherwise.

delete_path

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

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

add_cycle

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

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

has_cycle

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

Return true if the graph has all the edges CW$a-$b, CW$b-$c, ..., CW$x-$y, CW$y-$z, and CW$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 CW$a-$b, CW$b-$c, ..., CW$x-$y, CW$y-$z, and CW$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.

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
    $g->is_dag

Return true if the graph is directed and acyclic, false otherwise.

is_cyclic

    $g->is_cyclic

Return true if the graph is cyclic (contains at least one cycle). (This is identical to CWhas_a_cycle.) To find at least that one cycle, see find_a_cycle.

is_acyclic

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

To find a cycle, use find_a_cycle.

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 CW$u to CW$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.

add_vertices

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

Add zero or more vertices to the graph.

add_edges

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

Add zero or more edges to the graph. The edges are specified as a list of array references.

is_directed

directed

    $g->is_directed()
    $g->directed()

Return true if the graph is directed, false otherwise.

is_undirected

undirected

    $g->is_undirected()
    $g->undirected()

Return true if the graph is undirected, false otherwise.

is_refvertexed

refvertexed

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 CWunionfind parameter, the time complexity is (essentially) O(V), otherwise O(V log V). See also connected_components, connected_component, 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 inside the anonymous arrays is undefined. For directed graphs, see strongly_connected_components and weakly_connected_components.

connected_component_by_vertex

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

For an undirected graph, return an index identifying the connected component the vertex belongs to, the indexing starting from zero. For the inverse, see connected_component_by_index. If the graph has been created with a true CWunionfind 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 CWunionfind 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.

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.

is_biconnected

   $g->is_biconnected

For an undirected graph, return true if the graph is biconnected (if it has no articulation points, also known as cut vertices).

is_edge_connected

   $g->is_edge_connected

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

is_edge_separable

   $g->is_edge_separable

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

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 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 an index identifying the biconnected component the vertex belongs to, the indexing starting from zero. 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 inside the anonymous array is undefined. Also note that one vertex can belong to more than one biconnected component.

same_biconnected_components

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

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

biconnected_graph

    $bcg = $g->biconnected_graph

For an undirected graph, return its biconnected graph.

bridges

   $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.

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 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. See also same_weakly_connected_components. For undirected graphs, see same_connected_components or same_biconnected_components.

weakly_connected

is_weakly_connected

    $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 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($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 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_index. 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 component.

weakly_connected_graph

    $wcg = $g->weakly_connected_graph

For a directed graph, return its weakly connected graph. For undirected graphs, see connected_graph and biconnected_graph.

strongly_connected_components

   my @scc = $g->strongly_connected_components;

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. See also weakly_connected_components. For undirected graphs, see connected_components, or see biconnected_components.

strongly_connected_graph

   my $scg = $g->strongly_connected_graph;

Fof a directed graph, return the strongly connected graph of the graph. The vertices in the strongly connected graph are formed from the strongly connected elements of the graph (currently by sorting the vertices of the original graph present in the strongly connected component and concatenating the vertex names with CW+, for example CWa+b+c); the edges connect the strongly connected elements of the graph. 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 CW$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 CW$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 CW$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_successorful_vertex

    $g->is_successorful_vertex($v)

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

is_predecessorless_vertex

    $g->is_predecessorless_vertex($v)

Return true if the vertex CW$v has no predecessors (no edges entering the vertex), false if it has. Isolated vertices will return true: if you do not want this, use is_source_vertex().

is_predecessorful_vertex

    $g->is_predecessorful_vertex($v)

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

is_isolated_vertex

    $g->is_isolated_vertex($v)

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

is_interior_vertex

    $g->is_interior_vertex($v)

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

is_exterior_vertex

    $g->is_exterior_vertex($v)

Return true if the vertex CW$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 CW$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()

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

successors

    @s = $g->successors($v)

Return the immediate successor vertices of the vertex.

neighbors

neighbours

Return the neighbo(u)ring vertices. Also known as the adjacent vertices.

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

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

Return the immediate predecessor vertices of the vertex.

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.

A vertex has a degree based on the number of incoming and outgoing edges. This really makes sense only for directed graphs.

degree

vertex_degree

    $d = $g->degree($v)
    $d = $g->vertex_degree($v)

For directed graphs: the in-degree minus the out-degree at the vertex. For undirected graphs: the number of edges at the vertex.

in_degree

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

The number of incoming edges at the vertex.

out_degree

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

The number of outgoing edges at the vertex.

average_degree

   my $ad = $g->average_degree;

Return the average 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 are vertices with more than one instance, normally adding vertices is idempotent. To enable counted vertices on a graph, give the CWcountvertexed parameter a true value

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

To find out how many times the vertex has been added:

get_vertex_count

    my $c = $g->get_vertex_count($v);

Return the count of the vertex, or undef if the vertex does not exist.

Multiedges are edges with more than one life, meaning that one has to delete them as many times as they have been added. Normally adding 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. You can think of this as the graph elements being refcounted, 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 countededges on a graph, give the CWcountedged parameter a true value

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

Similarly for vertices

    use Graph;
    my $g0 = Graph->new(multiedged => 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

    $g->is_multivertexed
    $g->multivertexed

Return true if the graph is multivertexed.

A multiedged (either the weak or the strong kind) graph is a multigraph, for which you can test with CWis_multi_graph().

NOTE: The various graph algorithms do not in general work well with multigraphs, and no effort has been made to test the algorithms with multigraphs.

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)

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

    $id0 = $g->add_vertex_get_id($v)
    $id1 = $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)

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

get_edge_count

    my $c = $g->get_edge_count($u, $v);

Return the count (the countedness) of the edge, or undef if the edge does not exist.

The following multi-entity utility functions exist, mirroring the non-multi vertices and edges:

add_weighted_edge_by_id

add_weighted_edges_by_id

add_weighted_path_by_id

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

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 CWeval to trap that, or supply the CWempty_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 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 CW$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, also known as Shortest Path Trees (SPTs). For either a directed or an undirected graph, return a (tree) subgraph that from a single start vertex (the single source) travels the shortest possible paths (the paths with the lightest weights) to all the other vertices. Note that the SSSP is neither reflexive (the shortest paths do not include the zero-length path from the source vertex to the source vertex) nor transitive (the shortest paths do not include transitive closure paths). If no weight is defined for an edge, 1 (one) is assumed.

SPT_Dijkstra

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

Find the single-source shortest paths using Dijkstra's algorithm. The graph cannot contain negative edges (negative edges cause the algorithm to abort). You can choose the first vertex with CW$opt{ first_root }.

SSSP_Dijkstra

single_source_shortest_paths

Aliases for SPT_Dijkstra.

SPT_Bellman_Ford

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

Find the single-source shortest paths using Bellman-Ford's algorithm. The graph can contain negative edges but not negative cycles (negative cycles cause the algorithm to abort). You can choose the first vertex with CW$opt{ first_root }.

SSSP_Bellman_Ford

Alias for SPT_Bellman_Ford.

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 is the sum of weight attribute of the edges along the shortest path. If no weight attribute name is specified explicitly

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

the attribute CWweight is assumed. If an edge has no defined weight attribute, the value of one is assumed when getting the attribute. Once computed, you can query the APSP object with

path_length

    my $l = $apsp->path_length($u, $v);

Return the length of the shortest path between the two 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 CW$v in the all-pairs shortest paths.

average_path_length

    my $apl = $g->average_path_length;

Return the average (shortest) path length over all the vertex pairs of the graph. Note that this recomputes the APSP each time when called.

longest_path

graph_diameter

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

In scalar context return the longest (shortest) path length over all the vertex pairs of the graph. In list context return the vertices along the shortest path. Note that this recomputes the APSP each time when called. This measure is also known as the graph diameter.

shortest_path

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

In scalar context return the shortest (shortest) length over all the vertex pairs of the graph. In list context return the vertices along the shortest path. Note that this recomputes the APSP each time when called. 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 CW$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).

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 predeceessor of the vertex in the graph, or undef if there are no predeceessors.

random_graph

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

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

    vertices => vertices_def

where the vertices_def is one of

*

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

*

a number N in which case the vertices will be integers 0..N-1

The CW%opt may have either of the argument CWedges or the argument CWedges_fill. Both are used to define how many random edges to add to the graph; CWedges is an absolute number, while CWedges_fill is a relative number (relative to the number of edges in a complete graph, C). The number of edges can be larger than C, but only if the graph is countedged. The random edges will not include self-loops. If neither CWedges nor CWedges_fill is specified, an CWedges_fill of 0.5 is assumed.

If you want repeatable randomness (what is an oxymoron?) you can use the CWrandom_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 CWrandom_edge option:

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

where CWd is a code reference receiving ($g, CI$u, CI$v, CI$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 CWedges or CWedges_fill so that there is a possibility of the filling process terminating.

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 (CW_) 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)

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

delete_vertex_attribute

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

Delete the named vertex attribute.

set_vertex_attributes

    $g->set_vertex_attributes($v, $attr)

Set all the attributes of the vertex from the anonymous hash CW$attr. NOTE: any attributes beginning with an underscore (CW_) 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

    $g->set_edge_attribute($u, $v, $name, $value)

Set the named edge attribute. If the edge does not exist, the set_...() will create it, and the other edge attribute methods will return false or empty. NOTE: any attributes beginning with an underscore (CW_) are reserved for the internal use of the Graph module.

get_edge_attribute

    $value = $g->get_edge_attribute($u, $v, $name)

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->get_vertex_attributes($u, $v, $attr)

Set all the attributes of the edge from the anonymous hash CW$attr. NOTE: any attributes beginning with an underscore (CW_) 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

get_edge_attribute_names_by_id

get_edge_attribute_values_by_id

has_edge_attributes_by_id

delete_edge_attributes_by_id

    $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
    $g->get_edge_attribute_by_id($u, $v, $id, $name)
    $g->has_edge_attribute_by_id($u, $v, $id, $name)
    $g->delete_edge_attribute_by_id($u, $v, $id, $name)
    $g->set_edge_attributes_by_id($u, $v, $id, $attr)
    $g->get_edge_attributes_by_id($u, $v, $id)
    $g->get_edge_attribute_values_by_id($u, $v, $id)
    $g->get_edge_attribute_names_by_id($u, $v, $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 (CW_) 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 CW$attr. NOTE: any attributes beginning with an underscore (CW_) 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()

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

delete_graph_attributes

    $g->delete_graph_attributes()

Delete all the attributes of the named graph.

As convenient shortcuts the following methods add, query, and manipulate the attribute CWweight with the specified value to the respective Graph elements.

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)

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 CW$g0 and CW$g1 are isomorphic: the vertices CWb c d have been renamed as CWz 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.

A very rough guess at whether two graphs could be isomorphic is possible via the method

could_be_isomorphic

    $g0->could_be_isomorphic($g1)

If the graphs do not have the same number of vertices and edges, false is returned. If the distribution of in-degrees and out-degrees at the vertices of the graphs does not match, false is returned. Otherwise, true is returned.

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 renamed arbitrarily.) Note that for large graphs the product of these factorials can overflow the maximum presentable number (the floating point number) in the computer and you might get for example Infinity as the result.

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

expect_non_multivertexed

expect_undirected

A graph takes up at least 1160 bytes of memory.

A vertex takes up at least 110 bytes of memory.

An edge takes up at least 390 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. In practice you can expect at least about 200 bytes per vertex, and twice that for an edge. The numbers are for a 32-bit platform.

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

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.

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 CWhyperedged and CWhypervertexed 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

is_hypervertexed

hypervertexed

    $g->is_hypervertexed
    $g->hypervertexed

is_hyperedged

hyperedged

    $g->is_hyperedged
    $g->hyperedged

Since hypervertices consist of more than one vertex:

vertices_at

    $g->vertices_at($v)

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

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

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 CW$g->add_vertex(qw(a b)) no more means adding also a vertex qw(b a).

is_omnivertexed

omnivertexed

Another oddity that fell out of the implementation is the uniqueness attribute, that comes naturally in CWuniqedged and CWuniqvertexed flavours. It does what it sounds like, to unique or not the vertices participating in edges and vertices. Without too much explanation:

is_uniqedged

uniqedged

is_uniqvertexed

uniqvertexed

The Graph 0.2 (and 0.2xxxx) had the following features

•

vertices() always sorted the vertex list, which most of the time is unnecessary and wastes CPU.

•

edges() returned a flat list where the begin and end vertices of the edges were intermingled: every even index had an edge begin vertex, and every odd index had an edge end vertex. This had the unfortunate consequence of CWscalar(@e = edges) being twice the number of edges, and complicating any algorithm walking through the edges.

•

The vertex list returned by edges() was sorted, the primary key being the edge begin vertices, and the secondary key being the edge end vertices.

•

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 CWcompat02 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:

has_attribute

has_attributes

get_attribute

get_attributes

set_attribute

set_attributes

delete_attribute

delete_attributes

Do not use the above, use the new attribute interfaces instead.

vertices_unsorted

Alias for vertices() (or rather, vertices05()) since the vertices() 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).

•

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.

•

Graph::add_edge: graph is not hyperedged ... Maybe you used add_weighted_edge() with only the two vertex arguments.

•

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 attributes instead. Another possibility is that you meant to have objects (blessed references) as graph vertices, but forgot to use CWrefvertexed (see refvertexed) when creating the graph.

A possible future direction is a new graph module written for speed: this may very possibly mean breaking or limiting some of the APIs or behaviour as compared with this release of the module.

What definitely won't happen in future releases is carrying over the Graph 0.2xxxx backward compatibility API.

All bad terminology, bugs, and inefficiencies are naturally mine, all mine, and not the fault of the below.

Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my pre-0.50 code. If they missed something, that was only because of my fiendish code.

The following literature for algorithm descriptions and some test cases:

•

Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert Sedgewick, Addison Wesley

•

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

•

Graphs, Networks and Algorithms, Dieter Jungnickel, Springer

Jarkko Hietaniemi jhi@iki.fi

This module is licensed under the same terms as Perl itself.