NAME

Graph::MoreUtils - utilities for graphs

SYNOPSIS

use Graph::MoreUtils qw( SSSR line smooth );
use Graph::Undirected;

my $G = Graph::Undirected->new;

# Greate graph here

# Get line graph for $G:
my $L = line( $G );

SSSR( $graph, $max_depth )

Finds the Smallest Set of Smallest Rings (SSSR) in Graph objects. Thus it should work with any Graph::Undirected object. The code is largely taken from the cod-tools package (https://wiki.crystallography.net/cod-tools/).

The algorithm returns a superset of minimum cycle basis of a graph in order to produce deterministic results. As a result it does not succumb to the counterexample of oxabicyclo[2.2.2]octane (https://depth-first.com/articles/2020/08/31/a-smallest-set-of-smallest-rings/, section "SSSR and Uniqueness"). The algorithm has means to control the maximum size of rings included in the SSSR to reduce its complexity. The default value of undef stands for no limit.

line( $graph )

Generates line graphs for Graph::Undirected objects. Line graph is constructed nondestructively and returned from the call. Both simple and multiedged graphs are supported.

Call accepts additional options hash. Currently only one option is supported, loop_end_vertices, which treats the input graph as having self-loops on pendant vertices, that is, increasing the degrees of vertices having degrees of 1. Thus they are not "lost" during line graph construction. In the resulting line graph these self-loops are represented as instances of Graph::MoreUtils::Line::SelfLoopVertex.

smooth( $graph )

Smooths the given graph by collating vertices of degree 2.

SEE ALSO

perl(1)

AUTHORS

Andrius Merkys, <merkys@cpan.org>