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: <1355441679.2993.1.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: Thu, 13 Dec 2012 23:34:39 +0000
In-Reply-To: <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>
	 <alpine DOT DEB DOT 2 DOT 00 DOT 1212122120390 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 Wed, 2012-12-12 at 21:27 +0100, gedau AT igor2 DOT repo DOT hu wrote:

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

Nice ;)

I thought we'd be able to modify one of the graph partitioning
algorithms, but I hadn't appreciated how simple and elegant you could
make the modification.

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

Clifton Electronics