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

FreeBSD Manual Pages


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

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

       version 1.007001

	 # 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";

       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.

	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

	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

	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

	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

	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

   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.			- General discussion	- About	the mailing lists

       Please direct usage questions or	support	issues to the mailing list:

       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

       Heikki Lehvaslaiho <>

       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)


Want to link to this manual page? Use this URL:

home | help