NAME

Graph::BitMatrix - create and manipulate a V x V bit matrix of graph G

SYNOPSIS

    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()

DESCRIPTION

This class enables creating bit matrices that compactly describe the connected of the graphs.

Class Methods

new($g): Create a bit matrix from a Graph $g. The %opt, if present, can have the following options:

Object Methods

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.

ALGORITHM

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.

AUTHOR AND COPYRIGHT

Jarkko Hietaniemi jhi@iki.fi

LICENSE

This module is licensed under the same terms as Perl itself.

Graph::BitMatrix - create and manipulate a V x V bit matrix of graph G