1Graph::TransitiveClosurUes:e:rMaCtornitxr(i3b)uted PerlGDroacpuhm:e:nTtraatnisointiveClosure::Matrix(3)
2
3
4

NAME

6       Graph::TransitiveClosure::Matrix - create and query transitive closure
7       of graph
8

SYNOPSIS

10           use Graph::TransitiveClosure::Matrix;
11           use Graph::Directed; # or Undirected
12
13           my $g  = Graph::Directed->new;
14           $g->add_...(); # build $g
15
16           # Compute the transitive closure matrix.
17           my $tcm = Graph::TransitiveClosure::Matrix->new($g);
18
19           # Being reflexive is the default,
20           # meaning that null transitions are included.
21           my $tcm = Graph::TransitiveClosure::Matrix->new($g, reflexive => 1);
22           $tcm->is_reachable($u, $v)
23
24           # is_reachable(u, v) is always reflexive.
25           $tcm->is_reachable($u, $v)
26
27           # The reflexivity of is_transitive(u, v) depends of the reflexivity
28           # of the transitive closure.
29           $tcg->is_transitive($u, $v)
30
31           my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_length => 1);
32           $tcm->path_length($u, $v)
33
34           my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_vertices => 1);
35           $tcm->path_vertices($u, $v)
36
37           my $tcm = Graph::TransitiveClosure::Matrix->new($g, attribute_name => 'length');
38           $tcm->path_length($u, $v)
39
40           $tcm->vertices
41

DESCRIPTION

43       You can use "Graph::TransitiveClosure::Matrix" to compute the transi‐
44       tive closure matrix of a graph and optionally also the minimum paths
45       (lengths and vertices) between vertices, and after that query the tran‐
46       sitiveness between vertices by using the "is_reachable()" and "is_tran‐
47       sitive()" methods, and the paths by using the "path_length()" and
48       "path_vertices()" methods.
49
50       If you modify the graph after computing its transitive closure, the
51       transitive closure and minimum paths may become invalid.
52

Methods

54       Class Methods
55
56       new($g)
57           Construct the transitive closure matrix of the graph $g.
58
59       new($g, options)
60           Construct the transitive closure matrix of the graph $g with
61           options as a hash. The known options are
62
63           "attribute_name" => attribute_name
64                   By default the edge attribute used for distance is "w".
65                   You can change that by giving another attribute name with
66                   the "attribute_name" attribute to the new() constructor.
67
68           reflexive => boolean
69                   By default the transitive closure matrix is not reflexive:
70                   that is, the adjacency matrix has zeroes on the diagonal.
71                   To have ones on the diagonal, use true for the "reflexive"
72                   option.
73
74                   NOTE: this behaviour has changed from Graph 0.2xxx: transi‐
75                   tive closure graphs were by default reflexive.
76
77           path_length => boolean
78                   By default the path lengths are not computed, only the
79                   boolean transitivity.  By using true for "path_length" also
80                   the path lengths will be computed, they can be retrieved
81                   using the path_length() method.
82
83           path_vertices => boolean
84                   By default the paths are not computed, only the boolean
85                   transitivity.  By using true for "path_vertices" also the
86                   paths will be computed, they can be retrieved using the
87                   path_vertices() method.
88
89       Object Methods
90
91       is_reachable($u, $v)
92           Return true if the vertex $v is reachable from the vertex $u, or
93           false if not.
94
95       path_length($u, $v)
96           Return the minimum path length from the vertex $u to the vertex $v,
97           or undef if there is no such path.
98
99       path_vertices($u, $v)
100           Return the minimum path (as a list of vertices) from the vertex $u
101           to the vertex $v, or an empty list if there is no such path, OR
102           also return an empty list if $u equals $v.
103
104       has_vertices($u, $v, ...)
105           Return true if the transitive closure matrix has all the listed
106           vertices, false if not.
107
108       is_transitive($u, $v)
109           Return true if the vertex $v is transitively reachable from the
110           vertex $u, false if not.
111
112       vertices
113           Return the list of vertices in the transitive closure matrix.
114
115       path_predecessor
116           Return the predecessor of vertex $v in the transitive closure path
117           going back to vertex $u.
118

RETURN VALUES

120       For path_length() the return value will be the sum of the appropriate
121       attributes on the edges of the path, "weight" by default.  If no
122       attribute has been set, one (1) will be assumed.
123
124       If you try to ask about vertices not in the graph, undefs and empty
125       lists will be returned.
126

ALGORITHM

128       The transitive closure algorithm used is Warshall and Floyd-Warshall
129       for the minimum paths, which is O(V**3) in time, and the returned
130       matrices are O(V**2) in space.
131

SEE ALSO

133       Graph::AdjacencyMatrix
134

136       Jarkko Hietaniemi jhi@iki.fi
137

LICENSE

139       This module is licensed under the same terms as Perl itself.
140
141
142
143perl v5.8.8                       2004-11-08Graph::TransitiveClosure::Matrix(3)
Impressum