Mail Archives: geda-user/2012/12/12/02:05:29

X-Authentication-Warning: mail set sender to geda-user-bounces using -f
X-Recipient: geda-user AT delorie DOT com
Date: Wed, 12 Dec 2012 08:13:02 +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: <1355011808.19390.8.camel@localhost>
Message-ID: <alpine.DEB.2.00.1212120740300.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
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

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

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.

    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


Tibor Palinkas

- Raw text -

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