Mail Archives: geda-user/2012/12/14/05:38:19
On Wed, 12 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>
>
> 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.
>
>
>
III. manual net tagging
Do not use I. or II., require(?) the user to manually select a net
for each object placed and highlight shorts, as proposed by John Doty
and Levente Kovacs.
- Raw text -