/ 
Boost-Graph-1.1
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);

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

Input Parameters:
- 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.

Usage: 
$graph->add_edge(node1=>$node1, node2=>$node2, weight=>$weight, edge=>$edge);

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

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

get_nodes()

Returns a reference to a list of all the nodes.

has_edge($node1,$node2)

Returns 1 if the given edge is in the graph.

has_node($node)

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

nodecount()

Returns the number of nodes in the graph.

edgecount()

Returns the number of edges in the graph.

neighbors($node)

Returns the nodes that are neighbors of this node.

children_of_directed($node)

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

parents_of_directed($node)

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

Graph Algorithms

breadth_first_search($start_node)

Receives the start node and returns a listref of nodes from a breadth first traversal of the 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($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($start_node,$end_node)

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.

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.