NAME

YAGL - Yet Another Graph Library

VERSION

version 0.1

SYNOPSIS

use YAGL;

my $g = YAGL->new;

# Populate the graph with 124 vertices, with randomly allocated
# weighted edges between some of the vertices. The 'p' argument is
# the probability that a given node A will *not* be connected to
# another randomly selected node B.

$g->generate_random_vertices(
    { n => 124, p => 0.1, max_weight => 100_000 } );

# Add vertices to the graph.

$g->add_vertex('abc123');
$g->add_vertex('xyz789');
$g->add_vertex('I_AM_A_TEST');

# Add edges to the graph.  You can store arbitrary attributes on
# edges in hashrefs.

$g->add_edge( 'abc123', 'xyz789', { weight => 1_000_000 } );
$g->add_edge( 'I_AM_A_TEST', 'abc123', { weight => 12345 } );

# Write the graph out to a CSV file.  This file can be read back
# in later with the 'read_csv' method. The CSV format is limited,
# it can only store the following columns:
# node,neighbor,weight,is_directed

$g->write_csv('foo.csv');

# Pick a start and end vertex at random from the graph.

my @vertices = $g->get_vertices;

my $i     = int rand @vertices;
my $j     = int rand @vertices;
my $start = $vertices[$i];
my $end   = $vertices[$j];

# Using breadth-first search, find a path between the start and
# end vertices, if any such path exists.  Otherwise, this method
# returns undef.

my @path;
@path = $g->find_path_between( $start, $end );

# Get a string representation of the graph in the graphviz
# language for passing along to graphviz tools like `dot`.

my $dot_string = $g->to_graphviz;

# Color the vertices

$g->color_vertices;

# Find a Hamiltonian cycle in the graph, if any exist:

$g->hamiltonian_walks(closed => 1, n_solutions => 1);

DESCRIPTION

This library implements a graph data structure, and a number of common algorithms on graphs. It can be used for both directed and undirected graphs. Features include:

Generating random graphs.
Serializing graphs to and from CSV files.
Vertices and edges can have arbitrary attributes associated with them (stored in hashrefs).
Breadth-first search (BFS) to find the shortest path between two nodes.
Depth-first search (DFS).
Find minimum spanning trees of weighted graphs.
List the connected components.
Dijkstra's algorithm for finding the shortest path through a weighted graph.
A general method for exhaustive search with backtracking.
Finding Hamiltonian walks (open and closed) using exhaustive search with backtracking.
Vertex coloring.

For a possibly interesting example, see the file examples/ladders.pl, which is an approximate port to Perl of the LADDERS program from the book The Stanford GraphBase by Donald E. Knuth. It uses Dijkstra's algorithm to build a "word ladder" of the form:

WORDS - WOODS - GOODS - GOADS - GRADS - GRADE - GRAPE - GRAPH

Finally, note that this library is still in development. There are some important algorithms that are not yet implemented. Also, some algorithms that are implemented for undirected graphs are not yet implemented for directed graphs. Test coverage is OK, but can still be improved.

METHODS

INITIALIZATION AND RANDOMIZATION

new

Initialize a new undirected graph:

my $g = YAGL->new;

To make a directed graph, set the is_directed argument:

my $g = YAGL->new(is_directed => 1);

Note that a YAGL object must be set as directed or undirected when it's created, and it can't be changed later.

generate_random_vertices

Generate n vertices with random names, and distribute edges randomly among them with a 1-p probability of connection. Further, assign random weights to each edge up to the value of max_weight.

Note that this needs to be called on a graph object that already exists. Also, it is usually best to call this on a brand new, empty graph, since it will overwrite or update existing vertices and edges if the random vertex name generator comes up with a name that is already in use. This is unlikely in practice since the random names are alphanumeric gibberish like "cu991".

Example:

my $g = YAGL->new;
$g->generate_random_vertices({n => 48, p => 0.1, max_weight => 1000});

Arguments:

n: Number of vertices.
p: Probability that a given vertex A will not be connected to another randomly selected vertex B. In other words, the probability that A will be connected to B is 1-p.
max_weight: All edges are given a random integer weight less than or equal to this number.

SERIALIZATION

write_csv

Write a CSV representation of this graph out to a (named) file.

read_lst

Read in a *.lst file that represents a graph (from https://hog.grinvin.org).

read_hcp

Read in a *.hcp file that represents a graph (from https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/fhcp-challenge-set).

read_csv

Read in a CSV file that represents a graph.

to_graphviz

Generate a Graphviz representation of this graph (really, a string).

draw

Given a file name, dumps a representation of the graph (as GraphViz) and uses dot to build an image of the graph. All of this happens in $TMPDIR. This assumes you have a copy of dot on your system.

$g->draw('24-ham-00');
# To view the file, open $TMPDIR/24-ham-00.jpg

BOOLEAN METHODS

is_empty

Returns true if the graph is empty - that is, if it has no vertices.

is_complete

Return true if this is a complete graph. A complete graph is one wherein each vertex is connected to every other vertex.

is_tree

Return true if this graph is a tree. A graph is a tree if its number of edges is one fewer than its number of vertices. This definition is taken from Even's book Graph Algorithms.

is_connected

Return true if for each vertex A in this graph, there is a path between A and every other vertex in the graph.

has_cycle

Return true if there is a cycle in this graph; in other words, if this graph is not a tree.

is_colored

Return true if this graph has already been colored using the color_vertices method.

is_directed

Return true if this is a directed graph. Graphs can only be marked as directed during object initialization, by setting the is_directed argument to new.

is_bipartite

Returns true if the graph G is bipartite. False otherwise.

Note that this method operates on a copy of the graph, to avoid overwriting any existing vertex colorings.

METHODS ON VERTICES

add_vertex

Add a vertex V to this graph, if it does not already exist. Return undef if V already exists.

$g->add_vertex('s');

add_vertices

Add multiple vertices to this graph. Takes an array as its argument.

my @to_add = qw/a b c d e f/;
$g->add_vertices(@to_add);

get_neighbors

Given a vertex in the graph, get its neighbors - that is, the other vertices to which it is connected.

$g->get_neighbors('s');

has_vertex

Return true if the vertex in question is a part of the graph.

$g->has_vertex('a');

remove_vertex

Remove the named vertex from the graph, if it exists.

$g->remove_vertex('s');

Note that removing a vertex will also delete all edges (and edge attributes) between the given vertex and its former neighbors.

get_vertices

Return a list of the vertices in the graph.

my @v = $g->get_vertices;

get_degree

Given a vertex V, return the degree of that vertex -- that is, the number of edges between V and other vertices (its neighbors).

set_vertex_attribute

Given a vertex V, store a hashref of attributes about that vertex.

get_vertex_attribute

Given a vertex V and an attribute string, retrieve the value of that attribute.

my $weight = $g->get_vertex_attribute('s', 'weight');
# 123

get_vertex_attributes

Given a vertex V, return all of the vertex's attributes, whatever they are. Reads from the object's internal hashref, so beware: these values could be anything.

my $attrs = $g->get_vertex_attributes('s');

delete_vertex_attributes

Given a vertex V, delete all of its attributes (if any).

$g->delete_vertex_attributes('s');

set_vertex_color

Given a vertex V and some color C, sets a 'color' attribute on V. Shorthand for using set_vertex_attribute.

$g->set_vertex_color('s', 'red');

get_vertex_color

Given a vertex V, get its color (if any). Shorthand for calling get_vertex_attribute.

$g->get_vertex_color('s');

METHODS ON EDGES

get_edge

Get the edge between two vertices, A and B. Return undef if no such edge exists. If the edge does exist, return an array reference containing A, B, and a (possibly empty) hash reference of edge attributes.

my $edge = $g->get_edge('s', 'a');

get_edges

Get a list containing all of the edges in the graph. Specifically, this will be a list of array references, with the contents of each array reference as described in the documentation for get_edge().

my @edges = $g->get_edges;

edge_between

Given two vertices A and B, return something truthy if there exists an edge between A and B. Otherwise, return undef.

if ($g->edge_between('s', 'a')) {
  say 'Yes';
}

get_edge_attributes

Given two vertices A and B that have an edge between them, return whatever attributes are stored for that edge. Note that this can be any arbitrary Perl data structure that could be stored in a hash reference.

get_edge_attribute

Given two vertices A and B that have an edge between them, and a specific (text) attribute T, return whatever values are associated with T for that edge. For example, a (numeric) weight.

my $edge_weight = $g->get_edge_attribute('s', 'a', 'weight');

get_edge_weight

Shortcut for the following call to get_edge_attribute().

my $edge_weight = $g->get_edge_attribute('s', 'a', 'weight');

set_edge_attribute

Given two vertices A and B that have an edge between them, store a specific attribute key-value pair (a hash reference) that you want to associate with that edge.

my $edge_weight = $g->set_edge_attribute('s', 'a', { weight => 123 });

delete_edge_attributes

Given two vertices A and B that have an edge between them, delete all of the attributes (weight, color, etc.) associated with that edge.

$g->delete_edge_attributes('s', 'a');

add_edge

Given two vertices A and B, add an edge between them, as well as a hash reference containing any attributes that should be associated with that edge. Note that if either of the vertices do not yet exist, they will be created.

$g->add_edge('s', 'a', { name => 'my great edge'});

add_edges

Given a list of array references that describe vertices in the format

[['a', 'b', { weight => 123 }], ... ]

add all of the edges listed, as well as the attributes that should be associated with each edge. Note that if either of the vertices do not yet exist, they will be created.

$g->add_edge('s', 'a', { name => 'my great edge'});

remove_edge

Given two vertices A and B, remove the edge (if any) between them, as well as any associated attributes.

$g->remove_edge('s', 'a');

SEARCH

dijkstra

Given two vertices START and END on a graph with weighted edges, find the shortest path between them using Dijkstra's algorithm.

$g->dijkstra($a, $b);

has_walk

Given a list of vertices, determine whether they constitute a walk. Given an optional argument, will determine if it is a closed walk.

$walk = qw/a f d b c e l m j k i h g/;
$g->has_walk($walk, {closed => 1});

paths_between

Given two vertices START and END, return a list of all the paths between them.

Note that this method is implemented using exhaustive search, so it will grind to a halt for larger graphs.

find_path_between

Given two vertices START and END in an unweighted graph, find the shortest path between them using breadth-first search.

mst

The mst method finds the minimum spanning tree of the current graph object. As such, it takes no arguments; instead, it searches for the lowest-weight edge in the graph, chooses a vertex from one end of that edge as the starting vertex, and builds the spanning tree from there.

dfs

The dfs method performs depth-first-search on the graph beginning at the vertex START; for each vertex visited by the search, invoke $sub.

connected_components

The connected_components method returns the connected components of the graph, as a list of lists.

If there are no connected components, it will return an empty list:

[]

If there is only one connected component, it will return a list with one element: a list of the vertices of the connected component:

[['a', 'b', 'c', 'd']]

If there are n connected components, it will return a list with n elements:

[['a', 'b'], ['c', 'd'], ['e', 'f', 'g']]

exhaustive_search

The exhaustive_search method performs an exhaustive search of all trees in the graph. The way this works is very close to the algorithm for depth-first-search, except that exhaustive_search unmarks the vertices it has visited after the recursive self-call; this is described in more detail on p.623 of Sedgewick's Algorithms, 2nd ed.

It takes two arguments: the name of the starting vertex, and an optional subroutine argument.

$g->exhaustive_search('a', sub { say $_[0] });

hamiltonian_walks

The hamiltonian_walks method does an exhaustive search to find all of the open or closed Hamiltonian walks on the graph, if they exist. It takes an optional closed argument to determine which type to look for.

$g->hamiltonian_walks(closed => 1);
$g->hamiltonian_walks;      # Finds open walks by default.

is_planar

The is_planar method tests whether a graph is planar.

CLONING (OBJECT COPYING) AND EQUALITY CHECKS

clone: Given a graph object, the clone method makes a fresh copy of that object.

INTERNAL HELPER METHODS

_array_eq: Given two array references, are their contents equal? NB. Only works on flat, non-nested arrays.
_memberp: Given a string element and an array, return true if the element is in the array.
_add_neighbor: The _add_neighbor method is the internal helper used to add an edge (and any edge attributes) between two vertices.
_remove_neighbor: The _remove_neighbor method is an internal helper used for deleting an edge between two vertices.
_st_walk: The _st_walk method is used internally for building walks (paths) along spanning trees, such as are built inside find_path_between and dijkstra.
_edge_attrs: The _edge_attrs method is an internal helper that returns all of the graph's edge attributes.
_vertex_attrs: The _vertex_attrs method is an internal helper that returns all of the graph's vertex attributes.
_make_vertex_name: The _make_vertex_name method is used to generate random vertex names, such as when generating random graphs.

COLORING

get_color_degree

The get_color_degree method returns the "color degree" of a vertex: that is, how many colors its neighbors have.

color_vertices

The color_vertices method colors the vertices of the graph using the algorithm due to Brelaz, as described in Skiena, Implementing Discrete Mathematics. Specifically:

1. Number the colors from 1 to k.
2. Color the vertex of largest degree with color 1.
3. Then repeatedly select the vertex with highest color degree, where the color degree is the number of adjacent vertices which have already been colored, and color it with the smallest possible color.

uncolor_vertices

The uncolor_vertices method "uncolors" every vertex in the graph by setting its color attribute to undef.

vertex_colors

The vertex_colors method returns a list containing each vertex and its color.

chromatic_number

The chromatic_number method does not actually return the chromatic number. It returns the number of colors that were used to color the vertices of the graph using the color_vertices method.

set_cover

_covers_all_items

del

_disjoint

get_anti_neighbors

complement

REFERENCES

Even, Shimon. Graph Algorithms.
Skiena, Steven. Implementing Discrete Mathematics.
Sedgewick, Robert. Algorithms, 2nd ed.

BUGS

Undoubtedly! Please file any issues at https://github.com/rmloveland/YAGL.

AUTHOR

Richard Loveland <r@rmloveland.com>

COPYRIGHT AND LICENSE

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

To install YAGL, copy and paste the appropriate command in to your terminal.

cpanm

cpanm YAGL

CPAN shell

perl -MCPAN -e shell
install YAGL

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)