X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Message-ID: <50CACDF3.9090707@xs4all.nl>
Date: Fri, 14 Dec 2012 07:57:55 +0100
From: Bert Timmerman <bert DOT timmerman AT xs4all DOT nl>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.19) Gecko/20110429 Fedora/2.0.14-1.fc13 SeaMonkey/2.0.14
MIME-Version: 1.0
To: geda-user AT delorie DOT com
Subject: Re: [geda-user] Find rat lines - prototype solver for minimal cut
 short-resolving
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>
In-Reply-To: <alpine.DEB.2.00.1212131517470.26605@igor2priv>
Content-Type: text/plain; charset=windows-1252; format=flowed
X-Virus-Scanned: by XS4ALL Virus Scanner
X-MIME-Autoconverted: from 8bit to quoted-printable by smtp-vbr14.xs4all.nl id qBE6vtEa092372
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by delorie.com id qBE6vxQe004880
Reply-To: geda-user AT delorie DOT com

gedau AT igor2 DOT repo DOT hu wrote:
> 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
>
>
>
>
Hi Tibor,

Maybe it's mentioned already: after checking out trying make fails 
"solve.h".

<quote>
[bert AT vortex pcb-mincut]$ make
cc -g -Wall   -c -o main.o main.c
main.c: In function ‘main’:
main.c:12: warning: implicit declaration of function ‘exit’
main.c:12: warning: incompatible implicit declaration of built-in 
function ‘exit’
main.c:14: warning: implicit declaration of function ‘solve’
cc -g -Wall   -c -o solve.o solve.c
solve.c:22:19: error: solve.h: No such file or directory
solve.c:34: error: expected ‘)’ before ‘*’ token
solve.c:184: error: expected ‘)’ before ‘*’ token
make: *** [solve.o] Error 1
[bert AT vortex pcb-mincut]$
</quote>

Could you please include solve.h so I can test and play with pcb-mincut.

Maybe we can adapt pcb-mincut into a plug-in for pcb ;-)

TIA and kind regards,

Bert Timmerman.