Boost::Graph - Perl interface to the Boost-Graph C++ libraries.
use Boost::Graph; # Create an empty instance of a Graph my $graph = new Boost::Graph(directed=>0, net_name=>'Graph Name', net_id=>1000); # add edges $graph->add_edge(node1=>'a', node2=>'b', weight=>1.1, edge=>'edge name'); $graph->add_edge(node1=>$node1, node2=>$node2, weight=>2.3, edge=>$edge_obj);
Boost::Graph is a perl interface to the Boost-Graph C++ libraries that offer many efficient and peer reviewed algorithms.
Installation works as with any other CPAN distribution. This package comes bundled with the Boost Graph C++ Library, version 1.33. This allows the package to install without any extra installation steps. However, if you would like to use a different version of Boost, you can edit the following line in Directed/Makefile.PL and Undirected/Makefile.PL to point to your installation:
'INC' => '-I. -I../include -I/usr/local/include/boost-1_33/',
note, the Boost Library location on the example system is located in /usr/local/include/boost-1_33/
See http://www.boost.org/libs/graph/doc/
To add edges and nodes to a graph, you must first instantiate the class using this method.
Input Parameters [Optional]: - directed: set to 1 for a directed graph (edges with source and sink nodes) - net_name: a name for the graph - net_id: an id stored in the object for the graph Returns: An empty instance of the Boost::Graph object Usage: my $graph = new Boost::Graph(); my $graph = new Boost::Graph(directed=>0, net_name=>'Graph Name', net_id=>1000);
The method adds the given nodes and the edge between them to the graph. In and undirected graph, the order of the nodes does not matter. In a directed graph, node1 is the source and node2 is the sink. The edge parameter can be used to store an object along with the pairing. The weight parameter can give a numeric value to the edge (default 1.0).
There are two ways to use this method:
$graph->add_edge($node1,$node2); -- or -- $graph->add_edge(node1=>$node1, node2=>$node2, weight=>$weight, edge=>$edge);
The first method simply adds the edge to the graph with the default weight of 1.0 and no edge object. In a directed graph, the first node is used as the source and the second as the sink. If you would like to specify an edge weight or include an object with the edge, use the named parameter version.
Named Parameters version: - node1: the source node - node2: the sink node - weight: the weight value for the edge (a number) [optional] - edge: an scalar or object to be associated with the edge [optional] Returns: 1 if the edge is new, 0 if edge exists already.
$graph->add_node($node);
Adds the node to the network (only needed for disjoint nodes). Returns 1 if node is new, 0 if node exists already.
$graph->get_edges();
Returns a reference to a list of edges that are 3 part lists: [node1, node2, edge_object].
$graph->get_nodes();
Returns a reference to a list of all the nodes.
$graph->has_edge($node1,$node2);
Returns 1 if the given edge is in the graph.
$graph->has_node($node);
Returns 1 if the passed node is in the network (checks for identical object makeup).
$graph->neighbors($node);
Returns the nodes that are neighbors of this node.
$graph->children_of_directed($node);
Returns a listref of the nodes that are children of the input node. For Directed graphs only.
$graph->parents_of_directed($node);
Returns a listref of the nodes that are parents of the input node. For Directed graphs only.
$graph->nodecount();
Returns the number of nodes in the graph.
$graph->edgecount();
Returns the number of edges in the graph.
Paths and cycles are simple extensions of edges: paths are edges starting from where the previous edge ended, and cycles are paths returning back to the start vertex of the first edge.
$graph->add_path($a, $b, $c, ..., $x, $y, $z)
Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph. Returns the graph.
$graph->has_path($a, $b, $c, ..., $x, $y, $z)
Return true if the graph has all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, false otherwise.
$graph->breadth_first_search($start_node);
Receives the start node and returns a listref of nodes from a breadth first traversal of the graph.
$graph->depth_first_search($start_node);
Receives the start node and returns a listref of nodes from a depth first traversal of the graph.
$graph->dijkstra_shortest_path($start_node,$end_node);
Dijkstra's Shortest Path algorithm finds the shortest weighted-path between the start and end nodes.
Returns a hashref with keys:
- path: path is a listref of the nodes in the path - weight: weight is a scalar giving the total weight of the path
$graph->all_pairs_shortest_paths_johnson($start_node,$end_node);
Johnsons' All pairs shortest paths, computes the shortest path between all nodes. Good for sparce graphs.
The first time this method is called, the shortest path between each pair of nodes in the graph is computed. The total weight of the path between the start and end node is returned. Unless the graph is altered, the original matrix does not need to be re-computed.
$graph->all_pairs_shortest_paths_floyd_warshall($start_node,$end_node);
Floyd-Warshall's All pairs shortest paths, computes the shortest path between all nodes. Good for dense graphs.
$graph->connected_components();
For an undirected graph, returns the nodes of the connected components of the graph as a list of anonymous arrays. The ordering of the anonymous arrays or the ordering of the nodes inside the anonymous arrays (the components) is undefined.
$graph->transitive_links($nodes);
Receives a listref of nodes and returns a listref of nodes that are (disjoint from the input set) transitive connectors of the input set in the current network. The transitive distance is limited to one node. (i.e. given a and c as input, and with edges a-b and b-c, then node b will be returned). Note: Perl Implementation, not part of the BGL.
None by default.
The Boost Graph Library (BGL): http://www.boost.org/libs/graph/doc/
David Burdick, <dburdick@systemsbiology.org>
Copyright 2005 by David Burdick
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
To install Boost::Graph, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Boost::Graph
CPAN shell
perl -MCPAN -e shell install Boost::Graph
For more information on module installation, please visit the detailed CPAN module installation guide.