equivalence_classes(iterable, relation)
The equivalence classes, or blocks, consist of objects from iterable
which are all equivalent. They are defined to be equivalent if the :None:None:`relation` function returns :None:None:`True` when passed any two objects from that class, and :None:None:`False` otherwise. To define an equivalence relation the function must be reflexive, symmetric and transitive.
This function does not check that :None:None:`relation` represents an equivalence relation. You can check that your equivalence classes provide a partition using is_partition
.
An iterable of elements/nodes.
A Boolean-valued function that implements an equivalence relation (reflexive, symmetric, transitive binary relation) on the elements of iterable
- it must take two elements and return :None:None:`True` if they are related, or :None:None:`False` if not.
A set of frozensets representing the partition induced by the equivalence relation function :None:None:`relation` on the elements of iterable
. Each member set in the return set represents an equivalence class, or block, of the partition.
Duplicate elements will be ignored so it makes the most sense for iterable
to be a set
.
Returns equivalence classes of :None:None:`relation` when applied to iterable
.
Let :None:None:`X` be the set of integers from :None:None:`0` to :None:None:`9`, and consider an equivalence relation :None:None:`R` on :None:None:`X` of congruence modulo 3
: this means that two integers :None:None:`x` and :None:None:`y` in :None:None:`X` are equivalent under :None:None:`R` if they leave the same remainder when divided by 3
, i.e. :None:None:`(x - y) mod 3 = 0`.
The equivalence classes of this relation are :None:None:`{0, 3, 6, 9}`, :None:None:`{1, 4, 7}`, :None:None:`{2, 5, 8}`: :None:None:`0`, 3
, :None:None:`6`, :None:None:`9` are all divisible by 3
and leave zero remainder; :None:None:`1`, :None:None:`4`, :None:None:`7` leave remainder :None:None:`1`; while :None:None:`2`, :None:None:`5` and :None:None:`8` leave remainder :None:None:`2`. We can see this by calling equivalence_classes
with :None:None:`X` and a function implementation of :None:None:`R`.
>>> X = set(range(10))See :
... def mod3(x, y): return (x - y) % 3 == 0
... equivalence_classes(X, mod3) # doctest: +SKIP {frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.minors.contraction.equivalence_classes
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them