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           my $n = $tcm->path_length($u, $v)
33
34           my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_vertices => 1);
35           my @v = $tcm->path_vertices($u, $v)
36
37           my $tcm =
38               Graph::TransitiveClosure::Matrix->new($g,
39                                                     attribute_name => 'length');
40           my $n = $tcm->path_length($u, $v)
41
42           my @v = $tcm->vertices
43

DESCRIPTION

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

Methods

56   Class Methods
57       new($g)
58           Construct the transitive closure matrix of the graph $g.
59
60       new($g, options)
61           Construct the transitive closure matrix of the graph $g with
62           options as a hash. The known options are
63
64           "attribute_name" => attribute_name
65                   By default the edge attribute used for distance is "w".
66                   You can change that by giving another attribute name with
67                   the "attribute_name" attribute to the new() constructor.
68
69           reflexive => boolean
70                   By default the transitive closure matrix is not reflexive:
71                   that is, the adjacency matrix has zeroes on the diagonal.
72                   To have ones on the diagonal, use true for the "reflexive"
73                   option.
74
75                   NOTE: this behaviour has changed from Graph 0.2xxx:
76                   transitive closure graphs were by default reflexive.
77
78           path_length => boolean
79                   By default the path lengths are not computed, only the
80                   boolean transitivity.  By using true for "path_length" also
81                   the path lengths will be computed, they can be retrieved
82                   using the path_length() method.
83
84           path_vertices => boolean
85                   By default the paths are not computed, only the boolean
86                   transitivity.  By using true for "path_vertices" also the
87                   paths will be computed, they can be retrieved using the
88                   path_vertices() method.
89
90   Object Methods
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.32.0                      2020-07-28Graph::TransitiveClosure::Matrix(3)
Impressum