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>
X-Mailer:	Evolution 3.6.0-0ubuntu3
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 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

- Raw text -