Graph-Easy
6 results

 view release on metacpan or  search on metacpan

CHANGES  view on Meta::CPAN 

948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
  + 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:

CHANGES  view on Meta::CPAN 

1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
* 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

CHANGES  view on Meta::CPAN 

1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
* 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 "https://metacpan.org/pod/TODO">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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/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 

86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
  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 

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 

1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
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 

1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
  # 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 

1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
 
    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 

2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
  # 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 

9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 

257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
  $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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#############################################################################
# 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 

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
  # 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 

180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
  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 

269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
    $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 

316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
  $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 

377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
  $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 

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#
#############################################################################
 
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 

994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
  # 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 0.515 second using v1.01-cache-2.11-cpan-3cd7ad12f66 )