Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Bio::Coordinate::GraphUser Contributed Perl DocumentaBio::Coordinate::Graph(3)

NAME
       Bio::Coordinate::Graph -	Finds shortest path between nodes in a graph.

VERSION
       version 1.007001

SYNOPSIS
	 # get a hash of hashes	representing the graph.	E.g.:
	 my $hash= {
		    '1'	=> {
			    '2'	=> 1
			   },
		    '2'	=> {
			    '4'	=> 1,
			    '3'	=> 1
			   },
		    '3'	=> undef,
		    '4'	=> {
			    '5'	=> 1
			   },
		    '5'	=> undef
		   };

	 # create the object;
	 my $graph = Bio::Coordinate::Graph->new(-graph	=> $hash);

	 # find	the shortest path between two nodes
	 my $a = 1;
	 my $b = 6;
	 my @path = $graph->shortest_paths($a);
	 print join (",	", @path), "\n";

DESCRIPTION
       This class calculates the shortest path between input and output
       coordinate systems in a graph that defines the relationships between
       them. This class	is primarely designed to analyze gene-related
       coordinate systems. See Bio::Coordinate::GeneMapper.

       Note that this module can not be	used to	manage graphs.

       Technically the graph implemented here is known as Directed Acyclic
       Graph (DAG). DAG	is composed of vertices	(nodes)	and edges (with
       optional	weights) linking them. Nodes of	the graph are the coordinate
       systems in gene mapper.

       The shortest path is found using	the Dijkstra's algorithm. This
       algorithm is fast and greedy and	requires all weights to	be positive.
       All weights in the gene coordinate system graph are currently equal (1)
       making the graph	unweighted. That makes the use of Dijkstra's algorithm
       an overkill. A simpler and faster breadth-first would be	enough.
       Luckily the difference for small	graphs is not significant and the
       implementation is capable of taking weights into	account	if needed at
       some later time.

   Input format
       The graph needs to be primed using a hash of hashes where there is a
       key for each node. The second keys are the names	of the downstream
       neighboring nodes and values are	the weights for	reaching them. Here is
       part of the gene	coordiante system graph:

	   $hash = {
		    '6'	=> undef,
		    '3'	=> {
			    '6'	=> 1
			   },
		    '2'	=> {
			    '6'	=> 1,
			    '4'	=> 1,
			    '3'	=> 1
			   },
		    '1'	=> {
			    '2'	=> 1
			   },
		    '4'	=> {
			    '5'	=> 1
			   },
		    '5'	=> undef
		   };

       Note that the names need	to be positive integers. Root should be	'1'
       and directness of the graph is taken advantage of to speed calculations
       by assuming that	downsream nodes	always have larger number as name.

       An alternative (shorter)	way of describing input	is to use hash of
       arrays. See Bio::Coordinate::Graph::hash_of_arrays.

METHODS
   new
   graph
	Title	: graph
	Usage	: $obj->graph($my_graph)
	Function: Read/write method for	the graph structure
	Example	:
	Returns	: hash of hashes grah structure
	Args	: reference to a hash of hashes

   hash_of_arrays
	Title	: hash_of_arrays
	Usage	: $obj->hash_of_array(%hasharray)
	Function: An alternative method	to read	in the graph structure.
		  Hash arrays are easier to type. This method converts
		  arrays into hashes and assigns equal values "1" to
		  weights.

	Example	: Here is an example of	simple structure containing a graph.

		  my $DAG = {
			     6	=> [],
			     5	=> [],
			     4	=> [5],
			     3	=> [6],
			     2	=> [3, 4, 6],
			     1	=> [2]
			    };

	Returns	: hash of hashes graph structure
	Args	: reference to a hash of arrays

   shortest_path
	Title	: shortest_path
	Usage	: $obj->shortest_path($a, $b);
	Function: Method for retrieving	the shortest path between nodes.
		  If the start node remains the	same, the method is sometimes
		  able to use cached results, otherwise	it will	recalculate
		  the paths.
	Example	:
	Returns	: array	of node	names, only the	start node name	if no path
	Args	: name of the start node
		: name of the end node

   dijkstra
	Title	: dijkstra
	Usage	: $graph->dijkstra(1);
	Function: Implements Dijkstra's	algorithm.
		  Returns or sets a list of mappers. The returned path
		  description is always	directed down from the root.
		  Called from shortest_path().
	Example	:
	Returns	: Reference to a hash of hashes	representing a linked list
		  which	contains shortest path down to all nodes from the start
		  node.	E.g.:

		   $res	= {
			     '2' => {
				      'prev' =>	'1',
				      'dist' =>	1
				    },
			     '1' => {
				      'prev' =>	undef,
				      'dist' =>	0
				    },
			   };

	Args	: name of the start node

FEEDBACK
   Mailing lists
       User feedback is	an integral part of the	evolution of this and other
       Bioperl modules.	Send your comments and suggestions preferably to the
       Bioperl mailing list.  Your participation is much appreciated.

	 bioperl-l@bioperl.org			- General discussion
	 http://bioperl.org/wiki/Mailing_lists	- About	the mailing lists

   Support
       Please direct usage questions or	support	issues to the mailing list:
       bioperl-l@bioperl.org

       rather than to the module maintainer directly. Many experienced and
       reponsive experts will be able look at the problem and quickly address
       it. Please include a thorough description of the	problem	with code and
       data examples if	at all possible.

   Reporting bugs
       Report bugs to the Bioperl bug tracking system to help us keep track of
       the bugs	and their resolution. Bug reports can be submitted via the
       web:

	 https://github.com/bioperl/%%7Bdist%7D

AUTHOR
       Heikki Lehvaslaiho <heikki@bioperl.org>

COPYRIGHT
       This software is	copyright (c) by Heikki	Lehvaslaiho.

       This software is	available under	the same terms as the perl 5
       programming language system itself.

perl v5.32.0			  2016-12-15	     Bio::Coordinate::Graph(3)

NAME | VERSION | SYNOPSIS | DESCRIPTION | METHODS | FEEDBACK | AUTHOR | COPYRIGHT

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Bio::Coordinate::Graph&sektion=3&manpath=FreeBSD+12.2-RELEASE+and+Ports>

home | help