/ 
Boost-Graph-1.4
River stage zero No dependents
/ Boost::Graph

NAME

Boost::Graph - Perl interface to the Boost-Graph C++ libraries.

SYNOPSIS

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);

ABSTRACT

Boost::Graph is a perl interface to the Boost-Graph C++ libraries that offer
many efficient and peer reviewed algorithms.

DESCRIPTION

Boost::Graph is a perl interface to the Boost-Graph C++ libraries that offer many efficient and peer reviewed algorithms.

INSTALLATION

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/

Methods

new [Constructor]

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);

Accessors

add_edge

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.

add_node

$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.

get_edges

$graph->get_edges();

Returns a reference to a list of edges that are 3 part lists: [node1, node2, edge_object].

get_nodes

$graph->get_nodes();

Returns a reference to a list of all the nodes.

has_edge

$graph->has_edge($node1,$node2);

Returns 1 if the given edge is in the graph.

has_node

$graph->has_node($node);

Returns 1 if the passed node is in the network (checks for identical object makeup).

neighbors

$graph->neighbors($node);

Returns the nodes that are neighbors of this node.

children_of_directed

$graph->children_of_directed($node);

Returns a listref of the nodes that are children of the input node. For Directed graphs only.

parents_of_directed

$graph->parents_of_directed($node);

Returns a listref of the nodes that are parents of the input node. For Directed graphs only.

nodecount

$graph->nodecount();

Returns the number of nodes in the graph.

edgecount

$graph->edgecount();

Returns the number of edges in the graph.

Paths and Cycles

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.

add_path

$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.

has_path

$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 Algorithms

$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.

dijkstra_shortest_path

$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

all_pairs_shortest_paths_johnson

$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.

all_pairs_shortest_paths_floyd_warshall

$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.

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.

connected_components

$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.

EXPORT

None by default.

SEE ALSO

The Boost Graph Library (BGL): http://www.boost.org/libs/graph/doc/

AUTHOR

David Burdick, <dburdick@systemsbiology.org>

COPYRIGHT AND LICENSE

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.