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:
- 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.
|