X-Authentication-Warning:	delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient:	geda-user AT delorie DOT com
Date:	Tue, 11 Dec 2012 19:59:58 +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:	<alpine.DEB.2.00.1212110530020.26605@igor2priv>
Message-ID:	<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>
User-Agent:	Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version:	1.0
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

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

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.

Best regards,

Tibor

- Raw text -