silk.md

input:

• dimensions of design
• matrix of (currently) occupied spaces (i.e., extracted cell placements)
• locations of pins of a given net, and their direction

procedure:

1. create a min-heap for each pin in the net

2. create a union-find structure for the pins

3. initialize n_groups to len(pins)

4. initialize a distance matrix, doing the following:

5. mark each pin (or pin + partial net) with BT_START and distance 0

6. initialize a visited matrix, doing the following:

7. mark all locations as unvisited

8. mark all current groups

9. while n_groups > 1:

10. select the group with the lowest min-heap element

11. expand the heap as before

12. if the lowest min-heap element expands into a group not currently in my union-find set:

13. create a new "segment" with these two points as endpoints

14. with the intersecting point, backtrace to the remote BT_START

15. with the point from which we expanded, backtrace to the local BT_START

16. add this segment with the addition of the two backtraces

17. delete the min-heap corresponding to both sets

18. mark all points along the partial net as visited, and add these points to the new min-heap for expansion

OLD

1. backtrace to the nearest BT_START, generating a new partial net
2. mark all parts of the to-be-joined groups as unvisited, marking each pin and partial net with BT_START and distance 0
3. join the two groups in the union-find structure
4. decrement n_groups

output:

• list of blocks connecting all pins of net