Graph-Easy
view release on metacpan or search on metacpan
+ allow spaces in set_attribute('size', '9 , 8')
* Node::Cell:
+ add a group() method to make things like $cell->group() easier
* Group:
+ is also a Graph::Easy, to inherit from it (for nesting)
+ find right-most cell for label if "align: right"
+ rename find_label_cell() to _find_label_cell() (is internal use only)
* Graph:
+ add use_class(), and use it instead of hard-coded class names
+ due to bad caching, one couldn't set the node size as class-attribute
+ weaken() is costly and O(N), so avoid it whenever possible.
Graph creation and destroy are now O(1) again. Creating a graph with
N nodes and N-1 edges takes (bench/stress.pl):
N 0.39 0.39 | 0.40 0.40
Create Destroy | Create Destroy
----------------------------|------------------------
4000 0.35 0.23 | 0.31 0.12
8000 0.77 0.68 | 0.61 0.21
16000 1.91 2.26 | 1.19 0.48
32000 9.32 8.02 | 2.32 0.78
* Parser:
* as_html(): reimplement output for edges with 4x4 table cells, including
correct start/end points, label colors. Finally works in all
major browsers and looks better than ever :)
* as_html(): generate graph-table caption from label attribute
* as_html(): correctly handle multi-celled nodes
* as_html(): generated links have class 'l'
* as_ascii(): handle multi-lined labels on edges correctly
* as_ascii(): invisible nodes are 3x3, not 5x3 in minimum size
* don't unnec. load "Heap" and "Heap::Fibonacci"
* Graph: add as_txt_file() as alias for as_txt()
* add weaken() in Edge::Cell to trigger early DESTROY of graphs
* move the ASCII code to Graph::Easy::As_ascii and load it on demand
* Parser: report wrong attribute names/values better
* Parser: allow '$graph = Graph::Easy::Parser->from_text("...")'
* Parser: fix parsing of undirected edges with following nodes/attributes
* Parser: parse "[ A ]\n { ... }" and "[ A ] { ...\n...}" properly
* Parser/Layout: support undirected (arrowless) edges properly
* Layout: set proper flags for bidirectional edges (so they are rendered
correctly (Thanx to Scott Beuker)
* Layout: stop an endless loop in the chain-backtracking code
* Layout: set correctly edge label cells on found A* paths
* as_ascii(): Drawing line crossings now works. Really! Believe me!
* as_ascii(): labels on horizontal edge pieces are now included
* rename "todo/" to "todos/" because case-insensitive OS have problems
with "TODO" and "todo/"...
* layout: move the alarm(0) to where it belongs and propagate
fatal errors to the outside
* Layout: calculating positions needs an int() to have nodes not fall
between the cell-grid
* Node: move the assignment to {id} into new(), so that subclasses
like Graph::Easy::Edge etc get a unique ID, too
* use Scalar::Util's weaken so that the Node's references back to their graph
do not prevent the graph from being freed
* Upon DESTROY, reset the appropriate fields in node/edge objects, so they
can be reused safely in other graphs
* A*: fixed an endless-loop in the path-backtracking code
* adding node clusters as well as managing them is now easier
* No longer uses Graph. We store nodes/edges in a hash in Graph::Easy object
as opposed to the Graph object. In addition we store per-node the edges
this node is involved in. This all results in less code, great speed and
memory improvements (see bench/no_graph.txt): v0.25 uses only about 50% of
the memory as 0.24!
bench/stress.pl view on Meta::CPAN
#!/usr/bin/perl -w
BEGIN
{
use lib 'lib';
$|++;
}
use Scalar::Util qw/weaken/;
use Time::HiRes qw/time/;
use Data::Dumper;
use Graph::Easy;
my $N1 = shift || 5000;
my $N2 = shift || 40000;
my $STEP = shift || 2;
# results
my $RC = [];
bench/stress.pl view on Meta::CPAN
my $old_object;
# create N objects, and "link" them together
for my $i (1..$N)
{
my $o = new_object($i);
$container->{nodes}->{$i} = $o;
$o->{graph} = $container;
weaken($o->{graph});
if ($old_object)
{
my $link = new_link($old_object, $o, $i);
$container->{edges}->{$i} = $link;
$link->{graph} = $container;
{
no warnings;
weaken($link->{graph});
weaken($link->{to}->{graph});
weaken($link->{from}->{graph});
}
}
$old_object = $o;
}
print Dumper($container),"\n" if $N < 10;
}
sub new_object
{
lib/Graph/Easy.pm view on Meta::CPAN
use 5.008002;
use Graph::Easy::Base;
use Graph::Easy::Attributes;
use Graph::Easy::Edge;
use Graph::Easy::Group;
use Graph::Easy::Group::Anon;
use Graph::Easy::Layout;
use Graph::Easy::Node;
use Graph::Easy::Node::Anon;
use Graph::Easy::Node::Empty;
use Scalar::Util qw/weaken/;
$VERSION = '0.76';
@ISA = qw/Graph::Easy::Base/;
use strict;
use warnings;
my $att_aliases;
use Graph::Easy::Util qw(ord_values);
lib/Graph/Easy.pm view on Meta::CPAN
print STDERR "# add_edge '$x->{name}' ($x->{id}) -> '$y->{name}' ($y->{id}) (edge $edge->{id}) ($x -> $y)\n" if $self->{debug};
for my $n ($x,$y)
{
$self->_croak("Cannot add node $n ($n->{name}), it already belongs to another graph")
if ref($n->{graph}) && $n->{graph} != $self;
}
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
weaken($x->{graph} = $self) unless ref($x->{graph});
weaken($y->{graph} = $self) unless ref($y->{graph});
weaken($edge->{graph} = $self) unless ref($edge->{graph});
# Store at the edge from where to where it goes for easier reference
$edge->{from} = $x;
$edge->{to} = $y;
# store the edge at the nodes/groups, too
$x->{edges}->{$edge->{id}} = $edge;
$y->{edges}->{$edge->{id}} = $edge;
# index nodes by their name so that we can find $x from $x->{name} fast
lib/Graph/Easy.pm view on Meta::CPAN
# already exists?
return $no->{$n} if exists $no->{$n};
my $uc = $self->{use_class};
$x = $uc->{node}->new( $x ) unless ref $x;
# store the node
$no->{$n} = $x;
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
weaken($x->{graph} = $self) unless ref($x->{graph});
$self->{score} = undef; # invalidate last layout
$x;
}
sub add_nodes
{
my $self = shift;
lib/Graph/Easy.pm view on Meta::CPAN
my $uc = $self->{use_class};
# make it work with read-only scalars:
my $xx = $x;
$xx = $uc->{node}->new( $x ) unless ref $x;
# store the node
$no->{$n} = $xx;
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
weaken($xx->{graph} = $self) unless ref($xx->{graph});
push @rc, $xx;
}
$self->{score} = undef; # invalidate last layout
@rc;
}
#############################################################################
lib/Graph/Easy.pm view on Meta::CPAN
# group with that name already exists?
my $name = $group;
$group = $self->{groups}->{ $group } unless ref $group;
# group with that name doesn't exist, so create new one
$group = $uc->{group}->new( name => $name ) unless ref $group;
# index under the group name for easier lookup
$self->{groups}->{ $group->{name} } = $group;
# register group with ourself and weaken the reference
$group->{graph} = $self;
{
no warnings; # don't warn on already weak references
weaken($group->{graph});
}
$self->{score} = undef; # invalidate last layout
$group;
}
sub del_group
{
# delete group
my ($self,$group) = @_;
lib/Graph/Easy/Edge/Cell.pm view on Meta::CPAN
use warnings;
use Graph::Easy::Edge;
use Graph::Easy::Attributes;
require Exporter;
use vars qw/$VERSION @EXPORT_OK @ISA/;
@ISA = qw/Exporter Graph::Easy::Edge/;
$VERSION = '0.76';
use Scalar::Util qw/weaken/;
#############################################################################
# The different cell types:
use constant {
EDGE_CROSS => 0, # + crossing lines
EDGE_HOR => 1, # -- horizontal line
EDGE_VER => 2, # | vertical line
EDGE_N_E => 3, # |_ corner (N to E)
lib/Graph/Easy/Edge/Cell.pm view on Meta::CPAN
$self->_croak("Creating edge cell without a parent edge object")
unless defined $self->{edge};
$self->_croak("Creating edge cell without a type")
unless defined $self->{type};
# take over settings from edge
$self->{style} = $self->{edge}->style();
$self->{class} = $self->{edge}->class();
$self->{graph} = $self->{edge}->{graph};
$self->{group} = $self->{edge}->{group};
weaken($self->{graph});
weaken($self->{group});
$self->{att} = $self->{edge}->{att};
# register ourselves at this edge
$self->{edge}->_add_cell ($self, $args->{after}, $args->{before});
$self;
}
sub arrow_count
{
lib/Graph/Easy/Group.pm view on Meta::CPAN
#############################################################################
# A group of nodes. Part of Graph::Easy.
#
#############################################################################
package Graph::Easy::Group;
use Graph::Easy::Group::Cell;
use Graph::Easy;
use Scalar::Util qw/weaken/;
@ISA = qw/Graph::Easy::Node Graph::Easy/;
$VERSION = '0.76';
use strict;
use warnings;
use Graph::Easy::Util qw(ord_values);
#############################################################################
lib/Graph/Easy/Group.pm view on Meta::CPAN
# if defined attribute "nodeclass", put our nodes into that class
$n->sub_class($self->{att}->{nodeclass}) if exists $self->{att}->{nodeclass};
# register ourselves with the member
$n->{group} = $self;
# set the proper attribute (for layout)
$n->{att}->{group} = $self->{name};
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
# If the node does not belong to a graph yet or belongs to another
# graph, add it to our own graph:
weaken($n->{graph} = $self->{graph}) unless
$n->{graph} && $self->{graph} && $n->{graph} == $self->{graph};
$n;
}
sub add_member
{
# add a node or group to this group
my ($self,$n) = @_;
lib/Graph/Easy/Group.pm view on Meta::CPAN
my $cl = $self->attribute('nodeclass');
$n->sub_class($cl) if $cl ne '';
# register ourselves with the member
$n->{group} = $self;
# set the proper attribute (for layout)
$n->{att}->{group} = $self->{name};
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
# If the node does not belong to a graph yet or belongs to another
# graph, add it to our own graph:
weaken($n->{graph} = $self->{graph}) unless
$n->{graph} && $self->{graph} && $n->{graph} == $self->{graph};
$n;
}
sub del_member
{
# delete a node or group from this group
my ($self,$n) = @_;
lib/Graph/Easy/Group.pm view on Meta::CPAN
$n->{att}->{group} = $self->{name};
# XXX TODO TEST!
# # if defined attribute "nodeclass", put our nodes into that class
# $n->sub_class($self->{att}->{nodeclass}) if exists $self->{att}->{nodeclass};
# register ourselves with the member
$n->{group} = $self;
# Register the nodes and the edge with our graph object
# and weaken the references. Be careful to not needlessly
# override and weaken again an already existing reference, this
# is an O(N) operation in most Perl versions, and thus very slow.
# If the node does not belong to a graph yet or belongs to another
# graph, add it to our own graph:
weaken($n->{graph} = $self->{graph}) unless
$n->{graph} && $self->{graph} && $n->{graph} == $self->{graph};
}
@arg;
}
#############################################################################
sub _del_edge
lib/Graph/Easy/Group.pm view on Meta::CPAN
$self->{edges_within}->{ $e->{id} } = $e;
# if defined attribute "edgeclass", put our edges into that class
my $edge_class = $self->attribute('edgeclass');
$e->sub_class($edge_class) if $edge_class ne '';
# XXX TODO: inline
$self->add_node($e->{from});
$self->add_node($e->{to});
# register us, but don't do weaken() if the ref was already set
weaken($e->{group} = $self) unless defined $e->{group} && $e->{group} == $self;
$e;
}
sub add_edge
{
# Add an edge to the graph of this group, then register it with this group.
my ($self,$from,$to) = @_;
my $g = $self->{graph};
lib/Graph/Easy/Group.pm view on Meta::CPAN
$self->{groups}->{ $group->{name} } = $group;
# make attribute->('group') work
$group->{att}->{group} = $self->{name};
# register group with the graph and ourself
$group->{graph} = $self->{graph};
$group->{group} = $self;
{
no warnings; # don't warn on already weak references
weaken($group->{graph});
weaken($group->{group});
}
$self->{graph}->{score} = undef; # invalidate last layout
$group;
}
# cell management - used by the layouter
sub _cells
{
lib/Graph/Easy/Parser.pm view on Meta::CPAN
#
#############################################################################
package Graph::Easy::Parser;
use Graph::Easy;
$VERSION = '0.76';
use Graph::Easy::Base;
@ISA = qw/Graph::Easy::Base/;
use Scalar::Util qw/weaken/;
use strict;
use warnings;
use constant NO_MULTIPLES => 1;
use Graph::Easy::Util qw(ord_values);
sub _init
{
my ($self,$args) = @_;
lib/Graph/Easy/Parser.pm view on Meta::CPAN
# second, third etc. get previous as origin
my ($sx,$sy) = (1,0);
my $origin = $rc[-2];
if ($last_sep eq '||')
{
($sx,$sy) = (0,1); $origin = $first_in_row;
$first_in_row = $node;
}
$node->relative_to($origin,$sx,$sy);
push @{$rc[0]->{autosplit_parts}}, $node;
weaken @{$rc[0]->{autosplit_parts}}[-1];
# suppress as_txt output for other parts
$node->{autosplit} = undef;
}
# nec. for border-collapse
$node->{autosplit_xy} = "$x,$y";
$idx++; # next node ID
$last_sep = $sep;
$x++;
( run in 2.066 seconds using v1.01-cache-2.11-cpan-65fba6d93b7 )