1Graph::TransitiveClosurUes:e:rMaCtornitxr(i3b)uted PerlGDroacpuhm:e:nTtraatnisointiveClosure::Matrix(3)
2
6 Graph::TransitiveClosure::Matrix - create and query transitive closure
7 of graph
8
10 use Graph::TransitiveClosure::Matrix;
11 use Graph::Directed; # or Undirected
12 my $g = Graph::Directed->new;
14 $g->add_...(); # build $g
15 # Compute the transitive closure matrix.
17 my $tcm = Graph::TransitiveClosure::Matrix->new($g);
18 # 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 # is_reachable(u, v) is always reflexive.
25 $tcm->is_reachable($u, $v)
26 # The reflexivity of is_transitive(u, v) depends on the reflexivity
28 # of the transitive closure.
29 $tcg->is_transitive($u, $v)
30 my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_length => 1);
32 my $n = $tcm->path_length($u, $v)
33 my $tcm = Graph::TransitiveClosure::Matrix->new($g, path_vertices => 1);
35 my @v = $tcm->path_vertices($u, $v)
36 my $tcm =
38 Graph::TransitiveClosure::Matrix->new($g,
39 attribute_name => 'length');
40 my $n = $tcm->path_length($u, $v)
41 my @v = $tcm->vertices
43
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 If you modify the graph after computing its transitive closure, the
53 transitive closure and minimum paths may become invalid.
54
56 Class Methods
57 new($g)
58 Construct the transitive closure matrix of the graph $g.
59 new($g, options)
61 Construct the transitive closure matrix of the graph $g with
62 options as a hash. The known options are
63 "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 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 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 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 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 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 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 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 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 has_vertices($u, $v, ...)
114 Return true if the transitive closure matrix has all the listed
115 vertices, false if not.
116 is_transitive($u, $v)
118 Return true if the vertex $v is transitively reachable from the
119 vertex $u, false if not.
120 vertices
122 Return the list of vertices in the transitive closure matrix.
123 path_successor($u, $v)
125 Return the successor of vertex $u in the transitive closure path
126 towards vertex $v.
127 all_paths($u, $v)
129 Return list of array-refs with all the paths from $u to $v. Will
130 ignore self-loops.
131
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 If you try to ask about vertices not in the graph, undefs and empty
138 lists will be returned.
139
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
146 Graph::AdjacencyMatrix
147
149 Jarkko Hietaniemi jhi@iki.fi
150
152 This module is licensed under the same terms as Perl itself.
153perl v5.34.0 2021-07-22Graph::TransitiveClosure::Matrix(3)