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