X-Authentication-Warning: delorie.com: mail set sender to geda-user-bounces using -f X-Recipient: geda-user AT delorie DOT com Date: Tue, 11 Dec 2012 06:23:48 +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 In-Reply-To: <1355188647.12937.14.camel@localhost> 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> <1355188647 DOT 12937 DOT 14 DOT camel AT localhost> User-Agent: Alpine 2.00 (DEB 1167 2008-08-23) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed 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 Tue, 11 Dec 2012, Peter Clifton wrote: > However, in general, coping with the "it started out shorted" case, I > can imagine producing a graph structure (quite possibly including > cycles), representing the topology of the connected traces. Nodes would > represent pins / pads, or junction points between copper tracks and > polygons. (Although I'm not sure exactly how polygons should work in > this scheme - perhaps a polygon is node?) I think you may need to consider any junction as a node, since it is possible to cause a short by inserting a new trace line connecting two existing traces, without connecting any pin/pad. But first, we need to decide what should be highlighted. I see many different apporaches here: 1. we try to highlight the shortest trace(s) which if the user removes the short is resolved - this assumes the short is caused by a wrong trace, which is not very long 2. we try to highlight whole, diverse segments of traces an polys from which removing one careflly would solve the problem - this assumes the short is cased by any trace/poly 3. we highligh pads affected - this doesn't assume anything but doesn't help much either For examples, let's assume a simple netlist that connects nodes a and b in the net1 and C and D in net2. The simplex shorted example comes to mind: (example A) a---b | C---D Removing the vertical line connecting the wrong pins helps. Same example where using only pins as nodes of the graph wouldn't work: (example B) a-+-b | C-+-D The reason I used plural in the above listing: (example C) a---b | | C---D Both vertical traces need to be highlighted, removing only one doesn't help. A tricky case is when we share shorts: (example D) a b | | +---+ | | C D Connected everything wrong: (example E) a b | | C D > Assuming a two-nets shorted case for simplicity, we could then start > colouring / labelling the graph in some way. Pins and pads would be > tagged with their proper net assignment, and this _could_ be allowed to > propagate down edges representing copper tracks / polygons etc.. This would work well for examples A and C, but I am not sure it woudln't do something strange with example B if it is assymetrical (can't come up with an example, tho). In example D it would probably highlight the entier horizontal line (assuming we started propagation from all four pins in the same time and did it in parallel), which seems to be a good choice. In example D it would highlight the two vertical lines, which is fine. > > It might be possible to use the structure of the graph to help tease out > where the problem lies. (It could be, for example, that the graph > identifies a single edge connecting an otherwise partitioned graph of > nodes belonging to two different nets). > > I don't know enough (any?) graph theory, but perhaps we should > investigate finding whether there are known algorithms for finding > optimum partitions of graphs which separate various populations of > nodes. I can ask a friend today who is good in graph theory. > For that "what is shorted to what" case, we might employ some kind of > voting heuristic which flags that there are (say), 3 mis-connected pins > on the "should be VCC" pins connected to a piece of copper where 100 > "should be GND" pins are connected... therefore that copper should > "probably" be GND, so flag the VCC pins as a warning. This would work as long as the connections are assymetrical. Take example C: the two vertical lines try to be as much net1 as much net2. I may misunderstand the original question here, but if we define each junction as a node, that also means we had to split up a long line into segments (in example D vertical lines are not single lines for finding short or even for highlighting shorts). Together with your parallel propagation idea, it doesn't seem to be necessary to decide what is shorted to what, only to find a collision during propagation, and that would do the Right Thing to highlight. Thus This propagation seems to be a simple and elegant solution on the graph level, but gets tricky when we translate it to PCB at the end. For lines, this means we need to be able to split up lines at junctions for highlight - I think really splitting PCB lines into segments would cause serious side effects (changing width or clearance would affect only a shoirt segment that the user did not create). With polygons it is even trickier: take example C and imagine the lines drawn are only the outline of a polygon. I see two ways to handle this: 1. take the poly as a single object; in this case the whole poly is highlighted. The user would remove it and then a set of rats would remain, which may be a reasonable behaviour. Handle overlapping polys as single. 2. vote the poly to be one of the nets (dangerous in symmetrical cases) and detach pins/pads of other networks. This is easy only with thermals, in other cases this means finding and removing the right set of traces. Handle overpallying polys as single 3. split up the poly to lines modelling it; i'd use a star topology, or maybe a ring in the middle: a b | | +---+ | | +---+ | | C D The same propagation algo could be run and it would highlight the two vertical (virtual) lines in this topology, which may give a hint how we need to split the poly. However, as long as the example is symmetrical, it's impossible to decide whether the poly is more net1 or net2. I'd draw a schematics of the problem with non-copper lines over the poly and highight the poly. Overlapping polys: take them as single _before_ drawing the ring map. Drawing the ring map may be tricky if pins are dispersed. > > > Another possible heuristic would be to have a metric of "how badly > shorted" the net(s) are, and to evaluate how removing each piece of > copper in turn affects that metric. Perhaps this could lead to us > highlighting the errant track or clearance which introduced the short. This brute force approach will work in all my examples; however, this still assumes the short is caused by a line/poly. Take a huge board with ground plane connecting 42 pins legally; place a new pin that should be connected to VCC in the middle of ground plane by mistake. This method would remove the whole ground plane, while the user knows moving that single pin would have been the solution. In this case only the 2nd approach of the poly resolution above would do something reasonable. Regards, Tibor