relations (version 0.6-4)

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)

Arguments

x

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

type

character string indicating the kind of components sought.

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.

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.

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