NAME

Graph::Layout::Aesthetic - A module for laying out graphs

SYNOPSIS

use Graph::Layout::Aesthetic;

$aglo = Graph::Layout::Aesthetic->new($topology, ?$nr_dimensions?);
$aglo->add_force($force ?, $weight?);
@forces = $aglo->forces;
$forces = $aglo->forces;
$aglo->clear_forces;

$nr_dimensions = $aglo->nr_dimensions;
$topology = $aglo->topology;

@old_vertex_coordinates = $aglo->coordinates($vertex?@new_vertex_coordinates?);
$old_vertex_coordinates = $aglo->coordinates($vertex?@new_vertex_coordinates?);
@old_coordinates = $aglo->all_coordinates(?@new_coordinates?);
$old_coordinates = $aglo->all_coordinates(?@new_coordinates?);

@edges = $aglo->increasing_edges;
$edges = $aglo->increasing_edges;

$aglo->zero;
$aglo->randomize(?$size?);
$aglo->jitter(?$distance?);
($min, $max) = $aglo->frame;
($min, $max) = $aglo->iso_frame;
$aglo->normalize;

$aglo->init_gloss($temperature, $end_temperature, $iterations ?,$randomize_size?);
$aglo->step(?$temperature ?, $jitter_size??);
$aglo->pause;
$paused = $aglo->paused;
$aglo->_gloss($end_time);
# Valid parameter keys/value pairs are:
#   begin_temperature => $temperature
#   end_temperature   => $end_temperature
#   iterations        => $iterations
#   hold              => $boolean
#   monitor           => $monitor
#   monitor_delay     => $seconds
$aglo->gloss(%parameters);
@gradient = $aglo->gradient;
$gradient = $aglo->gradient;
$stress = $aglo->stress;

$old_temperature   = $aglo->temperature(?$new_temperature ?, $warn??);;
$old_end_temperature = $aglo->end_temperature(?$new_end_temperature ?,
  						$warn??);
$old_iterations = $aglo->iterations(?$new_iterations?);

$aglo->coordinates_to_graph($graph, %parameters);
# Valid parameter keys/value pairs are:
#   id_attribute  => $string
#   id_attribute  => \%name_to_num
#   pos_attribute => $string
#   pos_attribute => \@strings
#   min_attribute => $string
#   min_attribute => \@strings
#   max_attribute => $string
#   max_attribute => \@strings

Graph::Layout::Aesthetic->gloss_graph($graph, %parameters)
# Valid parameter keys/value pairs are:
#   literal           => $boolean
#   nr_dimensions     => $integer
#   forces            => \%forces
#   begin_temperature => $temperature
#   end_temperature   => $end_temperature
#   iterations        => $iterations
#   hold              => false or 1
#   monitor           => $monitor
#   monitor_delay     => $seconds
#   pos_attribute     => $string
#   pos_attribute     => \@strings

DESCRIPTION

A Graph::Layout::Aesthetic object represents a state in the process of laying out a graph. The idea is that the state is repeatedly modified until an acceptable layout is reached. This is done by considering the current state from the point of view of a number of aesthetic criteria, each of which will provide a step along which it would like to change the current state. A weighted average is then taken of all these steps, leading to a proposed step. The size of this step is then limited using a decreasing parameter (the temperature) and applied. Small random disturbances may also be applied to avoid getting stuck in a subspace.

The package also comes with a simple commandline tool gloss.pl (based on this package) that allows you to lay out graphs.

EXAMPLE1

use Graph::Layout::Aesthetic;
use Graph::Layout::Aesthetic::Monitor::GnuPlot;

# Set up some $topology here, see Graph::Layout::Aesthetic::Toplogy
my $aglo = Graph::Layout::Aesthetic->new($topology);

# Decide what kind of aesthetic properties we want
# We want nodes not to close to each other
$aglo->add_force("node_repulsion");
# We want edge lengths short
$aglo->add_force("min_edge_length");

# Do the actual layout and monitor progress (optional)
$aglo->gloss(monitor => Graph::Layout::Aesthetic::Monitor::GnuPlot->new);

# Display the result
my $i;
for ($aglo->all_coordinates) {
  print "Vertex ", $i++, ": @$_\n";
}

EXAMPLE2

use Graph 0.50;
use Graph::Layout::Aesthetic;

my $g = Graph->new(...);
# set up your graph here

Graph::Layout::Aesthetic->gloss_graph($g,
                                      forces => {
                                          node_repulsion  => 1,
                                          min_edge_length => 1
                                      });
# That's all folks. Vertex positions will be in the "layout_pos" attribute

EXAMPLE3

See gloss.pl (found in the bin/ directory of the Graph::Layout::Aesthetic distribution) for an example of a simple commandline program based on this module. If you have gnuplot you can use the examples documented there to view the kind of layouts you can generate using this module.

METHODS

$aglo = Graph::Layout::Aesthetic->new($topology, ?$nr_dimensions?)

Creates a new Graph::Layout::Aesthetic object that will be used to lay out the graph described by the finished Graph::Layout::Aesthetic::Topology object $topology. The position space for each vertex is assumed to have $nr_dimensions dimensions (defaults to 2 if not given).

Vertices start out without any particular positions (they may not even be valid numbers). You'll have to do some initial placement yourself (notice that gloss already has a randomize built in).

The initial temperature is 1e2, the end_temperature is 1e-3 and the default number of iterations is 1000.

$aglo->add_force($force_name ?, $weight?)

The steps on the Graph::Layout::Aesthetic state are caused by applying forces to the vertices that will supposedly make the graph layout more pleasing. Each application of this method will add a new force named $force_name with weight $weight (defaults to 1) working on the graph vertices.

$force_name has to be a name potentially known to Graph::Layout::Aesthetic::Force. Because this will try to load force modules on demand, force names are first converted to a style more in line with the one used for perl modules by using:

$force_name =~ s/(?:^|_)([[:lower:]])/\u$1/g;

So if you use "node_repulsion" as force name, it will actually try to load Graph::Layout::Aesthetic::Force::NodeRepulsion. This package comes with a number of preprogrammed forces, see Graph::Layout::Aesthetic::Force for a list.

There are no forces defined for a newly created Graph::Layout::Aesthetic object, so you'll have to apply this method one or more times if you want anything to happen.

@forces = $aglo->forces

Returns a list of the forces being applied to $aglo. Each element is a two element array reference consisting of force and weight.

$forces = $aglo->forces

This is the same as

$forces = [$aglo->forces];

$aglo->clear_forces

Forgets about any forces that have been added (for example by using add_force).

$nr_dimensions = $aglo->nr_dimensions

Returns the dimension of the space in which the vertices will be placed.

$topology = $aglo->topology

Returns the Graph::Layout::Aesthetic::Topology object that's being laid out.

@old_vertex_coordinates = $aglo->coordinates($vertex,?@new_vertex_coordinates?)

Returns the $nr_dimensions coordinates of vertex $vertex just before this call.

If @new_vertex_coordinates is given these become the new vertex coordinates. Can be passed as a list of coordinates or as an array reference.

$old_vertex_coordinates = $aglo->coordinates($vertex,?@new_vertex_coordinates?)

This is the same as:

$old_vertex_coordinates = [$aglo->coordinates($vertex,@new_vertex_coordinates)];

If you just wanted to know how many elements are in a coordinate, this would of course be the number of dimensions,

$aglo->nr_dimensions;

@old_coordinates = $aglo->all_coordinates(?@new_coordinates?)

Returns a list of coordinate references just before this call, one for each vertex.

If @new_coordinates is given these become the new coordinates. Can be passed as a list of coordinates or as an array reference.

$old_coordinates = $aglo->all_coordinates(?@new_coordinates?)

This is the same as:

$old_coordinates = [$aglo->all_coordinates(?@new_coordinates?)];

If you wanted to know how many elements there are in the all_coordinates list, that would be the same as the number of vertices,

$aglo->topology->nr_vertices;

@edges = $aglo->increasing_edges

Returns a list of edges, where each edge is a reference to an array of start point and end point. Each point itself again is represented by a reference to its coordinates. The direction of the returned edges is from lower numbered vertex to higher numbered vertex (so it ignores the direction with which the edge was entered into the topology).

This method exists for backward compatibility with the way the original gloss program reported the edge list. For many applications it will probably make more sense to combine the result of $topology->edges with $aglo->all_coordinates.

$edges = $aglo->increasing_edges

This is the same as

$edges = [$aglo->increasing_edges];

$aglo->zero

Sets all coordinates of all vertices to 0.

$aglo->randomize(?$size?)

For every coordinate of every vertex a random number (2*rand()-1)*$size is chosen and assigned (but rand() returning exactly 0 is excluded). $size defaults to 1 if not given.

$aglo->jitter(?$distance?)

Chooses one coordinate of one vertex and displaces it by (rand()*2-1)*$distance (but rand() returning exactly 0 or 0.5 is excluded). $distance defaults to 1e-5.

($min, $max) = $aglo->frame

Calculates the smallest enclosing box of all coordinates. $min will be a reference to minimal values for each coordinate, and $max a reference to maximum values.

($min, $max) = $aglo->iso_frame

Calculates the smallest enclosing box of all coordinates where all box sizes are the same. The box will be symmetrically placed around the box that would be returned by frame. $min will be a reference to minimal values for each coordinate, and $max a reference to maximum values.

$aglo->normalize

Scales and moves all points so that the new iso_frame has minimum [0, 0, ..] and maximum [1, 1,...].

$aglo->init_gloss($temperature, $end_temperature, $iterations?, $randomize_size?)

Sets new values for current (starting) $temperature, $end_temperature and $iterations. If $randomize_size is bigger than 0 (the default is 1) it also does a:

$aglo->randomize($randomize_size);

This method is used before a new or restarted _gloss or to change the initial default values.

$aglo->step(?$temperature ?, $jitter_size??)

Do a single step at temperature $temperature (defaults to $aglo->temperature) and with jitter size $jitter_size (defaults to the minimum of 1e-5 and temperature). A step involves:

$aglo->jitter($jitter_size) if $jitter_size;
Calculate the weighted sum of all aesthetic forces
Limit the size of the displacement the combined force would like to cause to the $temperature if it's bigger (but keep the direction).
Apply the calculated displacement to all vertices

Notice it doesn't change iterations or temperature.

$aglo->pause

Normally the layout methods _gloss and gloss run until there are no more iteration to be done. By calling this method you set a flag telling them to stop as soon as a new step would be taken. The only chance you get to do this is normally during the gloss monitor calbback or during a force gradient call.

The pause flag is implictly cleared at object construction or when you enter _gloss or gloss.

$paused = $aglo->paused

Return true if layout is paused, false otherwise.

$aglo->_gloss(?$end_time?)

A convenience method that repeatedly applies the step method until $end_time is reached, the target number of iterations is reached or the layout gets paused. After each step it changes the temperature in the direction of the end temperature. $end_time defaults to some huge number, so if it's not given the loop will be completely controlled by the target number of iterations. Giving 0 as $end_time will do only one step (including lowering of temperature and iterations left).

_gloss basically equivalent to:

if ($aglo->iterations <= 0) croak("No more iterations left");
my $lambda = ($aglo->temperature / $aglo->end_temperature) ** (1 / $aglo->iterations);
$aglo->paused(0);
while ($aglo->iterations > 0 && !$aglo->paused) {
    $aglo->step;

    $aglo->temperature($aglo->temperature / lambda);
    $aglo->iterations( $aglo->iterations() - 1);

    return if $end_time <= time();
}

$aglo->gloss(%parameters)

This method does a complete graph layout. It first sets temperatures and iterations from the given %parameters (using init_gloss) and randomizes all coordinates (unless requested not to). It then iterates as many times as requested (using _gloss) or until the layout gets paused.

If requested it can also monitor the progress of the layout. This means that at the start and at regular times thereafter (including the end) a given callback gets called which can then do things like display the current configuration. A simple monitor based on gnuplot comes with this package, see Graph::Layout::Aesthetic::Monitor::GnuPlot.

%parameters represents key/value pairs used to pass parameters. Recognized are:

begin_temperature => $temperature

Starting temperature, defaults to 100

end_temperature => $end_temperature

Ending temperature, defaults to 1e-3

iterations => $iterations

Number of iterations requested, defaults to 1000.

hold => $boolean

If given a false value (the default), all vertex coordinates will be randomized before the iterations start. If given a true value, the vertex coordinates will remain what they were before this method call (supposedly because you did some explicit placement before or want to further optimize a previously generated layout).

monitor => $monitor

If given, $monitor will be called once initially and then periodically (and once for the final configuration) like this if it's a CODE reference:

$monitor->($aglo);

and like this if it's an object:

$monitor->plot($aglo);

You can use this to monitor (and optionally pause) the layout progress.

The default is no monitoring.

monitor_delay => $seconds

Indicates that you want the monitor callback activated every $seconds seconds (defaults to 2). The time is checked only at the end of each iteration, so the callbacks can come at a lower rate if your steps take very long. Using 0 as delay will cause the monitor callback to be called after each iteration.

@gradient = $aglo->gradient

Does an aesthetic forces calculation and returns the steps it would like to apply to each vertex (neither jitter nor temperature based limitation will have been applied). It returns a step for each vertex as an array reference to coordinate displacements.

$gradient = $aglo->gradient

This is the same as

$gradient = [$aglo->gradient];

If you just wanted to know how many elements are in the gradient, this would be the same as the number of vertices, so

$aglo->topology->nr_vertices;

$stress = $aglo->stress

Returns the length of the gradient vector in the vertices*dimensions dimensional configuration space. This gives you an idea about how good or bad the current state is.

$old_temperature = $aglo->temperature(?$new_temperature ?, $warn??);

If given a $new_temperature argument, it will set the temperature to that. The temperature will remain unchanged otherwise. If $warn is true (the default), it will complain if you set the temperature to lower than the current end_temperature.

In all cases it will return the temperature as it was just before this call.

$old_end_temperature = $aglo->end_temperature(?$new_end_temperature ?, $warn??)

If given a $new_end_temperature argument, it will set the end_temperature to that. The end_temperature will remain unchanged otherwise. If $warn is true (the default), it will complain if you set the end_temperature higher than the current temperature.

In all cases it will return the end_temperature as it was just before this call.

$old_iterations = $aglo->iterations(?$new_iterations?);

If given a $new_iterations argument, it will set the remaining iterations to that. The number of iterations will remain unchanged otherwise.

In all cases it will return the number of iterations left as it was just before this call.

$aglo->coordinates_to_graph($graph, %parameters)

Copies the current state coordinates of $aglo to vertex attributes of the standard Graph object $graph. It also stores the containing frame as global graph attributes.

%parameters are key/value pairs. Recognized are:

id_attribute => $name

$name is the the $graph vertices attribute that for each vertex identifies the corresponding vertex in $aglo->topology, and defaults to "layout_id". It may also be a hash reference, in which case node ids are looked up in the hash instead of as atrributes in the graph. So this argument is compatible with the id_attribute parameter of the Graph::Layout::Aesthetic::Topology from_graph method.

pos_attribute => $name

$name is the $graph vertices attribute that will be used to set the coordinates and defaults to "layout_pos" if not given at all.

If $name is undef, no vertex attribute will be set.

If $name is a plain string, it will set an attribute with this name on each vertex. The value will be an array reference to the coordinates of that vertex.

If $name is an array of names (size equal to the number of dimensions of the layout space), then for each vertex it will set an attribute for each element in $name whose value will be the corresponding coordinate component. So if for example you want your $graph nodes to have an attribute "layout_pos1" for the first coordinate and "layout_pos2" for the second (this is what Graph::Layouter uses and Graph::Renderer expects) you could use:

$aglo->coordinates_to_graph($graph,
                            pos_attribute => ["layout_pos1", "layout_pos2"]);
# And now you can get the second coordinate of vertex foo by doing:
my $y = $graph->get_vertex_attribute("foo", "layout_pos2");

min_attribute => $name

$name is the global graph attribute that will be used to set the minimum coordinates for the frame containing all poins (see the frame method and defaults to "layout_min" if not given at all.

Like pos_attribute you can give it an undef value (attribute will not be set), a string (one attribute will be set) or an array reference (an attribute will be set for each string in the array).

max_attribute => $name

$name is the global graph attribute that will be used to set the maximum coordinates for the frame containing all poins (see the frame method and defaults to "layout_max" if not given at all.

Like pos_attribute you can give it an undef value (attribute will not be set), a string (one attribute will be set) or an array reference (an attribute will be set for each string in the array).

So for complete compatibility with Graph::Layouter and Graph::Renderer you can use:

$aglo->coordinates_to_graph($graph,
                            pos_attribute => ["layout_pos1", "layout_pos2"],
                            min_attribute => ["layout_min1", "layout_min2"],
                            max_attribute => ["layout_max1", "layout_max2"]);

Graph::Layout::Aesthetic->gloss_graph($graph, %parameters)

This call combines the Graph::Layout::Aesthetic::Topology from_graph method, gloss and coordinates_to_graph, effectively giving a one call layout of a standard Graph object.

The parameters are key/value pairs and correspond to the ones from the above mentioned methods:

literal => $boolean

Corresponds to the literal parameter to the Graph::Layout::Aesthetic::Topology from_graph method.

nr_dimensions => $integer

The number of dimensions of the layout space. Defaults to 2.

forces => \%forces

Maps force names to weigths. All the forces in %forces will be added with their corresponding weights using add_force internally. (see EXAMPLE2).

begin_temperature => $temperature

Starting temperature, defaults to 100. The same as the gloss begin_temperature parameter.

end_temperature => $end_temperature

Ending temperature, defaults to 1e-3 The same as the gloss end_temperature parameter.

iterations => $iterations

Number of iterations requested, defaults to 1000. The same as the gloss iterations parameter.

hold => $boolean

The same as the gloss hold parameter meaning no randomization is done if given a true value (default is false). In the case the boolean is 1, the initial coordinates are retrieved from the same attributes as where the results will be set (see the pos_attribute parameter.

If the true value is not 1, it will behave in the same sort of way as the pos_attribute parameter parameter: if given a string, that will be the attribute containing the starting coordinates, if it's an array reference, the strings in there will correspond to the components of the starting coordinates. So you can do something like this:

# Set up starting coordinates of vertex_0
$graph->set_vertex_attribute("vertex_0", "x_start", 1);
$graph->set_vertex_attribute("vertex_0", "y_start", 1);
# Set the other vertices too
...

# Do layout
Graph::Layout::Aesthetic->gloss_graph($graph,
                                      hold => ["x_start", "y_start"],
                                      pos_attribute => ["x_end", "y_end"],
                                      forces => {
                                          min_edge_length => 1,
                                          node_repulsion  => 1,
                                      });

printf("The final coordinates of vertex_0 are (%f, %f)\n",
       $graph->get_vertex_attribute("vertex_0", "x_end"),
       $graph->get_vertex_attribute("vertex_0", "y_end"));
# Print the other vertices too
...

monitor => $monitor

The same as the gloss monitor parameter.

monitor_delay => $seconds

The same as the gloss monitor_delay parameter

pos_attribute => $string

The same as the coordinates_to_graph pos_attribute parameter (and also defaults to "layout_pos". It's also the default attribute initial coordinates come from if hold is 1.

min_attribute => $name

The same as the coordinates_to_graph min_attribute parameter.

max_attribute => $name

The same as the coordinates_to_graph max_attribute parameter.

EXPORT

None.

BUGS

Not threadsafe. Different object may have method calls going on at the same time, but any specific object should only have at most one call active. Notice that all forces coming with this package are threadsafe, so it's ok if your different objects use the same forces at the same time.

AUTHOR

Ton Hospel, <Graph-Layout-Aesthetic@ton.iguana.be> for the perl code and the XS wrappers.

Much of the C code is equal to or derived from the original code by D. Stott Parker.

COPYRIGHT AND LICENSE

Much of the C code is copyrighted by D. Stott Parker, who released it under the GNU GENERAL PUBLIC LICENSE (version 1).

To install Graph::Layout::Aesthetic, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Graph::Layout::Aesthetic

CPAN shell

perl -MCPAN -e shell
install Graph::Layout::Aesthetic

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

SYNOPSIS

DESCRIPTION

EXAMPLE1

EXAMPLE2

EXAMPLE3

METHODS

EXPORT

SEE ALSO

BUGS

AUTHOR

COPYRIGHT AND LICENSE

Module Install Instructions