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: <1355266186.18878.39.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:49:46 +0000
In-Reply-To: <alpine.DEB.2.00.1212110530020.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>
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 06:23 +0100, gedau AT igor2 DOT repo DOT hu wrote:

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

> I can ask a friend today who is good in graph theory.

Cool, thanks!

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

> This brute force approach will work in all my examples; however, this 
> still assumes the short is caused by a line/poly. Take a huge board with 
> ground plane connecting 42 pins legally; place a new pin that should be 
> connected to VCC in the middle of ground plane by mistake. This method 
> would remove the whole ground plane, while the user knows moving that 
> single pin would have been the solution. In this case only the 2nd
> approach of the poly resolution above would do something reasonable.

Actually, I would consider the thermals / connections to pins and pads
to be connections in the graph too, so they would be tested for the
effect of their removal like other copper in the net.

The net result should be that turning off the thermal would bring the
"shorty" metric down (to zero in this case), and the program could
highlight the thermal (or the pin) as being the problem.

I wasn't proposing that the software auto-removed any connections, but
merely performed a "thought experiment" regarding how the net-list would
look if it removed each one in turn. Those for which their removal helps
the short get highlighted as a warning.

The metric would probably need to include a positive term for successful
connections to avoid it's universal answer being "remove the ground
plane.. all the shorts then go away".



Regarding splitting lines you mentioned, yes - I skipped over that
"detail", as it hurt my brain too much. Doing this _nicely_ will
probably require line-splitting for the graph to be most useful.

A simpler (and less informative) graph where each PCB copper object is a
node would be far easier to produce from PCB though. Each object to
object connection would be an edge. (This is _almost_ how the
connectivity scanner / DRC code operates, only it doesn't actually
construct or keep an explicit tree structure as it traverses the board).

Polygons become easier to understand in the simpler graph case, they
just become a multiply connected node (probably most connection edges
are thermals linking to pin nodes).


Perhaps a mathematician can tell us whether "topology" is the right word
for this graph... I appreciate that it is not a physical 2D topology
graph in the same sense the toporouter produces. (Although conceivably
it could be a related representation.)

IIRC, the toporouter's base graph is a triangulation of the physical
board space, with nodes seeded at obstacles, and connecting edges along
obstacles tagged with zero routing capacity.

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

Clifton Electronics