components: Connected components

In relations: Data Structures and Algorithms for Relations

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

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.

References

S. Warshall (1962), A theorem on Boolean matrices. Journal of the ACM, 9/1, 11–12. 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))

relations documentation built on March 7, 2023, 8:01 p.m.