view release on metacpan or  search on metacpan

lib/Graph/Layouter/Spring.pm  view on Meta::CPAN

Graph::Layouter::Spring - spring graph drawing algorithm implementation

=cut


package Graph::Layouter::Spring;

use strict;
use Carp qw (croak);

use vars qw ($VERSION @ISA @EXPORT_OK);

# $Id: Spring.pm,v 1.8 2006/02/11 17:11:39 pasky Exp $
$VERSION = 0.03;


=head1 SYNOPSIS

  use Graph::Layouter::Spring;
  Graph::Layouter::Spring::layout($graph);

=cut


use base qw (Graph::Layouter);

require Exporter;
push @ISA, 'Exporter';

@EXPORT_OK = qw (layout);


=head1 DESCRIPTION

This module provides the famous spring graph drawing algorithm implementation.
See the C<Graph::Layouter> class documentation for usage description.

=cut


use Graph;
use Graph::Layouter;

=head2 How does it work

The algorithm is principially simple, simulating a space of electrically
charged particles. Basically, each node is thought of as a particle with the
same charge, therefore they all try to get as far of each other as possible. On
the other hand, though, there are the edges, which keep nodes together; higher
weight the edges have, stronger are they in pulling nodes near each other.

So to recapitulate, we have I<repulsive force> pushing nodes from each other
and I<attractive force> pushing connected nodes near each other. We then just
apply the repulsive force between each two nodes and the attractive force
between each two connected nodes; each node will have a resulting movement
force, which we will apply to the node's position (initially randomzero-zero)
after the forces calculation is finished.

However, we need to let this repeat for several times in order for the
positions to stabilize. In fact, a lot of iterations is needed; higher the
better, but also higher the slower, you can very easily get to tens of seconds
here so beware. Currently, the number of iterations is hardcoded to 500, but
this is expected to get configurable soon.

=cut

# TODO : _This_ should be all adjustable!

my $iterations = 100; # undef for no iterations limit
my $max_wait = 10; # (in seconds) undef for no time limit
my $max_repulsive_force_distance = 6;
my $k = 2;
my $c = 0.01;
my $max_vertex_movement = 0.5;

sub layout {
	my $graph = shift;

	Graph::Layouter::_layout_prepare($graph);

	# Cache
	my @vertices = $graph->vertices;

	# Bound execution based on time
	my $end;
	$end = time + $max_wait if defined $max_wait;

	unless (defined $end or defined $iterations) {
		croak "You did not bound the layouting loop by either time or iterations count!";
	}

	for (my $i = 0;
	     (defined $iterations ? $i < $iterations : 1)
	     	and (defined $end ? time <= $end : 1);
	     $i++) {
		_layout_iteration($graph, \@vertices);
	}

	Graph::Layouter::_layout_calc_bounds($graph);
}


sub _layout_repulsive($$$) {
	my ($graph, $vertex1, $vertex2) = @_;

	my $dx = $graph->get_vertex_attribute($vertex2, 'layout_pos1') -
	         $graph->get_vertex_attribute($vertex1, 'layout_pos1');
	my $dy = $graph->get_vertex_attribute($vertex2, 'layout_pos2') -
	         $graph->get_vertex_attribute($vertex1, 'layout_pos2');

	my $d2 = $dx * $dx + $dy * $dy;
	if ($d2 < 0.01) {
		$dx = rand (0.1) + 0.1;
		$dy = rand (0.1) + 0.1;
		$d2 = $dx * $dx + $dy * $dy;
	}

	my $d = sqrt $d2;
	if ($d < $max_repulsive_force_distance) {
		my $repulsive_force = $k * $k / $d;

		# Now, how simple and clear would this be without the silly
		# encapsulation games...

		$graph->set_vertex_attribute($vertex2, 'layout_force1',
			$graph->get_vertex_attribute($vertex2, 'layout_force1')
			+ $repulsive_force * $dx / $d);
		$graph->set_vertex_attribute($vertex2, 'layout_force2',
			$graph->get_vertex_attribute($vertex2, 'layout_force2')
			+ $repulsive_force * $dy / $d);

		$graph->set_vertex_attribute($vertex1, 'layout_force1',
			$graph->get_vertex_attribute($vertex1, 'layout_force1')
			- $repulsive_force * $dx / $d);
		$graph->set_vertex_attribute($vertex1, 'layout_force2',
			$graph->get_vertex_attribute($vertex1, 'layout_force2')
			- $repulsive_force * $dy / $d);
	}
}

sub _layout_attractive($@) {
	my ($graph, $vertex1, $vertex2) = @_;

	my $dx = $graph->get_vertex_attribute($vertex2, 'layout_pos1') -
	         $graph->get_vertex_attribute($vertex1, 'layout_pos1');
	my $dy = $graph->get_vertex_attribute($vertex2, 'layout_pos2') -
	         $graph->get_vertex_attribute($vertex1, 'layout_pos2');

	my $d2 = $dx * $dx + $dy * $dy;
	if ($d2 < 0.01) {
		$dx = rand (0.1) + 0.1;
		$dy = rand (0.1) + 0.1;
		$d2 = $dx * $dx + $dy * $dy;