Graph(3pm)

📦
version 0.9735 · 9 versions
, in debian trixie, ubuntu resolute, ubuntu stonking

🌈 Graph(3pm) 🌈

💖 NAME 💖

Graph — graph data structures and algorithms, bestie. That's the whole vibe. 💅

✨ SYNOPSIS ✨

Okay so here's the quick lil' taste of how you even start:

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->any_edge(...)
$g->delete_edge(...);

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

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

# And many, many more, see below.

Like, there's a whole buffet of methods, and this is just the appetizer. 🍓

📖 DESCRIPTION 📖

🙅‍♀️ Non-Description 🙅‍♀️

First things first, bestie: this module is not for drawing or rendering any sort of graphics or images, business stuff, visualization, or otherwise. It's giving "not that kind of graph". Zero drawing. None. 💀

💖 Description 💖

Instead, this module is for creating abstract data structures called graphs, and for doing various operations on those. That's the whole point. Slay. ✨

🐣 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. So if you're on something older, it's a no from me. 😭

🛠️ 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. Here's the full menu of options you can pass:

  • 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 new() constructor of the Graph::Directed class. You can test the directness of a graph with $g->is_directed() and $g->is_undirected(). 💅
  • undirected — a boolean option telling that an undirected graph should be created. One could also use the new() constructor of the Graph::Undirected class instead. Note that while often it is possible to think of 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 $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 edges 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 — 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. Also the following vertex/edge attributes are copied:
refvertexed/countvertexed/multivertexed
hyperedged/countedged/multiedged
NOTE: you can get an even shallower copy of a graph by:
my $c = $g->new;

This will copy only the graph properties (directed, and so forth), but none of the vertices or edges.

As of 0.9712, you can also copy the graph properties of an existing object, but with overrides:

my $c = $g->new(multiedged => 0);

🫶

  • deep_copy, 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).

If your vertices are references, the copied graph will have its connections fixed up. Support for this is new as of 0.9723, so please report any problems. 🐛

  • undirected_copy, 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). As of 0.9731 this preserves multiedged and multivertexed IDs. 🌈
  • undirected_copy_clear_cache — see "Clearing cached results".
$g->undirected_copy_clear_cache;
  • weak_connectivity_undirected_graph_clear_cache — see "Clearing cached results".
$g->weak_connectivity_undirected_graph_clear_cache;
  • undirected_copy_attributes — added in 0.9731. Like undirected_copy but also sets the copy's attributes to the same values as the original's. This is not a deep copy, so use caution in handling the copy's attributes. ⚠️
  • directed_copy, 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). As of 0.9731 this preserves multiedged and multivertexed IDs. 🔥
  • directed_copy_clear_cache — see "Clearing cached results".
$g->directed_copy_clear_cache;
  • directed_copy_attributes — added in 0.9731. Like directed_copy but also sets the copy's attributes to the same values as the original's. This is not a deep copy, so use caution in handling the copy's attributes. ⚠️
  • transpose, 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 — create a complete graph that has the same vertices as the original graph. A complete graph has an edge between every pair of vertices. 👑
  • max_cliques — returns a list (or array reference in scalar context), each of its elements is an anonymous array of vertices forming a maximal clique in the graph. The implementation uses the Bron-Kerbosch pivot algorithm.
my @cliques = $g->max_cliques;
  • bron_kerbosch_pivot — implements the Bron-Kerbosch pivot algorithm, mutating its fourth argument with the result.
$g->bron_kerbosch_pivot([], [$g->vertices], [], \ my @cliques);
  • complement_graph, complement — create a complement graph that has the same vertices as the original graph. A complement graph has an edge (u,v) if and only if the original graph does not have edge (u,v). 🪞
  • subgraph — creates a subgraph of a given graph. The created subgraph has the same graph properties (directedness, and so forth) as the original graph, but none of the attributes (graph, vertex, or edge).

A vertex is added to the subgraph if it is in the original graph.

An edge is added to the subgraph if there is an edge in the original graph that starts from the "src" set of vertices and ends in the "dst" set of vertices.

You can leave out dst in which case dst is assumed to be the same: this is called a vertex-induced subgraph.

my $c = $g->subgraph(\@src, \@dst);
my $c = $g->subgraph(\@src);
  • See also random_graph for a random constructor. 🎲

🧱 Basics 🧱

  • add_vertex — add the vertex to the graph. Returns the graph.
$g->add_vertex($v)

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 — add the edge to the graph. Implicitly first adds the vertices if the graph does not have them. Returns the graph.
$g->add_edge($u, $v)

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

An edge is also known as an arc.

For a hypergraph, the interface is different: if undirected, give a list of one or more vertices. If directed, give a list of two array-refs of vertices. As conceptually these are sets, the ordering of the contents is not important. 🕸️

  • has_vertex — return true if the vertex exists in the graph, false otherwise.
$g->has_vertex($v)
  • has_edge — return true if the edge exactly as specified exists in the graph, false otherwise.
$g->has_edge($u, $v)

Hyperedges which contain all the given vertices (in the right places if directed), but which also have others will not match. ❌

any_edge

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

Bestie, this is the lil shortcut you want. It returns true if any edge in the graph connects the first vertex to the second, and false if not. 💖

Heads up tho: this is a different question from has_edge. Same answer as peeking at the first vertex's successors to see if any of them match the second one — but done in a more efficient way. ✨ Slay.

delete_vertex

$g->delete_vertex($v)

Yeets the vertex out of the graph. Returns the graph — even if the vertex never existed in the graph in the first place. No drama, no error, just vibes. 🎀

If the graph was created multivertexed or countvertexed and a vertex has been added multiple times, that vertex needs at least an equal number of deletions before it's completely deleted. So like, one delete ≠ gone if it showed up 3 times. 🫠

delete_vertices

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

Deletes a whole lil squad of vertices from the graph. Returns the graph — even if none of them existed in the graph. 💅

Same multivertexed/countvertexed situation: if a vertex was added multiple times, it takes at least an equal number of deletions for it to be completely deleted. 🦋

delete_edge

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

Deletes the edge from the graph. Returns the graph — even if the edge wasn't even there. 🌸

If the graph was created multiedged or countedged and an edge has been added multiple times, that edge needs at least an equal number of deletions to become completely deleted. 😭

delete_edges

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

Deletes a bunch of edges at once. Returns the graph — even if none of the edges existed in the graph. ✨

And again, the multiedged/countedged rule: an edge added multiple times requires at least an equal number of deletions to be completely deleted. 💜

💫 Displaying 💫

Graphs have stringification overload, which means you can do adorable stuff like:

print "The graph is $g\n"

One-way (directed, unidirected) edges show up as '-'. Two-way (undirected, bidirected) edges show up as '='. Iconic, honestly. 👑

And if you wanna trigger the stringification yourself, there's a method:

stringify

🍓 Boolean 🍓

Graphs have boolifying overload, so you can do:

if ($g) { print "The graph is: $g\n" }

and it works even if the graph is empty. In fact, the boolify always returns true. 😌 So if you actually wanna test for something like vertices, test for vertices — don't rely on this, bestie.

boolify

🌈 Comparing 🌈

Wanna check if two graphs are equal? Two ways, pick your fighter.

The overloaded eq operator:

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

or the method:

eq

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

The tea: equality testing compares the stringified forms, which means it assumes total equality, not isomorphism — every single vertex must be named the same, and they must have identical edges between them. No wiggle room. 🙈

For unequality there's the matching overloaded ne operator and its method:

ne

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

See also "Isomorphism".

🧚 Paths and Cycles 🧚

Paths and cycles are basically simple extensions of edges: paths are edges starting from where the previous edge ended, and cycles are paths that loop back around to the start vertex of the first edge. It's giving... a journey. 🦋

add_path

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

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

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

delete_path

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

Deletes all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z — regardless of whether they exist or not. Returns the graph. 🎀

add_cycle

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

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

has_cycle

has_this_cycle

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

Returns 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". Don't get got, bestie. 💀

delete_cycle

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

Deletes all the 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), or an empty list if no cycle can be found. ⭐

Read this carefully, bestie: 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. That's just not what it does. 😭

👑 Graph Types 👑

is_simple_graph

$g->is_simple_graph

Returns true if the graph has no multiedges, false otherwise. ✨

is_pseudo_graph

$g->is_pseudo_graph

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

is_multi_graph

$g->is_multi_graph

Returns 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

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

is_cyclic

$g->is_cyclic

Returns true if the graph is cyclic (contains at least one cycle). 🌀

(This is identical to "has_a_cycle".)

To find at least one such cycle, see "find_a_cycle". 🔍

is_acyclic

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

is_bipartite

Returns true if the graph is bipartite (also known as 2-colourable, or not containing cycles of odd length). Currently only works with undirected graphs. 🙈

is_planar

Returns true if the graph is planar. The implementation is based on left-right planarity test as described in A characterization of planar graphs by Trémaux orders, de Fraysseix and Rosenstiehl <https://doi.org/10.1007/BF02579375>. Currently only works with undirected graphs. 💜

To find a cycle, use "find_a_cycle".

🦋 Transitivity 🦋

is_transitive

$g->is_transitive

Returns true if the graph is transitive, false otherwise. ✨

TransitiveClosure_Floyd_Warshall

transitive_closure

$tcg = $g->TransitiveClosure_Floyd_Warshall

Returns the transitive closure graph of the graph. 🌟

transitive_closure_matrix_clear_cache

$g->transitive_closure_matrix_clear_cache

See "Clearing cached results". 🧹

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

Adds 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));

Adds 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. ✨

For a hypergraph, each item in this list must be an array-ref of arguments suitable for "add_edge" — so for undirected, of vertices; for directed, of two array-refs of vertices. 🫶

rename_vertex

$g->rename_vertex('d', 'e')

Renames a vertex. It retains all of its edges. Throws exception if doesn't exist. 😤

Returns the graph. 💜

rename_vertices

$g->rename_vertices(sub { uc $_[0] })

Calls a function for each vertex-name, renaming it to the return value. 🌈

Returns the graph. ✨

filter_vertices

$g->filter_vertices(sub { my ($g, $v)=@_; $v =~ /^a/i })

Calls a function for each vertex; if it returns false, the vertex is deleted. Passed the graph, the vertex, and if "multivertexed", the ID (called once per "incarnation", i.e. ID). 🧚

Returns the graph. 🎀

filter_edges

$g->filter_edges(sub { my ($g, $u, $v, $id)=@_; $id eq 'Bakerloo' })

Calls a function for each edge; if it returns false, the edge is deleted. Passed the graph, the vertices, and if "multiedged", the ID (called once per "incarnation", i.e. ID). 🚇

Returns the graph. 💖

ingest

$g->ingest($g2)

Ingests all the vertices and edges of the given graph, including attributes. Returns the ingesting graph. 😋

🌸 Accessors 🌸

is_directed

directed

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

Returns true if the graph is directed, false otherwise. ➡️

is_undirected

undirected

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

Returns true if the graph is undirected, false otherwise. ⬅️

is_refvertexed

is_refvertexed_stringified

refvertexed

refvertexed_stringified

Returns true if the graph can handle references (including Perl objects) as vertices. 🪞

vertices

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

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

has_vertices

$g->has_vertices()

Returns true if the graph has any vertices, false otherwise. ✨

edges

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

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

has_edges

$g->has_edges()

Returns true if the graph has any edges, false otherwise. 💅

is_connected

$g->is_connected

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

If the graph was created with a true "unionfind" parameter, the time complexity is (essentially) O(V); otherwise O(V log V). ⏱️

See also <code>connected_components</code>, <code>connected_component_by_index</code>, <code>connected_component_by_vertex</code>, and <code>same_connected_components</code>, and <code>biconnectivity</code>.

For directed graphs, see <code>is_strongly_connected</code> and <code>is_weakly_connected</code>.

connected_components ✨

@cc = $g->connected_components()

For an undirected graph, this hands you the vertices of the connected components as a list of anonymous arrays. The ordering of those anonymous arrays, or the ordering of the vertices inside them (the components), is undefined — so don't come for order, bestie. 💅

For directed graphs, see <code>strongly_connected_components</code> and <code>weakly_connected_components</code>.

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, with the indexing starting from zero. 🔢

For the inverse, see <code>connected_component_by_index</code>.

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

See also <code>biconnectivity</code>.

For directed graphs, see <code>strongly_connected_component_by_vertex</code> and <code>weakly_connected_component_by_vertex</code>.

connected_component_by_index 🎀

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

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

For the inverse, see <code>connected_component_by_vertex</code>.

For directed graphs, see <code>strongly_connected_component_by_index</code> and <code>weakly_connected_component_by_index</code>.

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 <code>unionfind</code> parameter, the time complexity is (essentially) O(1), otherwise O(V log V). ⚡

For directed graphs, see <code>same_strongly_connected_components</code> and <code>same_weakly_connected_components</code>.

connected_graph 🌈

$cg = $g->connected_graph

For an undirected graph, return its connected graph. 🕸️

connectivity_clear_cache 🧹

$g->connectivity_clear_cache

See <code>Clearing cached results</code>. 🗑️

See <code>Connected Graphs and Their Components</code> 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. 🚨

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

⚠️ Note: more precisely, this would be called <code>is_edge_biconnected</code>, 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 <code>is_edge_biseparable</code>, 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. (Yes, "of of" — the original says that, bestie. 💀)

For the inverse, see <code>connected_component_by_index</code>. (Yes, the original cross-ref says <code>connected_component_by_index</code>, not biconnected. iykyk. 🤷‍♀️)

For directed graphs, see <code>strongly_connected_component_by_index</code> and <code>weakly_connected_component_by_index</code>.

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. (Yes, "an anonymous arrays" — original typo, we keep the vibe. 💅) 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, ...)

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. 🕸️

See <code>Connected Graphs and Their Components</code> for further discussion. 💬

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

biconnectivity_clear_cache 🧹

$g->biconnectivity_clear_cache

See <code>Clearing cached results</code>. 🗑️

strongly_connected, is_strongly_connected 💪

$g->is_strongly_connected

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

See also <code>is_weakly_connected</code>.

For undirected graphs, see <code>is_connected</code>, or <code>is_biconnected</code>.

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 <code>strongly_connected_component_by_index</code>.

See also <code>weakly_connected_component_by_vertex</code>.

For undirected graphs, see <code>connected_components</code> or <code>biconnected_components</code>.

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 as from <code>strongly_connected_components()</code>. 🌀

For the inverse, see <code>strongly_connected_component_by_vertex</code>.

For undirected graphs, see <code>weakly_connected_component_by_index</code>. (Yes, the original cross-ref says weakly for undirected here. Keep it. 🤷‍♀️)

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 <code>same_weakly_connected_components</code>.

For undirected graphs, see <code>same_connected_components</code> or <code>same_biconnected_components</code>.

strong_connectivity_clear_cache 🧹

$g->strong_connectivity_clear_cache

See <code>Clearing cached results</code>. 🗑️

weakly_connected, is_weakly_connected 🌊

$g->is_weakly_connected

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

A weakly connected graph is also known as a semiconnected graph. 🔗

⚠️ Note that there are two mutually incompatible definitions of "weakly connected". The definition used here is based on connectedness in the underlying undirected graph, hence this is also sometimes called "undirected-connected". -- The other definition, proposed by Graham, Knuth, and Motzkin in 1972, is currently not available within the Graph module. 📜

See also <code>is_strongly_connected</code>.

For undirected graphs, see <code>is_connected</code> or <code>is_biconnected</code>.

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 <code>strongly_connected_components</code>.

For undirected graphs, see <code>connected_components</code> or <code>biconnected_components</code>.

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 <code>weakly_connected_component_by_index</code>.

For undirected graphs, see <code>connected_component_by_vertex</code> and <code>biconnected_component_by_vertex</code>.

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. (Yes, "starting zero" — original. We love a typo. 💅) The order of vertices within a component is undefined, while the order of the weakly connected components is same as from <code>weakly_connected_components()</code>. 🌀

For the inverse, see <code>weakly_connected_component_by_vertex</code>.

For undirected graphs, see <code>connected_component_by_index</code> and <code>biconnected_component_by_index</code>. (No backticks in original? We'll keep them plain. But fine.)

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 <code>connected_graph</code> and <code>biconnected_graph</code>.

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

⚠️ 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 successors (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 $v has successors, false if not.

is_predecessorless_vertex 🍑

$g->is_predecessorless_vertex($v)

Return true if the vertex $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 $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.

For an undirected hypergraph, only true if an edge has the vertex as its sole participant.

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.

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

all_successors 🌌

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

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", "successors_by_radius".

successors_by_radius 📏

@s = $g->successors_by_radius(@v, $radius)

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", "successors_by_radius".

neighbors, neighbours 🫶

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

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

See also "all_neighbours" "all_reachable", and "neighbours_by_radius".

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", "all_reachable", and "neighbours_by_radius".

neighbors_by_radius, neighbours_by_radius 📐

@n = $g->neighbours_by_radius(@v, $radius)

Return the neighboring/neighbouring vertices of the argument vertices, recursively, out to the given radius.

all_reachable 🛰️

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

Return all the vertices reachable from 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", "all_successors", and "reachable_by_radius".

reachable_by_radius 📡

@r = $g->reachable_by_radius(@v, $radius)

Return all the vertices reachable from the argument vertices, recursively, out to the given radius.

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)

Return the immediate predecessor vertices of the vertex.

See also "all_predecessors", "all_neighbours", and "all_reachable".

all_predecessors 🌌

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

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

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

See also "predecessors", "predecessors_by_radius".

predecessors_by_radius 📏

@p = $g->predecessors_by_radius(@v, $radius)

For a directed graph, returns all predecessor vertices of the argument vertices, recursively, out to the given radius.

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.

as_hashes 🗂️

($nodes, $edges) = $g->as_hashes

Return hash-refs which map vertices to their attributes, and for edges, a two-level hash mapping the predecessor to its successors, mapped to the attributes.

If "multivertexed" is true, the vertices hash will have the second-level values be the multivertex's ID, and the third level will be attributes as above.

If "multiedged" is true, similar will be true for the edges hash.

For a hypergraph, the edges will instead be an array-ref of hashes with a key of "attributes", value a hash-ref (if "multiedged", two-level as above). Then with values of array-refs of vertex-names, for undirected:

vertices

And directed:

predecessors successors

✨ 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 supercomponent vertex, the "stringified" form of which is used as the vertex name.

✨ Degree ✨

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

Related methods are ✨

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

The union of edges from, and edges to, 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. 💖

✨ Counted Vertices ✨

Okay so 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);

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, Multivertices, Multigraphs ✨

Multiedges are edges with more than one "life" — you literally have 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. No cap.

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

To enable multiedges on a graph:

use Graph;
my $g0 = Graph->new(countedged => 1); # "weaker" kind
my $g0 = Graph->new(multiedged => 1); # "stronger" kind

Similarly for vertices:

use Graph;
my $g1 = Graph->new(countvertexed => 1); # "weaker" kind
my $g1 = Graph->new(multivertexed => 1); # "stronger" kind

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 kind or the strong kind) graph is a multigraph, for which you can test with is_multi_graph(). 🌈

NOTE: The various graph algorithms do not in general work well with multigraphs (they often assume simple graphs, that is, no multiedges or loops), and no effort has been made to test all algorithms with multigraphs. However, "SP_Dijkstra" and "SP_Bellman_Ford" have been tested with multiedges and do work (they choose the lowest weight of a given edge's incarnations). 💀

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

  • 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_path_by_id
  • add_edges_by_id
  • 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 ✨

  • 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; and $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). 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($root) or $sptg = $g->SPT_Dijkstra(%opt)

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. 😭
NOTE: after the first reachable tree from the first start vertex has been finished, and if there still are unvisited vertices, SPT_Dijkstra will keep on selecting unvisited vertices. 🔁

The next roots (in case the first tree doesn't visit all the vertices) can be chosen by setting one of the following options to true: "next_root", "next_alphabetic", "next_numeric", "next_random". 🌈

The "next_root" is the most customizable: the value needs to be a subroutine reference which will receive the graph and the unvisited vertices as hash reference. If you want to only visit the first tree, use "next_root =" sub { undef }>. The rest of these options are booleans. If none of them are true, a random unvisited vertex will be selected. 💅

The first start vertex is 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)

Return as a graph the single-source shortest paths of the graph using Bellman-Ford's algorithm. The graph can contain negative edges but not negative cycles (negative cycles cause the algorithm to abort with an error message "Graph::SPT_Bellman_Ford: negative cycle exists"). 💀

You can choose the start 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 lowkey 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 shortest path between two vertices, see "SP_Bellman_Ford".

SSSP_Bellman_Ford

Alias for SPT_Bellman_Ford. Periodt. 👑

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

Note that weight of 0 (zero) does not mean do not use this edge, it means essentially the opposite: an edge that has zero cost, an edge that makes the vertices the same. 👑

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 the Floyd-Warshall algorithm, of class Graph::TransitiveClosure.

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');

the attribute "weight" 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_successor

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

Returns the successor of vertex $u in the all-pairs shortest path to $v.

all_paths

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

Return list of array-refs with all the paths from $u to $v.

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 non-zero paths between vertex pairs of the graph's transitive closure. Depending on the arguments, this can be from a vertex, between two vertices, or to a vertex. An undefined (or not-given) vertex will match all.

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 interface returns a random one of them.

NOTE: this returns the longest shortest path, not the longest path.

diameter / graph_diameter

my $gd = $g->diameter;

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

For an unconnected graph, single-vertex, or empty graph, returns "undef".

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.

For an unconnected, single-vertex, or empty graph, returns "undef" or an empty list.

radius

my $gr = $g->radius;

The shortest longest path over all the vertex pairs is known as the graph radius. See also "diameter".

For an unconnected, single-vertex, or empty graph, returns Infinity.

center_vertices / centre_vertices

my @c = $g->center_vertices;
my @c = $g->center_vertices($delta);

The graph center is the set of vertices for which the 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).

For an unconnected, single-vertex, or empty graph, returns an empty list.

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, single-vertex, or empty graph, 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 desirable, 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 returned). To undo the caching, the following methods are available:

  • 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".
  • biconnectivity_clear_cache — Affects "biconnected_components", "biconnected_component_by_vertex", "biconnected_component_by_index", "is_edge_connected", "is_edge_separable", "articulation_points", "cut_vertices", "is_biconnected", "biconnected_graph", "same_biconnected_components", "bridges".
  • strong_connectivity_clear_cache — Affects "strongly_connected_components", "strongly_connected_component_by_vertex", "strongly_connected_component_by_index", "same_strongly_connected_components", "is_strongly_connected", "strongly_connected", "strongly_connected_graph".
  • SPT_Dijkstra_clear_cache — Affects "SPT_Dijkstra", "SSSP_Dijkstra", "single_source_shortest_paths", "SP_Dijkstra".
  • 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

  • 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 %opt may have either of the argument "edges" or the argument "edges_fill". Both are used to define how many random edges to add to the graph; "edges" is an absolute number, while "edges_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 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is assumed.

If you want repeatable randomness (what is an oxymoron?) you can use the "random_seed" option:

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

Since this all runs on the standard Perl srand(), the usual caveat applies: use it sparingly, and honestly consider just doing a single srand() call up at the top level of your app instead. 💅

The default random distribution of edges is flat — meaning any pair of vertices is equally likely to show up. Wanna define your own distribution? That's what the random_edge option is for:

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

where d is a code reference that receives ($g, $u, $v, $p) as its parameters — $g is the random graph, $u and $v are the vertices, and $p is the probability ([0,1]) for a flat distribution. It has to return a probability ([0,1]) that vertices $u and $v have an edge between them. 🫶

Heads up bestie: returning one for a particular pair of vertices doesn't guarantee that the edge will actually be in the resulting graph, because the required number of edges might be reached before that specific pair ever gets tested for the possibility of an edge. So be very careful to also adjust edges or edges_fill so there's a possibility of the filling process terminating. Don't get caught in an infinite loop, that's not the vibe. 😭
NOTE: a known problem with randomness in openbsd pre-perl-5.20 is that using a seed does not give you deterministic randomness. This affects any Perl code, not just Graph.

✨ Attributes ✨

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

But ngl — attaching attributes does slow down some other operations on the graph by a factor of three to ten. For example, adding edge attributes slows down anything that walks through all the edges. So like, know that going in. 💀

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

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

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, or "undef" if no such vertex.

  • 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're out here using multivertices, use the by_id variants instead:

  • 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 ("_") 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->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, or "undef" if no such edge.

  • 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're out here using multiedges, use the by_id variants instead:

  • 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 handling transparently graphs that are either "multiedged" or not:

  • get_edge_attribute_all

To get all values of a given attribute for a given edge, use "get_edge_attribute_all":

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

This will return all defined values for that edge and attribute, whether the graph is "multiedged" or not. This will be in no particular order. This is useful for path-weight calculation. ⭐

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

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.

💖 Weighted 💖

As convenient shortcuts, these methods add, query, and manipulate the attribute "weight" with the specified value to the respective Graph elements. So handy fr fr. ✨

  • 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 they're structurally the same graph — the only difference being that the vertices might have been renamed or substituted. It's giving "same energy, different name". 👑

For example, in the example below $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 checking of of all the possibilities (with possible optimization tricks, of course, but brute force still rules at the end of the day). 😭💀

okay so 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 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 LC. A set of measures of centrality based on betweenness. 1977.
https://www.scribd.com/document/580201172/A-Set-of-Measures-of-Centrality-Based-on-Betweenness

and in

Newman MEJ. A measure of betweenness centrality based on random walks. 2003.
http://arxiv.org/pdf/cond-mat/0309045

The implementation is based on the algorithm from:

Brandes U. A faster algorithm for betweenness centrality. 2000.
https://doi.org/10.1080/0022250X.2001.9990249.
  • 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, https://web.archive.org/web/20120616204225/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.

Returns an empty list (and therefore undefined in scalar context) if the graph has no vertices.

  • connected_subgraphs
@s = $g->connected_subgraphs;

Returns all connected subgraphs of $g.

  • subgraph_by_radius
$s = $g->subgraph_by_radius(@v, $radius);

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

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

  • expect_acyclic
  • expect_dag
  • expect_directed
  • expect_hyperedged
  • expect_multiedge
  • expect_multiedged
  • expect_multivertex
  • expect_multivertexed
  • expect_no_args
  • expect_non_multiedge
  • expect_non_multiedged
  • expect_non_multivertex
  • expect_non_multivertexed
  • expect_non_unionfind
  • expect_undirected

In many algorithms it is useful to have a value representing the infinity. The Graph provides (and itself uses):

  • Infinity — (Not exported, use Graph::Infinity explicitly)

📏 Size Requirements 📏

A graph takes up at least 1172 bytes of memory.

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

Hypergraphs are graphs with hyperedges.

To enable hyperness when constructing Graphs use the "hyperedged" attribute:

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

To test for hyperness of a graph use the

  • is_hyperedged
  • hyperedged
$g->is_hyperedged
$g->hyperedged

Edges in hypergraphs are either directed or undirected, as with simple graphs. If undirected, the edge is a blob of 0 or more vertices. For directed, the set of heads and set of tails are also possibly empty. In general, hypergraphs are simply generalisations of simple-graph ideas, with some of the arbitrary limitations removed.

For more information on directed hypergraphs, see Directed Hypergraphs and Applications, Gallo-Longo-Pallottino-Nguyen <https://doi.org/10.1016/0166-218X%2893%2990045-P>. It defines hyperarcs (directed edges in a hypergraph) as ordered pairs of subsets of V, and hyperedges (undirected) as single subsets of V. Since sets are unordered and elements within them are unique, this implies that the only valuable use for hypergraphs is where in a given connection entity (edge or arc), each vertex only appears at most once. Additionally, how the "hyper" property of edges works may change. The underpinning notion is that each edge will be considered an entry in an incidence matrix (dimensions |V| x |E|), with values of either (0, 1=participating) for undirected (hyperedges), or (-1=tail, 0, 1=head) for directed (hyperarcs) against each vertex.

An extension to this is that to extend directed multigraphs with self-loops (aka "quivers") to hypergraphs, the incidence-matrix values will instead be a bitfield, with bit 0 being participation in the tail, and bit 1 in the head.

🩺 DIAGNOSTICS 🩺

  • 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/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.

  • Deep recursion on subroutine "Graph::_biconnectivity_dfs" at ...

If you have more than 100 vertices, the recursive algorithm will trigger Perl's recursion protection. If you set environment variable "GRAPH_ALLOW_RECURSION" to a true value, this protection will be disabled, e.g.:

$ GRAPH_ALLOW_RECURSION=1 perl -Ilib util/grand.pl --test=bcc 101

🙏 ACKNOWLEDGEMENTS 🙏

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 algorithms 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

👀 SEE ALSO 👀

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

👑 AUTHOR 👑

Jarkko Hietaniemi jhi@iki.fi

Now being maintained by Neil Bowers <neilb@cpan.org>

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

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

and that's a wrap! this page is from perl v5.40.1, dated 2025-03-28, and it's the Graph(3pm) man page 💖✨

📦 where this page comes from