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:31: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 Subject: Re: [geda-user] Find rat lines - summary In-Reply-To: Message-ID: 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 On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote: > Hi all, > > I start to lose track of all the diverse ideas. This post is an effort to > structure the major directions. May it be incomplete, feel free to complete > it. > > In case there is a short... > > I. check whether we have history, since this way the qeustion is "what > user modification introduced the short" which might be more useful > than answer "which object(s) cause(s) the short at the moment". > > 1. bisect using the undo buffer (as Kai-Martin Knaak does manually) - > does not work accross sessions (restart/load) and as Markus > Hitter pointed it out, fails when new netlist is loaded > > 2. tag objects according to their first connection as suggested by Peter > Clifton. This info could be easily saved, making it immune to reload. > Needs more thoughts on some corner cases (new netlist, user moving and > object from one net to another) > > 3. separate connection/netlist history (saved with the PCB). No details > yet. > > II. no history available, try to highlight objects that are most likely to > help the user resolving the short. Nodes of the graph include > junctions, thermals, etc., much more verbose then the netlist. > > 1. propagate nets from all nodes as suggested by Peter Clifton. Doing > this in parallel may cause a collision close to the "real place > of the short" > > 2. find a minimal cut in a way the resulting graphs will reflect the > netlist and highlight only those cutting edge. To the end user this > means we find the smallest modification (deletion) that would fix the > problem (with or without leaving new rat lines). Sounds like an NP > hard problem, no working solution has been proposed in the thread yet. > > 3. Peter Clifton's remove-edges-and-see-how-that-improves-the-situation. > A good metric is needed to make sure we can measure small improvements > in cases where multiple edges must be removed to resolve the short. > Likely to select more edges than the minimum. > > 4. > stage 1 > classify nodes/edges: each belongs to one of the affected nets or is > neutral (could be in multiple nets or could be removed without > breaking only short, not legal redundant connection in a net). Assume > only neutral nodes/edges may participate in the short. Question is how > to do the classification properly: > > a. A modified version of Peter Clifton's propagation idea might work, > needs more thoughts. > b. A similar problem may be known in graph theory; Finding Steiner > tree for a net and trying to fit our nodes/edges on it would keep > the minimal amount (or length) of objects to form the net properly, > and take the rest as neutral. This Breaks badly with redundant > connections in a net. Needs more work. > > stage 2 > from stage 1 we already have sections with multiple nodes/edges that > are neutral and can be blamed for the short. If the user breaks each > such section, the short is resolved. > > a. highlight these sections and let the user break each wherever > (s)he wants (need a way to differentiate between sections) > b. try to find the best place to cut each section > A. middle of the section > B. smallest modification (however we measure that) > C. heat up the section with the modified verison of Joshua Lansford > idea; this may be used to highlight the shortest/smallest > object > > 5. minimal cut (proposed by Britton Kerin_ with the S->T modified connection graph; creating the modified graph is trival and there should be pseudo code and/or libraries available for calculating minimal cut. With uniformly wieghted edges it could reliably find the smallest amount of cuts resolving the short.