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: <1355188647.12937.14.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 01:17:27 +0000
In-Reply-To: <alpine.DEB.2.00.1212090407031.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>
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 Sun, 2012-12-09 at 04:24 +0100, gedau AT igor2 DOT repo DOT hu wrote:

> However, if we rephase the question from "what causes the short" to "what 
> user modification introduced the short", it could highlight something that 
> may be useful in more often. Proper implementation would be complicated 
> (need to save history of nets), but I see a reasonable cheat here: use the 
> undo buffer. This assumes there was no short at a point after loading the 
> board and the user is interested in which object he touched that first 
> caused the short.


Difficult indeed.

We could think of tagging copper with which net it belongs to (first
touch to an object (e.g. pin / pad) with a net, sticks. Any
inconsistencies would stick out then.

However, in general, coping with the "it started out shorted" case, I
can imagine producing a graph structure (quite possibly including
cycles), representing the topology of the connected traces. Nodes would
represent pins / pads, or junction points between copper tracks and
polygons. (Although I'm not sure exactly how polygons should work in
this scheme - perhaps a polygon is node?)

Assuming a two-nets shorted case for simplicity, we could then start
colouring / labelling the graph in some way. Pins and pads would be
tagged with their proper net assignment, and this _could_ be allowed to
propagate down edges representing copper tracks / polygons etc..

It might be possible to use the structure of the graph to help tease out
where the problem lies. (It could be, for example, that the graph
identifies a single edge connecting an otherwise partitioned graph of
nodes belonging to two different nets).

I don't know enough (any?) graph theory, but perhaps we should
investigate finding whether there are known algorithms for finding
optimum partitions of graphs which separate various populations of
nodes.

For that "what is shorted to what" case, we might employ some kind of
voting heuristic which flags that there are (say), 3 mis-connected pins
on the "should be VCC" pins connected to a piece of copper where 100
"should be GND" pins are connected... therefore that copper should
"probably" be GND, so flag the VCC pins as a warning.


Another possible heuristic would be to have a metric of "how badly
shorted" the net(s) are, and to evaluate how removing each piece of
copper in turn affects that metric. Perhaps this could lead to us
highlighting the errant track or clearance which introduced the short.


Kind regards,


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

Clifton Electronics