view release on metacpan or  search on metacpan

Graph.pm  view on Meta::CPAN

  my ($path_wt,@node_order) = $self->{_bgi}->dijkstraShortestPath($start_id,$end_id);
  $ret{weight}=$path_wt;
  $ret{path}=$self->_get_node_list(\@node_order);

  return \%ret;
}
#______________________________________________________________________________________________________________
# Johnsons All Pairs Shortest Paths
# returns path weight.
sub all_pairs_shortest_paths_johnson {
  my ($self,$start_node,$end_node) = @_;
  return undef unless $start_node && $self->has_node($start_node) && $end_node && $self->has_node($end_node);
  
  my $ret;
  my $start_id = $self->_get_node_id($start_node);
  my $end_id = $self->_get_node_id($end_node);
  $ret = $self->{_bgi}->allPairsShortestPathsJohnson($start_id,$end_id);

  return $ret;
}
#______________________________________________________________________________________________________________
# Floyd-Warshall All Pairs Shortest Paths
# returns path weight.
sub all_pairs_shortest_paths_floyd_warshall {
  my ($self,$start_node,$end_node) = @_;
  return undef unless $start_node && $self->has_node($start_node) && $end_node && $self->has_node($end_node);
  
  my $ret;
  my $start_id = $self->_get_node_id($start_node);
  my $end_id = $self->_get_node_id($end_node);
  $ret = $self->{_bgi}->allPairsShortestPathsFloydWarshall($start_id,$end_id);

  return $ret;
}
#______________________________________________________________________________________________________________
### Minimum Spanning Tree Algorithms ###
#______________________________________________________________________________________________________________
### Connected Components Algorithms ###
#______________________________________________________________________________________________________________
# Connected Components
sub connected_components {
  my ($self) = @_;
  die "connected_components(...) only for undirected graphs." if $self->{_directed}; 
  
  my @clusters; # list of listrefs that represent the connected clusters
  my @components = $self->{_bgi}->connectedComponents();
  for(my $node_id=0; $node_id<@components; $node_id++) {
    my $cluster = $components[$node_id];
    my $node_obj = $self->{_nodes_lookup}->{$node_id};
    if (defined($node_obj)) {
      push @{ $clusters[$cluster] }, $node_obj;
    }
  }
  shift @clusters if !defined($clusters[0]); # remove empty 0 node (we use non-zero indexing for node ids)
  return \@clusters;
}
#______________________________________________________________________________________________________________


#<link rel="stylesheet" href="http://search.cpan.org/s/style.css" type="text/css">
#<link rel="alternate" type="application/rss+xml" title="RSS 1.0" href="http://search.cpan.org/uploads.rdf">

1;
__END__

=head1 NAME

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

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

=head1 ABSTRACT

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

=head1 DESCRIPTION

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

=head1 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/

=head1 Methods

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

=head3 Accessors