Mail Archives: geda-user/2012/12/12/01:18:06
On Tue, 11 Dec 2012, Peter Clifton wrote:
> Yes - had a fear it might be complex.
>
> That doesn't mean it is intractable though,.. board auto-routing is a NP
> complete problem, but we still do a reasonable job.
I agree. My point is: finding a clean solution backed up with graph theory
(proven to work on all cases perfectly) needs a very different approach
than finding a set of good-enough methods and heuristics to get a
pretty good result in most of the cases. At least according to my
experience with such problems...
>
>> There were some alternative ideas, mostly improvements of the propagation
>> idea; instead of finding a single object to blame, it may highlight a
>> longer set of lines in a way that it is very likely to contain the part
>> the user is interested in, but this needs some more thinking.
>
> It is probably impossible to identify a single (or list of) object(s)
> which is/are to blame in any general case we encounter. There might be
> multiple solutions to resolve the short. We just need to try to provide
> helpful information to the user so she may resolve the issue.
Agreed. I'd further refine this part: in case we find the problem is NP,
we can safely tell we won't come up with a perfect solution and then we
could concentrate on one(s) that come(s) up with reasonable results for
the most common cases. Or even, results better than what we have now.
>
>
> I'm trying to think of the class of mistakes I make when causing
> shorts..
>
> 1. Dragged random object out of place (or moved instead of
> rubber-banded).
>
> 2. Applied thermal to wrong layer
>
> 3. Had inappropriately tagged / named mechanical layer short across some
> pins or vias.
>
> 4. Routed tracks after (1, 2 or 3), compounding the issue with more
> cross-connected geometry. This will probably be in the form of wiring
> some pins / pads to the wrong track, or to adjacent pins on the shorted
> net. It might (occasionally) be due to adding more thermals to the wrong
> layer.
5. random modification somewhere that modifies how polys are separated;
for example deleting a long trace that used to separate two smaller polys
in some unseen corner.
6. random mod of lines that modifies dicing of a poly
7. component rotated - i obviously get this 50% of the cases with
resistors
>
>
> Question...
>
> Should we be approaching this as a connectivity extraction, followed by
> net-list compare? We could probably retain information about the
> branching structure of the extracted wiring from the board to aid
> finding suitable points to describe the differences ("shorts").
I assumed all the time we retrain those as nodes in the graph, but didn't
consider using the graph for anything else. I still believe without having
the junctions as nodes, even if the pure netlist doesn't hav them, it is
harder to solve the problem.
> It might be interesting / useful to be able to perform a generic
> net-list comparison. Our "warn" annotation on PCB could then be a form
> of (back-?)annotation from the netlist comparison process.
>
> Speaking wildly off-topic, perhaps back-annotating schematic changes to
> reflect the as-drawn PCB geometry is a valid thing to wish for!
Sounds useful.
Regards,
Tibor
- Raw text -