1Graph::TransitiveClosurUes(e3r)Contributed Perl DocumentGartaipohn::TransitiveClosure(3)
2
3
4
5Graph::TransitiveClosure - create and query transitive closure of graph
6

SYNOPSIS

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

DESCRIPTION

49       You can use "Graph::TransitiveClosure" to compute the transitive
50       closure graph of a graph and optionally also the minimum paths (lengths
51       and vertices) between vertices, and after that query the transitiveness
52       between vertices by using the "is_reachable()" and "is_transitive()"
53       methods, and the paths by using the "path_length()" and
54       "path_vertices()" methods.
55
56       For further documentation, see the Graph::TransitiveClosure::Matrix.
57
58   Class Methods
59       new($g, %opt)
60           Construct a new transitive closure object.  Note that strictly
61           speaking the returned object is not a graph; it is a graph plus
62           other stuff.  But you should be able to use it as a graph plus a
63           couple of methods inherited from the
64           Graph::TransitiveClosure::Matrix class.
65
66   Object Methods
67       These are only the methods 'native' to the class: see
68       Graph::TransitiveClosure::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       The transitive closure matrix is stored as an attribute of the graph
79       called "_tcm", and any methods not found in the graph class are
80       searched in the transitive closure matrix class.
81
82
83
84perl v5.12.0                      2009-01-17       Graph::TransitiveClosure(3)