| 1 | package Graph::PetriNet; | ||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||
| 3 | 3 | ▶ | use 5.008000; | ||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||
| 4 | 3 | ▶ | use strict; | ||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||
| 5 | 3 | ▶ | use warnings; | ||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||
| 7 | 3 | require Exporter; | |||||||||||||||||||||||
| 8 | 3 | our @ISA = qw(Exporter); | |||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||
| 10 | 3 | our $VERSION = '0.03'; | |||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||
| 12 | 3 | ▶ | use Class::Trait; | ||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||
| 13 | |||||||||||||||||||||||||
| 14 | =pod | ||||||||||||||||||||||||
| 15 | |||||||||||||||||||||||||
| 16 | =head1 NAME | ||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||
| 18 | Graph::PetriNet - Perl extension for Petri Nets | ||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||
| 20 | =head1 SYNOPSIS | ||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||
| 22 | # build your places objects (see DESCRIPTION) | ||||||||||||||||||||||||
| 23 | my %places = ('place1' => ...., | ||||||||||||||||||||||||
| 24 | 'place2' => ....); | ||||||||||||||||||||||||
| 25 | # build your transition objects (see DESCRIPTION) | ||||||||||||||||||||||||
| 26 | my %transitions = ('trans1' => [ ... ], | ||||||||||||||||||||||||
| 27 | 'trans2' => [ ... ]); | ||||||||||||||||||||||||
| 28 | |||||||||||||||||||||||||
| 29 | use Graph::PetriNet; | ||||||||||||||||||||||||
| 30 | my $pn = new Graph::PetriNet (places => \%places, | ||||||||||||||||||||||||
| 31 | transitions => \%transitions); | ||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||
| 33 | # change a token setting at one place | ||||||||||||||||||||||||
| 34 | $pn->things ('place1')->tokens (42); | ||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||
| 36 | # walk through the whole life time | ||||||||||||||||||||||||
| 37 | while ($pn->ignitables) { | ||||||||||||||||||||||||
| 38 | $pn->ignite; | ||||||||||||||||||||||||
| 39 | warn "tokens: ". $pn->things ('place1')->tokens; | ||||||||||||||||||||||||
| 40 | } | ||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||
| 42 | # only ignite one particular transitions | ||||||||||||||||||||||||
| 43 | $pn->ignite ('trans1', 'trans2'); | ||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||
| 45 | my @places = $pn->places; | ||||||||||||||||||||||||
| 46 | my @trans = $pn->transitions; | ||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||
| 49 | =head1 DESCRIPTION | ||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||
| 51 | This package implements a bipartite graph to represent and interpret a I<Petri net> | ||||||||||||||||||||||||
| 52 | (L<http://en.wikipedia.org/wiki/Petri_net>). Accordingly, there are two kinds of nodes: | ||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||
| 54 | =over | ||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||
| 56 | =item * | ||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||
| 58 | L<Data nodes> carry the information to be processed and/or propagated. This package assumes that each | ||||||||||||||||||||||||
| 59 | such node has a unique label (just a string). The label is used to refer to the node. | ||||||||||||||||||||||||
| 60 | |||||||||||||||||||||||||
| 61 | =item * | ||||||||||||||||||||||||
| 62 | |||||||||||||||||||||||||
| 63 | L<Transition nodes> carry the information how and when processing has to occur. Also transitions | ||||||||||||||||||||||||
| 64 | have unique labels and also they are objects. Every transition node has a set of incoming data nodes | ||||||||||||||||||||||||
| 65 | from which it can consume data. And it has a set of outgoing data nodes which will be fill with new | ||||||||||||||||||||||||
| 66 | data after a transition. | ||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||
| 68 | =back | ||||||||||||||||||||||||
| 69 | |||||||||||||||||||||||||
| 70 | =head2 Processing Model | ||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||
| 72 | At any time the application can check which transitions are I<ignitable>. It can ask the petri net | ||||||||||||||||||||||||
| 73 | to fire some (or all of them). It is the responsibility of the transition nodes to do what they are | ||||||||||||||||||||||||
| 74 | supposed to do. | ||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||
| 76 | =head2 Node Semantics | ||||||||||||||||||||||||
| 77 | |||||||||||||||||||||||||
| 78 | As a default behavior (not overly useful, but here it is), transition nodes consume I<tokens> from | ||||||||||||||||||||||||
| 79 | the data nodes (actually one per node and transition) and then pass one token to the downstream data | ||||||||||||||||||||||||
| 80 | node. | ||||||||||||||||||||||||
| 81 | |||||||||||||||||||||||||
| 82 | To modify this behaviour, you simply implement your own data and transition nodes. To make this | ||||||||||||||||||||||||
| 83 | reasonably easy their behaviour is defined as I<trait>: You can either take these traits as they | ||||||||||||||||||||||||
| 84 | are, or import the trait with modifications, or develop a subtrait which you import into your | ||||||||||||||||||||||||
| 85 | objects, or write the objects from scratch. For an example look at C<t/02_makefileish.t> which | ||||||||||||||||||||||||
| 86 | implements a processing behaviour you would expect from I<make>. | ||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||
| 89 | B<NOTES>: | ||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||
| 91 | =over | ||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||
| 93 | =item * | ||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||
| 95 | The roles (traits) are currently written with L<Class::Trait>. Maybe in another time I reimplement | ||||||||||||||||||||||||
| 96 | this with L<Moose> roles. Maybe. | ||||||||||||||||||||||||
| 97 | |||||||||||||||||||||||||
| 98 | =item * | ||||||||||||||||||||||||
| 99 | |||||||||||||||||||||||||
| 100 | This graph is not implemented on top of L<Graph>, so using it as superclass. There is already a | ||||||||||||||||||||||||
| 101 | package L<Graph::Bipartite> (not recommended) which blocks the namespace, but there are no deep | ||||||||||||||||||||||||
| 102 | reasons why this should not be possible. | ||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||
| 104 | =back | ||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||
| 107 | =head1 INTERFACE | ||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||
| 109 | =head2 Constructor | ||||||||||||||||||||||||
| 110 | |||||||||||||||||||||||||
| 111 | The constructor expects a hash with the following fields: | ||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||
| 113 | =over | ||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||
| 115 | =item C<transitions> (mandatory, hash reference) | ||||||||||||||||||||||||
| 116 | |||||||||||||||||||||||||
| 117 | A hash reference, whereby the keys are labels for the transitions and the values are the transitions | ||||||||||||||||||||||||
| 118 | themselves. They can be anything but must be able to do the trait L<Graph::PetriNet::TransitAble>. | ||||||||||||||||||||||||
| 119 | |||||||||||||||||||||||||
| 120 | =item C<places> (mandatory, hash reference) | ||||||||||||||||||||||||
| 121 | |||||||||||||||||||||||||
| 122 | A hash reference, whereby the keys are labels for the places and the values are the places | ||||||||||||||||||||||||
| 123 | themselves. They can be anything but must be able to do the trait L<Graph::PetriNet::PlaceAble>. | ||||||||||||||||||||||||
| 124 | |||||||||||||||||||||||||
| 125 | =item C<initialize> (optional, integer) | ||||||||||||||||||||||||
| 126 | |||||||||||||||||||||||||
| 127 | If non-zero, then the constructor will invoke the C<token> method on all places, setting them to | ||||||||||||||||||||||||
| 128 | C<0>. | ||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||
| 130 | =back | ||||||||||||||||||||||||
| 131 | |||||||||||||||||||||||||
| 132 | Example: | ||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||
| 134 | my $pn = new Graph::PetriNet (# here I want something special | ||||||||||||||||||||||||
| 135 | places => { 'p1' => new My::Place (...), | ||||||||||||||||||||||||
| 136 | 'p2' => new My::Place (...), | ||||||||||||||||||||||||
| 137 | }, | ||||||||||||||||||||||||
| 138 | # too lazy, happy with the default behavior | ||||||||||||||||||||||||
| 139 | transitions => { | ||||||||||||||||||||||||
| 140 | 't1' => [ bless ({}, 'Whatever'), [ 'p1' ], [ 'p2' ] ], | ||||||||||||||||||||||||
| 141 | 't2' => [ bless ({}, 'Whatever'), [ 'p2' ], [ 'p2' ] ] | ||||||||||||||||||||||||
| 142 | }); | ||||||||||||||||||||||||
| 143 | |||||||||||||||||||||||||
| 144 | =cut | ||||||||||||||||||||||||
| 145 | |||||||||||||||||||||||||
| 146 | 2 | ▶ | sub new { | ||||||||||||||||||||||
|
Subroutine
new: called CC=6 SCAR=17.9
Pod
undocumented
| |||||||||||||||||||||||||
| 147 | 2 | my $class = shift; | |||||||||||||||||||||||
| 148 | 2 | my $self = bless { places => {}, transitions => {} }, $class; | |||||||||||||||||||||||
| 149 | 2 | my %opts = @_; | |||||||||||||||||||||||
| 150 | 2 | foreach my $p (keys %{ $opts{places} }) { # check for all places | |||||||||||||||||||||||
| 151 | 14 | my $pl = $opts{places}->{$p}; # what the place object is | |||||||||||||||||||||||
| 152 | 14 | ▶ | Class::Trait->apply($pl, 'Graph::PetriNet::PlaceAble') # that it has our trait | ||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||
| 153 | unless $pl->can ('tokens'); | ||||||||||||||||||||||||
| 154 | 14 | $self->{places}->{$p} = $pl; # and register it with us | |||||||||||||||||||||||
| 155 | } | ||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||
| 157 | 2 | foreach my $t (keys %{$opts{transitions} }) { # for all the transition infor | |||||||||||||||||||||||
| 158 | 10 | my ($tr, $in, $out) = @{ $opts{transitions}->{$t} }; # collect what we get | |||||||||||||||||||||||
| 159 | 10 | ▶ | Class::Trait->apply($tr, 'Graph::PetriNet::TransitionAble') # assert the trait | ||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||
| 160 | unless $tr->can ('ignitable'); | ||||||||||||||||||||||||
| 161 | 10 | $tr->inputs ($in); # tug in input and | |||||||||||||||||||||||
| 162 | 10 | $tr->outputs ($out); # output | |||||||||||||||||||||||
| 163 | 10 | $self->{transitions}->{$t} = $tr; # register | |||||||||||||||||||||||
| 164 | } | ||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||
| 166 | 2 | ▶ | $self->reset if $opts{initialize}; | ||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||
| 167 | 2 | return $self; | |||||||||||||||||||||||
| 168 | } | ||||||||||||||||||||||||
| 169 | |||||||||||||||||||||||||
| 170 | =pod | ||||||||||||||||||||||||
| 171 | |||||||||||||||||||||||||
| 172 | =head2 Methods | ||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||
| 174 | =over | ||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||
| 176 | =item B<places> | ||||||||||||||||||||||||
| 177 | |||||||||||||||||||||||||
| 178 | I<@labels> = I<$pn>->places | ||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||
| 180 | Retrieve the labels of all places in the network. | ||||||||||||||||||||||||
| 181 | |||||||||||||||||||||||||
| 182 | =cut | ||||||||||||||||||||||||
| 183 | |||||||||||||||||||||||||
| 184 | 1 | ▶ | sub places { | ||||||||||||||||||||||
|
Subroutine
places: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||
| 185 | 1 | my $self = shift; | |||||||||||||||||||||||
| 186 | 1 | return keys %{ $self->{places} }; | |||||||||||||||||||||||
| 187 | } | ||||||||||||||||||||||||
| 188 | |||||||||||||||||||||||||
| 189 | =pod | ||||||||||||||||||||||||
| 190 | |||||||||||||||||||||||||
| 191 | I<@labels> = I<$pn>->transitions | ||||||||||||||||||||||||
| 192 | |||||||||||||||||||||||||
| 193 | Retrieve the labels of all transitions in the network. | ||||||||||||||||||||||||
| 194 | |||||||||||||||||||||||||
| 195 | =cut | ||||||||||||||||||||||||
| 196 | |||||||||||||||||||||||||
| 197 | 1 | ▶ | sub transitions { | ||||||||||||||||||||||
|
Subroutine
transitions: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||
| 198 | 1 | my $self = shift; | |||||||||||||||||||||||
| 199 | 1 | return keys %{ $self->{transitions} }; | |||||||||||||||||||||||
| 200 | } | ||||||||||||||||||||||||
| 201 | |||||||||||||||||||||||||
| 202 | =pod | ||||||||||||||||||||||||
| 203 | |||||||||||||||||||||||||
| 204 | =item B<things> | ||||||||||||||||||||||||
| 205 | |||||||||||||||||||||||||
| 206 | I<@things> = I<$pn>->things (I<$label>, ...) | ||||||||||||||||||||||||
| 207 | |||||||||||||||||||||||||
| 208 | Given some labels, this method returns the things with this label, or C<undef> if there is none. | ||||||||||||||||||||||||
| 209 | |||||||||||||||||||||||||
| 210 | =cut | ||||||||||||||||||||||||
| 211 | |||||||||||||||||||||||||
| 212 | 4 | ▶ | sub things { | ||||||||||||||||||||||
|
Subroutine
things: called CC=3 SCAR=11.4
Pod
documented
| |||||||||||||||||||||||||
| 213 | 4 | my $self = shift; | |||||||||||||||||||||||
| 214 | 4 | return map { $self->{places} ->{$_} | |||||||||||||||||||||||
| 215 | 6 | ▶ | || $self->{transitions}->{$_} | ||||||||||||||||||||||
|
Condition60%3/5
$self->{'places'}{$_} || $self->{'transitions'}{$_} || undef
$self->{"places"}{$_} or $self->{"transitions"}{$_}
MC/DC0%0/2
$self->{'places'}{$_} || $self->{'transitions'}{$_} || undef
$self->{"places"}{$_}
$self->{"transitions"}{$_}
Truth table66%2/3
A or B
A= $self->{"places"}{$_}B= $self->{"transitions"}{$_}
| |||||||||||||||||||||||||
| 216 | || undef } | ||||||||||||||||||||||||
| 217 | @_; | ||||||||||||||||||||||||
| 218 | } | ||||||||||||||||||||||||
| 219 | |||||||||||||||||||||||||
| 220 | =pod | ||||||||||||||||||||||||
| 221 | |||||||||||||||||||||||||
| 222 | =item B<reset> | ||||||||||||||||||||||||
| 223 | |||||||||||||||||||||||||
| 224 | I<$pn>->reset | ||||||||||||||||||||||||
| 225 | |||||||||||||||||||||||||
| 226 | Resets all places to have zero tokens. | ||||||||||||||||||||||||
| 227 | |||||||||||||||||||||||||
| 228 | =cut | ||||||||||||||||||||||||
| 229 | |||||||||||||||||||||||||
| 230 | 2 | ▶ | sub reset { | ||||||||||||||||||||||
|
Subroutine
reset: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||
| 231 | 2 | my $self = shift; | |||||||||||||||||||||||
| 232 | 2 | map { $_->tokens (0) } values %{ $self->{places} }; | |||||||||||||||||||||||
| 233 | } | ||||||||||||||||||||||||
| 234 | |||||||||||||||||||||||||
| 235 | =pod | ||||||||||||||||||||||||
| 236 | |||||||||||||||||||||||||
| 237 | =item B<ignitables> | ||||||||||||||||||||||||
| 238 | |||||||||||||||||||||||||
| 239 | I<@is> = I<$pn>->ignitables | ||||||||||||||||||||||||
| 240 | |||||||||||||||||||||||||
| 241 | This method returns a list of transitions which can be fired. It returns the labels, not the object. | ||||||||||||||||||||||||
| 242 | |||||||||||||||||||||||||
| 243 | =cut | ||||||||||||||||||||||||
| 244 | |||||||||||||||||||||||||
| 245 | 22 | ▶ | sub ignitables { | ||||||||||||||||||||||
|
Subroutine
ignitables: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||
| 246 | 22 | my $self = shift; | |||||||||||||||||||||||
| 247 | 22 | return grep { $self->{transitions}->{$_}->ignitable } keys %{ $self->{transitions} }; | |||||||||||||||||||||||
| 248 | } | ||||||||||||||||||||||||
| 249 | |||||||||||||||||||||||||
| 250 | =pod | ||||||||||||||||||||||||
| 251 | |||||||||||||||||||||||||
| 252 | =item B<ignite> | ||||||||||||||||||||||||
| 253 | |||||||||||||||||||||||||
| 254 | I<$pn>->ignite | ||||||||||||||||||||||||
| 255 | I<$pn>->ignite (I<label>, ...) | ||||||||||||||||||||||||
| 256 | |||||||||||||||||||||||||
| 257 | This methods ignites those transitions which are handed in (as labels). If none is handed in, then | ||||||||||||||||||||||||
| 258 | all ignitables with be ignited. | ||||||||||||||||||||||||
| 259 | |||||||||||||||||||||||||
| 260 | =cut | ||||||||||||||||||||||||
| 261 | |||||||||||||||||||||||||
| 262 | 14 | ▶ | sub ignite { | ||||||||||||||||||||||
|
Subroutine
ignite: called CC=3 SCAR=11.1
Pod
documented
| |||||||||||||||||||||||||
| 263 | 14 | my $self = shift; | |||||||||||||||||||||||
| 264 | 14 | ▶ | my @is = @_ ? @_ : $self->ignitables; | ||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||
| 265 | 14 | foreach my $tr (map { $self->{transitions}->{$_} } @is) { | |||||||||||||||||||||||
| 266 | 17 | $tr->ignite; | |||||||||||||||||||||||
| 267 | } | ||||||||||||||||||||||||
| 268 | } | ||||||||||||||||||||||||
| 269 | |||||||||||||||||||||||||
| 270 | =pod | ||||||||||||||||||||||||
| 271 | |||||||||||||||||||||||||
| 272 | =back | ||||||||||||||||||||||||
| 273 | |||||||||||||||||||||||||
| 274 | =head1 SEE ALSO | ||||||||||||||||||||||||
| 275 | |||||||||||||||||||||||||
| 276 | L<http://en.wikipedia.org/wiki/Petri_net>, L<Graph::PetriNet::PlaceAble>, L<Graph::PetriNet::TransitionAble> | ||||||||||||||||||||||||
| 277 | |||||||||||||||||||||||||
| 278 | =head1 AUTHOR | ||||||||||||||||||||||||
| 279 | |||||||||||||||||||||||||
| 280 | Robert Barta, E<lt>drrho@cpan.orgE<gt> | ||||||||||||||||||||||||
| 281 | |||||||||||||||||||||||||
| 282 | =head1 COPYRIGHT AND LICENSE | ||||||||||||||||||||||||
| 283 | |||||||||||||||||||||||||
| 284 | Copyright (C) 2009 by Robert Barta | ||||||||||||||||||||||||
| 285 | |||||||||||||||||||||||||
| 286 | This library is free software; you can redistribute it and/or modify it under the same terms as Perl | ||||||||||||||||||||||||
| 287 | itself, either Perl version 5.10.0 or, at your option, any later version of Perl 5 you may have | ||||||||||||||||||||||||
| 288 | available. | ||||||||||||||||||||||||
| 289 | |||||||||||||||||||||||||
| 290 | |||||||||||||||||||||||||
| 291 | =cut | ||||||||||||||||||||||||
| 292 | |||||||||||||||||||||||||
| 293 | 3 | "against all gods"; | |||||||||||||||||||||||
| 294 | |||||||||||||||||||||||||
| 295 | __END__ | ||||||||||||||||||||||||