.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Graph::BitMatrix 3pm"
.TH Graph::BitMatrix 3pm "2005-04-16" "perl v5.20.2" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Graph::BitMatrix \- create and manipulate a V x V bit matrix of graph G
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 12
\&    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()
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This class enables creating bit matrices that compactly describe
the connected of the graphs.
.SS "Class Methods"
.IX Subsection "Class Methods"
.IP "new($g)" 4
.IX Item "new($g)"
Create a bit matrix from a Graph \f(CW$g\fR.  The \f(CW%opt\fR, if present,
can have the following options:
.RS 4
.IP "\(bu" 8
connect_edges
.Sp
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.
.RE
.RS 4
.RE
.SS "Object Methods"
.IX Subsection "Object Methods"
.ie n .IP "get($u, $v)" 4
.el .IP "get($u, \f(CW$v\fR)" 4
.IX Item "get($u, $v)"
Return true if the bit matrix has a \*(L"one bit\*(R" between the vertices
\&\f(CW$u\fR and \f(CW$v\fR; in other words, if there is (at least one) a vertex going from
\&\f(CW$u\fR to \f(CW$v\fR.  If there is no vertex and therefore a \*(L"zero bit\*(R", return false.
.ie n .IP "set($u, $v)" 4
.el .IP "set($u, \f(CW$v\fR)" 4
.IX Item "set($u, $v)"
Set the bit between the vertices \f(CW$u\fR and \f(CW$v\fR; in other words, connect
the vertices \f(CW$u\fR and \f(CW$v\fR by an edge.  The change does not get mirrored
back to the original graph.  Returns nothing.
.ie n .IP "unset($u, $v)" 4
.el .IP "unset($u, \f(CW$v\fR)" 4
.IX Item "unset($u, $v)"
Unset the bit between the vertices \f(CW$u\fR and \f(CW$v\fR; in other words, disconnect
the vertices \f(CW$u\fR and \f(CW$v\fR by an edge.  The change does not get mirrored
back to the original graph.  Returns nothing.
.ie n .IP "get_row($u, $v1, $v2, ..., $vn)" 4
.el .IP "get_row($u, \f(CW$v1\fR, \f(CW$v2\fR, ..., \f(CW$vn\fR)" 4
.IX Item "get_row($u, $v1, $v2, ..., $vn)"
Test the row at vertex \f(CW\*(C`u\*(C'\fR for the vertices \f(CW\*(C`v1\*(C'\fR, \f(CW\*(C`v2\*(C'\fR, ..., \f(CW\*(C`vn\*(C'\fR
Returns a list of \fIn\fR truth values.
.ie n .IP "set_row($u, $v1, $v2, ..., $vn)" 4
.el .IP "set_row($u, \f(CW$v1\fR, \f(CW$v2\fR, ..., \f(CW$vn\fR)" 4
.IX Item "set_row($u, $v1, $v2, ..., $vn)"
Sets the row at vertex \f(CW\*(C`u\*(C'\fR for the vertices \f(CW\*(C`v1\*(C'\fR, \f(CW\*(C`v2\*(C'\fR, ..., \f(CW\*(C`vn\*(C'\fR,
in other words, connects the vertex \f(CW\*(C`u\*(C'\fR to the vertices \f(CW\*(C`vi\*(C'\fR.
The changes do not get mirrored back to the original graph.
Returns nothing.
.ie n .IP "unset_row($u, $v1, $v2, ..., $vn)" 4
.el .IP "unset_row($u, \f(CW$v1\fR, \f(CW$v2\fR, ..., \f(CW$vn\fR)" 4
.IX Item "unset_row($u, $v1, $v2, ..., $vn)"
Unsets the row at vertex \f(CW\*(C`u\*(C'\fR for the vertices \f(CW\*(C`v1\*(C'\fR, \f(CW\*(C`v2\*(C'\fR, ..., \f(CW\*(C`vn\*(C'\fR,
in other words, disconnects the vertex \f(CW\*(C`u\*(C'\fR from the vertices \f(CW\*(C`vi\*(C'\fR.
The changes do not get mirrored back to the original graph.
Returns nothing.
.IP "vertices" 4
.IX Item "vertices"
Return the list of vertices in the bit matrix.
.SH "ALGORITHM"
.IX Header "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.
.SH "AUTHOR AND COPYRIGHT"
.IX Header "AUTHOR AND COPYRIGHT"
Jarkko Hietaniemi \fIjhi@iki.fi\fR
.SH "LICENSE"
.IX Header "LICENSE"
This module is licensed under the same terms as Perl itself.