/ 
Graph-Simple-0.04
River stage zero No dependents
/ Graph::Simple

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.

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: @_" });

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 feature-rich 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.