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 07:25:52 +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: <1355266018.18878.38.camel@localhost>
Message-ID: <alpine.DEB.2.00.1212120712220.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> <1355266018 DOT 18878 DOT 38 DOT camel AT localhost>
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, Peter Clifton wrote:

> Yes - had a fear it might be complex.
>
> That doesn't mean it is intractable though,.. board auto-routing is a NP
> complete problem, but we still do a reasonable job.

I agree. My point is: finding a clean solution backed up with graph theory 
(proven to work on all cases perfectly) needs a very different approach 
than finding a set of good-enough methods and heuristics to get a 
pretty good result in most of the cases. At least according to my 
experience with such problems...

>
>> There were some alternative ideas, mostly improvements of the propagation
>> idea; instead of finding a single object to blame, it may highlight a
>> longer set of lines in a way that it is very likely to contain the part
>> the user is interested in, but this needs some more thinking.
>
> It is probably impossible to identify a single (or list of) object(s)
> which is/are to blame in any general case we encounter. There might be
> multiple solutions to resolve the short. We just need to try to provide
> helpful information to the user so she may resolve the issue.

Agreed. I'd further refine this part: in case we find the problem is NP, 
we can safely tell we won't come up with a perfect solution and then we 
could concentrate on one(s) that come(s) up with reasonable results for 
the most common cases. Or even, results better than what we have now.

>
>
> I'm trying to think of the class of mistakes I make when causing
> shorts..
>
> 1. Dragged random object out of place (or moved instead of
> rubber-banded).
>
> 2. Applied thermal to wrong layer
>
> 3. Had inappropriately tagged / named mechanical layer short across some
> pins or vias.
>
> 4. Routed tracks after (1, 2 or 3), compounding the issue with more
> cross-connected geometry. This will probably be in the form of wiring
> some pins / pads to the wrong track, or to adjacent pins on the shorted
> net. It might (occasionally) be due to adding more thermals to the wrong
> layer.

5. random modification somewhere that modifies how polys are separated; 
for example deleting a long trace that used to separate two smaller polys 
in some unseen corner.

6. random mod of lines that modifies dicing of a poly

7. component rotated - i obviously get this 50% of the cases with 
resistors


>
>
> Question...
>
> Should we be approaching this as a connectivity extraction, followed by
> net-list compare? We could probably retain information about the
> branching structure of the extracted wiring from the board to aid
> finding suitable points to describe the differences ("shorts").

I assumed all the time we retrain those as nodes in the graph, but didn't 
consider using the graph for anything else. I still believe without having 
the junctions as nodes, even if the pure netlist doesn't hav them, it is 
harder to solve the problem.

> It might be interesting / useful to be able to perform a generic
> net-list comparison. Our "warn" annotation on PCB could then be a form
> of (back-?)annotation from the netlist comparison process.
>
> Speaking wildly off-topic, perhaps back-annotating schematic changes to
> reflect the as-drawn PCB geometry is a valid thing to wish for!

Sounds useful.

Regards,

Tibor