X-Authentication-Warning:	delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient:	geda-user AT delorie DOT com
DKIM-Signature:	v=1; a=rsa-sha256; c=simple; d=mail.ud03.udmedia.de; h=
	in-reply-to:references:mime-version:content-type:message-id:cc
	:content-transfer-encoding:from:subject:date:to; s=beta; bh=W3+E
	eU0/Q7NjIyMy0Jhz1/VNy8l5EJgrjRy3f+qOdiE=; b=PLyWZs/ICYJnxBrf5zuC
	Uv6LrJlqhH8PlIt1orZkowGvoLAx6Fh4MzTX8wiQgHNrpn7uhTLsx9rNOsISJWi2
	RhXl6Vaf2ref7fPlag/xSzpxbYSdQya4EvZc2MNBdHHAgnFrutcDx8v0X561dpHo
	I/Xdl8UEoS2IB8Fwr64PDeY=
In-Reply-To:	<alpine.DEB.2.00.1212131517470.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 1212131517470 DOT 26605 AT igor2priv>
Mime-Version:	1.0 (Apple Message framework v753.1)
Message-Id:	<68345C18-5F26-4781-93A5-A6432883B540@jump-ing.de>
Cc:	geda-dev AT delorie DOT com
From:	Markus Hitter <mah AT jump-ing DOT de>
Subject:	Re: [geda-user] Find rat lines - prototype solver for minimal cut short-resolving
Date:	Thu, 13 Dec 2012 23:46:01 +0100
To:	geda-user AT delorie DOT com
X-Mailer:	Apple Mail (2.753.1)
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

Am 13.12.2012 um 15:36 schrieb gedau AT igor2 DOT repo DOT hu:

> I've put together a minimalistic prototype solver for the problem.  
> All test cases I've posted earlier are included as valid input for  
> the solver. The solver is based on the Karger's algorithm for  
> finding minimal cut, as suggested by Britton Kerin, with the extra  
> S and T nodes introduced with strong (redundant) connections to  
> each node of the corresponding net.
>
> It currently solves all test cases properly. It is written in C  
> (not in a portable way). The solver itself is less than 200 lines  
> with a lot of debugging code included and relies on a graph lib of  
> about 200 lines (uses only about half of it). There are a lot of  
> room for optimization, which I would do in case of interest (*).
>
> The code is accessible from svn://repo.hu/random/pcb-mincut
>
> It is not the most efficient algorithm to solve the problem. My  
> friends with more algorithm theory insight suggested two better  
> solutions, and I am willing to implement some sort of prototype for  
> them in the same framework, in case of interest (*).
>
>
> (*) interest: a PCB developer with commit right wants to merge the  
> code into PCB; he would also need to extract the graph from PCB  
> internals in whatever format (I am willing to write the converter)  
> and translate the result to PCB highlights.

Hello Tibor,

this sounds excellent!

Short of DJ giving you commit access to the repo, I'd volunteer to  
put your test code into a branch, so it can be tested in real-world  
situations. Solving only test cases makes it probably difficult to  
judge which of the solvers/strategies works best on non-trivial boards.

To track the case, can you please open a "bug" on Launchpad and  
upload the patches there? Well, I hope you have patches which can be  
applied to the pcb sources :-) As long as the code remains in a  
branch, cleanup and optimisation isn't important.


Thanks,
Markus

- - - - - - - - - - - - - - - - - - -
Dipl. Ing. (FH) Markus Hitter
http://www.jump-ing.de/

- Raw text -