Coverage for klayout_pex/netlist/rc_network.py: 99%
106 statements
« prev ^ index » next coverage.py v7.17.2, created at 2026-11-06 13:14 +0000
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#
25"""
26RC networks for netlist reduction.
28An :class:`RCNetwork` is an undirected graph: its nodes are connected by branches,
29each a conductance and a capacitance in parallel (either may be zero).
30Parallel resistors and capacitors between the same pair of nodes add up into one branch.
32Node names are case-insensitive, as in SPICE: 'A' and 'a' are the same node,
33which keeps the spelling it was first created with.
35A node can be tied to ground (by a large resistor, when written), which is a mark of the node, not a branch:
36the reductions don't see it as a resistor.
37"""
39from __future__ import annotations
41import math
42from typing import *
45class Branch:
46 """
47 A conductance [S] and a capacitance [F] in parallel, shared by the two nodes it connects
48 """
50 __slots__ = ('conductance', 'capacitance')
52 def __init__(self, conductance: float = 0.0, capacitance: float = 0.0):
53 self.conductance = conductance
54 self.capacitance = capacitance
56 def __repr__(self) -> str:
57 return f"Branch(conductance={self.conductance!r}, capacitance={self.capacitance!r})"
60class RCNetwork:
61 """
62 Nodes connected by branches (see :class:`Branch`).
64 Nodes are integers, numbered in the order they were created; removed nodes keep their number.
65 A protected node is never removed or merged by the reductions.
66 """
68 def __init__(self):
69 self._names: List[str] = []
70 self._node_by_key: Dict[str, int] = {}
71 self._branches: List[Optional[Dict[int, Branch]]] = []
72 self._protected: List[bool] = []
73 self._tied: List[bool] = []
75 # ----------------------------------------------------------------------- nodes
77 @staticmethod
78 def name_key(name: str) -> str:
79 """The identity of a node name (case-insensitive, as in SPICE)"""
80 return name.casefold()
82 def node(self, name: str) -> int:
83 """The node of this name, created if there is none"""
84 node = self.find_node(name)
85 if node is not None:
86 return node
87 node = len(self._names)
88 self._names.append(name)
89 self._node_by_key[self.name_key(name)] = node
90 self._branches.append({})
91 self._protected.append(False)
92 self._tied.append(False)
93 return node
95 def find_node(self, name: str) -> Optional[int]:
96 """The node of this name, None if there is none (or if it was removed)"""
97 node = self._node_by_key.get(self.name_key(name))
98 if node is None or self._branches[node] is None:
99 return None
100 return node
102 def name(self, node: int) -> str:
103 return self._names[node]
105 def sort_key(self, node: int) -> Tuple[str, str]:
106 """Orders nodes by name, independent of the order they were created in"""
107 name = self._names[node]
108 return self.name_key(name), name
110 def nodes(self) -> List[int]:
111 """The nodes that were not removed, in the order they were created"""
112 return [n for n, branches in enumerate(self._branches) if branches is not None]
114 def is_alive(self, node: int) -> bool:
115 """False once the node was removed or merged into another one"""
116 return self._branches[node] is not None
118 def protect(self, node: int):
119 self._protected[node] = True
121 def is_protected(self, node: int) -> bool:
122 return self._protected[node]
124 def tie(self, node: int):
125 """Mark a node as tied to ground (see the module docs)"""
126 self._tied[node] = True
128 def untie(self, node: int):
129 self._tied[node] = False
131 def is_tied(self, node: int) -> bool:
132 return self._tied[node]
134 def tied_nodes(self) -> List[int]:
135 """The tied nodes that were not removed, in the order they were created"""
136 return [n for n in self.nodes() if self._tied[n]]
138 # -------------------------------------------------------------------- branches
140 def branches(self, node: int) -> Dict[int, Branch]:
141 """The branches of a node, by neighbour (read only: change them with the methods below)"""
142 branches = self._branches[node]
143 if branches is None:
144 raise KeyError(f"Node {node} ({self._names[node]}) was removed")
145 return branches
147 def branch(self, node1: int, node2: int) -> Optional[Branch]:
148 return self.branches(node1).get(node2)
150 def add(self, node1: int, node2: int, conductance: float = 0.0, capacitance: float = 0.0):
151 """
152 Add a conductance [S] and a capacitance [F] between two nodes, in parallel to what is there.
153 Between a node and itself they have no effect and are dropped.
154 """
155 if node1 == node2 or (conductance == 0.0 and capacitance == 0.0):
156 return
157 branches1 = self.branches(node1)
158 branch = branches1.get(node2)
159 if branch is None:
160 branch = Branch()
161 branches1[node2] = branch
162 self.branches(node2)[node1] = branch
163 branch.conductance += conductance
164 branch.capacitance += capacitance
166 def remove_node(self, node: int):
167 """Remove a node and its branches"""
168 for neighbour in self.branches(node):
169 del self._branches[neighbour][node]
170 self._branches[node] = None
171 self._tied[node] = False
173 def merge_node(self, node: int, into: int):
174 """
175 Short a node to another one: its branches move to ``into`` (adding up with those there),
176 the branch between the two disappears, and the node is removed
177 """
178 for neighbour, branch in list(self.branches(node).items()):
179 if neighbour != into:
180 self.add(into, neighbour, branch.conductance, branch.capacitance)
181 self.remove_node(node)
183 def edges(self) -> List[Tuple[int, int, Branch]]:
184 """Every branch once, as (node1, node2, branch) with node1 < node2"""
185 return [(node1, node2, branch)
186 for node1, branches in enumerate(self._branches) if branches is not None
187 for node2, branch in branches.items() if node1 < node2]
189 # ---------------------------------------------------------------- node metrics
191 def conductance_sum(self, node: int) -> float:
192 """γ_N, the sum of the conductances at a node [S]"""
193 return sum(b.conductance for b in self.branches(node).values())
195 def capacitance_sum(self, node: int) -> float:
196 """χ_N, the sum of the capacitances at a node [F]"""
197 return sum(b.capacitance for b in self.branches(node).values())
199 def time_constant(self, node: int) -> float:
200 """
201 τ_N = χ_N / γ_N, the nodal time constant [s] (Sheehan, TICER, ICCAD 1999, (1.3)),
202 infinite for a node without resistor
203 """
204 conductance = self.conductance_sum(node)
205 if conductance == 0.0:
206 return math.inf
207 return self.capacitance_sum(node) / conductance
209 def degree(self, node: int) -> int:
210 """The number of neighbours, by resistor or capacitor"""
211 return len(self.branches(node))
213 def resistive_degree(self, node: int) -> int:
214 """The number of neighbours by resistor (RDeg in Sheehan, TCAD 2007)"""
215 return sum(1 for b in self.branches(node).values() if b.conductance != 0.0)
217 # ------------------------------------------------------------------- summaries
219 def resistor_count(self) -> int:
220 """The number of node pairs with a resistor between them"""
221 return sum(1 for _, _, b in self.edges() if b.conductance != 0.0)
223 def capacitor_count(self) -> int:
224 """The number of node pairs with a capacitor between them"""
225 return sum(1 for _, _, b in self.edges() if b.capacitance != 0.0)
227 def connected_node_count(self) -> int:
228 """The number of nodes with at least one branch"""
229 return sum(1 for branches in self._branches if branches)