Disjoint set

disjoint_set.py

#!/usr/bin/python3
'''
https://stackoverflow.com/questions/20154368/union-find-implementation-using-python
'''
def union_find(lis):
    lis = map(set, lis)
    unions = []
    for item in lis:
        temp = []
        for s in unions:
            if not s.isdisjoint(item):
                item = s.union(item)
            else:
                temp.append(s)
        temp.append(item)
        unions = temp
    return unions

if __name__ == '__main__':
    l = []
    l.append(["1", "2"])
    l.append(["2", "3"])
    l.append(["4", "5"])
    l.append(["6", "7"])
    l.append(["1", "7"])
    ds=union_find(l)
    for i in range(0,len(ds)):
        tmp_list=list(ds[i])
        tmp_list.sort()
        print(i,":",tmp_list)

disjoint_set_c.pyx

# distutils: language=c++
'''
https://stackoverflow.com/questions/20154368/union-find-implementation-using-python
'''
def union_find(lis):
    lis = map(set, lis)
    unions = []
    for item in lis:
        temp = []
        for s in unions:
            if not s.isdisjoint(item):
                item = s.union(item)
            else:
                temp.append(s)
        temp.append(item)
        unions = temp
    return unions

disjoint_set_c_run.py

#!/usr/bin/tcsh -f
"/bin/true" '''\'
setenv PYTHONPATH `realpath $0 | xargs dirname`
exec python3.13 $0 $*
'''
from disjoint_set_c import union_find
l = []
l.append(["1", "2"])
l.append(["2", "3"])
l.append(["4", "5"])
l.append(["6", "7"])
l.append(["1", "7"])
ds=union_find(l)
for i in range(0,len(ds)):
    tmp_list=list(ds[i])
    tmp_list.sort()
    print(i,":",tmp_list)

disjoint_set_c_setup.py

#!/usr/bin/python3.13
from setuptools import setup
from Cython.Build import cythonize

setup(
    ext_modules = cythonize("disjoint_set_c.pyx", language_level=3)
)

Makefile

MODULE=disjoint_set_c
VER=13
EXT=cpython-3$(VER)-$(HOSTTYPE)-gnu.so
SO=$(MODULE).$(EXT)
%.$(EXT): %_setup.py %.pyx
	python3.$(VER) $< build_ext -i
	strip $@
	-rm -rf build
all: $(SO)
clean:
	-rm -rf $(SO) $(MODULE).cpp

run_all

#!/usr/bin/tcsh -f
make clean all
disjoint_set.py | sum
disjoint_set_c_run.py | sum