1Graph::TransitiveClosurUes(e3r)Contributed Perl DocumentGartaipohn::TransitiveClosure(3)
2
3
4

SYNOPSIS

6           use Graph::TransitiveClosure;
7           use Graph::Directed; # or Undirected
8
9           my $g  = Graph::Directed->new;
10           $g->add_...(); # build $g
11
12           # Compute the transitive closure graph.
13           my $tcg = Graph::TransitiveClosure->new($g);
14           $tcg->is_reachable($u, $v) # Identical to $tcg->has_edge($u, $v)
15
16           # Being reflexive is the default, meaning that null transitions
17           # (transitions from a vertex to the same vertex) are included.
18           my $tcg = Graph::TransitiveClosure->new($g, reflexive => 1);
19           my $tcg = Graph::TransitiveClosure->new($g, reflexive => 0);
20
21           # is_reachable(u, v) is always reflexive.
22           $tcg->is_reachable($u, $v)
23
24           # The reflexivity of is_transitive(u, v) depends of the reflexivity
25           # of the transitive closure.
26           $tcg->is_transitive($u, $v)
27
28           # You can check any graph for transitivity.
29           $g->is_transitive()
30
31           my $tcg = Graph::TransitiveClosure->new($g, path_length => 1);
32           $tcg->path_length($u, $v)
33
34           # path_vertices is automatically always on so this is a no-op.
35           my $tcg = Graph::TransitiveClosure->new($g, path_vertices => 1);
36           $tcg->path_vertices($u, $v)
37
38           # Both path_length and path_vertices.
39           my $tcg = Graph::TransitiveClosure->new($g, path => 1);
40           $tcg->path_vertices($u, $v)
41           $tcg->length($u, $v)
42
43           my $tcg = Graph::TransitiveClosure->new($g, attribute_name => 'length');
44           $tcg->path_length($u, $v)
45

DESCRIPTION

47       You can use "Graph::TransitiveClosure" to compute the transitive clo‐
48       sure graph of a graph and optionally also the minimum paths (lengths
49       and vertices) between vertices, and after that query the transitiveness
50       between vertices by using the "is_reachable()" and "is_transitive()"
51       methods, and the paths by using the "path_length()" and "path_ver‐
52       tices()" methods.
53
54       For further documentation, see the Graph::TransitiveClosure::Matrix.
55
56       Class Methods
57
58       new($g, %opt)
59           Construct a new transitive closure object.  Note that strictly
60           speaking the returned object is not a graph; it is a graph plus
61           other stuff.  But you should be able to use it as a graph plus a
62           couple of methods inherited from the Graph::TransitiveClo‐
63           sure::Matrix class.
64
65       Object Methods
66
67       These are only the methods 'native' to the class: see Graph::Transi‐
68       tiveClosure::Matrix for more.
69
70       is_transitive($g)
71           Return true if the Graph $g is transitive.
72
73       transitive_closure_matrix
74           Return the transitive closure matrix of the transitive closure
75           object.
76
77       INTERNALS
78
79       The transitive closure matrix is stored as an attribute of the graph
80       called "_tcm", and any methods not found in the graph class are
81       searched in the transitive closure matrix class.
82
83
84
85perl v5.8.8                       2004-11-08       Graph::TransitiveClosure(3)
Impressum