Mail Archives: geda-user/2012/12/11/17:50:57
On Tue, 2012-12-11 at 06:23 +0100, gedau AT igor2 DOT repo DOT hu wrote:
> > 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.
Cool, thanks!
> > 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.
Actually, I would consider the thermals / connections to pins and pads
to be connections in the graph too, so they would be tested for the
effect of their removal like other copper in the net.
The net result should be that turning off the thermal would bring the
"shorty" metric down (to zero in this case), and the program could
highlight the thermal (or the pin) as being the problem.
I wasn't proposing that the software auto-removed any connections, but
merely performed a "thought experiment" regarding how the net-list would
look if it removed each one in turn. Those for which their removal helps
the short get highlighted as a warning.
The metric would probably need to include a positive term for successful
connections to avoid it's universal answer being "remove the ground
plane.. all the shorts then go away".
Regarding splitting lines you mentioned, yes - I skipped over that
"detail", as it hurt my brain too much. Doing this _nicely_ will
probably require line-splitting for the graph to be most useful.
A simpler (and less informative) graph where each PCB copper object is a
node would be far easier to produce from PCB though. Each object to
object connection would be an edge. (This is _almost_ how the
connectivity scanner / DRC code operates, only it doesn't actually
construct or keep an explicit tree structure as it traverses the board).
Polygons become easier to understand in the simpler graph case, they
just become a multiply connected node (probably most connection edges
are thermals linking to pin nodes).
Perhaps a mathematician can tell us whether "topology" is the right word
for this graph... I appreciate that it is not a physical 2D topology
graph in the same sense the toporouter produces. (Although conceivably
it could be a related representation.)
IIRC, the toporouter's base graph is a triangulation of the physical
board space, with nodes seeded at obstacles, and connecting edges along
obstacles tagged with zero routing capacity.
--
Peter Clifton <peter DOT clifton AT clifton-electronics DOT co DOT uk>
Clifton Electronics
- Raw text -