X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Date: Wed, 12 Dec 2012 05:49:10 +0100 (CET)
X-X-Sender: igor2 AT igor2priv
To: geda-user AT delorie DOT com
X-Debug: to=geda-user AT delorie DOT com from="gedau AT igor2 DOT repo DOT hu"
From: gedau AT igor2 DOT repo DOT hu
Subject: Re: [geda-user] Find rat lines
In-Reply-To: <CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw@mail.gmail.com>
Message-ID: <alpine.DEB.2.00.1212120532080.26605@igor2priv>
References: <20121204183305 DOT 6b04c0dc AT jive DOT levalinux DOT org> <20121208112649 DOT 388a9d22 AT jive DOT levalinux DOT org> <1355011808 DOT 19390 DOT 8 DOT camel AT localhost> <alpine DOT DEB DOT 2 DOT 00 DOT 1212090407031 DOT 26605 AT igor2priv> <1355188647 DOT 12937 DOT 14 DOT camel AT localhost> <alpine DOT DEB DOT 2 DOT 00 DOT 1212110530020 DOT 26605 AT igor2priv>
 <alpine DOT DEB DOT 2 DOT 00 DOT 1212111935190 DOT 26605 AT igor2priv> <CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw AT mail DOT gmail DOT com>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Reply-To: geda-user AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: geda-user AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk



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