=head1 NAME

Graph::Layouter - lay out graph onto an abstract plane

=cut


package Graph::Layouter;

use strict;
use Carp qw (croak);

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

# $Id: Layouter.pm,v 1.2 2004/04/06 15:24:14 pasky Exp $
$VERSION = 0.02;


=head1 SYNOPSIS

  my $graph = new Graph;
  ...

  use Graph::Layouter;
  my $layouted = Graph::Layouter::layout($graph);

  use Graph::Layouter qw(layout);
  my $layouted = layout($graph);

  use Graph::Layouter;
  my $layouted = Graph::Layouter->layout($graph);
  ...
  $layouted->layout();

=cut


use base qw (Graph);

require Exporter;
push @ISA, 'Exporter';

@EXPORT_OK = qw (layout);


=head1 DESCRIPTION

This module provides an abstract class for various algorithms of graph nodes
positioning at a virtual surface. That is, if you have a graph stuffed into a
C<Graph> object, C<Graph::Layouter> will take it and assign each node in the
graph virtual coordinates in a plane.

C<Graph::Layouter> does not do anything besides assigning the coordinates ---
you will need to have the nodes and edges laid out to some real plane on your
own, or use a bundled C<Graph::Renderer> modules family.

This module contains only the abstract class, you will probably want to get an
instance of some particular layouting algorithm instead;
C<Graph::Layouter::Spring> is bundled with this distribution. The general
interface for all the subclasses is described below, but be sure consult also
the particular class' documentation for remarks, special notes and specific
extensions.


=head2 Interface

=over 4

=cut


use Graph;


=item B<layout()>

This subroutine is the only entry point of this module, taking a given graph
and laying it out appropriately. The subroutine can be called in several ways:

=over 4

=item I<Functional interface>

The subroutine can be called as a function (it is not automatically exported,
but you can import it on your own if you really want; see the synopsis above).
It takes one parameter, the C<Graph> class (or any descendant) instance. It
will set the layout back into the graph and return its parameter back for
convenience.

=item I<Class constructor interface>

TODO

=item I<Class method interface>

TODO

=back

=cut

sub layout {
	my $graph = shift;

	croak "Graph::Layouter::layout() called instead of something of a subclass!";
	$graph;
}


# Make sure the appropriate attributes are set up on all the nodes.
#
# This is a private device for subclasses, which are expected to call this in
# layout, when they are just about to start doing the work. Note that some
# subclasses might want to set the attributes to a different initial value or
# so.
sub _layout_prepare($) {
	my $graph = shift;

	foreach my $vertex ($graph->vertices) {
		$graph->set_attribute('layout_pos1', $vertex, 0);
		$graph->set_attribute('layout_pos2', $vertex, 0);
		$graph->set_attribute('layout_force1', $vertex, 0);
		$graph->set_attribute('layout_force2', $vertex, 0);
	}

	$graph;
}

# Calculate the bounding coordinate values (min/max extremes in a given
# dimension) and store them into global graph attributes.
#
# This is a private device for subclasses, which are expected to call this in
# layout, when they are already done with the work.
sub _layout_calc_bounds($) {
	my $graph = shift;

	# Make sure Perl does not emit a metric ton of warnings blab when
	# counting with infinity numbers. Blah.

	local $^W = 0;

	my ($minx, $maxx, $miny, $maxy) = ('Infinity', -'Infinity', 'Infinity', -'Infinity');

	foreach my $vertex ($graph->vertices) {
		my @pos = ($graph->get_attribute('layout_pos1', $vertex),
		           $graph->get_attribute('layout_pos2', $vertex));
		$maxx = $pos[0] if $pos[0] > $maxx;
		$minx = $pos[0] if $pos[0] < $minx;
		$maxy = $pos[1] if $pos[1] > $maxy;
		$miny = $pos[1] if $pos[1] < $miny;
	}

	$graph->set_attribute('layout_min1', $minx);
	$graph->set_attribute('layout_max1', $maxx);
	$graph->set_attribute('layout_min2', $miny);
	$graph->set_attribute('layout_max2', $maxy);
	$graph;
}


=back

=head2 Data encoding

The layouting function saves the layout data (coordinates of nodes) back to the
C<Graph> object, in a form of vertex attributes - C<layout_pos1> and
C<layout_pos2> (C<pos1> is the x dimension, C<pos2> the y dimension; it is
planned to make it possible to layout in three or unlimited number of
dimensions space).

We also provide C<layout_min1>, C<layout_max1> as well as C<layout_min2>,
C<layout_max2> global graph attributes, containing the extreme values in the
respective dimensions. This is usually needed to properly map the virtual
coordinates to some physical points.

If you intend to use C<Graph> attributes in conjunction with the
C<Graph::Layouter>, you are advised not to infrige the C<layout_> namespace. If
you are writing a C<Graph::Layouter> subclass, you are advised to put your
attributes to a C<layout__subclassname_> namespace.


=head1 SEE ALSO

C<Graph>, C<Graph::Renderer>


=head1 BUGS

The object-oriented interface is missing as well as some more universal layout
calling interface (hash parameters).


=head1 COPYRIGHT

Copyright 2004 by Petr Baudis E<lt>pasky@ucw.czE<gt>.

This code is distributed under the same copyright terms as
Perl itself.


=head1 VERSION

Version 0.02

$Id: Layouter.pm,v 1.2 2004/04/06 15:24:14 pasky Exp $

=cut

1;