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

an R object 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. 10.1145/321105.321107.

J. A. La Poutr<U+00E9> 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

# NOT RUN {
## 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 DataCamp Workspace