delorie.com/archives/browse.cgi   search  
Mail Archives: geda-user/2012/12/12/15:22:51

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: <alpine.DEB.2.00.1212120740300.26605@igor2priv>
Message-ID: <alpine.DEB.2.00.1212122128060.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 1212120740300 DOT 26605 AT igor2priv>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
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


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.


- Raw text -


  webmaster     delorie software   privacy  
  Copyright 2019   by DJ Delorie     Updated Jul 2019