1package Graph::BitMatrix; 2 3use strict; 4 5# $SIG{__DIE__ } = sub { use Carp; confess }; 6# $SIG{__WARN__} = sub { use Carp; confess }; 7 8sub _V () { 2 } # Graph::_V() 9sub _E () { 3 } # Graph::_E() 10sub _i () { 3 } # Index to path. 11sub _s () { 4 } # Successors / Path to Index. 12 13sub new { 14 my ($class, $g, %opt) = @_; 15 my @V = $g->vertices; 16 my $V = @V; 17 my $Z = "\0" x (($V + 7) / 8); 18 my %V; @V{ @V } = 0 .. $#V; 19 my $bm = bless [ [ ( $Z ) x $V ], \%V ], $class; 20 my $bm0 = $bm->[0]; 21 my $connect_edges; 22 if (exists $opt{connect_edges}) { 23 $connect_edges = $opt{connect_edges}; 24 delete $opt{connect_edges}; 25 } 26 $connect_edges = 1 unless defined $connect_edges; 27 Graph::_opt_unknown(\%opt); 28 if ($connect_edges) { 29 # for (my $i = 0; $i <= $#V; $i++) { 30 # my $u = $V[$i]; 31 # for (my $j = 0; $j <= $#V; $j++) { 32 # vec($bm0->[$i], $j, 1) = 1 if $g->has_edge($u, $V[$j]); 33 # } 34 # } 35 my $Vi = $g->[_V]->[_i]; 36 my $Ei = $g->[_E]->[_i]; 37 if ($g->is_undirected) { 38 for my $e (keys %{ $Ei }) { 39 my ($i0, $j0) = @{ $Ei->{ $e } }; 40 my $i1 = $V{ $Vi->{ $i0 } }; 41 my $j1 = $V{ $Vi->{ $j0 } }; 42 vec($bm0->[$i1], $j1, 1) = 1; 43 vec($bm0->[$j1], $i1, 1) = 1; 44 } 45 } else { 46 for my $e (keys %{ $Ei }) { 47 my ($i0, $j0) = @{ $Ei->{ $e } }; 48 vec($bm0->[$V{ $Vi->{ $i0 } }], $V{ $Vi->{ $j0 } }, 1) = 1; 49 } 50 } 51 } 52 return $bm; 53} 54 55sub set { 56 my ($m, $u, $v) = @_; 57 my ($i, $j) = map { $m->[1]->{ $_ } } ($u, $v); 58 vec($m->[0]->[$i], $j, 1) = 1 if defined $i && defined $j; 59} 60 61sub unset { 62 my ($m, $u, $v) = @_; 63 my ($i, $j) = map { $m->[1]->{ $_ } } ($u, $v); 64 vec($m->[0]->[$i], $j, 1) = 0 if defined $i && defined $j; 65} 66 67sub get { 68 my ($m, $u, $v) = @_; 69 my ($i, $j) = map { $m->[1]->{ $_ } } ($u, $v); 70 defined $i && defined $j ? vec($m->[0]->[$i], $j, 1) : undef; 71} 72 73sub set_row { 74 my ($m, $u) = splice @_, 0, 2; 75 my $m0 = $m->[0]; 76 my $m1 = $m->[1]; 77 my $i = $m1->{ $u }; 78 return unless defined $i; 79 for my $v (@_) { 80 my $j = $m1->{ $v }; 81 vec($m0->[$i], $j, 1) = 1 if defined $j; 82 } 83} 84 85sub unset_row { 86 my ($m, $u) = splice @_, 0, 2; 87 my $m0 = $m->[0]; 88 my $m1 = $m->[1]; 89 my $i = $m1->{ $u }; 90 return unless defined $i; 91 for my $v (@_) { 92 my $j = $m1->{ $v }; 93 vec($m0->[$i], $j, 1) = 0 if defined $j; 94 } 95} 96 97sub get_row { 98 my ($m, $u) = splice @_, 0, 2; 99 my $m0 = $m->[0]; 100 my $m1 = $m->[1]; 101 my $i = $m1->{ $u }; 102 return () x @_ unless defined $i; 103 my @r; 104 for my $v (@_) { 105 my $j = $m1->{ $v }; 106 push @r, defined $j ? (vec($m0->[$i], $j, 1) ? 1 : 0) : undef; 107 } 108 return @r; 109} 110 111sub vertices { 112 my ($m, $u, $v) = @_; 113 keys %{ $m->[1] }; 114} 115 1161; 117__END__ 118=pod 119 120=head1 NAME 121 122Graph::BitMatrix - create and manipulate a V x V bit matrix of graph G 123 124=head1 SYNOPSIS 125 126 use Graph::BitMatrix; 127 use Graph::Directed; 128 my $g = Graph::Directed->new; 129 $g->add_...(); # build $g 130 my $m = Graph::BitMatrix->new($g, %opt); 131 $m->get($u, $v) 132 $m->set($u, $v) 133 $m->unset($u, $v) 134 $m->get_row($u, $v1, $v2, ..., $vn) 135 $m->set_row($u, $v1, $v2, ..., $vn) 136 $m->unset_row($u, $v1, $v2, ..., $vn) 137 $a->vertices() 138 139=head1 DESCRIPTION 140 141This class enables creating bit matrices that compactly describe 142the connected of the graphs. 143 144=head2 Class Methods 145 146=over 4 147 148=item new($g) 149 150Create a bit matrix from a Graph $g. The C<%opt>, if present, 151can have the following options: 152 153=over 8 154 155=item * 156 157connect_edges 158 159If true or if not present, set the bits in the bit matrix that 160correspond to edges. If false, do not set any bits. In either 161case the bit matrix of V x V bits is allocated. 162 163=back 164 165=back 166 167=head2 Object Methods 168 169=over 4 170 171=item get($u, $v) 172 173Return true if the bit matrix has a "one bit" between the vertices 174$u and $v; in other words, if there is (at least one) a vertex going from 175$u to $v. If there is no vertex and therefore a "zero bit", return false. 176 177=item set($u, $v) 178 179Set the bit between the vertices $u and $v; in other words, connect 180the vertices $u and $v by an edge. The change does not get mirrored 181back to the original graph. Returns nothing. 182 183=item unset($u, $v) 184 185Unset the bit between the vertices $u and $v; in other words, disconnect 186the vertices $u and $v by an edge. The change does not get mirrored 187back to the original graph. Returns nothing. 188 189=item get_row($u, $v1, $v2, ..., $vn) 190 191Test the row at vertex C<u> for the vertices C<v1>, C<v2>, ..., C<vn> 192Returns a list of I<n> truth values. 193 194=item set_row($u, $v1, $v2, ..., $vn) 195 196Sets the row at vertex C<u> for the vertices C<v1>, C<v2>, ..., C<vn>, 197in other words, connects the vertex C<u> to the vertices C<vi>. 198The changes do not get mirrored back to the original graph. 199Returns nothing. 200 201=item unset_row($u, $v1, $v2, ..., $vn) 202 203Unsets the row at vertex C<u> for the vertices C<v1>, C<v2>, ..., C<vn>, 204in other words, disconnects the vertex C<u> from the vertices C<vi>. 205The changes do not get mirrored back to the original graph. 206Returns nothing. 207 208=item vertices 209 210Return the list of vertices in the bit matrix. 211 212=back 213 214=head1 ALGORITHM 215 216The algorithm used to create the matrix is two nested loops, which is 217O(V**2) in time, and the returned matrices are O(V**2) in space. 218 219=head1 AUTHOR AND COPYRIGHT 220 221Jarkko Hietaniemi F<jhi@iki.fi> 222 223=head1 LICENSE 224 225This module is licensed under the same terms as Perl itself. 226 227=cut 228