Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
networkx.algorithms.minors.equivalence_classes¶

equivalence_classes
(iterable, relation)[source]¶ Returns equivalence classes of
relation
when applied toiterable
.The equivalence classes, or blocks, consist of objects from
iterable
which are all equivalent. They are defined to be equivalent if therelation
function returnsTrue
when passed any two objects from that class, andFalse
otherwise. To define an equivalence relation the function must be reflexive, symmetric and transitive. Parameters
 iterablelist, tuple, or set
An iterable of elements/nodes.
 relationfunction
A Booleanvalued function that implements an equivalence relation (reflexive, symmetric, transitive binary relation) on the elements of
iterable
 it must take two elements and returnTrue
if they are related, orFalse
if not.
 Returns
 set of frozensets
A set of frozensets representing the partition induced by the equivalence relation function
relation
on the elements ofiterable
. 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 aset
.
Examples
Let
X
be the set of integers from0
to9
, and consider an equivalence relationR
onX
of congruence modulo3
: this means that two integersx
andy
inX
are equivalent underR
if they leave the same remainder when divided by3
, i.e.(x  y) mod 3 = 0
.The equivalence classes of this relation are
{0, 3, 6, 9}
,{1, 4, 7}
,{2, 5, 8}
:0
,3
,6
,9
are all divisible by3
and leave zero remainder;1
,4
,7
leave remainder1
; while2
,5
and8
leave remainder2
. We can see this by callingequivalence_classes
withX
and a function implementation ofR
.>>> X = set(range(10)) >>> def mod3(x, y): return (x  y) % 3 == 0 >>> equivalence_classes(X, mod3) {frozenset({1, 4, 7}), frozenset({8, 2, 5}), frozenset({0, 9, 3, 6})}