Coverage for klayout_pex/util/disjoint_sets.py: 100%

1# 

2# -------------------------------------------------------------------------------- 

3# SPDX-FileCopyrightText: 2024-2026 Martin Jan Köhler and Harald Pretl 

4# Johannes Kepler University, Institute for Integrated Circuits. 

5# 

6# This file is part of KPEX 

7# (see https://github.com/iic-jku/klayout-pex). 

8# 

9# This program is free software: you can redistribute it and/or modify 

10# it under the terms of the GNU General Public License as published by 

11# the Free Software Foundation, either version 3 of the License, or 

12# (at your option) any later version. 

13# 

14# This program is distributed in the hope that it will be useful, 

15# but WITHOUT ANY WARRANTY; without even the implied warranty of 

16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 

17# GNU General Public License for more details. 

18# 

19# You should have received a copy of the GNU General Public License 

20# along with this program. If not, see <http://www.gnu.org/licenses/>. 

21# SPDX-License-Identifier: GPL-3.0-or-later 

22# -------------------------------------------------------------------------------- 

23# 

24 

25from typing import Dict, Iterable 

26 

27 

28class DisjointSets: 

29 """ 

30 Sets of IDs that get joined, e.g. the nodes of a resistor network (union-find) 

31 """ 

32 

33 def __init__(self, ids: Iterable[int]): 

34 self.parent: Dict[int, int] = {i: i for i in ids} 

35 

36 def find(self, i: int) -> int: 

37 """ 

38 :return: the ID that stands for the set of i 

39 """ 

40 while self.parent[i] != i: 

41 self.parent[i] = self.parent[self.parent[i]] 

42 i = self.parent[i] 

43 return i 

44 

45 def union(self, a: int, b: int): 

46 self.parent[self.find(a)] = self.find(b)