relations (version 0.6-13)

components: Connected components

Description

Computes (strongly or weakly) connected components of an endorelation.

Usage

relation_connected_components(x, type = c("strongly", "weakly"))
relation_condensation(x)
relation_component_representation(x)

Value

For relation_connected_components(), an object of class

relation_classes_of_objects, i.e., a list of sets giving the elements of the corresponding connected components, named by the leaders' character representation. The list of leaders is added as a

leaders attribute.

For relation_condensation(), an (acyclic) endorelation.

For relation_component_representation(), an endorelation with same domain as x.

Arguments

x

an R object inheriting from class relation, representing a crisp endorelation without missings.

type

character string indicating the kind of components sought.

Details

Let \(G\) be the graph of an endorelation \(R\).

A weakly connected component of some node \(k\) in \(G\) is the set of all nodes reachable from \(k\). A strongly connected component of some node \(k\) is the set of all nodes reachable from \(k\), from which \(k\) can be reached. Each component is represented by some element, the leader.

The component representation graph of a cyclic endorelation \(R\) is composed of directed cycles, one for each strongly connected component of \(R\) containing more than one element, linking all corresponding elements.

The condensation of \(R\) is the graph of all leaders of \(R\).

References

S. Warshall (1962), A theorem on Boolean matrices. Journal of the ACM, 9/1, 11--12. tools:::Rd_expr_doi("10.1145/321105.321107").

J. A. La Poutré and J. van Leeuwen (1988), Maintenance of Transitive Closures and Transitive Reductions of Graphs. Proceedings of the International Workshop of Graph-Theoretic Concepts in Computer Science, Springer, London, 106--120.

See Also

plot.relation(), transitive_reduction()

Examples

## example from La Poutre and van Leeuwen:

require("sets")				# set(), pair() etc.

G <- set(pair(1L, 2L), pair(2L, 1L), pair(1L, 3L), pair(3L, 1L),
         pair(3L, 7L), pair(2L, 5L), pair(2L, 6L), pair(6L, 5L),
         pair(5L, 7L), pair(4L, 6L), pair(5L, 4L), pair(4L, 7L))

R <- endorelation(graph = G)

relation_connected_components(R)
relation_graph(relation_condensation(R))
relation_graph(relation_component_representation(R))