X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Date: Wed, 12 Dec 2012 21:41:13 +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
Subject: Re: [geda-user] Find rat lines
In-Reply-To: <1355188647.12937.14.camel@localhost>
Message-ID: <alpine.DEB.2.00.1212122135380.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>
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

Hi all,

another friend of mine with background in physics proposed an interesting 
solution based on springs.

Take our connection graph (with all the extra nodes for junctions) and 
replace line segments with springs. Take all pins of net1 and place them 
at -1;0 and take all pins of net2 and place them in +1;0 and place all the 
junctions in 0;0. Add sufficient friction to avoid oscillation then 
release the system and run the simulation until sum of spring energy 
changes less than Epsilon between two iterations. Draw a verticla line at 
0;0 - what sprins it cuts are the edges we are looking for.

This approach is too complicated for me to verify with examples without 
implementing a prototype, but I can imagine something like this could 
work. IIRC grpahviz's dot rendering does something similar to optimize 
placing of edges and minimize overall size.

Regards,

Tibor