X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Date: Thu, 13 Dec 2012 15:36:30 +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
cc: geda-dev AT delorie DOT com
Subject: Re: [geda-user] Find rat lines - prototype solver for minimal cut
 short-resolving
In-Reply-To: <1355011808.19390.8.camel@localhost>
Message-ID: <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>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII
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

Hello all,

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.

Best regards,

Tibor Palinkas