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.

Examples

Run this code

## 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))

Run the code above in your browser using DataLab

Last chance! 50% off unlimited learning