NAME
Graph::Simple  simple and intuitive interface for manipulating graph
VERSION
version 0.04
DESCRIPTION
In computer science, a graph is an abstract data type that is meant to implement the graph and hypergraph concepts from mathematics.
A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges, of certain entities called vertices. As in mathematics, an edge (x,y) is said to point or go from x to y.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.) most oftenly refered to as the weight of the edge.
See Wikipedia for more details about the theory.
This class provides an easy to use and intuitive API for manipulating graphs in Perl. It's a native Perl implementation based on Moo.
ATTRIBUTES
is_weighted
Boolean flag to tell if the graph is weighted
is_directed
Boolean flag to tell if the graph is directed
METHODS
vertices
Return the array of vertices
my @vertices = $g>vertices;
add_edge
Adds a new edge to the graph, and add the corresponding vertices. Note that on undirected graphs, adding u,v also adds v,u.
$g>add_edge("Foo", "Bar");
On weighted graph, it's possible to pass the weight of the edge as a third argument
$g>add_edge("Foo", "Bar", 3);
delete_edge
$g>delete_edge(x, y)
Removes the edge from x to y, if it is there.
neighbors
my @neighbors = $g>neighbors('u');
Lists all vertices y such that there is an edge from x to y.
weight
Accessor to the weight of the edge. If called with two arguments, return the value previously set, with three arguments, set the weight:
# reader
my $w = $g>weight('u', 'v');
# setter
$g>weight('u', 'v', 42);
is_adjacent
$g>is_adjacent(x, y)
Tests whether there is an edge from node x to node y.
breadth_first_search
Performs a BFS traversal on the graph, returns the parents hash produced.
Callbacks can be given to trigger code when edges or vertices are discovered/processed.
$g>breadth_first_search($vertex,
cb_vertex_discovered => sub { print "discovered vertex @_" },
cb_vertex_processed => sub { print "processed vertex @_" },
cb_edge_discovered => sub { print "new edge: @_" });
depth_first_search
Performs a DFS traversal on the graph, returns the parents hash produced.
Callbacks can be given to trigger code when edges or vertices are discovered/processed.
$g>breadth_first_search('Foo',
cb_vertex_discovered => sub { print "discovered vertex @_" },
cb_vertex_processed => sub { print "processed vertex @_" },
cb_edge_discovered => sub { print "new edge: @_" },
);
prim
Implementation of the Prim algorithm to grow a Minimum Spanning Tree of the graph.
Return the tree produced (as a Graph::Simple
object).
my $mst = $g>prim('Foo');
dijkstra
Implementation of the Dijkstra algorithm to find all possible shortest paths from a vertex $s
to all other vertices of the graph.
The return value of this method is a hashref containing the following entries:
 spanning_tree

A Graph::Simple object representing the minimum spanning tree produced by the Dijkstra traversal.
 distances

An hashref containing for each vertices the distance between that vertex and the source vertex.
my $dijkstra = $g>dijkstra('E');
shortest_path
Return the shortest path between two vertices as a list of vertices.
my @path = $g>shortest_path('A', 'E');
# eg: ( 'A', 'D', 'F', 'E' )
Note that internally, this method uses the spanning tree produced by the Dijkstra algorithm to compute the shortest path.
SYNOPSYS
my $g = Graph::Simple>new ( is_directed => 1, is_weighted => 1);
$g>add_edge( 'Al', 'Bob', 2 );
$g>add_edge( 'Al', 'Jim', 3 );
$g>add_edge( 'Joe', 'Jim', 3 );
$g>neighbors('Al');
SEE ALSO
This distribution has been written because when I looked on CPAN for an easy to use and lightweight interface for manipulating graphs in Perl, I dind't find something that fitted my expectations.
Other distributions exist though:
 Graph

A rather featurerich implementation but with a complex API.
 Graph::Fast

Less features than Graph but presumably faster. Appears to be unmaintained since 2010 though.
 Graph::Boost

Perl bindings to the C++ graph library Boost. Certainly the fastest implementation but depends on C++, obviously.
AUTHOR
Alexis Sukrieh <sukria@sukria.net>
COPYRIGHT AND LICENSE
This software is copyright (c) 2013 by Alexis Sukrieh.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.