Graph::BitMatrix - create and manipulate a V x V bit matrix of
graph G
use Graph::BitMatrix;
use Graph::Directed;
my $g = Graph::Directed->new;
$g->add_...(); # build $g
my $m = Graph::BitMatrix->new($g, %opt);
$m->get($u, $v)
$m->set($u, $v)
$m->unset($u, $v)
$m->get_row($u, $v1, $v2, ..., $vn)
$m->set_row($u, $v1, $v2, ..., $vn)
$m->unset_row($u, $v1, $v2, ..., $vn)
$a->vertices()
This class enables creating bit matrices that compactly describe
the connected of the graphs.
- new($g)
- Create a bit matrix from a Graph $g. The
%opt, if present, can have the following
options:
- connect_edges
If true or if not present, set the bits in the bit matrix that
correspond to edges. If false, do not set any bits. In either case the
bit matrix of V x V bits is allocated.
- transpose
If true, set the bits in the bit matrix that correspond to
edges but in the reverse direction. This has the effect of transposing
the matrix. Obviously makes no difference to the result for undirected
graphs.
- get($u, $v)
- Return true if the bit matrix has a "one bit" between the
vertices $u and $v; in
other words, if there is (at least one) a vertex going from
$u to $v. If there is no
vertex and therefore a "zero bit", return false.
- set($u, $v)
- Set the bit between the vertices $u and
$v; in other words, connect the vertices
$u and $v by an edge. The
change does not get mirrored back to the original graph. Returns
nothing.
- unset($u,
$v)
- Unset the bit between the vertices $u and
$v; in other words, disconnect the vertices
$u and $v by an edge. The
change does not get mirrored back to the original graph. Returns
nothing.
- get_row($u, $v1,
$v2, ..., $vn)
- Test the row at vertex "u" for the
vertices "v1",
"v2", ...,
"vn" Returns a list of n truth
values.
- set_row($u, $v1,
$v2, ..., $vn)
- Sets the row at vertex "u" for the
vertices "v1",
"v2", ...,
"vn", in other words, connects the
vertex "u" to the vertices
"vi". The changes do not get mirrored
back to the original graph. Returns nothing.
- unset_row($u,
$v1, $v2, ..., $vn)
- Unsets the row at vertex "u" for the
vertices "v1",
"v2", ...,
"vn", in other words, disconnects the
vertex "u" from the vertices
"vi". The changes do not get mirrored
back to the original graph. Returns nothing.
- vertices
- Return the list of vertices in the bit matrix.
The algorithm used to create the matrix is two nested loops, which
is O(V**2) in time, and the returned matrices are O(V**2) in space.
Jarkko Hietaniemi jhi@iki.fi
This module is licensed under the same terms as Perl itself.