X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
X-Cam-AntiVirus: no malware found
X-Cam-SpamDetails: not scanned
X-Cam-ScannerInfo: http://www.cam.ac.uk/cs/email/scanner/
Message-ID: <1355266018.18878.38.camel@localhost>
Subject: Re: [geda-user] Find rat lines
From: Peter Clifton <pcjc2 AT cam DOT ac DOT uk>
To: geda-user AT delorie DOT com
Date: Tue, 11 Dec 2012 22:46:58 +0000
In-Reply-To: <alpine.DEB.2.00.1212111935190.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>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.6.0-0ubuntu3 
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
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, 2012-12-11 at 19:59 +0100, 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).

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.

> The propagation idea (parallel propagation of nets from all pins 
> finding the first collision) would work. We've spent some time trying to 
> construnct more examples to see how it'd perform. We think it'd 
> not find the "real cause" of the short, but something closer to it than 
> the current short highlight does.
> 
> 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.


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.



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").

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!

Regards,

-- 
Peter Clifton <peter DOT clifton AT clifton-electronics DOT co DOT uk>

Clifton Electronics