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 on 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
66                   "weight".  You can change that by giving another attribute
67                   name with the "attribute_name" attribute to the new()
68                   constructor.
69
70           reflexive => boolean
71                   By default the transitive closure matrix is not reflexive:
72                   that is, the adjacency matrix has zeroes on the diagonal.
73                   To have ones on the diagonal, use true for the "reflexive"
74                   option.
75
76           path => boolean
77                   If set true, sets "path_length" and "path_vertices". If
78                   either of those are true (and "path_vertices" is by
79                   default), then both are calculated.
80
81           path_length => boolean
82                   By default "false", but see above as overridden by default
83                   "path_vertices" being true. If calculated, they can be
84                   retrieved using the path_length() method.
85
86           path_vertices => boolean
87                   By default the paths are computed, with the boolean
88                   transitivity, they can be retrieved using the
89                   path_vertices() method.
90
91           path_count => boolean
92                   As an alternative to setting "path_length", if this is true
93                   then the matrix will store the quantity of paths between
94                   the two vertices. This is still retrieved using the
95                   path_length() method. The path vertices will not be
96                   available. You should probably only use this on a DAG, and
97                   not with "reflexive".
98
99   Object Methods
100       is_reachable($u, $v)
101           Return true if the vertex $v is reachable from the vertex $u, or
102           false if not.
103
104       path_length($u, $v)
105           Return the minimum path length from the vertex $u to the vertex $v,
106           or undef if there is no such path.
107
108       path_vertices($u, $v)
109           Return the minimum path (as a list of vertices) from the vertex $u
110           to the vertex $v, or an empty list if there is no such path, OR
111           also return an empty list if $u equals $v.
112
113       has_vertices($u, $v, ...)
114           Return true if the transitive closure matrix has all the listed
115           vertices, false if not.
116
117       is_transitive($u, $v)
118           Return true if the vertex $v is transitively reachable from the
119           vertex $u, false if not.
120
121       vertices
122           Return the list of vertices in the transitive closure matrix.
123
124       path_successor($u, $v)
125           Return the successor of vertex $u in the transitive closure path
126           towards vertex $v.
127
128       all_paths($u, $v)
129           Return list of array-refs with all the paths from $u to $v. Will
130           ignore self-loops.
131

RETURN VALUES

133       For path_length() the return value will be the sum of the appropriate
134       attributes on the edges of the path, "weight" by default.  If no
135       attribute has been set, one (1) will be assumed.
136
137       If you try to ask about vertices not in the graph, undefs and empty
138       lists will be returned.
139

ALGORITHM

141       The transitive closure algorithm used is Warshall and Floyd-Warshall
142       for the minimum paths, which is O(V**3) in time, and the returned
143       matrices are O(V**2) in space.
144

SEE ALSO

146       Graph::AdjacencyMatrix
147
149       Jarkko Hietaniemi jhi@iki.fi
150

LICENSE

152       This module is licensed under the same terms as Perl itself.
153
154
155
156perl v5.34.0                      2022-01-21Graph::TransitiveClosure::Matrix(3)
Impressum