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 21:27:57 +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:	<CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw@mail.gmail.com>
Message-ID:	<alpine.DEB.2.00.1212122120390.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> <CAC4O8c__Yhb8ZijkVeZzELtNMAO8-=V3aDiEdiCC=BPMPy67Xw AT mail DOT gmail DOT com>
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, Britton Kerin wrote:

> On Tue, Dec 11, 2012 at 9:59 AM,  <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).
>
> Perhaps I don't understand what's being done, but there are some faster
> minimum-cut algorithms:
>
>   http://en.wikipedia.org/wiki/Minimum_cut
>   http://en.wikipedia.org/wiki/Karger%27s_algorithm
>
> It seems like the difficulty would be keeping the graph up-to-date across
> all existing PCB operations (part move, past, manual wire, etc.)
>

It turned out it was not you who didn't understand what's being done here, 
but me who didn't understand how it is being done with minimum cut.

My friend showed me a great approach how to apply this solution on our 
problme. Using the original connection graph of the two shorted 
net (enchanched netlist with the line segments and object forming new 
edges and virtual nodes) wouldn't work because it would find the minimum 
cut to split the whole graph in two. We need to modify the graph to get 
minimal cut to respect what should stay on one part and what should stay 
on the other.

The modification is introducing two new virtual nodes called S and T (this 
is some sort of convention, I think). Connect S to each net1 nodes with 
edges of infinite weight; connect T to each net2 nodes with edges of 
infinite weight. Assign a finite number (1, or the length of the line 
segment) to all other edges. If minimal cut is ran on this new graph, it 
will never cut an infinite weight edge, thus we keep our nets togheter.
It will cut finite weighted edges minimizing total weight cut, resolving 
our short.

If all original edges are assigned weight 1, it will find the minimum 
amount of cuts needed for resolving the short.

Regards,

Tibor

- Raw text -