Mail Archives: geda-user/2012/12/11/23:41:16
On Tue, 11 Dec 2012, Britton Kerin wrote:
> On Tue, Dec 11, 2012 at 9:59 AM, <gedau AT igor2 DOT repo DOT hu> wrote:
>>
>>
>> On Tue, 11 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>>
>>> I can ask a friend today who is good in graph theory.
>>
>>
>> Today we sat together and I demonstrated the problem in PCB and described
>> the details. After modelling the problem (graphs) he evaluated both
>> solutions (propagation nets and finding cutting edges).
>>
>> After decomposing the problem, he concluded that finding the cutting edges
>> may be an NP problem (in case it is important to minimize the number of
>> cuts) and would be impossible to solve on a large board with a complicated
>> situation (multiple traces causing shorts).
>
> Perhaps I don't understand what's being done, but there are some faster
> minimum-cut algorithms:
>
> http://en.wikipedia.org/wiki/Minimum_cut
If I understand the not very verbose wikipedia page, this is close to what
we need, bit slightly different. Running this on a shorted PCB would find
the best places to cut the traces in a way we get smaller nets with
minimal weight, but doesn't guarantee the smaller nets will match our
netlist. In other words our case is more complicated because we want to
minimize number of cuts _while_ we know exactly what nodes should stay on
each new independent graph.
During modelling, we classified nodes of N nets into N+1 types, the +1
being "could be anything". For a net1=a,b net2=C,D example, extra,
non-netlisted nodes numberes:
a--1--b
|
2
|
C--3--4--D
The min cut may find 3-4 or 4-D, because cutting only one edge there
results in 2 independet graphs. However, we see that C-3-4-D is net2 and
a-1-b is net1 and cutting makes sense only on 1-2 or 2-3.
The thing gets more complicated when we allow multiple legal connection
between a and b and we also allow multiple short paths betwene the two
nets. In this case we would need to identify the smallest amount of edges
to be removed to result separate net1 and net2. Example:
+-5-6-8--+
| | |
a--1--b |
| 9
2 |
| |
C--3--4--D
| |
+--7--+
In this case we need two cuts, a ranom pair from set (1-2,2-3) and
(8-9,9-D). Removing more may hurt, there may be legal reasons
for 3-7-D and a-5-6-8-b (for technical reasons multiple parallel
PCB objects connect two nodes).
> It seems like the difficulty would be keeping the graph up-to-date across
> all existing PCB operations (part move, past, manual wire, etc.)
I think first a simpler problem should be solved: assume we can build the
graph from scratch using a given PCB, and we need to determine best cuts
(whatever best means). Later, if this already works well, it is an
optimization if we don't need to rebuild the graph all the time.
Best regards,
Tibor
- Raw text -