1package Graph::AdjacencyMatrix;
2
3use strict;
4
5use Graph::BitMatrix;
6use Graph::Matrix;
7
8use base 'Graph::BitMatrix';
9
10use Graph::AdjacencyMap qw(:flags :fields);
11
12sub _V () { 2 } # Graph::_V
13sub _E () { 3 } # Graph::_E
14
15sub new {
16    my ($class, $g, %opt) = @_;
17    my $n;
18    my @V = $g->vertices;
19    my $want_distance;
20    if (exists $opt{distance_matrix}) {
21	$want_distance = $opt{distance_matrix};
22	delete $opt{distance_matrix};
23    }
24    my $d = Graph::_defattr();
25    if (exists $opt{attribute_name}) {
26	$d = $opt{attribute_name};
27	$want_distance++;
28    }
29    delete $opt{attribute_name};
30    my $want_transitive = 0;
31    if (exists $opt{is_transitive}) {
32	$want_transitive = $opt{is_transitive};
33	delete $opt{is_transitive};
34    }
35    Graph::_opt_unknown(\%opt);
36    if ($want_distance) {
37	$n = Graph::Matrix->new($g);
38	for my $v (@V) { $n->set($v, $v, 0) }
39    }
40    my $m = Graph::BitMatrix->new($g, connect_edges => $want_distance);
41    if ($want_distance) {
42	# for my $u (@V) {
43	#     for my $v (@V) {
44	#         if ($g->has_edge($u, $v)) {
45	#             $n->set($u, $v,
46	#                    $g->get_edge_attribute($u, $v, $d));
47        #        }
48        #     }
49        # }
50	my $Vi = $g->[_V]->[_i];
51	my $Ei = $g->[_E]->[_i];
52	my %V; @V{ @V } = 0 .. $#V;
53	my $n0 = $n->[0];
54	my $n1 = $n->[1];
55	if ($g->is_undirected) {
56	    for my $e (keys %{ $Ei }) {
57		my ($i0, $j0) = @{ $Ei->{ $e } };
58		my $i1 = $V{ $Vi->{ $i0 } };
59		my $j1 = $V{ $Vi->{ $j0 } };
60		my $u = $V[ $i1 ];
61		my $v = $V[ $j1 ];
62		$n0->[ $i1 ]->[ $j1 ] =
63		    $g->get_edge_attribute($u, $v, $d);
64		$n0->[ $j1 ]->[ $i1 ] =
65		    $g->get_edge_attribute($v, $u, $d);
66	    }
67	} else {
68	    for my $e (keys %{ $Ei }) {
69		my ($i0, $j0) = @{ $Ei->{ $e } };
70		my $i1 = $V{ $Vi->{ $i0 } };
71		my $j1 = $V{ $Vi->{ $j0 } };
72		my $u = $V[ $i1 ];
73		my $v = $V[ $j1 ];
74		$n0->[ $i1 ]->[ $j1 ] =
75		    $g->get_edge_attribute($u, $v, $d);
76	    }
77	}
78    }
79    bless [ $m, $n, [ @V ] ], $class;
80}
81
82sub adjacency_matrix {
83    my $am = shift;
84    $am->[0];
85}
86
87sub distance_matrix {
88    my $am = shift;
89    $am->[1];
90}
91
92sub vertices {
93    my $am = shift;
94    @{ $am->[2] };
95}
96
97sub is_adjacent {
98    my ($m, $u, $v) = @_;
99    $m->[0]->get($u, $v) ? 1 : 0;
100}
101
102sub distance {
103    my ($m, $u, $v) = @_;
104    defined $m->[1] ? $m->[1]->get($u, $v) : undef;
105}
106
1071;
108__END__
109=pod
110
111=head1 NAME
112
113Graph::AdjacencyMatrix - create and query the adjacency matrix of graph G
114
115=head1 SYNOPSIS
116
117    use Graph::AdjacencyMatrix;
118    use Graph::Directed; # or Undirected
119
120    my $g  = Graph::Directed->new;
121    $g->add_...(); # build $g
122
123    my $am = Graph::AdjacencyMatrix->new($g);
124    $am->is_adjacent($u, $v)
125
126    my $am = Graph::AdjacencyMatrix->new($g, distance_matrix => 1);
127    $am->distance($u, $v)
128
129    my $am = Graph::AdjacencyMatrix->new($g, attribute_name => 'length');
130    $am->distance($u, $v)
131
132    my $am = Graph::AdjacencyMatrix->new($g, ...);
133    my @V  = $am->vertices();
134
135=head1 DESCRIPTION
136
137You can use C<Graph::AdjacencyMatrix> to compute the adjacency matrix
138and optionally also the distance matrix of a graph, and after that
139query the adjacencyness between vertices by using the C<is_adjacent()>
140method, or query the distance between vertices by using the
141C<distance()> method.
142
143By default the edge attribute used for distance is C<w>, but you
144can change that in new(), see below.
145
146If you modify the graph after creating the adjacency matrix of it,
147the adjacency matrix and the distance matrix may become invalid.
148
149=head1 Methods
150
151=head2 Class Methods
152
153=over 4
154
155=item new($g)
156
157Construct the adjacency matrix of the graph $g.
158
159=item new($g, options)
160
161Construct the adjacency matrix of the graph $g with options as a hash.
162The known options are
163
164=over 8
165
166=item distance_matrix => boolean
167
168By default only the adjacency matrix is computed.  To compute also the
169distance matrix, use the attribute C<distance_matrix> with a true value
170to the new() constructor.
171
172=item attribute_name => attribute_name
173
174By default the edge attribute used for distance is C<w>.  You can
175change that by giving another attribute name with the C<attribute_name>
176attribute to new() constructor.  Using this attribute also implicitly
177causes the distance matrix to be computed.
178
179=back
180
181=back
182
183=head2 Object Methods
184
185=over 4
186
187=item is_adjacent($u, $v)
188
189Return true if the vertex $v is adjacent to vertex $u, or false if not.
190
191=item distance($u, $v)
192
193Return the distance between the vertices $u and $v, or C<undef> if
194the vertices are not adjacent.
195
196=item adjacency_matrix
197
198Return the adjacency matrix itself (a list of bitvector scalars).
199
200=item vertices
201
202Return the list of vertices (useful for indexing the adjacency matrix).
203
204=back
205
206=head1 ALGORITHM
207
208The algorithm used to create the matrix is two nested loops, which is
209O(V**2) in time, and the returned matrices are O(V**2) in space.
210
211=head1 SEE ALSO
212
213L<Graph::TransitiveClosure>, L<Graph::BitMatrix>
214
215=head1 AUTHOR AND COPYRIGHT
216
217Jarkko Hietaniemi F<jhi@iki.fi>
218
219=head1 LICENSE
220
221This module is licensed under the same terms as Perl itself.
222
223=cut
224